2y ago

34 Views

2 Downloads

1.09 MB

437 Pages

Transcription

CS 758: Cryptography/Network SecurityDouglas R. StinsonDavid R. Cheriton School of Computer ScienceUniversity of WaterlooSpring 2016D.R. Stinson (University of Waterloo)CS 758Spring 20161 / 424

1Course Information2Goals of Cryptography3Mathematical Background4A Formal Model for Security5Identification6Key Management7Multicast Security8Additional TopicsD.R. Stinson (University of Waterloo)CS 758Spring 20162 / 424

Course InformationTable of Contents1Course InformationD.R. Stinson (University of Waterloo)CS 758Spring 20163 / 424

Course InformationCS 758: Cryptography / Network Securityoffered in the Winter term, 2015, by Doug Stinsonmy office: DC 3522my email address: dstinson@uwaterloo.camy web page:http://www.math.uwaterloo.ca/ dstinson/provides a link to the course web page:http://www.math.uwaterloo.ca/ dstinson/CS 758/S16/CS758.htmlD.R. Stinson (University of Waterloo)CS 758Spring 20164 / 424

Course InformationObjectives/Prerequisitesbasic cryptography concerns secure communication between twoparties, while in this course we are interested in cryptographicprotocols in multiuser/network contextprerequisites: a previous course in cryptography (e.g. C&O 487,Applied Cryptography) is helpful but not requiredmathematical background: basic complexity theory, elementarynumber theory, algebra (finite groups, finite fields, linear algebra),probability (random variables), combinatoricsThis is not a math course, but it has significant mathematicalcontent. If you are math-phobic, this course is not for you.D.R. Stinson (University of Waterloo)CS 758Spring 20165 / 424

Course InformationCourse RequirementsStudents’ grades will be based on some combination of assignmentsand a project.I encourage students to work in groups of two (or three) for theproject.The project will include a written component as well as a presentationin class.The project will involveIIpreparing a report on a recent research paper on a topic related to thecourse material, and/orimplementing and analyzing one or more protocols on a topic related tothe course material.D.R. Stinson (University of Waterloo)CS 758Spring 20166 / 424

Course InformationCourse OutlineReview of cryptographic primitives and their applications toinformation security, and notions of cryptographic security. Discussionof public-key encryption, secret-key encryption, messageauthentication, signature schemes, and hash functions.Techniques for entity authentication. Passwords, challenge-response,identification schemes (e.g., Fiat-Shamir, Guillou-Quisquater), generaltechniques for zero-knowledge proofs for NP-complete languages.D.R. Stinson (University of Waterloo)CS 758Spring 20167 / 424

Course InformationCourse Outline (cont.)Protocols for key establishment, transport, agreement andmaintenance. Online key distribution using a trusted server(Kerberos). Public-key techniques, including Diffie-Hellman keyagreement, man-in-the-middle attacks, STS and forward secrecy.Unconditionally secure key distribution, including the Blom schemeand combinatorial key distribution patterns.Cryptography in a multi-user setting. Secret sharing schemes(including Shamir threshold schemes and schemes for general accessstructures). Conference key distribution and broadcast encryption.Copyright protection techniques and tracing schemes.D.R. Stinson (University of Waterloo)CS 758Spring 20168 / 424

Course InformationIntroduction to Cryptography and SecurityIn the rest of this module, we discuss the following:goals of cryptographycryptographic tools (primitives)mathematical backgrounda formal model for securityD.R. Stinson (University of Waterloo)CS 758Spring 20169 / 424

Goals of CryptographyTable of Contents2Goals of CryptographyCryptographic ToolsD.R. Stinson (University of Waterloo)CS 758Spring 201610 / 424

Goals of CryptographyGoals of CryptographyconfidentialityConfidentiality (or secrecy) means that data cannot beunderstood by an unauthorized party.data integrityData integrity means that data cannot be modified by anunauthorized party.data origin authenticationData origin authentication is achieved when it can be verifiedthat data was transmitted by a particular source.entity authenticationEntity authentication (or identification) refers to theverification of the identity of a person, computer or otherdevice.D.R. Stinson (University of Waterloo)CS 758Spring 201611 / 424

