In the last lessons we have covered the mathematics machinery necessary to now discuss RSA. RSA got it's name from the last initials of the three people that first publicly described it in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman, who were at MIT. RSA is an algorithm for public-key cryptography. It is also the first known algorithm suitable for signing (we'll discuss this later) and also for encryption. RSA is very widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys combined with up-to-date implementations. For definitions of all of the words in here see the section on this MEC page Cryptography.

The RSA algorithm involves three steps:key generation, encryption and decryption. We will proceed with key encryption, then explain how these keys are used to encrypt and decrypt.


Key Generation:

For RSA we generate both a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. We generate the keys for RSA in the following way:

1. Choose two distinct large random primes p and q. Generally these should be 100 digits plus.
   
2. Compute n=pq
   • This n is used as the modulus for both the public and private keys
3. Choose an integer e such that 1 < e < φ(n) and gcd(e,φ(n))=1 (where φ(n) is the Euler φ-function we've been discussing)
   • e is released as the public key exponent
4. Compute d to satisfy de=1 (mod φ(n))
   • Notice that we can always do this because gcd(e,φ(n))=1, thus e is in Z_φ(n)^* and hence has a unique multiplicative inverse, namely d.
   • d is kept as the private key exponent (hence must be kept secret)

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d.


Encryption:

Liz transmits her public key (n,e) to Jason and keeps the private key secret. Jason then wishes to send message M to Liz.

He first turns M into a number m < n by using an agreed-upon reversible protocol known as a padding scheme (we will discuss this later). He then computes the ciphertext c corresponding to:

c=m^e (mod n)

This can be done quickly with some short cuts. Jason then transmits c to Liz.


Decryption:

Liz can recover m from c by using her private key exponent d by the following computation:

m=c^d (mod n).

Given m, she can then recover the original message M, since the padding scheme is reversible.

The above decryption procedure works because:

c^d=(m^e)^d=m^ed (mod n).

Now, since ed= 1 + k φ(n), (note this is because ed=1 (mod φ(n)),

m^ed=m^{1 + k φ(n)}= m(m^k)^φ(n)=m (mod n).

The last congruence follows from Euler's theorem which states: If a and n are positive integers with gcd(a,n)=1, then a^φ(n)=1 (mod n). However we already knew this because since gcd(a,n)=1 a is in Z_n^* and since the order of this group is φ(n), we get the result.

Note: This requires that m be relatively prime to n. Since n=pq, this is only the case if m is a multiple of p or q. Since p and q are usually very large primes this makes it extremely unlikely.

There are many ways to convert a text message into a number. For example you could just sent one letter at a time and denote the letters A-z with the numbers 0-25, then your message M is made into a number by converting each letter to its appropriate number (and removing spaces). Note: If you m>n cut it into enough pieces so that each piece (say m_i) is less than n. Then proceed with your algorithm. For more sophisticated methods are converting text to a number in such a way that it makes it harder to crack the code. These are called padding schemes. They are used to prevent a number of attacks that potentially work against RSA without padding. To see some of these go to Padding Schemes.


Cryptographic Hash Functions:A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will almost certainly change the hash value.


Signing messages:

Suppose Liz sends an encrypted message to Jason, and in the message she claims to be Liz but how is Jason to know that it is indeed Liz? Since Jason's public key is well public, anyone can send Jason and claim to be Liz. But with RSA Liz can "sign" her message in a way that Jason know that whoever is sending the message has Liz's private key and is thus Liz (assuming private keys are kept private). She does this by computing a hash value of the message (say h) raises it to the power d (mod n), where (n,d) is Liz's private key and attaches it to the message. When Jason receives the signed message, he uses the same hash algorithm in conjunction with Liz's public key. He raises the signature to the power of e (mod n), where (n,e) is Liz's public key, and compares the resulting hash value with the message's actual hash value. If they agree, he then knows that whoever wrote the message possessed Liz's private key.

Note: To provide more secure information transfering, the same keys should never be used for both encryption and signing purposes.


Problem Set 9 :

Challenge: Write a computer program to implement this program for primes of your choice! If you like you can share it with a friend(s) and have them change the primes they use. Then you can send secure messages to each other!

End of Problem Set 9

References and Further Reading:
[1]Cryptographic hash function [2]RSA