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
Report this Material
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
Are you sure you want to buy this material for
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'