Goals of CryptographyGoals of Cryptography (cont.)non-repudiationNon-repudiation occurs when it is impossible for someone todeny having transmitted a message that, in fact, they didtransmit.access controlAccess control refers to the restriction of electronic orphysical access to authorized parties.anonymityAnonymity refers to the anonymous transmission of data, sothat the origin cannot be determined.D.R. Stinson (University of Waterloo)CS 758Spring 201612 / 424

Goals of CryptographyCryptographic ToolsCryptographic Toolsencryption schemesEncryption schemes are used to achieve confidentiality.signature schemesSignature schemes are used to “sign” data. A signaturehelps to ensure data integrity and data origin authentication,and it can also provide non-repudiation.message authentication codesA message authentication code provides data integrity.cryptographic hash functionsA hash function shrinks a long string into a short,random-looking string. They are used to provideunpredictable redundancy in data. They are also used for keyderivation.D.R. Stinson (University of Waterloo)CS 758Spring 201613 / 424

Goals of CryptographyCryptographic ToolsCryptographic Tools (cont.)key agreement protocolsA key agreement protocol is used to establish a commonsecret key known to two or more specified parties. Usuallythis key is to be subsequently used for another cryptographicpurpose such as symmetric-key encryption or messageauthentication.identification schemesAn identification scheme provides entity authentication.pseudorandom number generatorsPseudorandom number generators expand a small, trulyrandom, seed into a long string of bits that cannot bedistinguished from random bits. Pseudorandom numbergenerators are used in many cryptographic contexts, forexample, in the generation of keys.D.R. Stinson (University of Waterloo)CS 758Spring 201614 / 424

Goals of CryptographyCryptographic ToolsTools and their Usage of KeysA short summary of cryptographic tools and their usage of keys is providedin the following table. A check mark X indicates that the given algorithmand key combination is feasible.schemeencryption schemesignature schemeMAChash functionkey agreement schemeidentification schemeD.R. Stinson (University of Waterloo)keyspublic/private? secret?XXXXXno key?XXXCS 758XXSpring 201615 / 424

Goals of CryptographyCryptographic ToolsSecure Socket LayerclientserverI’m Alice I’m Bob, Inc. PK, sig (PK) CA verify PKgenerate MSy ePK (MS) MS dPK (y)K1 , K2 h(MS)K1 , K2 h(MS)D.R. Stinson (University of Waterloo)CS 758Spring 201616 / 424

Goals of CryptographyCryptographic ToolsCryptosystemA cryptosystem is a five-tuple (P, C, K, E, D), where the followingconditions are satisfied:1P is a finite set of possible plaintexts2C is a finite set of possible ciphertexts3K, the keyspace, is a finite set of possible keys4For each K K, there is an encryption rule eK E and acorresponding decryption rule dK D. Each eK : P C anddK : C P are functions such that dK (eK (x)) x for everyplaintext element x P.D.R. Stinson (University of Waterloo)CS 758Spring 201617 / 424

Goals of CryptographyCryptographic ToolsPublic-key vs Secret-key Cryptosystemsin a secret-key cryptosystem, K is known to both Alice and Bob:AliceBobKKy eK (x)y x dK (y)in a public-key cryptosystem, K is known only to Bob and eK ispublic:AliceBobekKy eK (x)D.R. Stinson (University of Waterloo)y CS 758x dK (y)Spring 201618 / 424

Goals of CryptographyCryptographic ToolsA Substitution-Permutation u33S133S2S33S4v3w34Ku44S144S2S34S4v45KyD.R. Stinson (University of Waterloo)CS 758Spring 201619 / 424

