【文章內(nèi)容簡介】 approach to puting xc mod n is inefficient when c is large. ? Instead, represent c as bit string bk1 … b0 and use the following algorithm: z = 1 For i = k1 downto 0 do z = z2 mod n if bi = 1 then z = z* x mod n 11/4/2020 Lecture 3: Pubic Key Cryptography 25 Example: 3037 mod 77 z = z2 mod n if bi = 1 then z = z* x mod n i b z 5 1 30 =1*1*30 mod 77 4 0 53 =30*30 mod 77 3 0 37 =53*53 mod 77 2 1 29 =37*37*30 mod 77 1 0 71 =29*29 mod 77 0 1 2 =71*71*30 mod 77 11/4/2020 Lecture 3: Pubic Key Cryptography 26 Lagrange’s Theorem ? Order of an element in a group divides the order of the group 11/4/2020 Lecture 3: Pubic Key Cryptography 27 Euler’s totient function ? Given positive integer n, Euler’s totient function is the number of positive numbers less than n that are relatively prime to n ? Fact: If p is prime then ? {1,2,3,…,p1} are relatively prime to p. ( ) 1pp? ? ?)(n?11/4/2020 Lecture 3: Pubic Key Cryptography 28 Euler’s totient function ? Fact: If p and q are prime and n=pq then ? Each number that is not divisible by p or by q is relatively prime to pq. ? . p=5, q=7: {1,2,3,4,,6,,8,9,,11,12,13,,,16,17,18,19,,,22,23,24,,26,27,,29,,31,32,33,34,} ? pqp(q1) = (p1)(q1) )1)(1()( ???? qpn11/4/2020 Lecture 3: Pubic Key Cryptography 29 Euler’s Theorem and Fermat’s Theorem ? If a is relatively prime to n then ? If a is relatively prime to n then ap1 = 1 mod p Proof : follows from Lagrange’s Theorem na n m o d1)( ??11/4/2020 Lecture 3: Pubic Key Cryptography 30 RSA Cryptosystem 11/4/2020 Lecture 3: Pubic Key Cryptography 31 “Textbook” RSA: KeyGen ? Alice wants people to be able to send her encrypted messages. ? She chooses two (large) prime numbers, p and q and putes n=pq and . [“l(fā)arge” =512 bits +] ? She chooses a number e such that e is relatively prime to and putes d, the inverse of e in (., ed =1 mod \phi(n)) ? She publicizes the pair (e,n) as her public key.(e is called RSA exponent, n is called RSA modulus)She keeps d secret and destroys p, q, and ? Plaintext and ciphertext messages are elements of Zn and e is the encryption key. )(n?)(n?)(nZ?)(n?11/4/2020 Lecture 3: Pubic Key Cryptography 32 RSA: Encryption ? Bob wants to send a message x (an element of Zn*) to Alice. ? He looks up her encryption key, (e,n), in a directory. ? The encrypted message is ? Bob sends y to Alice. nxxEy e m o d)( ??11/4/2020 Lecture 3: Pubic Key Cryptography 33 RSA: Decryption ? To decrypt the message she’s received from Bob, Alice putes Claim: D(y) = x nyyD d m o d)( ?nxxEy e m o d)( ??11/4/2020 Lecture 3: Pubic Key Cryptography 34 RSA: why does it all work ? Need to show ? D[E[x]] = x ? E[x] and D[y] can be puted efficiently if keys are known ? E1[y] cannot be puted efficiently without knowledge of the (private) decryption key d. ? Also, it should be possible to select keys reasonably efficiently ? This does not have to be done too often, so efficiency requirements are less stringent. 11/4/2020 Lecture 3: Pubic Key Cryptography 35 E and D are inverses: Case 1: gcd(x,n)=1 nxnxnxxnxnxnxnxnyyDttnnteddededm o dm o d1m o d)(m o dm o dm o d)()m o d(m o d)()(1)(???????????Because From Euler’s Theorem )(m o d1 ned ??11/4/2020 Lecture 3: Pubic Key Cryptography 36 Alternative Proof that E and D are inverses )(|m o dm o dm o d1m o d1)(m o d11)1)(1(1)(1)()()1(11xxpp