### Create a StudySoup account

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

Already have a StudySoup account? Login here

# AlgorithmicNumberTheoryandCryptography CS303

Drexel

GPA 3.88

### View Full Document

## 55

## 0

## Popular in Course

## Popular in ComputerScienence

This 12 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS303 at Drexel University taught by JeremyJohnson in Fall. Since its upload, it has received 55 views. For similar materials see /class/212430/cs303-drexel-university in ComputerScienence at Drexel University.

## Reviews for AlgorithmicNumberTheoryandCryptography

### 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/23/15

EIGamaI Public Key Cryptography CS 303 Alg Number Theory amp Cryptography Jeremy Johnson Taher EIGamaI quotA PublicKey Cryptosystem and a Signature Scheme Based on Discrete Logarithmsquot IEEE Transactions on Information Theory v IT31 n 4 1985 pp469 472 or CRYPTO 84 pp10 18 SpringerVerlag Outline I Primitive Element Theorem I Diffie Hellman Key Distribution I EIGamaI Encryption I EIGamaI Digital Signatures 12102008 Goldwasser Public Key Cryptography Let M be a message and let C be the encrypted message ciphertext A public key cryptosystem has a separate method E for encrypting and D decrypting I DEM M I Both E and D are easy to compute I Publicly revealing E does not make it easy to determine D I EDM M needed for signatures The collection of E s are made publicly available but the D s remain secret Called a oneway trapdoor function hard to invert but easy if you have the secret information 2 Order I Definition Let b eZn The order of b is the smallest positive integer satisfying be 2 1 mod n I Theorem 91 If b has order e modulo n and if is a positive integer such that b1 a 1 mod n then ej Proof j qgtlter O s r lt e bj E 1 E becl bIr E bIr mod n This implies that r 0 since e is the smallest power of b equivalent to 1 mod n I Corollary 92 Let b eZn ordbn Primitive Element Theorem I Zp ltocgt ie 0rd0c p1 I Example I 27 lt3gt 313 322 336 344 355 361 213 lt2gt 212 224 238 243 256 2612 2711 289 295 2010 2117 2121 I Note ordoc p1 gt 1 oc a2 06 distinct Discrete Logarithms I Discrete log problem I Given Zp lt0cgt I ogOLy x if y 00 I Example Z13lt2gt 212 224 238 243 256 2612 2711 289 295 2010 2117 2121 Log25 9 Properties of Primitive Elements I Theorem 94 If b has order e modulo n then ordbi egcdei I Theorem 97 Let p be a prime and d a divisor of p1 then the number of positive integers less than p with order d is ltgtd I Corollary The number of primitive elements mod p is equal to ltgtp1 gt 1 Some Lemmas l Lemma 96 Let Px be a polynomial of degree t and let p be a prime If p does not divide the coefficient of xt in Px then Px 2 0 mod p has at most t solutions mod p Proof By induction on the degree of Pxt Px1 O gt Px P1xgtltx X1 and the degree of P1x t1 l Lemma 98 The sum of ltgtd over the divisors of n n I Example 12 ltlgt1 ltlgt2 ltlgt3 ltlgt4 ltlgt6 12112224 12 Proof of Theorem 97 l Theorem 97 Let p be a prime and d a divisor of p1 then the number of positive integers less than p with order d is ltgtd Proof Ifthere is an element a of order d then by Theorem 94 a gcdid1 is also of order d By Lemma 96 1 a a2a l391 are the roots of Pxxd1 and there ltgtd elements of order d Since every elements is of order dp1 and p1 2der ltgtd there must be an element of order d for every dp1 and hence exactly ltgtd of them Public Key Distribution I The goal is for two users to securely exchange a key over an insecure channel The key is then used in a normal cryptosystem I DiffieHellman Key Exchange I Y ocx mod q q prime or primitive all elements are powers of oc X log06 Y mod q discrete log Yi ocXi mod q for each user K ocxm mod q shared key Kij YiXj mod q YJXi mod q EIGamaI Encryption I Zp ltdgt m e ZIo message I B encrypts a message to A A x random h 00 public key p och I B y random k 00 shared key K hy 0ch I EAm c1c2 c1 k c2mK mod p I DAc1c2 c21K mod p K c1X 0ch I Security depends on Computational DiffieHellman CDH assumption given or ocxocy it is hard to compute 0ch Do not use same k twice EIGamaI Digital Signature I Zp lt0cgt m e ZIo message I A signs message m I A h 00 public key p 0ch secret key x I A k random with gcdkp11 I r ock mod p I s m xr1k mod p1 m sk xr mod p1 I Signature rs I Verify ocmrshr

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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