Goals of CryptographyCryptographic ToolsThe Advanced Encryption Standard (AES)AES has a block length of 128 bits, and it supports key lengths of 128,192 and 256 bits. The number of rounds, Nr, depends on the key length:Nr 10 if the key length is 128 bits; Nr 12 if the key length is 192 bits;and Nr 14 if the key length is 256 bits.1Given a plaintext x, initialize State to be x and performAddRoundKey , which x-ors the RoundKey with State.2For each of the first Nr 1 rounds, perform a substitution operationcalled SubBytes on State using an S-box; perform a permutationShiftRows on State; perform an operation MixColumns on State; andperform AddRoundKey .3Perform SubBytes; perform ShiftRows; and perform AddRoundKey .4Define the ciphertext y to be State.D.R. Stinson (University of Waterloo)CS 758Spring 201620 / 424

Goals of CryptographyCryptographic ToolsAES StatesAll operations in AES are byte-oriented operations, and all variables usedare considered to be formed from an appropriate number of bytes. Theplaintext x consists of 16 bytes, denoted x0 , . . . , x15 . State is representedas a four by four array of bytes, initialized as follows:s0,0s1,0s2,0s3,0s0,1s1,1s2,1s3,1D.R. Stinson (University of Waterloo)s0,2s1,2s2,2s3,2s0,3x0s1,3x 1s2,3x2s3,3x3CS 758x4 x8x5 x9x6 x10x7 x11x12x13x14x15Spring 201621 / 424

Goals of CryptographyCryptographic ToolsThe Finite Field F256The operation SubBytes performs a substitution on each byte of Stateindependently, which involves operations in the finite fieldF28 Z2 [x]/(x8 x4 x3 x 1).Let BinaryToField convert a byte to a field element; and let FieldToBinaryperform the inverse conversion. This conversion is done in the obviousway: the field element7Xai xii 0corresponds to the bytea7 a6 a5 a4 a3 a2 a1 a0 ,where ai Z2 for 0 i 7.D.R. Stinson (University of Waterloo)CS 758Spring 201622 / 424

Goals of CryptographyCryptographic ToolsSubBytesAlgorithm: SubBytes(a7 a6 a5 a4 a3 a2 a1 a0 )external FieldInv , BinaryToField, FieldToBinaryz BinaryToField(a7 a6 a5 a4 a3 a2 a1 a0 )if z 6 0then z FieldInv (z)(a7 a6 a5 a4 a3 a2 a1 a0 ) FieldToBinary (z)(c7 c6 c5 c4 c3 c2 c1 c0 ) (01100011)for i 0 to 7do bi (ai ai 4 ai 5 ai 6 ai 7 ci ) mod 2return (b7 b6 b5 b4 b3 b2 b1 b0 )D.R. Stinson (University of Waterloo)CS 758Spring 201623 / 424

Goals of CryptographyCryptographic ToolsShiftRowsThe operation ShiftRows acts on State as shown in the following diagram:s0,0s1,0s2,0s3,0s0,1s1,1s2,1s3,1D.R. Stinson (University of Waterloo)s0,2s1,2s2,2s3,2s0,3s0,0s1,3s 1,1s2,3s2,2s3,3s3,3CS 2Spring 201624 / 424

Goals of CryptographyCryptographic ToolsMixColumnsAlgorithm: MixColumn(c)external FieldMult, BinaryToField, FieldToBinaryfor i 0 to 3do ti BinaryToField(si,c )u0 FieldMult(x, t0 ) FieldMult(x 1, t1 ) t2 t3u1 FieldMult(x, t1 ) FieldMult(x 1, t2 ) t3 t0u2 FieldMult(x, t2 ) FieldMult(x 1, t3 ) t0 t1u3 FieldMult(x, t3 ) FieldMult(x 1, t0 ) t1 t2for i 0 to 3do si,c FieldToBinary (ui )D.R. Stinson (University of Waterloo)CS 758Spring 201625 / 424

