We have the following setup for the RSA algorithm:
- Pick two distinct primes .
- Compute .
- A message is a number such that .
- Let be a number relatively prime to .
- Note that such that
The following are publicly available: . Here is also called the public key and is the private key. The following is the encryption algorithm for message .
Encrypt(m, n, k):
- Return .
Decrypt(m, n, l):
- Return .
Let us prove some of the assumptions we made in the algorithm.
Claim: For any relatively prime to , there exists such that .
Given , we can compute in polynomial time using Euclid’s algorithm for computing gcd. (We’ll do this on Friday).
We will need the following theorem also called the Fermat’s little theorem.
Theorem (Fermat’s little theorem): For any prime then for any integer , .
Proof: If divides then both sides are . If does not divide then consider the sequence modulo . We claim that this set is the same as . Clearly no number in the set can be . Further if then divides . Since does not divide , it follows that it must divide and so . Take the product of the two sets, we get . Thus implying the theorem.
Claim: Let , and be relatively prime to and . Then for any , if then .
Proof: We claim that . Note that since , it follows that for some . Thus .By symmetry . We claim that this implies . Note that if is a multiple of and a multiple of where and are relatively prime then must be a multiple of . Thus setting we infer that . Since , we are done.
Note that one can show that factoring reduces to decrypting the message in the absence of the knowledge of . Thus the security of the RSA cryptosystem is based on the hardness of the factoring problem.