rsa

Public Key Cryptography and the RSA Algorithm:

Public Key Cryptography and the RSA Algorithm SUMMARY OF THE TECHNICAL PAPER PRESENTED BY R.L. Rivest, A. Shamir, and L. Adleman

Slide 2:

Introduction The era of “electronic mail" may soon be upon us; we must ensure that two important properties of the current “paper mail" system are preserved: (a) messages are private, and (b) messages can be signed. We demonstrate in this paper how to build these capabilities into an electronic mail system. At the heart of our proposal is a new encryption method. This method provides an implementation of a “public-key cryptosystem," an elegant concept invented by Die and Hellman. Their article motivated our research, since they presented the concept but not any practical implementation of such a system .

Private-Key Cryptography:

Private-Key Cryptography One key Key shared Alice sents a private key to Bob. All further message are encrypted and decrypted using the same key by both Alice and Bob. ALICE BOB

Public-Key Cryptography:

Public-Key Cryptography probably most significant advance in the 3000 year history of cryptography uses two keys – a public key and a private key asymmetric since parties are not equal uses clever application of number theory concepts to function complements rather than replaces private key cryptography

Slide 5:

PROPERTIES OF PROCEDURES D(E(M)) = M Both E and D are easy to compute E: PUBLIC::D:PUBLIC….. NO!!!!!! E(D(M)) = M If E satifies 1,2,3 Then TRAP DOOR ONE WAY FUNCTION If all 4 satified Then Trap door one way permutation For signatures

Slide 6:

PRIVACY

Slide 7:

SIGNATURE

RSA:

RSA by Rivest , Shamir & Adleman of MIT in 1977 first published: Scientific American, Aug. 1977. (after some censorship entanglements) Currently the “work horse” of Internet security: Most Public Key Infrastructure (PKI) products. SSL/TLS: Certificates and key-exchange. Secure e-mail: PGP, Outlook, …

Slide 10:

E and D are C = E(M) =M e (mod n), for a message M D(C) = C d (mod n), for a ciphertext C M is first represented as a integer between 0 and n-1 Our encryption and decryption algorithms The encryption key (e,n). Similarly, the decryption key (d,n).

Slide 11:

How should you choose your encryption and decryption keys

Slide 12:

Algorithms How to Encrypt and Decrypt Efficiently Step 1. Let e k e k - 1 ….e 1 e 0 be the binary representation of e . Step 2. Set the variable C to 1 . Step 3. Repeat steps 3a and 3b for i = k, k-1…..0 Step 3a. Set C to the remainder of C 2 when divided by n. Step 3b. If ei = 1, then set C to the remainder of C.M when divided by n. Step 4. Halt. Now C is the encrypted form of M.

Slide 13:

A very simple example of RSA encryption This is an extremely simple example using numbers you can work out on a pocket calculator primes p=11, q=3. n = pq = 11.3 = 33 phi = (p-1)(q-1) = 10.2 = 20 Choose e=3 Check gcd (e, p-1) = gcd (3, 10) = 1 (i.e. 3 and 10 have no common factors except 1), and check gcd (e, q-1) = gcd (3, 2) = 1 therefore gcd (e, phi) = gcd (e, (p-1)(q-1)) = gcd (3, 20) = 1 Compute d such that ed ≡ 1 (mod phi) i.e. compute d = e -1 mod phi = 3 -1 mod 20 i.e. find a value for d such that phi divides (ed-1) i.e. find d such that 20 divides 3d-1. Simple testing (d = 1, 2, ...) gives d = 7 Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi. Public key = (n, e) = (33, 3) Private key = (n, d) = (33, 7). Now say we want to encrypt the message m = 7, c = m e mod n = 7 3 mod 33 = 343 mod 33 = 13. Hence the ciphertext c = 13. To check decryption we compute m' = c d mod n = 13 7 mod 33 = 7.

Slide 14:

