CS计算机代考程序代写 algorithm CM30173: Cryptography\reserved@d =[@let@token art IV

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