**RSA**

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.