Rivest-Shamir-Adleman algorithm (RSA algorithm)

To set up the RSA algorithm you do the following:

1. You pick 2 n-bit random primes and .
2. You choose relatively prime to .
3. You let and you publish the public key .
4. You compute your private key (mod ).

Then to encrypt a message someone else does the following:

1. Take a public key .
2. You compute (mod ).
3. Then you send message .

Lastly to decipher the message using the private key you do the following.

1. You receive the message .
2. You calculate (mod ).
3. Revel in your secrete knowledge.

Note this works from Euler’s theorem (modular arithmetic) as so as .

Limitations

1. gcd(m,N) = 1
   1. Otherwise the encrypted message and share a common factor or and they can work out and using the extended Euclidean algorithm and work out .
2. 1. Otherwise looking at the message mod gives the wrong message.
   2. This is normally gotten around by breaking the message up and giving it in little chunks.
3. 1. Otherwise they can just calculate the ‘th root to understand the message.
   2. If is too small then you normally augment it by a factor and encrypt sending afterwards to let the person know they need to subtract it.
4. Can’t send the same and out multiple times.
   1. If you have 3 public keys , and then using the Chinese remainder theorem you can recover the original message .
5. We assume factoring is hard.
   1. If it was not other people would be able to recover and calculate .