| Home Page |

| Course Page |

Chapter 7. The RSA Cryptosystem

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

- Primality testing by
**trial division**- To test whether n is prime:
- Try to divide n by all primes 2, 3, 5, 7, 11, 13, ... ≤ sqrt(n)
- If any divide, then n is not prime (n is composite)
- If none divide, then n is prime
- Problem: This takes too long if n is large

- Fermat's Little Theorem
- Theorem: Let a and n be integers with 1 ≤ a ≤ n−1. If n is prime, then a
^{n−1}= 1 (mod n).

- Theorem: Let a and n be integers with 1 ≤ a ≤ n−1. If n is prime, then a
- The contrapositive of Fermat's Theorem is always true:
- If a
^{n−1}(mod n) ≠ 1, then n is not prime - That is, n is composite

- If a
- The converse of Fermat's Little Theorem is
*not*always true:- If a
^{n−1}(mod n) = 1, then n is prime ←*not*always true - If a
^{n−1}(mod n) = 1, but n is composite, then n is called a**pseudoprime**to the base a - However, the converse of Little Fermat's Theorem is
*almost*always true; pseudoprimes for a given base a are rare

- If a
- This suggests a
**probabilistic primality test,**the**Fermat Test,**to decide if n is prime:- Pick some random numbers a in the range 1 ≤ a ≤ n−1
- For each random number, compute a
^{n−1}(mod n) - If any result is ≠ 1, then n is definitely composite
- If all results are = 1, then n is probably prime
- The more random numbers (a) we try, the higher the probability that n really is prime
- Unfortunately, there are certain rare composite numbers called
**Carmichael numbers**which are pseudoprimes to every base a; the Fermat Test will always give the wrong answer for a Carmichael number

- Another theorem:
- Let n be an odd prime
- Let n−1 = 2
^{s}r, where r is odd - Let a be an integer such that gcd(a,n) = 1
- Then either a^r = 1 (mod n) or a^(2
^{j}r) = n−1 (mod n) for some j, 0 ≤ j ≤ s−1

- The contrapositive is always true:
- If a^r ≠ 1 (mod n) and a^(2
^{j}r) ≠ n−1 (mod n) for all j, 0 ≤ j ≤ s−1, then n is composite

- If a^r ≠ 1 (mod n) and a^(2
- The converse is
*not*always true:- If a^r = 1 (mod n) or a^(2
^{j}r) = n−1 (mod n) for some j, 0 ≤ j ≤ s−1, then n is prime ←*not*always true - If the above is true, but n is composite, again, n is called a
**pseudoprime**to the base a - For a randomly chosen a in the range 1 ≤ a ≤ n−1, the probability that n is a pseudoprime to the base a is at most 1/4

- If a^r = 1 (mod n) or a^(2
- This suggests a
**probabilistic primality test,**the**Miller-Rabin Test,**to decide if n is prime:- Pick 64 random numbers a in the range 1 ≤ a ≤ n−1
- For each random number, perform the above tests
- If any result is "composite," then n is definitely composite
- If all results are "prime," then n is probably prime
- If the outcome is "n is probably prime," the probability that n is not prime is (1/4)
^{64}= 2^{−128}

- To pick a k-bit prime number:
- Generate n = a string of k random bits
- Set the most significant bit to 1; this puts n in the range 2
^{k−1}≤ n ≤ 2^{k}−1 - Set the least significant bit to 1; this makes n odd (an even number other than 2 cannot be prime)
- Optionally, do a trial division test on n using primes up to some (small) limit
- To quickly determine if n has small prime factors and, if so, avoid doing the time-consuming Miller-Rabin test

- Do the Miller-Rabin test on n
- Repeat the above steps until the test says n is probably prime

- Class java.math.BigInteger

- R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems.
*Communications of the ACM,*21(2):120-126, February 1978. - The RSA formulas
- Let p be a 1024-bit prime
- Let q be a (different) 1024-bit prime
- n = pq is a 2048-bit composite number
- Let φ = (p−1)(q−1)
- Euler totient function of n
- The number of numbers < n that are relatively prime to n

- Choose e and d such that ed = 1 (mod φ); i.e., d = e
^{−1}(mod φ) - Public key = (e, n)
- Private key = d
- Let m be an integer, 1 ≤ m ≤ n−1
- Public operation: c = E(m) = m
^{e}(mod n) - Let c be an integer, 1 ≤ c ≤ n−1
- Private operation: m = D(c) = c
^{d}(mod n)

- Proof that D(E(m)) = m for RSA
- RSA encryption followed by decryption computes c
^{d}= m^{ed} - Case 1. gcd (m, p) = 1
- Then by Euler's Theorem (or Fermat's Little Theorem):

m^{Φ(p)}= m^{p−1}≡ 1 (mod p) - Raise both sides to the power k(q−1):

m^{k(p−1)(q−1)}≡ 1^{k(q−1)}= 1 (mod p) - Multiply both sides by m:

m ⋅ m^{k(p−1)(q−1)}= m^{1}⋅ m^{k(p−1)(q−1)}= m^{(1+k(p−1)(q−1))}≡ m (mod p) - Because ed ≡ 1 (mod φ), there is an integer k such that:

1 + kφ = ed, or

1 + k(p−1)(q−1) = ed - Therefore, m
^{ed}≡ m (mod p)

- Then by Euler's Theorem (or Fermat's Little Theorem):
- Case 2. gcd (m, p) ≠ 1
- Then gcd (m, p) must = p, which is the only other factor of the prime p
- So m must be a multiple of p
- In that case, m ≡ 0 (mod p) and m
^{ed}≡ 0 (mod p) - Therefore, m
^{ed}≡ m (mod p)