Goals of CryptographyCryptographic ToolsModes of OperationECB (electronic code book) mode corresponds to the naive use of ablock cipher: given a sequence x1 x2 · · · of plaintext blocks (eachconsisting of 128 bits, in the case of the AES), each xi is encryptedwith the same key K, producing a string of ciphertext blocks,y1 y2 · · · .In CBC (cipher block chaining) mode, each ciphertext block yi isx-ored with the next plaintext block, xi 1 , before being encryptedwith the key K. More formally, we start with an initializationvector, denoted by IV, and define y0 IV. Then we constructy1 , y2 , . . . , using the ruleyi eK (yi 1 xi ),i 1.D.R. Stinson (University of Waterloo)CS 758Spring 201626 / 424

Goals of CryptographyCryptographic ToolsCBC ModexIV y 01x2 eKeKencrypty1y2y1y2decryptIV y 0D.R. Stinson (University of Waterloo)dKdK x1x2CS 758Spring 201627 / 424

Goals of CryptographyCryptographic ToolsThe RSA Public-key CryptosystemLet n pq, where p and q are large primes. Let P C Zn , and defineK {(n, p, q, a, b) : ab 1 (mod φ(n))}.For K (n, p, q, a, b), defineeK (x) xb mod nanddK (y) y a mod n(x, y Zn ). The values n and b comprise the public key, and the valuesp, q and a form the private key.D.R. Stinson (University of Waterloo)CS 758Spring 201628 / 424

Goals of CryptographyCryptographic ToolsA Toy Examplesuppose Bob chooses primes p 101 and q 113then n 11413 and φ(n) 100 112 11200suppose Bob chooses public encryption exponent b 3533then his private decryption exponent is a b 1 mod 11200 6597suppose Alice wants to encrypt the plaintext x 9726she will computey 97263533 mod 11413 5761and send y to Bobwhen Bob receives the ciphertext y 5761, he computesx 57616597 mod 11413 9726.D.R. Stinson (University of Waterloo)CS 758Spring 201629 / 424

Goals of CryptographyCryptographic ToolsThe Rabin CryptosystemLet n pq, where p and q are primes. Let P C Zn , and defineK {(n, p, q)}.For K (n, p, q), defineeK (x) x2 mod nanddK (y) y mod n.The value n is the public key, while p and q are the private key.Note: there are four square roots of y modulo n.D.R. Stinson (University of Waterloo)CS 758Spring 201630 / 424

Goals of CryptographyCryptographic ToolsA Toy Examplesuppose Bob chooses primes p 7 and q 11then the encryption function iseK (x) x2 mod 77and the decryption function isdK (y) y mod 77suppose Alice encrypts the plaintext x 32 to send to Bobthe ciphertext is y 322 mod 77 23the four square roots of 23 modulo 77 are 10, 32 mod 77the four possible plaintexts are x 10, 32, 45 and 67D.R. Stinson (University of Waterloo)CS 758Spring 201631 / 424

Goals of CryptographyCryptographic ToolsSignature SchemesA signature scheme is a five-tuple (P, A, K, S, V), where the followingconditions are satisfied:1P is a finite set of possible messages2A is a finite set of possible signatures3K, the keyspace, is a finite set of possible keys4For each K K, there is a signing algorithm sig K S and acorresponding verification algorithm ver K V. Each sig K : P Aand ver K : P A {true, false} are functions such that thefollowing equation is satisfied for every message x P and for everysignature y A: true if y sig (x)ver (x, y) false if y 6 sig (x).D.R. Stinson (University of Waterloo)CS 758Spring 201632 / 424

Goals of CryptographyCryptographic ToolsSignatures with Hash FunctionsAliceBobKwithout hash functionverKy sigK (x)x, y verK (x, y) true?K, hwith hash functionverK , hz h(x)y sigK (z)x, y z h(x)verK (z, y) true?h : {0, 1} Z P is a public hash functionD.R. Stinson (University of Waterloo)CS 758Spring 201633 / 424