RECOLLECTION Prime number Coprime Gcd Euclid’s theorem Euler phi function or totient function Fermat’s Little Theorem : If p is a prime and a is any integer, then a p = a (mod p ). If gcd ( a, p ) = 1, then a p − 1 = 1 (mod p ).

Slide 15:

The Underlying Mathematics We demonstrate the correctness of the deciphering algorithm using an identity due to Euler and Fermat for any integer (message) M which is relatively prime to n , M Ω ( n ) = 1 (mod n ) Here Ω ( n ) is the Euler totient function For prime numbers p , Ω ( p ) = p- 1 In our case, we have by elementary properties of the totient function Ω ( n ) = Ω ( p ) . Ω ( q ) = ( p - 1) . ( q - 1) = n - ( p + q ) + 1 : Since d is relatively prime to Ω ( n ), e . d = 1 (mod Ω ( n )) Now D ( E ( M )) = ( E ( M )) d = ( M e ) d (mod n ) = M ed (mod n ) E ( D ( M )) = ( D ( M )) e = ( M d ) e (mod n ) = M ed (mod n ) and M ed = M k Ω ( n )+1 (mod n ) (for some integer k ) :

Slide 16:

we see that for all M such that p does not divide M M p - 1 = 1 (mod p ) and since ( p- 1) divides Ω ( n ) M k Ω ( n )+1 = M (mod p ) : Arguing similarly for q yields M k Ω ( n )+1 = M (mod q ) : Together these last two equations imply that for all M , M ed = M k Ω ( n )+1 = M (mod n ) : Therefore E and D are inverse permutations.

Slide 17:

Digital signatures Digital signing In order to sign a message the sender does the following: Produces a hash value of the message Uses his/her private key (n, d) to compute the signature S = M d mod n Sends the signature S to the recipient

Slide 18:

Signature verification The recipient does the following in order to verify the message: Uses the senders public key (n, e) to compute the hash value V = S e mod n Extracts the hash value from the message If both hash values are identical then the signature is valid

Slide 19:

Factoring n Factoring n would enable an enemy cryptanalyst to “break" our method. The factors of n enable him to compute (n) and thus d. Fortunately, factoring a number seems to be much more diffcult than determining whether it is prime or composite. The fastest factoring algorithm known to the authors is due to Richard Schroeppel (unpublished); it can factor n in approximately exp√ln (n) . ln ( ln (n)) = n √ln ln (n)/ ln (n) = ( ln (n )) √ ln (n)/ ln ( ln (n)) steps (here ln denotes the natural logarithm function).

Slide 20:

Table 1 Digits Number of operations Time 50 1.4 *10 10 3.9 hours 75 9.0 *10 12 104 days 100 2.3 *10 15 74 years 200 1.2 *10 23 3.8 *10 9 years 300 1.5 *10 29 4.9 *10 15 years 500 1.3 *10 39 4.2 * 10 25 years

Slide 21:

What are the advantages and disadvantages of public-key cryptography compared with secret-key cryptography? The primary advantage of public-key cryptography is increased security and convenience Another major advantage of public-key systems is that they can provide digital signatures that cannot be repudiated. A disadvantage of using public-key cryptography for encryption is speed. Public-key cryptography may be vulnerable to impersonation, even if users' private keys are not available.

Slide 22:

References R. Rivest , A. Shamir, L. Adleman . A Method for Obtaining Digital Signatures and Public-Key Cryptosystems . Communications of the ACM, Vol. 21 (2), pp.120-126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme. Wikipedia- RSA algorithm RSA Laboratories - 2_1_3 What are the advantages and disadvantages of public-key cryptography compared with secret-key cryptography.htm Using the RSA Algorithm for Encryption and Digital Signatures:Can You Encrypt, Decrypt, Sign and Verify without Infringing the RSA Patent? Patrick J. Flinn and James M. Jordan III [*] (c) 1997 Alston & Bird LLP July 9, 1997

Slide 23:

QUESTIONS?