### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 240 Class Note for CS 35500 with Professor Nita-Rotaru at Purdue

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 35 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 17 views.

## Similar to Course at Purdue

## Reviews for 240 Class Note for CS 35500 with Professor Nita-Rotaru at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

08355 Cryptography Lecture 17 18 19 Public Key CryptographyRSA Attacks against RSA CS355 Lecture 17Spn39ng 2007 1 Midterm 700 900 PM Wed Feb 28 2007 ME 261 Monday review for Midterm bring your questions to class CS355 Public Key Cryptography Overview Proposed in Diffie and Hellman 1976 New Directions in Cryptography publickey encryption schemes public key distribution systems DiffieHellman key agreement protocol digital signature Publickey encryption was proposed in 1970 by James Ellis in a classi ed paper made public in 1997 by the British Governmental Communications Headquarters DiffieHellman key agreement and concept of digital signature are still due to Diffie amp Hellman CS355 Lecture 17Spn39ng 2007 Public Key Encryption Publickey encryption CS355 each party has a PAIR K K4 of keys K is the public key and K391 is the private key such that DK391EKM M Knowing the publickey and the cipher it is computationally infeasible to compute the private key Publickey crypto systems are thus known to be asymmetric crypto systems The publickey K may be made publicly available eg in a publicly available directory Many can encrypt only one can decrypt Lecture 17Spn39ng 2007 PublicKey Encryption Needs Oneway Trapdoor Functions Given a publickey crypto system Alice has public key K EK must be a oneway function knowing y EKX it should be difficult to find x However EK must not be oneway from Alice s perspective The function EK must have a trapdoor such that knowledge of the trapdoor enables one to invert it 08355 Lecture 17Spn39ng 2007 RSA Algorithm Invented in 1978 by Ron Rivest Adi Shamir and Leonard Adleman Published as R L Rivest A Shamir L Adleman quotOn Digital Signatures and Public Key Cryptosysz emsquot Communications of the ACM vol 21 no 2 pp120 126 Feb 1978 Security relies on the difficulty of factoring large composite numbers Essentially the same algorithm was discovered in 1973 by Clifford Cocks who works for the British intelligence CS355 Lecture 17Spn39ng 2007 qu Let p and q be two large primes Denote their product npq Zn qu contains all integers in the range 1 pq1 that are relatively prime to both p and q The size of Zn is ltIgtpq p1q1npq1 i For every x E qu x0391q391 a 1 mod n CS355 Lecture 17Spn39ng 2007 Exponentiation in qu Motivation We want to use exponentiation for encryption Let e be an integer 1lteltp1q1 When is the function fxxe a onetoone function in qu If x6 is onetoone then it is a permutation in qu CS355 Lecture 17Spn39ng 2007 Exponentiation in qu Claim If e is relatively prime to p1q1 then fxxe is a onetoone function in qu Proof by constructing the inverse function of f As gcdep1q11 then there exists d and k st ed1kp1q1 Let yxe then ydxedx1k0391q391x mod pq ie gyyOI is the inverse of fxxe CS355 Lecture 17Spn39ng 2007 10 RSA Public Key Crypto System Key generation Select 2 large prime numbers of about the same size p and q Compute n pq and cIgtn q1p1 Select a random integer e 1 lt e lt cIgtn st gcde cIgtn 1 Compute d 1lt dlt cIgtn st ed a 1 mod cIgtn Public key e n Private key cl Note p and q must remain secret CS355 Lecture 17Spn39ng 2007 11 RSA Description cont Encryption Given a message M O lt M lt n M E Zn 0 use public key e n compute C Me mod n C E Zn 0 Decryption Given a ciphertext C use private key d Compute COI mod n Me mod nOI mod n MeOI mod n M 08355 Lecture 17Spn39ng 2007 12 RSA Example p11q7n77CIn60 d13e37 ed481 edmod60 1 LetM 15 Then C 2 Me mod n C a 1537 mod 77 71 M 501 mod n M 57113 mod 77 15 08355 Lecture 17Spn39ng 2007 13 Why does RSA work Need to show that MeOI mod n M n pq We have shown that when MEqu ie gcdM n 1 then Med M mod n What if MEqu O qu eg gcdM n p ed a 1 mod In so ed kcIgtn 1 for some integer k MeOI mod p M mod peOI mod p 0 so Med 5 M mod p MeOI mod q Mkqgt mod q M mod q M mod q so Med 5 M mod q As p and q are distinct primes it follows from the CRT that Med 5 M mod pq CS355 Lecture 17Spn39ng 2007 14 RSA Implementation n P Cl The security of RSA depends on how large n is which is often measured in the number of bits for n Current recommendation is 1024 bits for n p and q should have the same bit length so for 1024 bits RSA p and q should be about 512 bits pq should not be small CS355 Lecture 17Spn39ng 2007 15 RSA Implementation Select p and q prime numbers In general select numbers then test for primality Many implementations use the RabinMiller test probabilistic test CS355 Lecture 17Spn39ng 2007 16 RSA Implementation e e is usually chosen to be 3 or 216 1 65537 In order to speed up the encryption the smaller the number of 1 bits the better why CS355 Lecture 17Spn39ng 2007 17 Square and Multiply Algorithm for Exponen a on Computing xC mod n Example suppose that 053110101 X53X132XX322X22X X2X22X22X mod n Alg Squareandmultiply x n c ck1 ck2 c1 c0 z1 fori e k1 downto O z e 22 mod n ifci 1 thenzezx mod n return 2 CS355 Lecture 17Spn39ng 2007 18 RSA Implementation Decryption CRT is used in RSA by creating two equations for decryption The goal is to compute M from M Cd mod n Ml MmodpCdmodp M2MmodqCdmodq Fermat theorem on the exponents M1 5 Cd mod o l mod p M2 5 Cd m dq l mod q then the pair of equations M 5 M1 mod p M 5 M2 mod q has a unique solution M M a M1q391 mod pq M2p391 mod qp mod n CS355 Lecture 17Spn39ng 2007 19 Efficiency of computation modulo n Suppose that n is a kbit number and Os xy s n computing xy mod n takes time Ok computing xy mod n takes time Ok computing xy mod n takes time Ok2 computing x4 mod n takes time Ok3 computing xC mod n takes time OIog c k2 CS355 Lecture 17Spn39ng 2007 20 RSA on Long Messages RSA requires that the message M is at most n1 where n is the size of the modulus What about longer messages They are broken into blocks Smaller messages are padded CBC is used to prevent attacks I regarding the blocks C NOTE In practice RSA is used to encrypt symmetric keys 0 the message is not very long CS355 Lecture 17Spn39ng 2007 21 PohligHellman Exponentiation Cipher A symmetric key exponentiation cipher encryption key ep where p is a prime decryption key dp where eda1 mod p1 to encrypt M compute Me mod p to decrypt C compute COI mod p 08355 Lecture 17Spn39ng 2007 22 Attacks Against RSA CS355 Lecture 17Spn39ng 2007 23 MathBased Key Recovery Attacks Three possible approaches 1 Factor n pq 2 Determine lt1n 3 Find the private key d directly All the above are equivalent to factoring n CS355 Lecture 17Spn39ng 2007 24 Knowing ltIgtn Implies Factorization Knowing both n and ltIgtn one knows n0Ci cIgtr1 p1q1 pqIOq 1 n p np 1 iolt1gtn np pz n p pz nplt1gtnp pn0 pznqgtn1pn0 There are two solutions of p in the above equation Both p and q are solutions CS355 Lecture 17Spn39ng 2007 25 Factoring Large Numbers RSA640 bits Factored Nov 2 2005 RSA 200 663 bits is the largest RSA Challenge Number factored to date May 2005 Three most effective algorithms are quadratic sieve elliptic curve factoring algorithm number field sieve CS355 Lecture 17Spn39ng 2007 26 Fermat Factorization Compute n 1 n 22 n 32 till we find a square n x2 y2 80 n Xyxy p Xy and q xy Example n 295927 29592732 5442 80 n 54435443 Works well when p and q are close to each other CS355 Lecture 17Spn39ng 2007 Factoring Large Numbers One idea many factoring algorithms use Suppose one finds XZEyZ mod n such that X y mod n and X y mod n Then n Xyxy Neither Xy or Xy is divisible by n thus gcdxyn has a nontrivial factor of n CS355 Lecture 17Spn39ng 2007 28 Factoring when knowing e and cl Fact if npq then x251 mod n has four solutions that are ltn x251 mod n if and only if both x251 mod p and x251 mod q Two trivial solutions 1 and n1 1 is solution to x a 1 mod p and x a 1 mod q n1 is solution to x a 1 mod p and x a 1 mod q Two other solutions solution to x a 1 mod p and x a 1 mod q solution to x a 1 mod p and x a 1 mod q Eg n3 515 then x251 mod 15 has the following solutions 1 4 11 14 08355 Lecture 17Spn39ng 2007 29 Factoring when knowing e and cl Knowing a nontrivial solution to X251 mod n compute gcdx1n and gcdx1n Eg 4 and 11 are solution to x221 mod 15 gcd4115 5 gcd4115 3 gcd11115 3 gcd11115 5 CS355 Lecture 17Spn39ng 2007 30 Factoring when knowing e and d page 186 write ed 1 28 r r odd choose w at random such that 1ltwltn1 if w not relative prime to n then return gcdwn compute w W w4r unti find w2 tr a 1 mod n Fails when WV 1 mod n or w t is 1 mod n Input n2773e17d157 ed1266822 667 r667 Pick random w compute wr mod n w7 7667mod 2773 1 no good w8 8667mod 2773 471 and 47121 so 471 is a nontrivial square root of 1 mod 2773 compute gcd4711 277359 gcd4711 277347 277359 47 08355 Lecture 17Spn39ng 2007 31 Example Factoring n given d Input n2773 e17 d157 ed1266822 667 r667 Pick random w compute wr mod n w7 76671 no good w8 8667471 and 47121 so 471 is a nontrivial square root of 1 mod 2773 compute gcd4711 277359 gcd4711 277347 277359 47 08355 Lecture 17Spn39ng 2007 32 Decryption attacks on RSA RSA Problem Given a positive integer n that is a product of two distinct large primes p and q a positive integer e such that gcde p1q11 and an integer c find an integer m such that mesc mod n widely believed that the RSA problem is computationally equivalent to integer factorization however no proof is known The security of RSA encryption s scheme depends on the hardness of the RSA problem CS355 Lecture 17Spn39ng 2007 33 Summary of Key Recovery Mathbased Attacks on RSA Three possible approaches 1Factor n pq 2Determine lt1n 3Find the private key d directly All are equivalent finding out d implies factoring n if factoring is hard so is finding out CI 08355 Lecture 17Spn39ng 2007 34 Finding d Timing Attacks Timing Attacks on Implementations of DiffieHeIman RSA DSS and Other Systems 1996 Paul C Kocher By measuring the time required to perform decryption exponentiation with the private key as exponent an attacker can figure out the private key Possible countermeasures use constant exponentiation time add random delays blind values used in calculations CS355 Lecture 1 7 Spring 2007 35 Timing Attacks cont Is is possible in practice YES OpenSSL Security Advisory 17 March 2003 Timing based attacks on RSA keys Researchers have discovered a timing attack on RSA keys to which OpenSSL is generally vulnerable unless RSA blinding has been turned on RSA blinding the decryption time is no longer correlated to the value of the input ciphertext Instead of computing cOI mod n choose a secret random value r and compute recOI mod n A new value of r is chosen for each ciphertext CS355 Lecture 17Spn39ng 2007 36

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.