Apr 6. RSA


We have the following setup for the RSA algorithm:

  • Pick two distinct primes p, q.
  • Compute n = pq.
  • A message m is a number such that 1 \le m \le n-1.
  • Let k be a number relatively prime to (p-1)(q-1).
  • Note that \exists l such that kl = 1 \pmod{(p-1)(q-1)}

The following are publicly available: n, k. Here k is also called the public key and l is the private key. The following is the encryption algorithm for message m.

Encrypt(m, n, k):

  • Return M = m^k \pmod{n}.

Decrypt(m, n, l):

  • Return m = M^l \pmod{n}.

Let us prove some of the assumptions we made in the algorithm.

Claim: For any k relatively prime to (p-1)(q-1), there exists l such that kl = 1 \pmod{(p-1)(q-1)}.

Given k, we can compute l 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 p then for any integer a, a^p = a \pmod{p}.

Proof: If p divides a then both sides are 0. If p does not divide a then consider the sequence S = \{a, 2a, 3a, \cdots, (p-1)a\} modulo p. We claim that this set is the same as \{1, 2, 3, \cdots, p-1\}. Clearly no number in the set S can be 0. Further if ra = sa \pmod{p} then p divides (r-s)a. Since p does not divide a, it follows that it must divide (r-s) and so r = s. Take the product of the two sets, we get a^{p-1} \prod_{i=1}^{p-1} = \prod_{i=1}^{p-1} \pmod{p}. Thus a^{p-1} = 1 \pmod{p} implying the theorem.

Claim: Let n = pq, p \neq q and k be relatively prime to (p-1)(q-1) and kl = 1 \pmod{(p-1)(q-1)}. Then for any m, if M = m^k \pmod{n} then M^l = m \pmod{n}.

Proof: We claim that m^{kl} = m \pmod{p}. Note that since kl = 1 \pmod{(p-1)(q-1)}, it follows that kl = 1 + t(p-1)(q-1) for some t. Thus m^{kl} = m (m^{p-1})^{t(q-1)} = m \pmod{p}.By symmetry m^{kl} = m \pmod{q}. We claim that this implies m^{kl} = m \pmod{pq}. Note that if x is a multiple of p and a multiple of q where p and q are relatively prime then x must be a multiple of pq. Thus setting x = m^{kl} - m we infer that m^{kl} = m \pmod{pq}. Since n = pq, we are done.

Note that one can show that factoring reduces to decrypting the message in the absence of the knowledge of l. Thus the security of the RSA cryptosystem is based on the hardness of the factoring problem.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s