4003-482-01/4005-705-01 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 1024-bit prime
n = pq is a 2048-bit composite number
Let Φ(n) = (p−1)(q−1)
Euler totient function
The number of numbers < n that are relatively prime to n
Choose e and d such that ed = 1 (mod Φ(n)); i.e., d = e−1 (mod Φ(n))
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
Case 1: gcd(m,n) = 1
Euler's theorem: Let a and n be integers with gcd(a,n) = 1, then aΦ(n) = 1 (mod n)
Let E(m) = c = me (mod n)
Then D(E(m)) = D(c) = cd (mod n)
= med (mod n)
= mkΦ(n)+1 (mod n) for some k
= (mΦ(n))k m1 (mod n)
= 1k m1 (mod n)
= m
Case 2: gcd(m,n) ≠ 1
See textbook
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
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.1, Section 3.2, RSA Private Key
See PKCS #1 Version 2.1, 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
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
Alice encrypts a message m for:
Bob: c1 = m3 (mod n1)
Carol: c2 = m3 (mod n2)
Ted: 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
Suppose Alice does the private operation on two numbers m1 and m2:
c1 = m1d (mod n)
c2 = m2d (mod n)
Then Harry can compute the result of the private operation on the number m3 = m1m2 without knowing d:
c3 = m3d (mod n)
= (m1m2)d (mod n)
= m1dm2d (mod n)
= c1c2 (mod n)
To thwart this: Make sure no legitimate message is ever the product of two or more other legitimate messages
Shared factor attack
Suppose Alice chooses p and q as her RSA primes
Suppose Bob chooses p and r as his RSA primes (one is the same as Alice)
Alice publishes her RSA modulus nAlice
Bob publishes his RSA modulus nBob
Harry computes gcd (nAlice, nBob) which very quickly yields the nontrivial factor p
Harry can then compute Alice's q = nAlice/p and Bob's r = nBob/p
Harry can now reconstruct Alice's and Bob'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