### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Cryptography CS 55500

Purdue

GPA 3.68

### View Full Document

## 55

## 0

## Popular in Course

## Popular in ComputerScienence

This 25 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 55500 at Purdue University taught by Staff in Fall. Since its upload, it has received 55 views. For similar materials see /class/208087/cs-55500-purdue-university in ComputerScienence at Purdue University.

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

Cryptography CS 5 5 5 Lecture 12 Department of Computer Sciences Purdue University Cristina NitaRotaru Fall 2003Lecture 12 1 Lecture Outline Public cryptography RSA Factorization 1351 Cristina NitaRotaru D Fall 2003Lecture 12 Recommended Reading From Stinson Chapter 5 Cristina NitaRotaru D Fall 2003Lecture 12 Project Proposal Due next Tuesday in class or by email crisn if you can not come to the class about 2 pages Exceptional case you can also submit your Project proposal the Tuesday after the midterm if you are still looking for a project An updated list of projects send to the list last night Outline of the proposal suggestions Problem definition what do you want to solve Plan of action how do you approach the problem Evaluation methodology how will you decide if you succeeded or not Cristina NitaRotaru l1 Fall 2003Lecture 12 Midterm Material includes today s lecture There will be 5 problems similar with the ones in homework Closed books closed notes No number theory problems Some of the questions might ask you to make connections You don t need to remember schemes DES HASH There will be 5 problems 3 similar with the ones in homework and 2 that will test your understanding on the material Cristina NitaRotaru l1 Fall 2003Lecture 12 Midterm Difference between perfect secrecy Shannon s definition and how ciphers and hash are evaluated with respect to security The general mechanisms of iterative hash func ons Difference between stream ciphers and block ciphers Current considered secure sizes for the protocols discussd so far DES properties Cristina NitaRotaru l1 Fall 2003Lecture 12 Secure Communication Decryption Adversary K Symmetric encryption requires the parties the share a common secret key How to get the key in the first place Cristina NitaRotaruD Fall 2003Lecture 12 7 Public Key Cryptography Each party has a PAIR P S of keys P is the public key and S is the secret key Knowing the publickey and the cipher it is still computationally infeasible to compute the private key an NPclass problem The publickey may be distributed to anyone wishing to communicate securely with its owner DecSEncP M Cristina NitaRotaru D Fall 2003Lecture 12 Trapdoor Functions Definition A function f 01 9 01 is a trapdoor function iff Fx is a oneway function such that given some extra information it becomes feasible to find for any y in mgf and x in X st y fx Public key cryptography relies on trapdoor functions Cristina NitaRotaru D Fall 2003Lecture 12 9 Trapdoor Functions Factoring integers fpq n pq 0 Easy pq 0 Hard factoring pq into p and q Rootextraction fpqey ye mod pq 0 Easy ye mod pq 0 Hard given pq e and ye mod pq compute a y such that y 6 y6 mod pq Discrete log problem fgpx 9quot mod p Easy gX mod p Hard determine x from p g and 9X mod p Cristina NitaRotaru l1 Fall 2003Lecture 12 10 RSA Algorithm 0 Invented in 1978 by Ron Rivest Adi Shamir and Leonard Adleman Security relies on the difficulty of factoring large composite numbers Published as R L Rivest A Shamir L Adleman quotOn Digital Signatures and Public Key Cryptosystemsquot Communications of the ACM vol 21 no 2 pp120126 Feb 1978 Cristina NitaRotaru l1 Fall 2003Lecture 12 11 RSA Description Key generation Select 2 large prime numbersof about the same size p and q Compute n pq and I q1p1 Select a random integer e 1 lt e lt cIgtn st gcde cIgtn 1 Compute d 1lt dlt I st ed a 1 mod cIgtn Public key e n Secret key d Note pm is Euler s Totient function How do you know that exists ed such that ed a 1 mod 13n Cristina NitaRotaru l1 Fall 2003Lecture 12 12 RSA Description cont Encryption For the message M O lt M lt n use public key e n compute C Me mod n Decryption For a message C use private key d Compute Cd mod n Me mod nd mod n M Cristina NitaRotaruij Fall 2003Lecture 12 13 RSA Example p11q7n77cDn60 d13e37 ed481 edmod601 LetM15 ThenCEMemodn 051537 mod 7771 MECdmodn M57113mod 77 15 Cristina NitaRotaru D Fall 2003Lecture 12 14 Why Does RSA Work 0 IT S MAGIC Cristina NitaRotaru D Fall 2003Lecture 12 Why Does RSA Work Want to show that Med mod n M n pq ed a 1 mod cDn so ed kcDn 1 for some integer k Two cases gcdM p 1 Since p prime then we have Mir1 5 1 mod p M01kCI1 E 1 mod p M MP1kCI1 E M mod p Med 5 M mod p gcdm p p Medmod pMmodp0soMedEMmodp Similar show that Med 5 M mod q Since p and q are distinct primes we obtain Med 5 M mod pq Cristina NitaRotaru D Fall 2003Lecture 12 16 RSA Implementation Select p and q prime numbers In general select numbers then test for primality Many implementations use the RabinMiller test probabilistic test Cristina NitaRotaru D Fall 2003Lecture 12 RSA Implementation Significant improvement in decryption speed for RSA can be obtained by using the Chinese Remainder theorem to work modulo p and q respectively Theorem Let n1 n2 nk be integers st gcdni nj 1 wherei j Then the system x E a1 mod n1 x E a2 mod 112 x E ak mod nk There exists an integer x solving the system of simultaneous congruences and all solutions x are congruent modulo n n1 n2 nk Cristina NitaRotaru l1 Fall 2003Lecture 12 18 RSA Implementation CRT is used in RSA by creating two equations for decryption The goal is to compute M from M COI mod n M1 MmodpCdmodp M2MmodqCdmodq Fermat theorem on the exponents M1 Cd mod ID1 mod p M2 Cd mod 11 mod q then the pair of equations M M1 mod p M M2 mod q has a unique solution M M M1q391 mod pq M2p391 Cristina NitaRotaru l1 Fall 2003Lecture 12 19 RSA Implementation E o e is usually chosen to be 3 or 216 1 65537 Speed up the encryption the algorithm is called square andmultiply computed exponen a on The smallest the number of 1 bits the better Cristina NitaRotaru D Fall 2003Lecture 12 20 RSA Implementation N P Q RSA it s usually described as the number of bits for n Current recommendation is 1024 bits for n P and q must have the same bit length so for 1024 bits RSA p and q must be about 512 bits Pq should not be small otherwise p a sqrtn Some believe that p and q should be strong primes p1 has a large prime r p1 has a large prime r1 has a large prime Cristina NitaRotaru l1 Fall 2003Leoture 12 21 RSA and Factoring One possible attack against RSA is to factor n Factor n find p and q Compute I Compute d Breaking RSA is equivalent to factoring n Cristina NitaRotaru l1 Fall 2003Leoture 12 22 Factoring in Practice Three methods Quadratic sieve Elliptic curve Number field sieve RSA chalenges httpwwwrsasecuritycomrsalabschallengesfactoringnu mbershtml RSA155 512 bits was factored Cristina NitaRotaru l1 Fall 2003Lecture 12 23 Summary RSA security relies on the difficulty of factoring big composite numbers CRT used to speed up decryption e with small number of 1 s the speed up exponentiation Cristina NitaRotaru l1 Fall 2003Lecture 12 24 Next More about attacks on RSA Semantic security of RSA Rabin Cryptosystem Stinson Chapter 5 Cristina NitaRotaru D Fall 2003Lecture 12 25

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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