- So m
^{ed}≡ m (mod p) in both cases - By similar reasoning, m
^{ed}≡ m (mod q) in both cases - Therefore, m
^{ed}≡ m (mod lcm (p, q)), by a previous fact - But p and q are different primes, so gcd (p, q) = 1, so lcm (p, q) = pq/1 = pq = n
- Therefore, c
^{d}= m^{ed}≡ m (mod n). QED.

- RSA encryption followed by decryption computes c
- Also, E(D(m)) = m for RSA
- Security of RSA
- It must be difficult to compute D without knowing the private key
- The RSA public operation is modular exponentiation to the power e
- The RSA private operation is modular exponentiation to the power e
^{−1}= 1/e, that is, taking a modular e-th root - No one knows an efficient algorithm for taking an e-th root modulo a 2048-bit number

- It must be difficult to derive the private key given the public key
- If Harry the Hacker knows (e, n), no more efficient way to find d is known than to factor n
- No one knows an efficient algorithm for factoring a 2048-bit number
- On the other hand, 640-bit and 768-bit numbers have been factored
- The RSA Factoring Challenge: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

- It must be difficult to compute D without knowing the private key

- The Public Key Cryptography Standard (PKCS) #1: https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf
- Implement modular exponentiation with a square-and-multiply (or an even faster) algorithm
- To speed up the public operation:
- Use a small public exponent
- e = 3
- e = 65537 = 2
^{16}+ 1

- To speed up the private operation:
- Use the Chinese Remainder Theorem
- See PKCS #1 Version 2.2, Section 3.2, RSA Private Key
- See PKCS #1 Version 2.2, Section 5.1.2, RSA Decryption Primitive (RSADP)
- Speeds up the private operation by a factor of 4

- Chinese Remainder Theorem (CRT)
- Given a set of simultaneous congruences:

x ≡ a_{1}(mod m_{1})

x ≡ a_{2}(mod m_{2})

. . .

x ≡ a_{n}(mod m_{n})

where the moduli m_{1}, m_{2}, . . . m_{n}are pairwise relatively prime - Let M = m
_{1}m_{2}⋅ ⋅ ⋅ m_{n} - Then there is a unique value of x (mod M)
- Let:

b_{1}= (M / m_{1})^{−1}(mod m_{1})

b_{2}= (M / m_{2})^{−1}(mod m_{2})

. . .

b_{n}= (M / m_{n})^{−1}(mod m_{n}) - Then x ≡ a
_{1}b_{1}M / m_{1}+ a_{2}b_{2}M / m_{2}+ . . . + a_{n}b_{n}M / m_{n}(mod M)

- Given a set of simultaneous congruences:
- Chinese Remainder Theorem for the case of two moduli (as in RSA)
- Given the simultaneous congruences:

x ≡ a (mod p)

x ≡ b (mod q)

where p and q are relatively prime - Let c = q
^{−1}(mod p), d = p^{−1}(mod q) - Then x ≡ acq + bdp (mod pq)

- Given the simultaneous congruences:

- Primes too close together
- If the difference between p and q is small, then p and q are both close to sqrt(n), and dividing n by odd numbers around sqrt(n) (trial division factoring) will find them
- To thwart this: Choose p and q at random, then there is a negligible probability their difference will be small

