CS 758: Cryptography/Network Security

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