CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Mathematical background
Arithmetic modulo n
The Euclidean algorithm
The extended Euclidean algorithm
The Chinese remainder theorem
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Modular exponentiation
We will need to be able to raise elements of Zn to
a power working modulo n. This is called modular
exponentiation.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Modular exponentiation
We will need to be able to raise elements of Zn to
a power working modulo n. This is called modular
exponentiation.
We require a method to do this e!ciently.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Modular exponentiation
We will need to be able to raise elements of Zn to
a power working modulo n. This is called modular
exponentiation.
We require a method to do this e!ciently.
We will use the Chinese remainder theorem to
achieve this.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
What is the Chinese remainder theorem?
The Chinese remainder theorem is a way of solving
certain systems of congruences.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
What is the Chinese remainder theorem?
The Chinese remainder theorem is a way of solving
certain systems of congruences.
Let m1, m2, . . . , mr be pairwise relatively prime
positive integers. Suppose a1, a2, . . . , ar ! Z and
consider:
x ” a1 (mod m1)
x ” a2 (mod m2)
…
…
…
x ” ar (mod mr)
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
What is the Chinese remainder theorem?
The Chinese remainder theorem is a way of solving
certain systems of congruences.
Let m1, m2, . . . , mr be pairwise relatively prime
positive integers. Suppose a1, a2, . . . , ar ! Z and
consider:
x ” a1 (mod m1)
x ” a2 (mod m2)
…
…
…
x ” ar (mod mr)
The Chinese remainder theorem states that this system
has a unique solution modulo M = m1m2 · · ·mr
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Motivation
Let us consider n = 15 = 5 · 3, hence m1 = 5, m2 = 3.
We can represent a ! Z15 by coordinates (a (mod 5), a
(mod 3)):
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Motivation
Let us consider n = 15 = 5 · 3, hence m1 = 5, m2 = 3.
We can represent a ! Z15 by coordinates (a (mod 5), a
(mod 3)):
0 1 2 3 4
0 0 6 12 3 9
1 10 1 7 13 4
2 5 11 2 8 14
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Motivation
What if we select n = 8 = 4 · 2 and represent a ! Z8 by
(a (mod 4), a (mod 2))?
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Motivation
What if we select n = 8 = 4 · 2 and represent a ! Z8 by
(a (mod 4), a (mod 2))?
0 1 2 3
0 0/4 2/6
1 1/5 3/7
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Example: reconstruction of a
Given a it is a simple matter to find coordinates
(a1, a2) = (a (mod m1), a (mod m2)). What seems
more di!cult is reconstructing a given (a1, a2).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Example: reconstruction of a
Given a it is a simple matter to find coordinates
(a1, a2) = (a (mod m1), a (mod m2)). What seems
more di!cult is reconstructing a given (a1, a2).
Restated this might read:
Let M = m1 · m2, gcd(m1, m2) = 1, given
x ” a1 (mod m1), x ” a2 (mod m2)
find a unique solution x ” a (mod M).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
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).
Public-key cryptography
Mathematical background
Arithmetic modulo n
The Euclidean algorithm
The extended Euclidean algorithm
The Chinese remainder theorem