17crypto_L09
RSA Public Key Encryption
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
1
Reduced Set of Residues
� The RSA algorithm is based on a small amount of number
theory.
� The reduced set of residues (RSR) of a number n is the set
of all integers which have an inverse mod n.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
2
of all integers which have an inverse mod n.
�In other words, all the numbers a with
� gcd(a, n) = 1
�RSR of 10 = {1, 3, 7, 9}
�RSR of prime p = {1, 2, …, p-1 }
Euler Totient Function
� The Euler Totient Function φ is the size of this set.
� φ(10) = 4.
�φ(p) = p-1, where p is prime.
�φ(pq) =(p-1)(q-1), where p, q are prime.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
3
�φ(pq) =(p-1)(q-1), where p, q are prime.
�φ(pqr)=(p-1)(q-1)(r-1), where p, q,r are
prime.
� This second result can be proved by counting.
�There are pq-1 numbers in the range 1 .. pq-1
Euler Totient Function (2)
� We do not want factors of p: p,2p,…,(q-1)p
�There are q-1 of these.
� Similarly, there are p-1 factors of q.
� There are no numbers with factors p and q.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
4
� There are no numbers with factors p and q.
φ(pq) = (pq-1)-(q-1)-(p-1)
= pq-p-q+1
= (p-1)(q-1)
Fermat’s Theorem
� If p is prime and gcd(a,p)=1
�then ap-1 % p = 1.
� Proof from Euler’s generalization, which follows next.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
5
� Euler’s Generalization of Fermat’s Theorem
� aφ(n) % n = 1, provided gcd(a, n) = 1.
� Proof beyond the scope of this course.
A Probabilistic Primality Test
� Let a be a prime number.
� If an-1 % n ≠ 1, then n is NOT prime.
� If an-1 % n = 1, then n may be a prime, or the result
may be 1 by accident.
� Choose a series of prime numbers a, and calculate an-1%n.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
6
� Choose a series of prime numbers a, and calculate an-1%n.
� If the answer is 1 in all cases, then we can assume that n is
a prime with a small probability of error.
� Carmichael numbers are not prime but always pass this
test.
�There are not many of them.
Exponentiation Ciphers
� The RSA public key system is a form of exponentiation
cipher, and so we will consider exponentiation ciphers
first.
� The Plaintext Input
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
7
� The Plaintext Input
�Let us choose an integer n and split the plaintext into a
series of messages Pi with 0 ≤ Pi < n.
�This can be achieved by splitting the message into
blocks
�I will drop the i suffix from now on and just consider
what happens to one block.
Exponentiation Ciphers (2)
� Encryption
�Choose an integer e and calculate the cipher text C = Pe % n
� Decryption
�Choose an integer d and recover the message by P = Cd % n
� d and e must be inverses, so that
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
8
� d and e must be inverses, so that
�de ≡ 1 mod φ(n)
�Hence de = 1 mod λ φ(n) for some integer λ.
�We don’t need to know what λ is.
�Also gcd(d, φ(n)) = 1 for the inverse to exist.
�Therefore d is the unique inverse of e.
Proof
C = Pe % n
P' = Cd % n
= Ped % n
= P1+λφ(n) % n
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
9
= P1+λφ(n) % n
= P * Pλφ(n) % n
= P * (Pφ(n) % n)λ % n
= P, since Pφ(n) % n = 1
by Euler's generalisation of Fermat's theorem, assuming gcd(P, n) = 1.
Pohlig - Hellman Scheme
� Chose n = p, a prime.
� Hence φ = p-1 = n-1.
� This is not a public key system since
�if (n, e), which are necessary for encryption, are
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
10
�if (n, e), which are necessary for encryption, are
made public then
� φ can be calculated and hence also d.
Rivest Shamir Adleman (RSA)
Scheme
� Chose n = pq, the product of two primes.
� Then φ = (p-1)(q-1) which can only be calculated if
n is factored.
�We have to know both p and q to calculate φ.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
11
�We have to know both p and q to calculate φ.
� This is safe provided our enemies cannot factor n into two
primes.
� gcd(P,n) may not be 1 if P has either p or q as a factor.
� The values of p and q are so large that this is very unlikely
and can be ignored.
Difficulty of Factoring
� Factoring is not known to be NP-complete.
�Primality testing is similar to factoring. A polynomial
time algorithm for primality testing was discovered in
1995.
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
12
1995.
�There is no know polynomial time algorithm for
factoring.
� The best general purpose factoring algorithm is
O(n√(log log n / log n))
� This would involve about 1015 operations for a 100 digit
number.
The RSA Algorithm
1. Chose the length of n (number of bits) so that it is computationally
infeasible to factor n.
2. Chose two primes p and q of near equal length and calculate
� n = pq, φ = (p-1)(q-1).
φ
Crypto & SecDev 2017 © Ron Poet:
Lecture 9
13
� Choose p%4 ≠ 1 and q%4 ≠ 1 so that φ does not have too
many factors of 2.
3. Choose d as a prime, about the same length as n.
4. Calculate e using the inverse formula.
If e is too small (