Cryptography

RSA: The Elegant Code

Harman Kour

Jul 10, 2014 • 6 min read

The quest to share information securely and the curiosity to decipher the hidden meaning, has astounded the human mind since eternity. Whether it was the ancient art of steganography, or the development of ciphers from the Caesar Cipher to the Enigma Cipher Machine, the basic idea has been to protect information from falling into the wrong hands.

This science of cryptography took a very interesting turn during the 1970’s with the development of the concept of asymmetric ciphers by exploiting the one-way functions. This was achieved by a trio of three brilliant cryptographers at Stanford University, namely Whitfield Diffie, Martin Hellman and Ralph Merkle. Together they solved one of the greatest mysteries of sharing messages secretly without having to share the key. For instance, if Alice wants to communicate privately to Bob she must encrypt the message using a key. Now for Bob to be able to decrypt the message he must know the key. This is an example of a symmetric cipher which uses the same key to encode and decode the message. This implied that the key distribution is an inevitable part of decipherment. It could be achieved by personally meeting and sharing the key or delivering it through a reliable source which is not only less secure but also inconvenient.

Adi Shamir, Ronald Rivest, and Leonard Adleman : When they were students at MIT. Image Credit : ams.org

Another trio of computer scientists at MIT namely Ron Rivest, Adi Shamir and Leonard Aldeman developed a mathematical function in 1977 (called the RSA Code, named after their initials) which was based on the revolutionary concept of asymmetric ciphers (which uses separate keys for encryption and decryption).

The RSA Code, a system of asymmetric cryptography is a form of Public Key cryptography. To understand the mystery of RSA Code, we again take the example of Alice and Bob, who want to share some private information with each other. Alice creates a public key (which is a one way function- that is it is impossible for anyone to reverse it to decode the message). This is available to everyone who wants to send her a message. So Bob encrypts the message using the public keys and sends it to Alice. Now Alice needs to decipher the message sent to her and for this she possess a private key (some extra piece of information) that allows only her to decode any message sent to her since no one else possess the private key for decryption.

Mathematically it goes like this:

Alice takes two giant prime numbers, $p$ and $q$ . Let’s take $p=17$ and $q=11$ for simplicity. She multiplies $p$ and $q$ to get $N=187$ . In practice the numbers $p$ and $q$ are quite large, so that $N$ cannot be easily found out even if computers are employed.
She now picks up another number $e$ (say $7$ ) such that $e$ is relatively prime to $(p-1)(q-1)$ which in this case is $(17-1)(11-1)=160$ . This is an outcome of Euler’s Theorem which states that if we raise $a$ to the power Euler’s Totient function of $n$ then we end up with $1$ modulo $n$ . That Is $a^{\phi(n)}\equiv 1\pmod n$ , where $\phi(n)$ is the Euler’s totient function.

Alice now publishes $e$ and $N$ which are available to everyone as public keys for encryption.

Bob wants to send her a message $M$ (say $88$ ). He uses the encryption formula (one way function) along with the public keys issued by Alice to get the encryption key $C=M^e \pmod N$ such that in our example $C=11$ , where $C$ is called the Cipher Text, which is what he sends Alice.

Since modular functions are one way functions hence it is extremely difficult to work out $M$ from $C$ when larger primes are involved. So even if Eve (any third person or spy) catches hold of $C$ when Bob sends it to Alice, she can’t decipher it back to trace $88$ .

But Alice can decipher the message because she knows $p$ and $q$ . She calculates a special number, $d$ her private key according to the formula $ed\equiv 1\pmod{(p-1)(q-1)}$ . In our example $d=23$ which can be easily calculated using the technique of Euclid’s algorithm.

Once Alice has calculated her private key, she simply uses the decryption formula, $M\equiv C^d \pmod N$ . Here in our example after simplification we shall get $M=88$ .

Eureka! Alice is able to recover the original message sent by Bob. Thus this one-way function allows everyone to encrypt messages to a particular person by using the public keys ( $N$ and $e$ ) but only the intended person can decrypt the message because the recipient is the only person who knows $p$ and $q$ , and hence the only person who knows the private key $d$ .

The fundamental logic involved is the difficulty in factorizing $N$ (to get $p$ and $q$ ). Nowadays, for important transactions $N$ is taken to be of the order of atleast $10^{308}$ which would take all the computers in the world, put together, longer than the age of the universe to factorize $N$ .

As long as we do not come up with extremely efficient and faster ways of factorization, the RSA Code is here to stay in all its elegance, simplicity and beauty.

[This article has been written by Harman Kour, who is at present an intern with Gonit Sora.]

Sign up for more like this.