Waste less time on Facebook — follow Brilliant.

Introduction to cryptography(RSA Cipher)

In this note I want to discuss some ideas from modern cryptography..



Don't be intimidated by the size of the note...if you understand the ideas properly trust me it's worth it...you will learn about one of the most effective cipher systems still actively used today!!

\(\textbf{Public-Key Cryptography:}\)In conventional cryptographic systems like the Caesar cipher,the sender and the receiver jointly have a secret key that is used for encryption and decryption.But in public-key cryptography two keys are used - an encryption key and a decryption key.Though these keys are related,there is no easy way to derive the decryption key from the encryption key.Thus the encryption key can be made public without compromising the decryption key.A major advantage of the public cryptosystem is that it is unnecessary for the senders and the receivers to exchange a key in advance of their decision to communicate with one another.

\(\textbf{Rivest-Shamir-Adleman Cipher:}\)In 1977,Ronald Rivest,Adi Shamir and Leonhard Adleman proposed a public-key encryption system that uses elementary ideas from number theory.It's security depends on the assumption that in the current state of computer technology,factorization of composite numbers having large prime factors is so time consuming that it is almost unrealistic.



\(\textbf{Procedure:}\)At first the user of the RS system chooses a pair of very large distinct primes.Then the two numbers are multiplied to form a number \(n = pq\) called the \(\text{enciphering modulus}\).The factorization of this product is beyond all computational abilities.Next,they need to select a positive integer \(k\) such that \(\gcd(k,\phi (n))=1\) called the \(\text{enciphering exponent}\).the pair \((n,k)\) is kept in a public profile(like a telephone directory) as the user's personal encryption key which allows anyone else to encrypt and send a message to this individual,but the primes \(p\) and \(q\) are unknown to everybody else.





\(\textbf{Step 1.}\)First each alphabet of the message to be sent is converted into a 2-digit number.A standard procedure for executing this is using the following assignment:



\(\textbf{Step 2.}\)It is aasumed that the message \(M < n\), where n is the enciphering modulus.Otherwise it is diffucult to distinguish M from any larger integer congruent to \(M\) modulo n. If the message M is too long then it is broken into separate blocks of digits \(M_1,M_2,....M_s\) of appropriate size and each is coded separately.

\(\textbf{Step 3.}\)After looking up the intended recipient's encryption key \((n,k\) in the public directory,the sender disguises the plaintext \(M\) into the ciphertext \(r\),by raising M to the \(k\)-th power and then taking modulo \(n\),that is, \[M^{k} \equiv r \pmod{n}\]. \(k\) is selected such that \(gcd(k,\phi(n))=1\)


\(\textbf{Step 1.}\)The authorized personnel deciphers the message by first determining the recovery exponent \(j\), for which \[kj \equiv 1 \pmod{\phi(n)}\]

Since \(gcd(k,\phi(n)) = 1\),this linear congruence has a uniqee solution modulo \(\phi(n)\).The Euclidean Algorithm produces \(j\) as a solution \(x\) to the equation \[kx+\phi(n)y = 1\]. Note that the recovery exponent can only be obtained by someone who knows both \(k\) and \(\phi(n) = (p-1)(q-1)\) and hence both \(p\) and \(q\).The knowledge of any unauthorized third party is limited to the public key \((n,k)\).

\(\textbf{Step 2.}\)Now if we calculate \(r^{j} \mod n\), we get,\[\ r^{j} \equiv (M^{k})^{j} \equiv M^{1+\phi(n)*t} \equiv M*M^{\phi(n)*t}\] \[\equiv M*1^{t} \equiv M \pmod n\] whenever \(gcd(M,n)=1\).

In other words raising the plaintext number to the \(j\)-th power and taking moduulo n recovers the plaintext.

It is to be noted that the assumption \(gcd(M,n)=1\) was used to use Euler's theorem.In case they are not relatively prime, we can prove by similar argument that \[r^{j} \equiv M \pmod p\] \[r^{j} \equiv M \pmod q\] Since \(gcd(p,q)=1\), we have \(r^{j} \equiv M \pmod{pq}\),that is \(r^{j} \equiv M \pmod n\)!!

\(\textbf{Step3.}\)Convert the digital representation to the alphabetic one.


Let us consider an unrealistically small example choosing 2 primes \(p = 29\) and \(q=53\).

The enciphering modulus is then \(n = 29*53 = 1537\) and \(\phi(n) = 28*52 = 1456\).

Since \(gcd(47,1436)=1\), we may choose \(k=47\) to be the enciphering exponent.It can be calculated that in this case the recovery exponent will be \(31\).

Let the first block from the digital version of the plaintext be \(131\),this encrypts to the ciphertext \[131^{47} \equiv 570 \pmod{1537}\].But by using the recovery exponent \(j = 31\), we can decrypt this to \[570^{31} \equiv 131 \pmod{1537}\].

This is the original digital form of the plaintext !!!

\(\textbf{Applications:}\)Banks(1024-bit),Facebook(1024-bit),Twitter(1024-bit),Ebay(1024-bit) all use the RSA cipher to protect our internet secrets!!The numbers in the brackets denote the number of digits of the enciphering modulus. A 768 bit key has recently been broken.



Have fun encrypting :D ....i'll try to do a few more posts on modern ciphers next week


\(1.\)Introduction to Algorithms by Cormen,Leiserson,Rivest and Stein

\(2.\)Elementary Number Theory by David M.Burton(I took the example from here)

\(3.\)Encryption and huge numbers by NumberPhile (Video by Brady Haran and demonstrated by Dr.James Grime)

Note by Eddie The Head
2 years, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

Thanks! I hope you won't mind if I post another link here which contains some basic knowledge on Cryptography (it might help someone out) : Khan Academy Videos on Cryptography. Kou$htav Chakrabarty · 2 years, 7 months ago

Log in to reply

@Kou$htav Chakrabarty You re welcome to post any related material:) Eddie The Head · 2 years, 7 months ago

Log in to reply

Wow, interesting stuff! Who would've imagined how far a supposedly minor theorem such as Fermat's Little Theorem could go? Cody Johnson · 2 years, 8 months ago

Log in to reply

This is amazing! I loved reading this! Finn Hulse · 2 years, 7 months ago

Log in to reply

gr8 stuff .......... Pratyush Ranjan Tiwari · 2 years, 7 months ago

Log in to reply

Well i always was in need of learnin about this!!.....NOW it;s HERE! thnx "Eddie the Head" i might need to contact u for discussions...if u agree?.see my brilliant profile.. Arya Samanta · 2 years, 6 months ago

Log in to reply

@Arya Samanta Sure...I'm always available for discussion... also check out my other cryptography posts :) Eddie The Head · 2 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...