Goals of CryptographyCryptographic ToolsRSA Signature SchemeLet n pq, where p and q are primes. Let P A Zn , and defineK {(n, p, q, a, b) : n pq, p, q prime, ab 1 (mod φ(n))}.The values n and b are the public key, and the values p, q, a are the privatekey.For K (n, p, q, a, b), definesig K (x) xa mod nandver K (x, y) true x y b (mod n)(x, y Zn ).D.R. Stinson (University of Waterloo)CS 758Spring 201634 / 424

Goals of CryptographyCryptographic ToolsPrimitive Elements in Zpsuppose p is prime; then there exists a primitive element α Zp{αi mod p : 0 i p 2} Zp \{0}the powers of α (modulo p) yield all the non-zero elements in Zpαp 1 1 (mod p), and α has order p 1if q (p 1), then β α(p 1)/q mod p has order qD.R. Stinson (University of Waterloo)CS 758Spring 201635 / 424

Goals of CryptographyCryptographic ToolsPrimitive Elements in Z132 is a primitive element modulo 13:20 mod 13 122 mod 13 424 mod 13 326 mod 13 1228 mod 13 9210 mod 13 1021 mod 13 223 mod 13 825 mod 13 627 mod 13 1129 mod 13 5211 mod 13 7the primitive elements modulo 13 are 2, 6, 7 and 11D.R. Stinson (University of Waterloo)CS 758Spring 201636 / 424

Goals of CryptographyCryptographic ToolsDigital Signature StandardLet p be a 1024-bit prime and let q be a 160-bit prime that divides p 1.Let α Zp be an element of order q. Let P {0, 1} , A Zq Zq ,and defineK {(p, q, α, a, β) : β αa (mod p)},where 0 a q 1. The values p, q, α and β are the public key, and a isthe private key.For K (p, q, α, a, β), and for a (secret) random number k,1 k q 1, definesig K (x, k) (γ, δ),whereγ (αk mod p) mod qδ (SHA-1 (x) aγ)kD.R. Stinson (University of Waterloo)CS 758and 1mod q.Spring 201637 / 424

Goals of CryptographyCryptographic ToolsDigital Signature Standard (cont.)For x {0, 1} and γ, δ Zq , verification is done by performing thefollowing computations:e1 SHA-1 (x) δ 1 mod qe2 γ δ 1 mod qver K (x, (γ, δ)) true (αe1 β e2 mod p) mod q γ.D.R. Stinson (University of Waterloo)CS 758Spring 201638 / 424

Goals of CryptographyCryptographic ToolsA Toy ExampleSuppose we take q 101 and p 78q 1 7879. 3 is a primitiveelement in Z7879 , so α 378 mod 7879 170 has order q. Supposea 75; then β αa mod 7879 4567. Suppose Alice wants to sign themessage digest SHA-1 (x) 22, and she chooses the random valuek 50. Then she computesk 1 mod 101 50 1 mod 101 99,γ (17050 mod 7879) mod 101 2518 mod 101 94,andδ (22 75 94)99 mod 101 97.D.R. Stinson (University of Waterloo)CS 758Spring 201639 / 424

Goals of CryptographyCryptographic ToolsA Toy Example (cont.)The signature (94, 97) on the message digest 22 is verified by the followingcomputations:δ 1 97 1 mod 101 25e1 22 25 mod 101 45e2 94 25 mod 101 27(17045 456727 mod 7879) mod 101 2518 mod 101 94.Hence, the signature is valid.D.R. Stinson (University of Waterloo)CS 758Spring 201640 / 424

Goals of CryptographyCryptographic ToolsHash Functions and FamiliesA hash family is a four-tuple (X , Y, K, H), where the following conditionsare satisfied:1X is a set of possible messages2Y is a finite set of possible message digests or authentication tags3K, the keyspace, is a finite set of possible keys4For each K K, there is a hash function hK H. EachhK : X Y.X can be a finite or infinite set; Y is always a finite set. If Y is finite, thewe assume that X 2 Y .An unkeyed hash function is a single hash function h : X Y, i.e., ahash family in which there is only one possible key.D.R. Stinson (University of Waterloo)CS 758Spring 201641 / 424

