### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 709 Class Note for CSE 543 at PSU

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Department

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

## Similar to Course at Penn State

## Reviews for 709 Class Note for CSE 543 at PSU

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

A Method for Obtaining Digital Signatures and PublicKey Cryptosystems Part 2 Authors RL Rivest A Shamir and L Adleman Presented by BingRong Lin Scope 0 The focus is on quotEfficient Algorithmquot and quotSecurityquot of RSA o Ignore the proof of the referenced theorems but a Theorems are given b Welcome to discuss with me after the class Outline 0 Efficient algorithm c Find Large Prime Numbers Primality Test Encrypt amp Decrypt Determine d amp e 0 Security of the Method Factor n Compute Cigtn without a Compute d without a amp b Compute D in some other way Encrypt amp Decrypt o DMMOI mod n o ddkdk1d1 binary representation 0 MOI Ak2 gtlt AM2 gtlt gtlt A1 If dk1 AkM else Ak1 EX Y11Y1011Y2 x 1 2 x Y 2 x Y 0 Mol mod n Ak mod n2 x Ak1 mod n2 x gtlt A1 mod n Hint ab mod 0 a mod cb mod C Primality test 0 chab1 amp Jab ab12 If b is prime it is always TURE Oltaltb Euler39s criterion o p is an odd prime a is coprime to p if a is quadratic residue modulo p ie there exists a number k such that k 2 E a mod p then alPW2 E 1 mod 9 Else aP12 E 1 mod 2 Jacobi symbol Jab 0 0 if b divides a 0 1 if a is quadratic residue modulo b o 1 others Primality test cont 0 Jab 0 1 if a1 o Ja2b1bb3918 if a is even o J bmod a a1a391b3914 others o Hint quadratic reciprocity Determine d amp e 0 Choose d o Relatively prime to n o d should be chosen from a large enough set Compute eEd391 mod n 0 Above equation is identical to altned1 o Based on Euclid s algorithm x0 ln X1d 39 Xi1 E Xi1 mOd Xi Compute ai and bi such that Xi ai x X0 bi x X1 If Xk1 then ebk Example 0 X0 n 2668 X1 d 157 39 Xi1 E Xi1mOdXi 0 X2 2668 mod 157 156 o X3157 mod 156 1 o XiaigtltX0bigtltX1 x2 1562668 16 157x0 16X1 X31157 1156X11X2 X11X0 16X1 X017X1 o e 17 Security of the Method 0 No techniques exist to prove that an encryption scheme is secure 0 Factoring large number is a wellknow problem that has been worked on for 300 years a Show breaking the system is equivalent to factoring problem How to break o Input ne o Possible breaking approaches a Factor n o Wellknown problem hard b Compute n without a 0 Equivalent to factoring 0 Compute dd without aampb 0 Equivalent to factoring d Compute D in some other way 0 May equivalent to factoring Compute n without a o If it is possible then n can be easily factored ltlgtn IO1XQ1 n pq 1 pq2 Ioq2 4n 39 CI IOQ IOCI Compute dd without aampb o d o If it is possible then n can be easily factored ed1kn o 6 Reimann s hypothesis and tests for primality shows n can be factored by using any multiple of n o d find a key equivalent to d o If it is possible then n can be easily factored ddwmm 0 Finding one enables n to be factored Conclusions 0 The authors show the efficient algorithms of o encrypt amp decrypt o Primality test has been largely superseded by the Miller Rabin primaty test 0 Compute e o The security of the method is based on factoring problem

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

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