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
Chinese remainder theorem
Theorem
Let m1, m2, . . . , mr ! Z be pairwise relatively prime
and a1, a2, . . . , ar ! Z. The system of r congruences
x ” ai (mod mi), 1 # i # r, has a unique solution
modulo M = m1m2 · · ·mr:
x ”
r!
i=1
aiMiyi (mod M),
were Mi =
M
mi
, yi ” M
!1
i (mod mi).
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
Example of CRT
Let r = 3, M = 1001 = 7! 11! 13. We want to find a
unique x such that
x ” 5 (mod 7)
x ” 3 (mod 11)
x ” 10 (mod 13)
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
Example of CRT
Let r = 3, M = 1001 = 7! 11! 13. We want to find a
unique x such that
x ” 5 (mod 7)
x ” 3 (mod 11)
x ” 10 (mod 13)
We calculate:
M1 = 143, M2 = 91, M3 = 77, y1 = 5, y2 = 4, y3 = 12
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
Example of CRT
Let r = 3, M = 1001 = 7! 11! 13. We want to find a
unique x such that
x ” 5 (mod 7)
x ” 3 (mod 11)
x ” 10 (mod 13)
We calculate:
M1 = 143, M2 = 91, M3 = 77, y1 = 5, y2 = 4, y3 = 12
then
x ”
r!
i=1
aiMiyi (mod M)
” 5 · 143 · 5 + 3 · 91 · 4 + 10 · 77 · 12 (mod 1001)
” 13907 ” 894 (mod 1001)
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 exponentiation
The Chinese remainder theorem can be used to speed
up modular exponentiation
xy (mod n)
if n is composite.
We will return to this when we consider 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
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
Fermat’s little theorem
Theorem
Suppose p prime and b # Z!p then
bp ” b (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
A generalisation
Theorem (Euler)
For all b # Z!n
b!(n) ” 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
Recap
Extended Euclidean algorithm: calculate
multiplicative inverses for elements in Z!n
Chinese remainder theorem: find solutions to some
systems of congruences
Fermat’s little theorem and Euler’s generalisation
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
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
Description of RSA
Cryptosystem
Let n = pq, p, q prime.
P = C = Zn
K = {(n, p, q, a, b) | ba ” 1 (mod !(n))}
For k = (n, p, q, a, b) # K we have
ek(x) = x
b (mod n)
and
dk(y) = y
a (mod n)
for x, y # Zn.
(n, b) is called the public key and (p, q, a) is called
the private key
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
Public-key cryptosystem
Alice Bob
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
Unsecured channel
ek(x) = y dk(y) = x
ek
dk
xx
Key source
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
Small example
Bob chooses p = 127 and q = 131 and calculates:
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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
!(n) = (p $ 1) ! (q $ 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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
!(n) = (p $ 1) ! (q $ 1)
= (127 $ 1) ! (131 $ 1) = 16380
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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
!(n) = (p $ 1) ! (q $ 1)
= (127 $ 1) ! (131 $ 1) = 16380
Bob now selects some b such that gcd(b, !(n)) = 1.
Lets use 4057 and we calculate
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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
!(n) = (p $ 1) ! (q $ 1)
= (127 $ 1) ! (131 $ 1) = 16380
Bob now selects some b such that gcd(b, !(n)) = 1.
Lets use 4057 and we calculate
b”1 = 10453 (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
Small example
Bob chooses p = 127 and q = 131 and calculates:
n = 127 ! 131 = 16637
!(n) = (p $ 1) ! (q $ 1)
= (127 $ 1) ! (131 $ 1) = 16380
Bob now selects some b such that gcd(b, !(n)) = 1.
Lets use 4057 and we calculate
b”1 = 10453 (mod !(n))
So Bob’s public key will be (n, b) = (16637, 4057) and
his private key will be (p, q, a) = (127, 131, 10453).
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
Small example
Alice has Bob’s public key (n, b) = (16637, 4057) and
she wishes to encrypt the plaintext x = 9031. She
computes:
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
Small example
Alice has Bob’s public key (n, b) = (16637, 4057) and
she wishes to encrypt the plaintext x = 9031. She
computes:
xb (mod n) = 90314057 (mod 16637) = 1870
So Alice sends y = 1870 over the insecure channel.
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
Small example
Alice has Bob’s public key (n, b) = (16637, 4057) and
she wishes to encrypt the plaintext x = 9031. She
computes:
xb (mod n) = 90314057 (mod 16637) = 1870
So Alice sends y = 1870 over the insecure channel.
Bob now uses his decryption exponent a to compute:
ya (mod n) = 187010453 (mod 16637) = 9031
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