Goals of CryptographyCryptographic ToolsSignature Schemes vs MACsAliceBobK, hsignature schemeverK , hz h(x)y sigK (z)x, y z h(x)verK (z, y) true?KMACKy hK (x)x, y y hK (x)?D.R. Stinson (University of Waterloo)CS 758Spring 201642 / 424

Goals of CryptographyCryptographic ToolsIterated Hash FunctionsSuppose compress : {0, 1}m t {0, 1}m is a hash function (where t 1).We construct an iterated hash functionh: [{0, 1}i {0, 1} i m t 1preprocessingGiven an input string x, where x m t 1, construct astring y, using a public algorithm, such that y 0 (mod t).Typically, y x k pad(x), where pad is a padding functionsuch that the mapping x 7 y is injective. Denotey y1 k y2 k · · · k yr ,where yi t for 1 i r.D.R. Stinson (University of Waterloo)CS 758Spring 201643 / 424

Goals of CryptographyCryptographic ToolsIterated Hash Functions (cont.)processingLet IV be a public initial value which is a bitstring of lengthm. Then compute the following:z0 IVz1 compress(z0 k y1 )z2 compress(z1 k y2 ). . . . .zr compress(zr 1 k yr ).optional output transformationLet g : {0, 1}m {0, 1} be a public function. Defineh(x) g(zr ).D.R. Stinson (University of Waterloo)CS 758Spring 201644 / 424

Goals of CryptographyCryptographic ToolsThe processing step in an iterated hash mpress.compressz r-1compresszrFigure: An Iterated Hash FunctionD.R. Stinson (University of Waterloo)CS 758Spring 201645 / 424

Goals of CryptographyCryptographic ToolsSecure Hash AlgorithmSHA-1 is an iterated hash function with a 160-bit message digest. SHA-1is built from word-oriented operations on bitstrings, where a word consistsof 32 bits (or eight hexadecimal digits). The operations used in SHA-1 areas follows:X YX YX Y XX YROTLs (X)bitwise “and” of X and Ybitwise “or” of X and Ybitwise “xor” of X and Ybitwise complement of Xinteger addition modulo 232circular left shift of X by s positions (0 s 31)D.R. Stinson (University of Waterloo)CS 758Spring 201646 / 424

Goals of CryptographyCryptographic ToolsSecure Hash Algorithm (cont.)Algorithm: SHA-1-pad(x)d (447 x ) mod 512 the binary representation of x , where 64y x k 1 k 0d k The resulting string y has length divisible by 512. Then we write y as aconcatenation of n blocks, each having 512 bits:y M 1 k M2 k · · · k Mn .Each Mi will be written as the concatenation of 16 words:Mi W0 k W1 k · · · k W15 .D.R. Stinson (University of Waterloo)CS 758Spring 201647 / 424

Goals of CryptographyCryptographic ToolsSecure Hash Algorithm (cont.)Define the functions f 0 , . . . , f 79 as follows: (B C) (( B) D) B C Df i (B, C, D) (B C) (B D) (C D) B C Difififif0 t 1920 t 3940 t 5960 t 79.Each function f i takes three words B, C and D as input, and producesone word as output.D.R. Stinson (University of Waterloo)CS 758Spring 201648 / 424

Goals of CryptographyCryptographic ToolsAlgorithm: SHA-1 (x)initialize H0 , H1 , H2 , H3 , H4for i 1 to n for t 16 to 79 do Wt ROTL1 (Wt 3 Wt 8 Wt 14 Wt 16 ) A H0 ; B H1 ; C H2 ; D H3 ; E H4 for t 0 to 79do temp ROTL5 (A) f t (B, C, D) E Wt Kt do E D; D C; C ROTL30 (B) B A; A temp H H0 A; H1 H1 B; H2 H2 C 0H3 H3 D; H4 H4 Ereturn (H0 k H1 k H2 k H3 k H4 )D.R. Stinson (University of Waterloo)CS 758Spring 201649 / 424

Goals of CryptographyCryptographic ToolsCBC MACsSuppose that (P, C, K, E, D) is a cryptosystem, where P C {0, 1}t .Let IV be the bitstring consisting of t zeroes, and let K K be a secretkey. Finally, let x x1 k · · · k xn be a bitstring of length tn (for somepositive integer n), where each xi is a bitstring of length t. We computeCBC-MAC K (x) as follows.Algorithm: CBC-MAC (x, K)IV 00 · · · 0 (or some other vector)y0 IVfor i 1 to ndo yi eK (yi 1 xi )return (yn )D.R. Stinson (University of Waterloo)CS 758Spring 201650 / 424

Goals of CryptographyCryptographic ToolsPublic- vs Secret-key CryptographyspeedSecure secret-key cryptographic protocols are much fasterthan correpsonding secure public-key cryptographic protocols(e.g., 100 to 1000 times faster). Here we are comparingpublic- vs secret-key cryptosystems; and signature schemesvs MACs.algebraic descriptionPublic-key cryptographic protocols are usually based onsimple-to-describe mathematical functions, and their securitydepends on certain computational problems that areinfeasible, or believed to be infeasible.Secret-key cryptosystems tend to be based on performing asequence of very simple operations (e.g., substitutions andpermutations) in such a way that the system has a verycomplex algebraic description.D.R. Stinson (University of Waterloo)CS 758Spring 201651 / 424

Goals of CryptographyCryptographic ToolsPublic- vs Secret-key Cryptography (cont.)key lengthsKey lengths of secure public-key cryptosystems aresometimes significantly longer than those of secure secretkey cryptosystems. For example, RSA keys are typicallytaken to be at least 1024 bits in length, while an AES key is128 bits long. It should be noted, however, that key lengthsof elliptic curve cryptosystems are much shorter than mostother public-key cryptosystems, e.g., 160 bits is a popularkey length.D.R. Stinson (University of Waterloo)CS 758Spring 201652 / 424

Goals of CryptographyCryptographic ToolsPublic- vs Secret-key Cryptography (cont.)utilityPublic-key cryptosystems do not require that a secret key beknown to two parties before the system is used, of course.Public keys can be listed in a directory or posted on a webpage, for example. However, such methods ofcommunicating public keys must also be accompanied byappropriate mechanisms to allow the public keys to beauthenticated. This is done by using certificates, containingsigned public keys, possibly in the context of a securepublic-key infrastructure. On the other hand, theauthenticity of secret keys is, in general, guaranteed by theprotocol used to generate or distribute them, or assumed tohave been done securely at an earlier time.D.R. Stinson (University of Waterloo)CS 758Spring 201653 / 424

Mathematical BackgroundTable of Contents3Mathematical BackgroundModular arithmeticGroupsQuadratic ResiduesSome AlgorithmsExample: Rabin DecryptionComputational ProblemsD.R. Stinson (University of Waterloo)CS 758Spring 201654 / 424

Mathematical BackgroundModular arithmeticModular arithmeticSuppose a and b are integers, and m is a positive integer. Then we writea b (mod m) if m divides b a. The phrase a b (mod m) is called acongruence, and it is read as “a is congruent to b modulo m.” Theinteger m is called the modulus.For example, we have 11 25 (mod 6) because 6 (11 ( 25)).We will use the notation a mod m (without parentheses) to denote thenon-negative remainder when a is divided by m. Thus, a b (mod m) ifand only if a mod m b mod m. If we replace a by a mod m, we saythat a is reduced modulo m.For example, to compute 101 mod 7, we write 101 7 14 3. Since0 3 6, it follows that 101 mod 7 3. As another example, supposewe want to compute ( 101) mod 7. In this case, we have 101 7 ( 15) 4. Since 0 4 6, it follows that( 101) mod 7 4.D.R. Stinson (University of Waterloo)CS 758Spring 201655 / 424

Mathematical BackgroundModular arithmeticModular arithmetic (cont.)Zn is is used to denote the set {0, . . . , n 1}, which is usually equippedwith the two operations and . Addition and multiplication in Zn workexactly like real addition and multiplication, except that the results arereduced modulo n.For example, suppose we want to compute 11 13 in Z16 . As integers, wehave 11 13 143. Then we reduce 143 modulo 16 as described above:143 8 16 15, so 143 mod 16 15, and hence 11 13 15 in Z16 .D.R. Stinson (University of Waterloo)CS 758Spring 201656 / 424

Mathematical BackgroundGroupsFinite Abelian GroupsA finite abelian group is a pair G (X, ?), where X is a finite set and ?is a binary operation defined on X, that satisfies the following properties:1the operation ? is closed, i.e., a ? b X for any a, b X2the operation ? is commutative, i.e., a ? b b ? a for any a, b X3the operation ? is associative, i.e., (a ? b) ? c a ? (b ? c) for anya, b, c X4There is an element id X called the identity, such thata ? id id ? a a for any a X5for every a X, there exists an element b X called the inverse ofa, such that a ? b b ? a id for any a XThe order of the group G (X, ?), denoted ord(G), is equal to X .D.R. Stinson (University of Waterloo)CS 758Spring 201657 / 424

Mathematical BackgroundGroupsExamples of Finite Abelian GroupsLet n 2 be an integer. Then (Zn , ) is an abelian group of order n,where denotes addition modulo n. The identity element is 0, and theinverse of a, usually denoted a, is ( a) mod n.Let p 2 be a prime. Define Zp Zp \{0}. Then (Zp , ·) is an abeliangroup of order p 1, where · denotes multiplication modulo p. Theidentity element is 1, and the inverse of a, usually denoted a 1 , iscomputed using the Extended Euclidean algorithm.Let n 2 be an integer. DefineZn Zn \{d Zn : gcd(d, n) 1}.Then (Zn , ·) is an abelian group where · denotes multiplication modulo n.D.R. Stinson (University of Waterloo)CS 758Spring 201658 / 424

Mathematical BackgroundGroupsExamples of Finite Abelian Groups (cont.)The identity element is 1, and the inverse of a, usually denoted a 1 , iscomputed using the Extended Euclidean algorithm.The order of (Zn , ·) is denoted φ(n) (note that φ(n) is just the numberof positive integers less than n that are relatively prime to n). φ(n) can becomputed from the following formula: suppose that n has prime powerfactorization Yn pi eii 1(the pi ’s are distinct primes and ei 1 for 1 i ). Thenφ(n) Ypi ei 1 (pi 1) i 1D.R. Stinson (University of Waterloo) Y pi ei pi ei 1 .i 1CS 758Spring 201659 / 424

Mathematical BackgroundGroupsOrder of Group ElementsFor a finite group (X, ?), define the order of an element a X (denotedord(a)) to be the smallest positive integer m such thata ? a ?{z· · · ? a} id.mIf the group operation is multiplication, then a ? a ?{z· · · ? a}mis written as an exponentiation, am . If the group operation is addition,then the same expression is written as a multiplication, ma.The identity element is defined to have order 1. It can be shown that theorder of any a X is a divisor of the order of the group, i.e.,ord(a) ord(G).D.R. Stinson (University of Waterloo)CS 758Spring 201660 / 424

Mathematical BackgroundGroupsOrder of Group Elements (cont.)It is also possible to show, for any a X, that the order of b ai (where,for concreteness, we assume that the group operation is writtenmultiplicatively) isord(a)ord(b) .gcd(ord(a), i)For example, if ord(a) 100 and b a35 , thenord(b) D.R. Stinson (University of Waterloo)100100 20.gcd(100, 35)5CS 758Spring 201661 / 424

Mathematical BackgroundGroupsCyclic GroupsA finite abelian group (X, ?) is a cyclic group if there exists an ele

basic cryptography concerns secure communication between two parties, while in this course we are interested in cryptographic protocols in multiuser/network context prerequisites: a previous course in cryptography (e.g. C&O 487, Applied Cryptography) is helpful but not required mat

Related Documents: