lecture3publickeycryptography

lecture3publickeycryptography内容摘要：

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 . [“large” =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。