深入浅出密码学习题答案.pdf

Solutions to Homework Problems (Odd Numbered Problems) Understanding Cryptography A Textbook for Students and Practitioners by Christof Paar and Jan Pelzl 1 2Solutions to Homework Problems (Odd Numbered Problems) Problems of Chapter 1 1.1 1. Letter frequency analysis of the ciphertext: letter count freq %letter count freq % A50.77N172.63 B6810.53O71.08 C50.77P304.64 D233.56Q71.08 E50.77R8413.00 F10.15S172.63 G10.15T132.01 H233.56U243.72 I416.35V223.41 J487.43W477.28 K497.59X203.10 L81.24Y192.94 M629.60Z00.00 2. Because the practice of the basic movements of kata is the focus and mastery of self is the essence of Matsubayashi Ryu karate do, I shall try to elucidate the movements of the kata according to my interpretation based on forty years of study. It is not an easy task to explain each movement and its significance, and some must remain unexplained. To give a complete explanation, one would have to be qualified and inspired to such an extent that he could reach the state of enlightened mind capable of recognizing soundless sound and shapeless shape. I do not deem myself the final authority, but my experience with kata has left no doubt that the following is the proper application and interpretation. I offer my theories in the hope that the essence of Okinawan karate will remain intact. 3. Shoshin Nagamine, further reading: The Essence of Okinawan Karate-Do by Shoshin Nagamine, Tuttle Publishing, 1998. 1.3 One search engine costs $ 100 including overhead. Thus, 1 million dollars buy us 10,000 engines. 1. key tests per second: 5108104= 51012keys/sec On average, we have to check (2127keys: (2127keys)/(51012keys/sec) = 3.401025sec = 1.081018years That is about 108= 100,000,000 times longer than the age of the universe. Good luck. 2. Let i be the number of Moore iterations needed to bring the search time down to 24h: 1.081018years365/2i= 1day 2i= 1,081018365days/1day i = 68.42 We round this number up to 69 assuming the number of Moore iterations is discreet. Thus, we have to wait for: 1.569= 103.5 years Note that it is extremely unlikely that Moores Law will be valid for such a time period! Thus, a 128 bit key seems impossible to brute-force, even in the foreseeable future. 1.5 1. 1529 mod 13 23 mod 13 6 mod 13 2. 229 mod 13 23 mod 13 6 mod 13 3. 23 mod 13 23 mod 13 6 mod 13 4. 23 mod 13 23 mod 13 6 mod 13 Solutions to Homework Problems (Odd Numbered Problems)3 15, 2 and -11 (and 29 and 3 respectively) are representations of the same equivalence class modulo 13 and can be used “synonymously”. 1.7 1. Multiplication table for Z4 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 2. Addition table for Z5Multiplication table for Z5 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 3. Addition table for Z6Multiplication table for Z6 + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 4. Elements without a multiplicative inverse in Z4are 2 and 0 Elements without a multiplicative inverse in Z6are 2, 3, 4 and 0 For all nonzero elements of Z5exists because 5 is a prime. Hence, all nonzero elements smaller than 5 are relatively prime to 5. 1.9 1. x = 9 mod 13 2. x = 72= 49 10 mod 13 3. x = 310= 95 8129 329 81 3 mod 13 4. x = 7100= 4950 1050 (3)50= (310)5 35 32= 9 mod 13 5. by trial: 75 11 mod 13 1.11 1. FIRST THE SENTENCE AND THEN THE EVIDENCE SAID THE QUEEN 2. Charles Lutwidge Dodgson, better known by his pen name Lewis Carroll 1.13 a (x1x2)1(y1y2) mod m b y1ax1mod m The inverse of (x1x2) must exist modulo m, i.e., gcd(x1x2),m) = 1. 4Solutions to Homework Problems (Odd Numbered Problems) Problems of Chapter 2 2.1 1. yi= xi+Kimod 26 xi= yiKimod 26 The keystream is a sequence of random integers from Z26. 2. x1= y1K1= ”B”R”= 117= 16 10 mod 26 = ”K” etc Decrypted Text: ”KASPAR HAUSER” 3. He was knifed. 2.3 We need 128 pairs of plaintext and ciphertextbits (i.e., 16 byte) in order to determine the key. siis being computed by si= xi Ly i; i = 1,2, ,128. 2.5 1. Z?i? 1? 1? 1? 0? 1? 0? 0? 1? 0? 1? 1? 1? 0? 1? 0? 0? 0? 0? 1? 1? 1? 0? 1? 0? = Z?0? = Z?1? = Z?2? = Z?3? = Z?4? = Z?5? = Z?6? = Z?7? = Z? 0? Sequence 1: z? 0? = 0 0 1 1 1 0 1 0 0 1 1 1 0 1 .? 2. 0? 1? 0? 0? 1? 1? 1? 0? 1? 0? 1? 0? 0? 1? 1? 1? 1? 1? 0? 1? 0? 0? 1? 1? = Z?0? = Z?1? = Z?2? = Z?3? = Z?4? = Z?5? = Z?6? = Z?7? = Z?0? Sequence 2: z? 0? = 1 1 0 1 0 0 1 1 1 0 1 0 0 1 .? Solutions to Homework Problems (Odd Numbered Problems)5 3. The two sequences are shifted versions of one another. 2.7 The feedback polynomial from 2.3 is x8+x4+x3+x+1. 0 0111001 10011100 01001110 00100111 = Z = Z = Z = Z = Z 0 1 2 14 15 11111111 01111111 00111111 0011111 00001111 10000111 01000011 00100001 10010000 11001000 11100100 01110010 0 s7s6s5s4s3s2s1 CLK 0 s So, the resulting fi rst two output bytes are (1001000011111111)2= (90FF)16. 2.9 1. The attacker needs 512 consecutive plaintext/ciphertext bit pairs xi, yito launch a successful attack. 2. a. First, the attacker has to monitor the previously mentioned 512 bit pairs. b. The attacker calculates si= xi+yimod 2, i = 0,1,.,2m1 c. In order to calculate the (secret) feedback coeffi cients pi, Oscar generates 256 linearly dependent equationsusingtherelationshipbetweentheunknownkeybits pi andthekeystreamoutputdefi ned by the equation si+m m1 j=0 pjsi+jmod 2;si,pj 0,1;i = 0,1,2,.,255 with m = 256. d. After generating this linear equation system, it can be solved e.g. using Gaussian Elimination, revealing the 256 feedback coeffi cients. 3. The key of this system is represented by the 256 feedback coeffi cients. Since the initial contents of the LFSR are unalteredly shifted out of the LFSR and XORed with the fi rst 256 plaintext bits, it would be easy to calculate them. 2.11 xi Ly i= xi L(x i Lz i) = zi W 22 = 101102J 9 = 010012 P 15 = 0111125 31 = 111112 6Solutions to Homework Problems (Odd Numbered Problems) I 8 = 010002A 0 = 000002 xi= 101100111101000 yi= 010011111100000 zi= 111111000001000 1. Initialization Vector: (Z0= 1,1,1,1,1,1) 2. C0 C1 C2 C3 C4 C5 = 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 = 1 1 0 0 0 0 3. yi= J z | 01001 5 z | 11111 A z | 00000 0 z | 11010 E z | 00100 D z | 00011 J z | 01001 2 z | 11100 B z | 00001 zi= 111111000001000011000101001111010001110010010 xi= 10110 | z W 01111 | z P 01000 | z I 10110 | z W 01110 | z O 01100 | z M 00001 | z B 00000 | z A 10011 | z T 4. Wombats live in Tasmania. 5. Known-plaintext Attack. Problems of Chapter 3 3.1 1. s(x1)Ls(x2) = 1110 s(x1 Lx 2) = s(x2) = 00006= 1110 2. s(x1)Ls(x2) = 1001 s(x1 Lx 2) = s(x2) = 10006= 1001 3. s(x1)Ls(x2) = 1010 s(x1 Lx 2) = s(x2) = 11016= 1010 3.3 S1(0) = 14 = 1110 S2(0) = 15 = 1111 S3(0) = 10 = 1010 S4(0) = 7 = 0111 S5(0) = 2 = 0010 S6(0) = 12 = 1100 S7(0) = 4 = 0100 S8(0) = 13 = 1101 Solutions to Homework Problems (Odd Numbered Problems)7 P(S) = D8D8 DBBC (L1,R1) = 0000 0000 D8D8 DBBC (1) 3.5 IP(x) maps bit 57 to position 33, which is position 1 in R0. E-Expansion box maps bit position 1 to positions 2 and 48. Input to S-Boxes: S1: 0 1 0 0 0 0 S2= S3= = S7: 0 0 0 0 0 0 S8: 0 0 0 0 0 1 Two S-Boxes get a different input. P(S) = D058 5B9E (L1,R1) = 8000 0000 D058 5B9E 1. 2 S-Boxes, S1and S8 2. According to design criteria, a minimum of 2 bits/bit. 22 = 4bits 3. See (1). 4. 6 bits have changed: 3 from S1 2 from S8 1 in the left half 3.7 1. K1+i= K16ifor i = 0,1,.7. 2. Following (a), two equations are established: C1+i= C16i D1+i= D16ifr i = 0,1,.,7. These equations yield C0,j= 0 und D0,j= 0 or C0,j= 0 und D0,j= 1 or C0,j= 1 und D0,j= 0 oder C0,j= 1 und D0,j= 1fr j = 1,2,.,28. Hence the four weak keys after PC-1 are given by: Kw1= 0.0 0.0 Kw2= 0.0 1.1 Kw3= 1.1 0.0 Kw4= 1.1 1.1 3. P(randomly chose a weak key) = 22 256 = 254. 3.9 Worst-Case: 256keys. Average: 256/2 = 255keys. 3.11 1. AsingleDESenginecancompute100106DESencryptionspersecond.ACOPACOBANA machine can, thus, compute 4620100106= 4.81010DES encryptions per second. For an average of 8Solutions to Homework Problems (Odd Numbered Problems) 255encryptions for a successfull brute-force attack on DES, 255/(4.81010) 750600 seconds are required (which approximately is 8.7 days). 2. For a successfull average attack in one hour, 8.724 18 machines are required. 3. The machine performs a bruteforce attack. However, there might be more powerful analytical at- tacks which explore weaknesses of the cipher. Hence, the keysearch machine provides only a lower security threshold. 3.13 1. The state of PRESENT after the execution of one round is F000 0000 0000 000F. Below you can fi nd all intermediate values. Plaintext0000 0000 0000 0000 Round keyBBBB 5555 5555 EEEE State after KeyAdd BBBB 5555 5555 EEEE State after S-Layer 8888 0000 0000 1111 State after P-Layer F000 0000 0000 000F 2. The round key for the second round is 7FFF F777 6AAA AAAA. Below you can fi nd all interme- diate values. KeyBBBB 5555 5555 EEEE FFFF Key state after rotationDFFF F777 6AAA AAAA BDDD Key state after S-box7FFF F777 6AAA AAAA BDDD Key state after CounterAdd 7FFF F777 6AAA AAAA 3DDD Round key for Round 27FFF F777 6AAA AAAA Problems of Chapter 4 4.1 1. The successor of the DES, the AES, was chosen by the NIST by a public proceeding. The purpose of this public contest was to allow broadly evaluation of the candidates by as many research organi- sations and institutes as possible. This strongly contrasts to the development of DES, which was only performed by IBM and the NSA fi rstly keeping details (e.g. the S-boxes) in secret. DES was published and standardized in 1975. 2. 1/2/97: Call for algorithms, which could potentially lead to the AES. The selection process was governedbytheNIST.8/20/98:15algorithmswerenominatedascandidatesfortheselectionprocess. 9.8.1999: 5 algorithms reach the ”fi nals” (Mars, RC6, Rijndael, Serpent, Twofi sh) 2.10.2000: NIST elects Rijndael to AES. 3. Rijndael 4. Dr. Vincent Rijmen and Dr. Joam Daemen from Belgium 5. Rijndael supports blocksizes of 128, 192 and 256 bit, as well as key lengths of 128, 192 and 256 bit. In fact, only the version with 128 bit blocksize (and all three key lengths) is called AES. 4.3 Multiplication table for GF(23), P(x) = x3+x+1 01xx+1x2x2+1x2+xx2+x+1 000000000 101xx+1x2x2+1x2+xx2+x+1 x0 xx2x2+xx+11x2+x+1x2+1 x+10 x+1x2+xx2+1x2+x+1x21x x20 x2x+1x2+x+1x2+xxx2+11 x2+10 x2+11x2xx2+x+1x+1x2+x x2+x0 x2+xx2+x+11x2+1x+1xx2 x2+x+1 0 x2+x+1x2+1x1x2+xx2x+1 4.5 Multiplication in GF(24): Solutions to Homework Problems (Odd Numbered Problems)9 1. A(x)B(x) = (x2+1)(x3+x2+1) = x5+x4+x2+x3+x2+1 A(x)B(x) = x5+x4+x3+1 x +1 x4+x+1 x5+x4+x3+1 x5+x2+x x4+x3+x2+x +1 x4+x +1 x3+x2 C = x3+x2 A(x)B(x) mod P(x). 2. A(x)B(x) = (x2+1)(x+1)= x3+x+x2+1 C = x3+x2+x+1 A(x)B(x) mod P(x) The reduction polynomial is used to reduce C(x) in order to reduce the result to GF(24). Otherwise, a simple multiplication without reduction would yield a result of a higher degree (e.g., with x5) which would not belong to GF(24) any more. 4.7 1. By the Extended Euclidean algorithm: x4+x+1 = x3(x)+x+1 t2(x) =t0q1t1= q1= x3= x3 x= 1(x+1)+1t3(x) =t1q2t2= 11x3= 1x3= x3+1 x+1= x+1(1)+0 So, A1= x3+1. Check: x(x3+1) = x4+x (x+1)+x mod P(x) = 1 mod P(x). 2. By the Extended Euclidean algorithm: x4+x+1 = x2+x+1(x2+x)+1 t2=t0q1t1= q1= x2+x+1 x2+x= x2+x1+0 So, A1= x2+x+1. Check: (x2+x)(x2+x+1)= x4+2x3+2x2+x = x4+x (x+1)+x mod P(x) = 1 mod P(x). 4.9 ? B = ByteSub(A)= 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 ?The ShiftRows operation does not change anything since all bytes of B equal each other. ?The MixComumn operation is equal for every resultig byteCiand is described by (01+01+02+03)hex(16)hex. We have to remind, that all calculations have to be done in GF(28), so that (01+01+02+03)hex= (01)hexand hence, all resulting bytes of C remain (16)hex C = MixColumn(B) = 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 ? The fi rst round key equals the unmodifi ed AES key. So, the output of the fi rst is CK = 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF = E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 E9 4.11 10Solutions to Homework Problems (Odd Numbered Problems) 1. d = 01, b = 1(b7x7+.+b0) = b. d0= b0, d1= b1, .,d7= b7. 2. d = 02b= x(b7x7+.+b0) = b7x8+b6x7+.+b0 x x8 x4+x3+x+1 mod P(x). d = b6x7+b5x6+b4x5+b3+b7x4+b2+b7x3+b1x2+b0+b7x+b7 d7= b6d6= b5 d5= b4d4= b3+b7 d3= b2+b7d2= b1 d1= b0+b7d0= b7 3. d = 03b= (x+1)b= xb+b Using solutions from a) and b): d = (b6+b7)x7+(b5+b6)x6+(b4+b5)x5+(b3+b4+b7)x4+(b2+b3+b7)x3+(b1+b2)x2+ (b0+b1+b7)x+(b0+b7) d7= b6+b7d6= b5+b6 d5= b4+b5d4= b3+b4+b7 d3= b2+b3+b7d2= b1+b2 d1= b0+b1+b7d0= b0+b7 4.13 1. A = 01h, A(x) = 1 A1(x) = 1 = 01h A1 (x) is now the input to the affi ne transformation of Rijndael as described in Subsection 4.2.1 of the Rijndael Specifi cations: MA1+V where M andV are a fi xed matrix and vector, respectively. MA1+V = M 1 0 0 0 0 0 0 0 + 1 1 0 0 0 1 1 0 = 1 1 1 1 1 0 0 0 + 1 1 0 0 0 1 1 0 = 0 0 1 1 1 1 1 0 ByteSub(01h) = 7Ch 2. A = 12h, A(x) = x4+x Apply extended Euclidean algorithm: A1(x) = x7+x5+x3+x = AAh. MA1+V = M 0 1 0 1 0 1 0 1 + 1 1 0 0 0 1 1 0 = 0 1 0 1 0 1 0 1 + 1 1 0 0 0 1 1 0 = 1 0 0 1 0 0 1 1 Remark: It is (big) coincidence that MA1= A1 . This only holds for this specifi c value of A1. ByteSub(12h) =C9h 4.15 1. RC8 = x7= (10000000)2 2. RC9 = x8= x4+x3+x+1= (00011011)2 3. RC10 = x9= x8x = x5+x4+x2+x = (00110110)2 Solutions to Homework Problems (Odd Numbered Problems)11 Problems of Chapter 5 5.1 Since the records are not related, we typically want to access only a single record and not its adjacent ones. The use of CBC mode is thus not well suited. ECB most seems to be the best choice. 5.3 The decryption of an ”CBC-encrypted” fi le is defi ned by xi= dK(yi)yi1. Since you know the key K and the pair (x0,y0 ) (from the fi rst fi le), the unknown IV can easily be obtained by converting the equation: IV = y1= dk(y0)x0 After that, the second (unidentifi ed) fi le can easily be decrypted by using the decryption equation men- tioned above (with y1= IV). 5.5 If the same IV is used for the OFB encryption, the confi dentiality may be compromized. If a plaintext block xjof such a message m is known, the output can be computed easily from the ciphertext block yj of the message m. This information then allows the computation of the plaintext block xjof any other message mthat is encrypted using the same IV. 5.7 1. 2. The problem with the scheme is that there are only 256 different inputs FBito the AES algorithm. That means there are only 256 different output vectors of length 128bit that form the keystream. To make things worse, the cipher output will run into a cycle quickly. Lets denote the sequence of feedback bytes by FB1,FB2,. As soon as a feedback byte FBjis generated that is equal to an earlier one FBi, i.e., i j, the sequence FBi,FBi+1,.,FBj= FBi,FBi+1,.,FBj= FBi,FBi+1,. repeats periodically. Since there are only 256 different values for FB, the maximum sequence length is 256. Since each value is associated with a 128 (16 byte) AES output, the keystream sequence si has a maximum cycle length of: 12816= 2048byte= 2kbyte. After this, the stream cipher output must repeat (and odds are that the cycle lenght is much shorter). Thus, if an attacker has to know at most 2kB of plaintext in order to recover the entire stream cipher output with which he can decrypt all other ciphertext. 3. No, we still only generate a maximum of 256 keystream words of length 16 byte. Remark: In the chapter on hash functions we will learn about the birthday paradox. This is applicable here too and tells us that the expected length of the sequence is in fact approximately 256 = 16. 5.9 The counter has to encrypt 1 TB of data without repeating itself. This yields an IV of maximum size of 91 = 12836 bits. 5.11 A missing or deleted bit in yiaffects the i-th feedback bit which enters the shift register of size ofbit. After+1 steps, the affected feedback bit leaves the shift register. As a consequence, all subsequent decryptions (i.e., decryptions of yi+.) are again correct. 5.13 With AES having a block size of 128 bit, a key search for AES-128 requires only a single pair of plaintext-ciphertext in order to identify the correct key. In case of AES-192, given a single pair (x,y) of plaintext and ciphertext, there are 2192128= 264possible keys kisatisfying y = eki(x). In order to fi nd the correct key with a probability of 50 percent, we require 263pairs of plaintexts and ciphertexts. 12Solutions to Homework Problems (Odd Numbered Problems) For achieving the same probability with AES-256, 2127plaintexts and ciphertexts are required (which is very very unlikely)! 5.15 y= eK3(eK2(eK1(x) 1. Precompute eKi(x) = z(1) i ; i = 1,2,.,256and store all pairs (z(1) i ,Ki) 2. Decrypt z(2) a,b= e 1 Kb(e 1 Ka(y); a =