Popular in Course
Popular in ComputerScienence
This 46 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 41 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
New Directions in Cryptography CS 303 Alg Number Theory amp Cryptography Jeremy Johnson Witfield Diffie and Martin E Hellman New Directions in Cryptography IEEE Transactions on Information Theory Vol IT22 No 6 Nov 1976 Classical Cryptography I Basic problem Secure communication over an insecure channel I Solution private key encryption I m gt 5km c gt kc m I Shannon provided a rigorous theory of perfect secrecy based on information theory I Adversary has unlimited computational resources but key must be as long as message Other Cryptographic Problems I Authentication I User Authentication verify that an individual is who heshe claims I Message Authentication Assure recipient that the message comes from authorized recipient and that the message I Message Integrity Assure that the message has not been modified I Threat of compromise of the receiver s authentication data I Threat of dispute Cryptoanalytic Attacks I Ciphertext only attack I Cryptanalyst possesses only ciphertext I Known plaintext attack I Cryptanalyst possesses substantial quantity of corresponding plaintext and ciphertext I Chosen plaintext attack I Cryptanalyst can submit an unlimited number of plaintext messages of his own choosing and examine the resulting ciphertext One Time Pad I Pad b1 bn 6 01 chosen randomly I m m1 mn I 5Padm c m e Pad I Padc c e Pad m e Pad e Pad m I Vmc Prpad3Padm c 12n I No information gained from seeing c I However 5Padm e 5Padm m e m Modern Cryptography I Adversary s resources are computationally bounded I Probabilistic polynomial time algorithm I Impossibility of breaking the encryption system gt lnfeasibility of breaking I Rely on gap between efficient algorithms for encryption and computational infeasibility of decryption by adversary 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 6 Implementation of PK I RSA Integer Factorization I El Gamal Discrete Logarithm I Goldwasser Micali Quadratic Redisuosity x I N pq x a nonresidue such that 1 I m 39 39 mt E I c 01 ct ci yixmi mod N yi random quadratic residue 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 OneWay Authentication I Oneway functions I Computationally easy to apply computationally hard to invert I login problem capable ofjudging authenticity of passwords without actually knowing them I Enter password PW and compute fPVV and compare with stored value of fPVV do not store PW I Requires additional encryption I True oneway authentication using digital signature I Oneway message authentication I Mm1m2mN mie01 I Generate 2N random bits x1X1x2X2xXN I Send fx1fX1fx2fX2fxNfXN for authentication I Late when M is to be sent send xi or Xi depending on whether mi 0 or 1 Cryptographic Protocol I A communication protocol with security assurances such as confidentiality message integrity anonymity I Entity authentication secure internet communication TLSSSLhttpsSSH key exchange digital signatures digital cash electronic voting I Want provany secure protocols I Key idea I Reduce problem to proving x e L NP without revealing any additional knowledge Coin Tossing Protocol I Want to flip a coin over the telephone I Fair and verifiable I Not subject to cheating I Blum protocol I B selects N P0 P E 3 mod 4 Q E 3 mod 4 I A selects x1xt and send x12xt2 to B I B guesses b1bt and sends to A I A sends x1xt to B and B checks xin bi Discussion I Cryptographic protocols are based on the secrecy of some private information and should preserve this secrecy I The privacy gives the advantage over adversaries I Want to prove that the secret is not given away during the protocol which might convey information derived from the secret Zero Knowledge Proof 1 Completeness ifthe statement is true the honest verifier that is one following the protocol properly will be convinced of this fact by an honest prover 2 Soundness if the statement is false no cheating prover can convince the honest verifier that it is true except with some small probability 3 Zeroknowledge if the statement is true no cheating verifier learns anything other than this fact This is formalized by showing that every cheating verifier has some simulator that given only the statement to be proven and no access to the prover can produce a transcript that quotlooks likequot an interaction between the honest prover and the cheating verifier Where s Waldo Open Sesame JeanJacques Quisquater Louis C Guillou Thomas A Berson How to Explain ZeroKnowledge Protocols to Your Children Advances in Cryptology CRYPTO 3989 Proceedings v435 p628631 1990 Example from GMR I Quadratic NonResiduosity l L x e Zm x is a quadratic nonresidue I Verifier generates r1rn random quadratic residues Flips n random coins b1bn bi 6 01 fb0 sends tt to rovert 2 1 n p xr bfl l Prover tries to determine bi Secure Passwords I Every users stores a statement of a theorem in a publicly readable directory I Upon login the user engages in a zero knowledge proof of the correctness of the theorem I lfthe proof is convincing access is granted I Guarantees that an adversary who overhears the proof can not learn enough to gain access Zero Knowledge in Practice I Trusted Platform Module Secure cryptoprocessor AMD HewlettPackard IBM lnfineon Intel Microsoft Sun Microsystems I Since this left unresolved privacy concerns version 12 of the TPM specification introduced quotDirect anonymous attestationquot a protocol based on the idea of a zeroknowledge pro of which allows a TPM user to receive a certification in such a way that the Privacy CA would not be able to link requests to a single user or platform while still being able to identify rogue TPMs Note Titl 3 415260839 7 An r o c C f VUlt0 m g L x X Af l vl DPAX 7 39 3 m K rm g by Ccv vamxv r l k Amrn N SSS law Jqsgyvxt M V V P 39I p 39 quotJ J In Vx Q N lijwl gt gt D wug 7v NJ pixn 7 v13 SL ki fryC VfHJ J n ncfajd rycf v1 mSCr XZ wm 97F gtm 7194 ltS 5 1 rm A14 L W K x VIM va ngqi y r MAL a A A 4 T Lq j gt 1 5J311 T2 EOOB 39 1 309 USA IX 1 K T rang bAY IWQJD 01 f w W 1 2 WWW V m wgw 4 U V P gt H mArgL HrHuNV Cm zfvcvrwcf V3 oi C 2 he d rFNH y Zv 4 49 u fa yn 43 Z awEC W75 W xviima c N C 93wva A N V Nn 1 L NW0 H 60AJ PL 7 DOCLgt3X e C ltxsee A HI n A g V7quot a 7 1 a 7 2 2amp7 PL 7 PKfgtquot V U 0y L 4 quot J PL a fh ak JI J pf ng a 0 mr A v 3 7 L I 07 42N 1463113 67C x P v harkL f N m X m m 3 I 0 gCEn fowKaw f U D J fay C lif 4 34 142 4 SK 73h Mnx soc esmlncfi mqYSS g Q 4w 0 u 5 4 r mu Hart 5 we 251 99 09 9 g L 05 MUWAIWLLV ZCEVQL gtamp 1me MU MC Ra VZFF A n cvv m p4 mo U w ww u H L Jr JE 7 fu u 4W 1 m4 foalEr A Cvx sr 9 36 4L H NW k 34me 94 J J L Y vtu 96th MLY W WM u 1MvUI mxwam C gnuUM Srl y S3 Paw Pris KY 31095 A l M l M 2 J Max RUB 3919 L 5 U M PA I PA 3 i 1 MLV KL C o u b 39 CC K Mhf j w H 35 TWltQLSE H Hui9 g 1m fr 7 Ex 2er 5c3L 2 w Va 6 bag 7 if K7elt gt L 0ch iiv 00d 7Cltltth l u P f in C K Sc g y IT r K 49 l P Lq I 76 535 F P T J it A K 0 QVL WAPnk MEL L 653 659 V g In 8r knit Dry W 7 k ijn 05w AU 2 I V T J J JVIVL Q C F Algorithmic Number Theory and Cryptography cs 303 Modular Arithmetic Jeremy R Johnson Introduction Objective To become familiar with modular arithmetic and some key algorithmic constructions that are important for computer algebra algorithms ModularArithmetic Modular inverses and the extended Euclidean algorithm Fermat s theorem Euler s Identity Chinese Remainder Theorem References Rivest Shamir Adelman Modular Arithmetic Zn Definition a a b mod n ltgt n b a Alternatively a qn b Properties equivalence relation a a a mod n Reflexive a E b mod n gt b a a mod n Symmetric a E b mod n and b a c mod n gt a E c mod n Transitive Definition An equivalence class mod n axanmodnaqnqu Modular Arithmetic Zn It is possible to perform arithmetic with equivalence classes mod n a b ab a b ab In order for this to make sense you must get the same answer equivalence class independent of the choice of a and b In other words if you replace a and b by numbers equivalent to a or b mod n you end of with the sumproduct being in the same equivalence class a1 a a2 mod n and b1 5 b2 mod n 2 a1 b1 5 a2 b2mod n a1 b1 5 a2 b2 mod n aQ1nbQZnabQ1QZn a Cl1quot b C12quot a b bQ1 aQZ C11 C12quot Representation of Zn The equivalence classes a mod n are typically represented by the representatives a Positive Representation Choose the smallest positive integer in the class a then the representation is 01n 1 Symmetric Representation Choose the integer with the smallest absolute value in the class a The representation is Ln12J Ln2J When n is even choose the positive representative with absolute value nl2 EG 26 21o123 25 21o12 Modular Inverses Definition x is the inverse of a mod n if ax 51 mod n The equation ax E 1 mod n has a solution iff gcdan 1 By the Extended Euclidean Algorithm there exist x and y such that ax ny gcdan When gcdan 1 we get ax ny 1 Taking this equation mod n we see that ax a 1 mod n By taking the equation mod n we mean applying the mod n homomorphism m Z Zm which maps the integer a to the equivalence class a This mapping preserves sums and products E mab ltlgtma mb ltIgtmab ltIgtma mb Fermat s Theorem Theorem If a 939 0 e Zp then a 391 a 1 mod p More generally if a e Zp then aP a a mod p Proof Assume that a at 0 e Zp Then a 2a p1a p1 ap1 Also since ai a aj mod p z i aj mod p the numbers a 2a p1a are distinct elements of Zp Therefore they are equal to 12p1 and their product is equal to p1 mod p This implies that p1 aP391Ep1 mod p gt aP391E1 mod p Euler phi function Definition phin a o lt a lt n and gcdm n 1 Properties ltpp p1 for prime p qgtpquote p1pquote1 P 1 ltIgt m ltpn for gcdmn 1 ltPP0l P101 Examples p15 p3 p5 24 8 12478111314 p9 3 13A2 1 23 6 124578 Euler s Identity The number of elements in Zn that have multiplicative inverses is equal to phin Theorem Let Zn be the elements of Zn with inverses called units lfa e Zn then aq lquot E 1 mod n Proof The same proof presented for Fermat s theorem can be used to prove this theorem Chinese Remainder Theorem Theorem If gcdmn 1 then given a and b there exist an integer solution to the system x E a mod m and x b mod n Proof Consider the map x gt x mod m x mod n This map is a 11 map from Zmn to Zm x Zn since if x and y map to the same pair then x a y mod m and x a y mod n Since gcdmn 1 this implies that x a y mod mn Since there are mn elements in both Zmn and Zm x Zn the map is also onto This means that for every pair ab we can find the desired x Alternative Interpretation of CRT Let Zm x Zn denote the set of pairs ab where a e Zm and b e Zn We can perform arithmetic on Zm x Zn by performing componentwise modular arithmetic asb csd abJCd abcgd acbd Theorem Zmn z Zm x Zn E There is a 11 mapping from Zmn onto Zm x Zn that preserves arithmetic ac mod m bd mod n a mod m b mod nc mod m d mod n ac mod m bd mod n a mod m b mod nc mod m d mod n The CRT implies that the map is onto E for every pair ab there is an integer x such that x mod m x mod n ab 11 Constructive Chinese Remainder Theorem Theorem If gcdmn 1 then there exist em and en orthogonal idempotents em a 1 mod m em a 0 mod n en a 0 mod m en a 1 mod n It follows that aem b en a a mod m and E b mod n Proof Since gcdmn 1 by the Extended Euclidean Algorithm there exist x and y with mx ny 1 Set em ny and en mx
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'