- Small public exponent
- We would like e to be small, e.g. e = 3 or e = 5, so the public operation is efficient
- If e is small and m is small, then m
^{e}may be less than n, and then c = E(m) is just m^{e}without the (mod n) - Harry can then compute D(c) = c
^{1/e}without the (mod n) - To thwart this: Make sure m
^{e}is always greater (much greater) than n

- Same number encrypted with different public keys, each with e = 3
- Alex encrypts a message m for:
- Blake: c
_{1}= m^{3}(mod n_{1}) - Corey: c
_{2}= m^{3}(mod n_{2}) - Devon: c
_{3}= m^{3}(mod n_{3})

- Blake: c
- Now, using the Chinese Remainder Theorem, Harry solves the three simultaneous congruences:
- x = c
_{1}(mod n_{1}) - x = c
_{2}(mod n_{2}) - x = c
_{3}(mod n_{3})

- x = c
- This yields x = m
^{3} - Then Harry finds m = x
^{1/3} - To thwart this: Make sure never to encrypt the same number for different parties

- Alex encrypts a message m for:
**Homomorphic property**of RSA- Arises in the context of digital signatures
- Suppose Alex does the private operation on two numbers m
_{1}and m_{2}:- s
_{1}= m_{1}^{d}(mod n) = signature on m_{1} - s
_{2}= m_{2}^{d}(mod n) = signature on m_{2}

- s
- Then Harry can compute the signature on the number m
_{3}= m_{1}m_{2}without knowing d:- s
_{3}= m_{3}^{d}(mod n) - = (m
_{1}m_{2})^{d}(mod n) - = m
_{1}^{d}m_{2}^{d}(mod n) - = s
_{1}s_{2}(mod n)

- s
- The signature of the product ((m
_{1}m_{2})^{d}) is the product of the signatures (s_{1}s_{2}) - To thwart this: Make sure no legitimate message is ever the product of two or more other legitimate messages

- Shared factor attack
- Suppose Alex chooses p and q as her RSA primes
- Suppose Blake chooses p and r as his RSA primes (one is the same as Alex)
- Alex publishes her RSA modulus n
_{Alex} - Blake publishes his RSA modulus n
_{Blake} - Harry computes gcd (n
_{Alex}, n_{Blake}) which very quickly yields the nontrivial factor p - Harry can then compute Alex's q = n
_{Alex}/p and Blake's r = n_{Blake}/p - Harry can now reconstruct Alex's and Blake's private keys
- This has actually happened in the real world!

A. Lenstra, J. Hughes, M. Augier, J. Bos, T. Kleinjung, and C. Wachter. Ron was wrong, Whit is right. Cryptology ePrint Archive, Report 2012/064, February 17, 2012. http://eprint.iacr.org/2012/064 - Conjecture: This could happen if people don't seed their random number generators with sufficient true random data before generating RSA primes, so occasionally someone generates the same "random" prime as someone else

- Other attacks based on the mathematics of RSA are possible; see
*Handbook of Applied Cryptography*, Section 8.2.2 - These attacks can all be thwarted if:
- m is about the same size as n, and
- The public operation is never performed with different public keys on the same m, and
- There is no "mathematical structure" in m, i.e., m looks like a random number, and
- Everyone generates their random primes p and q properly

- RSA can be viewed as a block cipher with a (log
_{2}n)-bit block size, so RSA could theoretically be used with a block cipher mode to encrypt a message - But an RSA implementation is typically several orders of magnitude slower than a block cipher implementation
- Instead:
**hybrid encryption**- Alex picks a random message key K
- Alex encrypts the message using a block cipher with key K: E
_{K}(M) - Alex encrypts K using RSA with Blake's public key: E
_{Blake}(K) - Alex sends (E
_{Blake}(K), E_{K}(M)) to Blake - K is used only for this one message; i.e., K is a nonce

- Problem
- K is a 128-bit or 256-bit number
- But RSA wants to encrypt a 2048-bit number
- So RSA will be encrypting a number with a lot of high-order zero bits
- Undesirable mathematical structure

- Solution: Increase K to a random-looking 2048-bit number using an
**encoding function**(a.k.a.**padding function**) - The Optimal Asymmetric Encryption Padding (OAEP) function used in PKCS #1
- M. Bellare and P. Rogaway. Optimal asymmetric encryption.
*Advances in Cryptology -- EUROCRYPT 1994,*pages 92-111, 1994. - See PKCS #1 Version 2.2, Section 7.1, RSAES-OAEP
- Provably secure against chosen ciphertext attacks
- Uses a
**hash function**to expand (pad) the message

- M. Bellare and P. Rogaway. Optimal asymmetric encryption.

| Course Page |

| Home Page |