Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 7. The RSA Cryptosystem Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Finding Large Prime Numbers

• 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 an−1 = 1 (mod n).

• The contrapositive of Fermat's Theorem is always true:
• If an−1 (mod n) ≠ 1, then n is not prime
• That is, n is composite

• The converse of Fermat's Little Theorem is not always true:
• If an−1 (mod n) = 1, then n is prime    ← not always true
• If an−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

• 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 an−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 = 2sr, where r is odd
• Let a be an integer such that gcd(a,n) = 1
• Then either a^r = 1 (mod n) or a^(2jr) = n−1 (mod n) for some j, 0 ≤ j ≤ s−1

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

• The converse is not always true:
• If a^r = 1 (mod n) or a^(2jr) = 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

• 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 2k−1 ≤ n ≤ 2k−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

### RSA

• 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) = me (mod n)
• Let c be an integer, 1 ≤ c ≤ n−1
• Private operation: m = D(c) = cd (mod n)

• Proof that D(E(m)) = m for RSA
• RSA encryption followed by decryption computes cd = med
• Case 1. gcd (m, p) = 1
• Then by Euler's Theorem (or Fermat's Little Theorem):
mΦ(p) = mp−1 ≡ 1 (mod p)
• Raise both sides to the power k(q−1):
mk(p−1)(q−1) ≡ 1k(q−1) = 1 (mod p)
• Multiply both sides by m:
m ⋅ mk(p−1)(q−1) = m1 ⋅ mk(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, med ≡ m (mod p)
• 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 med ≡ 0 (mod p)
• Therefore, med ≡ m (mod p)
• So med ≡ m (mod p) in both cases
• By similar reasoning, med ≡ m (mod q) in both cases
• Therefore, med ≡ 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, cd = med ≡ m (mod n). QED.

• 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

### Fast Implementation of RSA

• 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 = 216 + 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 ≡ a1 (mod m1)
x ≡ a2 (mod m2)
. . .
x ≡ an (mod mn)
where the moduli m1, m2, . . . mn are pairwise relatively prime
• Let M = m1 m2 ⋅ ⋅ ⋅ mn
• Then there is a unique value of x (mod M)
• Let:
b1 = (M / m1)−1 (mod m1)
b2 = (M / m2)−1 (mod m2)
. . .
bn = (M / mn)−1 (mod mn)
• Then x ≡ a1 b1 M / m1 + a2 b2 M / m2 + . . . + an bn M / mn (mod M)

• 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)

### Pitfalls in Using RSA

• 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 me may be less than n, and then c = E(m) is just me without the (mod n)
• Harry can then compute D(c) = c1/e without the (mod n)
• To thwart this: Make sure me 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: c1 = m3 (mod n1)
• Corey: c2 = m3 (mod n2)
• Devon: c3 = m3 (mod n3)
• Now, using the Chinese Remainder Theorem, Harry solves the three simultaneous congruences:
• x = c1 (mod n1)
• x = c2 (mod n2)
• x = c3 (mod n3)
• This yields x = m3
• Then Harry finds m = x1/3
• To thwart this: Make sure never to encrypt the same number for different parties

• Homomorphic property of RSA
• Arises in the context of digital signatures
• Suppose Alex does the private operation on two numbers m1 and m2:
• s1 = m1d (mod n) = signature on m1
• s2 = m2d (mod n) = signature on m2
• Then Harry can compute the signature on the number m3 = m1m2 without knowing d:
• s3 = m3d (mod n)
• = (m1m2)d (mod n)
• = m1dm2d (mod n)
• = s1s2 (mod n)
• The signature of the product ((m1m2)d) is the product of the signatures (s1s2)
• 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 nAlex
• Blake publishes his RSA modulus nBlake
• Harry computes gcd (nAlex, nBlake) which very quickly yields the nontrivial factor p
• Harry can then compute Alex's q = nAlex/p and Blake's r = nBlake/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

### Message Encryption with RSA

• RSA can be viewed as a block cipher with a (log2 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: EK(M)
• Alex encrypts K using RSA with Blake's public key: EBlake(K)
• Alex sends (EBlake(K), EK(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

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005