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
Summary
The set of residues modulo n denoted Zn is a
commutative ring.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Summary
The set of residues modulo n denoted Zn is a
commutative ring.
b ! Zn has a multiplicative inverse if and only if
gcd(n, b) = 1.
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Summary
The set of residues modulo n denoted Zn is a
commutative ring.
b ! Zn has a multiplicative inverse if and only if
gcd(n, b) = 1.
The number of positive integers b < n relatively
prime to n is !(n).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Summary
The set of residues modulo n denoted Zn is a
commutative ring.
b ! Zn has a multiplicative inverse if and only if
gcd(n, b) = 1.
The number of positive integers b < n relatively
prime to n is !(n).
The set of residues modulo n which are
relatively prime to n is denoted Z!
n
. This is an
Abelian group under multiplication, b ! Z!
n
have a
multiplicative inverse b"1 ! Z!
n
.
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
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
r1 = q2r2 + r3 0 < r3 < r2
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
r1 = q2r2 + r3 0 < r3 < r2
...
...
...
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
r1 = q2r2 + r3 0 < r3 < r2
...
...
...
rm"2 = qm"1rm"1 + rm 0 < rm < rm"1
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
r1 = q2r2 + r3 0 < r3 < r2
...
...
...
rm"2 = qm"1rm"1 + rm 0 < rm < rm"1
rm"1 = qmrm
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The Euclidean algorithm
The Euclidean algorithm calculates the greatest
common divisor of a, b ! N, a " b denoted gcd(a, b).
Set r0 = a, r1 = b and perform the following:
r0 = q1r1 + r2 0 < r2 < r1
r1 = q2r2 + r3 0 < r3 < r2
...
...
...
rm"2 = qm"1rm"1 + rm 0 < rm < rm"1
rm"1 = qmrm
It can be shown that
gcd(a, b) = gcd(r0, r1) = . . . = gcd(rm"1, rm) = rm
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Euclidean algorithm
Algorithm
Inputs: a, b ! N, a " b
Output: gcd(a, b)
r0 = a, r1 = b, m = 1
while rm #= 0 do
qm = $
rm!1
rm
%
rm+1 = rm"1 & qmrm
m = m + 1
end do
m = m & 1
return rm
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
Basic idea
In the Euclidean algorithm we had
rm"2 = qm"1rm"1 + rm and gcd(r0, r1) = rm
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
In the Euclidean algorithm we had
rm"2 = qm"1rm"1 + rm and gcd(r0, r1) = rm
We unwind the steps writing each in terms of the
inputs a and b:
r2 = r0 & q1r1 = a & q1b
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
In the Euclidean algorithm we had
rm"2 = qm"1rm"1 + rm and gcd(r0, r1) = rm
We unwind the steps writing each in terms of the
inputs a and b:
r2 = r0 & q1r1 = a & q1b
r3 = r1 & q2r2 = b & q2(a & q1b)
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
In the Euclidean algorithm we had
rm"2 = qm"1rm"1 + rm and gcd(r0, r1) = rm
We unwind the steps writing each in terms of the
inputs a and b:
r2 = r0 & q1r1 = a & q1b
r3 = r1 & q2r2 = b & q2(a & q1b)
= b & q2a + q1q2b = &q2a + (1 + q1q2)b
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
In the Euclidean algorithm we had
rm"2 = qm"1rm"1 + rm and gcd(r0, r1) = rm
We unwind the steps writing each in terms of the
inputs a and b:
r2 = r0 & q1r1 = a & q1b
r3 = r1 & q2r2 = b & q2(a & q1b)
= b & q2a + q1q2b = &q2a + (1 + q1q2)b
...
...
...
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
= (si"2 & qi"1si"1)a + (ti"2 & qi"1ti"1)b
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
= (si"2 & qi"1si"1)a + (ti"2 & qi"1ti"1)b
= sia + tib
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
= (si"2 & qi"1si"1)a + (ti"2 & qi"1ti"1)b
= sia + tib
...
...
...
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
= (si"2 & qi"1si"1)a + (ti"2 & qi"1ti"1)b
= sia + tib
...
...
...
rm = sma + tmb
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
...
...
...
ri"2 = si"2a + ti"2b
ri"1 = si"1a + ti"1b
ri = ri"2 & qi"1ri"1
= si"2a + ti"2b & qi"1(si"1a + ti"1b)
= (si"2 & qi"1si"1)a + (ti"2 & qi"1ti"1)b
= sia + tib
...
...
...
rm = sma + tmb
Hence we will find sm, tm ! Z such that
gcd(a, b) = sma + tmb
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Basic idea
From the above we can see that
ti =
!
"
#
0 if i = 0
1 if i = 1
ti"2 & qi"1ti"1 if i " 2
si =
!
"
#
1 if i = 0
0 if i = 1
si"2 & qi"1si"1 if i " 2
You can prove by induction that ri = sia + tib for all
0 ' i ' m (or see course text).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Finding the multiplicative inverse
Proposition
If we have gcd(n, b) = 1 then b"1 ( tm (mod n).
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
The extended Euclidean algorithm
Algorithm
Inputs: a, b ! N, a " b
Output: gcd(a, b) and s, t ! Z such that
sa + tb = gcd(a, b)
sold = 1, s = 0, told = 0, t = 1
q = $a
b
%, r = a & qb
while r > 0 do
tnew = told & qt, told = t, t = tnew
snew = sold & qs, sold = s, s = snew
a = b, b = r, q = $a
b
%, r = a & qb
end do
return (b, s, t)
Public-key cryptography
Mathematical background
Arithmetic modulo n
The Euclidean algorithm
The extended Euclidean algorithm
The Chinese remainder theorem