### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction To Cryptography CS 35500

Purdue

GPA 3.68

### View Full Document

## 45

## 0

## Popular in Course

## Popular in ComputerScienence

This 62 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 35500 at Purdue University taught by Cristina Nita-Rotaru in Fall. Since its upload, it has received 45 views. For similar materials see /class/208078/cs-35500-purdue-university in ComputerScienence at Purdue University.

## Reviews for Introduction To Cryptography

### 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: 09/19/15

CS355 Cryptography Lecture 15 Fermat and Euler s Theorems Groups CS355 Lecture 15Fall 2007 1 MIDTERM INFO 430520pm Thu Oct 3 and 5 2007 during class Material for MIDTERM WILL include lectures this week Additional office hours This week MTuWF 530 630 or by appointment C8355 Lecture 15Fal 2007 The Euler Phi Function Definition Given an integer n In is the number of all numbers a such that O lt a lt n and a is relatively prime to n ie gcda n1 Theorem If gcdmn 1 Imn Im ltIgtn CS355 Lecture 15Fal 2007 The Euler Phi Function Theorem Formula for In Let p be prime e m n be positive integers 1 100 p1 2 C13009 Pe Ioe391 3 If n 19161 pzeZupk 6quot then 1311 n1 i1 i p1 p2 pk CS355 Lecture 15Fall 2007 Fermat s Little Theorem Fermat s Little Theorem lfp is a prime number and a is a natural number that is not a multiple of p then al 1 a 1 mod p Proofidea gcda p 1 then the set i a mod p Olt i lt p is a permutation of the set 1 p1 othenvise we have 0ltnltmltp st ma mod p na mod p and thus p ma na gt p mn where 0ltmn lt p a x 2a x xp1a p1 atquot1 a p1 mod p Since gcdp1 p 1 we obtain atquot1 a 1 mod p CS355 Lecture 15Fal 2007 Euler s Theorem Euler s Theorem Given integer n gt 1 such that gcda n 1 then am a 1 mod n Corollary Given integer n gt 1 such that gcda n 1 then aqpm 1 mod n is a multiplicative inverse of a mod n Corollary Given integer n gt 1 x y and a positive integers with gcda n 1 Ifx a y mod cIgtn then aX a ay mod n CS355 Lecture 15Fal 2007 Consequence of Euler s Theorem Principle of Modular Exponentiation Given a n x y with n 2 1 and gcdan1 ifx a y mod qn then ax a ay mod n Proof idea aX ak n y ay 3 lnk by applying Euler s theorem we obtain aX a ay mod p CS355 Lecture 15Fal 2007 Groups Definition A group G is a set G on which a binary operation is defined which satisfies the following axioms Closure For all a b E G a b E G Associative For all a b c E G a bc a b 0 Identity El e EG st for all a E G a e a e a Inverse For all a E G El a391 E G s t a a391 a391 ae Example Z is a group Zn 0 1 n 1 Zn addition modulo IS a group Zn NOT a group WHY CS355 Lecture 15Fal 2007 Groups cont Definition A group G is called an abelian group if operation is a commutative operation Commutative For all a b E G a b b a Example R is an abelian group Definition A group G is cyclic if El g EG EG h g Example Cyclic groups 22 Zs CS355 Lecture 15Fal 2007 Subgroups Definition Given a set G and S a subset of G then S is a subgroup of the group G if S is a group Definition Proper subgroup subgroup which is not identical to G Nontrivial subgroup any subgroup of G which contains an element other than e Example Z is a subgroup of R CS355 Lecture 15Fall 2007 10 Order of a Group and Element Definition The order of a group G ordG is defined as the number of elements in the group Definition A group G is finite if G ordG is finite Definition The order of an element 9 of a finite group G is the smallest power of n such that g e where e is the identity element CS355 Lecture 15Fal 2007 Ring Definition A ring R satisfies the following axioms 1 R is an abelian group Identity is 0 2 is associative for all a b CE G a bc a b c 3 31EG1 0stforallaE G a1a 1 a 4 is distributive over abcab ac and bcabaca Example 2 0 1 n 1 Zn addition modulo Definition A ring R is commutative if abba CS355 Lecture 15Fall 2007 12 Field Definition A field F is a commutative ring where all elements in F but 0 have multiplicative inverses Example Zp gtl is a eld Where p is prime CS355 Lecture 15Fal 2007 CS355 08355 Cryptography Lecture 17 18 19 Public Key CryptographyRSA Attacks against RSA Lecture 17Spn39ng 2007 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 Trapdoor Oneway Functions Definition A function f O1 a 01 is a trapdoor oneway function iff fx is a oneway function however given some extra information it becomes feasible to compute f391 given y nd x st y fx CS355 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 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 17 Spring 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 Let M 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 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 Meda 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 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 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 17 Spring 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 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 n IOCI C13m p1q1 pq Io q 1 n p np 1 iolt1gtn nio p2 n p pz nplt1gtnp pn0 pzn n1pn0 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 27 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 CS355 08355 Cryptography Lecture 3 amp 4 Shift cipher substitution cipher Vigenere cipher Lecture 3 and 4 Fall 2007 Shift Cipher A substitution cipher The Key Space 1 25 Encryption given a key K each letter in the plaintext P is replaced with the K th letter following corresponding number shift right Decryption given K shift left History K 3 Caesar39s cipher CS355 Lecture 3 and 4 Fall 2007 Shift Cipher An Example CS355 ABCDEFGHIJKL MNO PQR S TUVWXYZ 0 12345678910111213141516171819202122 232425 P CRYPTOGRAPHYISFUN K 11 C NCJAVZRCLASJTDQFY Ce 2 211mod2613e N R171711m0d26 2 C N9 13 1311 mod 26249 Y Lecture 3 and 4 Fall 2007 Shift Cipher Cryptanalysis Can an attacker find K YES exhaustive search key space is small lt 26 possible keys Once K is found very easy to decrypt CS355 Lecture 3 and 4 Fall 2007 General Monoalphabetical Substitution Cipher The key space all permutations dz A B C Z Encryption given a key as each letter X in the plaintext P is replaced with 713X Decryption given a key as each letter Y in the cipherext P is replaced with n1Y Example ABCDEFGHIJKLMNOPQRSTUVWXYZ l39FBADCZHWYGOQXSVTRNMSKJIPFEU BECAUSE a AZDBJSZ CS355 Lecture 3 and 4 Fall 2007 Strength of the General Substitution Cipher Exhaustive search is infeasible key space size is 26 z 41026 Dominates the art of secret writing throughout the first millennium AD Thought to be unbreakable by many backthen CS355 Lecture 3 and 4 Fall 2007 Cryptanalysis of Substitution Ciphers Frequency Analysis Basic ideas Each language has certain features frequency of letters or of groups of two or more letters Substitution ciphers preserve the language features Substitution ciphers are vulnerable to frequency analysis attacks CS355 Lecture 3 and 4 Fall 2007 Frequency of Letters in English abcdefghijklmnopqrstuvwxyz CS355 Lecture 3 and 4 Fall 2007 8 Other Frequency Features of English Vowels which constitute 40 of plaintext are often separated by consonants Letter A is often found in the beginning of a word or second from last Letter is often third from the end of a word Letter Q is followed only by U And more CS355 Lecture 3 and 4 Fall 2007 Substitution Ciphers Cryptanalysis The number of different The cipher text is examined for CS355 ciphertext characters or combinations are counted to determine the frequency ofusage patterns repeated series and common combinations Replace ciphertext characters with possible plaintext equivalents using known language characteristics Lecture 3 and 4 Fall 2007 Frequency Analysis History Discovered by the Arabs earliest known description of frequency analysis is in a book by the ninthcentury scientist aIKindi Rediscovered or introduced from the Arabs in the Europe during the Renaissance Frequency analysis made substitution cipher insecure CS355 Lecture 3 and 4 Fall 2007 11 Improve the Security of Substitution Cipher Using nulls eg using numbers from 1 to 99 as the ciphertext alphabet some numbers representing nothing are inserted randomly Deliberately misspell words eg Thys haz thi ifekkt off diztaughting thi baans off frikwenseas Homophonic substitution cipher each letter is replaced by a variety of substitutes These make frequency analysis more difficult but not impossible CS355 Lecture 3 and 4 Fall 2007 12

### 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

#### "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!"

#### "I made $350 in just two days after posting my first study guide."

#### "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."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.