CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Mathematical background
The Chinese remainder theorem
Fermat’s little theorem
The RSA cryptosystem
Description of RSA
Encryption is the inverse of decryption
E!ciency concerns
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Recall
Definition (A public-key cryptosystem)
A public-key cryptosystem is a cryptosystem
(P, C,K, E ,D) where
1 For every k ! K, ek is the inverse of dk
2 For every k ! K and for every x ! P or y ! C,
ek(x) and dk(y) are easy to compute
3 It is computationally infeasible (for almost all
k ! K) to derive dk from ek
4 For every k ! K it is feasible to compute ek and dk
from k
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
ek and dk are inverses?
Alice sent a message x ! P encrypted with Bob’s public
key (n, b):
ek(x) ” x
b (mod n)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
ek and dk are inverses?
Alice sent a message x ! P encrypted with Bob’s public
key (n, b):
ek(x) ” x
b (mod n)
Bob decrypts with his private key (p, q, a):
dk(ek(x)) ” (x
b)a (mod n)
” xba (mod n)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
ek and dk are inverses?
Alice sent a message x ! P encrypted with Bob’s public
key (n, b):
ek(x) ” x
b (mod n)
Bob decrypts with his private key (p, q, a):
dk(ek(x)) ” (x
b)a (mod n)
” xba (mod n)
We need to prove that
xba ” x (mod n)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We need to show that
xba ” x (mod n)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We need to show that
xba ” x (mod n)
ba is defined by
ba ” 1 (mod !(n))
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We need to show that
xba ” x (mod n)
ba is defined by
ba ” 1 (mod !(n))
we can rewrite this:
ba = k!(n) + 1 for some k ! N
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We need to show that
xba ” x (mod n)
ba is defined by
ba ” 1 (mod !(n))
we can rewrite this:
ba = k!(n) + 1 for some k ! N
= k(p # 1)(q # 1) + 1.
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We need to show that
xba ” x (mod n)
ba is defined by
ba ” 1 (mod !(n))
we can rewrite this:
ba = k!(n) + 1 for some k ! N
= k(p # 1)(q # 1) + 1.
If gcd(x, p) = 1 we have
xp!1 ” 1 (mod p)
by Fermat’s little theorem.
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We raise both sides to the power k(q # 1):
xk(p!1)(q!1) ” 1 (mod p)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We raise both sides to the power k(q # 1):
xk(p!1)(q!1) ” 1 (mod p)
and multiplying both sides by x we have, for
gcd(x, p) = 1, that:
xk(p!1)(q!1)+1 ” x (mod p)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We raise both sides to the power k(q # 1):
xk(p!1)(q!1) ” 1 (mod p)
and multiplying both sides by x we have, for
gcd(x, p) = 1, that:
xk(p!1)(q!1)+1 ” x (mod p)
but if gcd(x, p) = p then this holds as both sides are
congruent to 0 (mod p).
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
We raise both sides to the power k(q # 1):
xk(p!1)(q!1) ” 1 (mod p)
and multiplying both sides by x we have, for
gcd(x, p) = 1, that:
xk(p!1)(q!1)+1 ” x (mod p)
but if gcd(x, p) = p then this holds as both sides are
congruent to 0 (mod p).
Hence for all x ! P,
xk(p!1)(q!1)+1 ” x (mod p)
$ xba ” x (mod p)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
By the same argument we have
xba ” x (mod q)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
By the same argument we have
xba ” x (mod q)
Now, p and q are relatively prime and we have a system
of congruences:
xba ” x (mod p)
xba ” x (mod q)
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Proof that decryption works
By the same argument we have
xba ” x (mod q)
Now, p and q are relatively prime and we have a system
of congruences:
xba ” x (mod p)
xba ” x (mod q)
Recalling that n = pq, the Chinese remainder theorem
implies that
xba ” x (mod n) as required.
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
Mathematical background
The Chinese remainder theorem
Fermat’s little theorem
The RSA cryptosystem
Description of RSA
Encryption is the inverse of decryption
E!ciency concerns
CM30173:
Cryptography
Part IV
Mathematical
background
The Chinese remainder
theorem
Fermat’s little theorem
The RSA
cryptosystem
Description of RSA
Encryption is the
inverse of decryption
E!ciency concerns
RSA parameter generation
Algorithm
1 Generate two large primes p, q such that p %= q
2 Calculate n = pq, !(n) = (p # 1)(q # 1)
3 Choose a random 1 < b < !(n) such that gcd(b, !(n)) = 1 4 Calculate a = b!1 (mod !(n)) 5 Set the public key to (n, b) and the private key to (p, q, a) CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Generating large primes We won’t study this in any detail. Basic method: generate a large random number, test this for primality. CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Generating large primes We won’t study this in any detail. Basic method: generate a large random number, test this for primality. PRIMES is in P: In 2002 Agrawal, Kayal and Saxena proved that there is a polynomial time deterministic algorithm for primality testing. CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Generating large primes We won’t study this in any detail. Basic method: generate a large random number, test this for primality. PRIMES is in P: In 2002 Agrawal, Kayal and Saxena proved that there is a polynomial time deterministic algorithm for primality testing. But we don’t use this. CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Generating large primes We won’t study this in any detail. Basic method: generate a large random number, test this for primality. PRIMES is in P: In 2002 Agrawal, Kayal and Saxena proved that there is a polynomial time deterministic algorithm for primality testing. But we don’t use this. Instead we use one of a variety of randomised polynomial time algorithms. The Miller-Rabin algorithm is the most prominent. CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Modular arithmetic The other large cost involved in the parameter generation is the calculation of a = b!1 (mod !(n)). We use extended Euclidean algorithm. Can be calculated in time O((log k)2) CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Modular arithmetic The other large cost involved in the parameter generation is the calculation of a = b!1 (mod !(n)). We use extended Euclidean algorithm. Can be calculated in time O((log k)2) What about the modular exponentiation in RSA? CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Modular arithmetic The other large cost involved in the parameter generation is the calculation of a = b!1 (mod !(n)). We use extended Euclidean algorithm. Can be calculated in time O((log k)2) What about the modular exponentiation in RSA? To calculate xb (mod n) can be: CM30173: Cryptography Part IV Mathematical background The Chinese remainder theorem Fermat’s little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption E!ciency concerns Modular arithmetic The other large cost involved in the parameter generation is the calculation of a = b!1 (mod !(n)). We use extended Euclidean algorithm. Can be calculated in time O((log k)2) What about the modular exponentiation in RSA? To calculate xb (mod n) can be: 1 Very slow: b # 1 modular multiplications 2 Faster: use the square and multiply algorithm 3 Faster again: use Chinese remainder theorem (if you are Bob) Public-key cryptography Mathematical background The Chinese remainder theorem Fermat's little theorem The RSA cryptosystem Description of RSA Encryption is the inverse of decryption Efficiency concerns