《密码学原理与实践》课后习题答案.pdf-资料库

algorithm_fish-6618281-4744302543419882790.pdf-第1页.png

第1页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第2页.png

第2页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第3页.png

第3页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第4页.png

第4页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第5页.png

第5页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第6页.png

第6页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第7页.png

第7页 / 共21页

algorithm_fish-6618281-4744302543419882790.pdf-第8页.png

第8页 / 共21页

Homework of Cryptography Tony Zhu December 20, 2010 1 Classical Cryptography 1.21 (c) Aﬃne Cipher Solution: Since in the aﬃne cryptosystem only φ(26) × 26 = 312 cases for key K = (a, b), list all the cases brutally with the help of computer and scan quickly, I found only one case seems meaningful: ocanadaterredenosaieuxtonfrontestceintdeﬂeuronsglorieuxcartonbrassaitporterlepeeils aitporterlacroixtonhistoireestuneepopeedesplusbrillan tsexploitsettavaleurdefoitrem- peeprotegeranosfoyersetnosdroits After breaking the long sentence, I found it should be the French version of Canada national anthem: O Canada Terre de nos a¨ıeux Ton front est ceint de ﬂeurons glorieux! Car ton bras sait porter l’´ep´ee Il sait porter la croix! Ton histoire est une ´epop´ee Des plus brillants exploits Et ta valeur, de foi tremp´ee Prot´egera nos foyers et nos droits 1.22 1

Proof. (a) Obviously in the case p1 ≥ p2 ≥ 0, q1 ≥ q2 ≥ 0, the sum p1q1 + p2q2 is maximized. i < q j, permute the positions of the two numbers and, according to the statement of last i > S , contradicts. So the only i is maximized, and if there exists i > j such that q Suppose S =n paragraph, we get S = i=1 piq + p jq + piq j arrangement for S is q phq 1 ≥ . . . ≥ q n. 0≤h≤n hi, j h v 2 Shannon’s Theory 2.2 Proof. P = C = K = {1, . . . , n}. ∀x ∈ P, ∀y ∈ C Pr[Y = y] = so Pr[K = k]Pr[x = dk(y)] = 1/n k∈K Pr[x|y] = Pr[x]Pr[y|x] Pr[y] Pr[x] 1 n = 1 n = Pr[x] that is this Latin Square Cryptosystem achieves perfect secrecy provided that ev- v ery key is used with equal probability. 2.3 Proof. Similarly as (2.2). 2.5 v Proof. According to Theorem 2.4, this cryptosystem provides perfect secrecy iﬀ every key is used with equal probability 1/|K |, and for every x ∈ P and y ∈ C , there is unique key k ∈ K , such that y = ek(x). 2

Due to perfect secrecy, we have Pr[x|y] = Pr[x] = Pr[x] Pr[x]Pr[y|x] Pr[y] Pr[y] = Pr[y|x] = Prek(x)=y[K = k] = 1/|K |. =⇒ =⇒ that is every ciphertext is equally probable. v 2.11 Proof. (Perfect secrecy ⇒ H(P|C)=H(P)). H(P|C) = − = − y∈C x∈P x∈P y∈C = H(P) Pr[y] y∈C Pr[y]Pr[x|y] log2 Pr[x|y] Pr[y]Pr[x] log2 Pr[x] = H(P). (H(P|C) = H(P) ⇒ Perfect secrecy). According to Theorem 2.7, H(P, C) ≤ H(P) + H(C) with equality iﬀ P and C are independent random variables. so H(P|C) = H(P) =⇒ H(P, C) = H(P) + H(C) =⇒ P and C are independent random variables =⇒ ∀x ∈ P, ∀y ∈ C, Pr[x|y] = Pr[x], that is the cryptosystem achieves perfect secrecy. v 2.12 3

Proof. We have H(K, P, C) = H(P|K, C) + H(K, C) = H(K, C), so 2.13 H(K, P, C) ≥ H(P, C) =⇒ H(K, C) ≥ H(P, C) =⇒ H(K|C) = H(K, C) − H(C) ≥ H(P, C) − H(C) = H(P|C). v + 1 3 log2 3 + 1 6 log2 6 ≈ 1.45915. Solution: H(P) = 1 2 H(K) = log2 3 ≈ 1.58496. Pr[1] = 2/9 Pr[2] = 5/18 Pr[3] = 1/3 Pr[4] = 1/6 H(C) ≈ 1.95469. H(K|C) = H(K) + H(P) − H(C) ≈ 1.08942. Pr[K2|1] = 0 Pr[K1|1] = 3/4 Pr[K1|2] = 2/5 Pr[K2|2] = 3/5 Pr[K2|3] = 1/3 Pr[K1|3] = 1/6 Pr[K1|4] = 0 Pr[K2|4] = 1/3 H(P|C) ≈ 1.08942. 2.14 Pr[K3|1] = 1/4 Pr[K3|2] = 0 Pr[K3|3] = 1/2 Pr[K3|4] = 2/3 Solution: H(K) = log2 216, H(P) = log2 26, H(C) = log2 26, H(K|C) = H(K) + H(P) − H(C) = log2 216 ≈ 7.75489. It is easy to evaluate: H(K|P, C) = log2 12 ≈ 3.58496. 4

2.19 Proof. A key in the product cipher S1×S2 has the form (s1, s2), where s1, s2 ∈ Z26, e(s1, s2)(x) = x + (s1 + s2). But this is precisely the deﬁnition of a key in the Shift Cipher. Further, the proba- bility of a key in S1 × S2 equals 26 , which is also the probability of a key in the Shift Cipher. Thus S1 × S2 is the Shift Cipher. v 26 pi = 1 1 26 = 1 25 i=0 25 i=0 2.20 Proof. (a) Similarly as (2.19). (b) The number of keys in S3 equals 26lcm(m1, m2). Form the following fact we can see that the keys in S1 × S2 are lesser when m1 0 (mod m2). Notice m2 < m1, m1 0 =⇒ m1 + m2 < 2m1 ≤ (mod m2) m2 gcd(m1, m2) m2 = l, where l lcm(m1, m2) the equation below, which essentially gives the representation of the keys of prod- uct cryptosystem S1×S2, would’t always has a solution (K1, K2) = (x1, . . . , xm1, y1, . . . , ym2) ∈ K1 × K2, for any selected key K = (z1, . . . , zl) ∈ K3,  Im1 ... Im1 Im2 Im2 ... Im2 Im2   x1 ... xm1 y1 ... ym2   ,  z1 ... ... zl = because the coeﬃcient matrix’s column number is less than the row number. Con- clusively, there must exist key K ∈ K3 that not in K1 × K2. v 3 The RSA Cryptosystem and Factoring Integers 5.2 5

Proof. (a) ri = qi+1ri+1 + ri+2 ≥ ri+1 + ri+2 ≥ 2ri+2. (b) (c) From (a), m ≤ log2 a + 1 ∼ log a ∼ log b. 5.3 Solution: (a) 17−1 ≡ 6 (mod 101). (b) 357−1 ≡ 1075 (mod 1234). (c) 3125−1 ≡ 1844 (mod 9987). 5.4 Solution: 8 × 93 − 13 × 57 = 3. v 5.5 Solution: It’s easy to see that −1(x, y, z) = 70x + 21y + 15z χ (mod 105). −1(2, 2, 3) = 17. χ So 5.6 Solution: Similarly we have −1(x, y, z) = (13×26×27)x +(252×27)y +(14×25×26)z χ So −1(12, 9, 23) = 470687. χ (mod 25×26×27). 5.7 Solution: Similarly we have −1(x, y) = (50 × 101)x + (51 × 99)y χ 13−1 ≡ 61 (mod 99), 15−1 ≡ 27 (mod 101). So (mod 99 × 101). (mod 99) (mod 101) (mod 99) (mod 101) 15x ≡ 56  13x ≡ 4  x ≡ 46 x ≡ 98 ⇐⇒ =⇒ x = 7471. 6

5.9 Proof. 5.11 α ±1 (mod p), α is primitive element modulo p ⇐⇒ the order of α ∈ Z∗ ⇐⇒ α ±1 (mod p), αq ≡ −1 p is 2q. (mod p). (Because the order of α could only be 2, q or 2q.) v Proof. By showing xλ(n) = 1 (mod n), ∀x ∈ Zn, we can prove the encryption and decryption are still inverse operations in this modiﬁed cryptosystem. Since we have Zn Zp ⊕ Zq, and the isomorphism is Ψ(h) = (h (mod p), h (mod q)), it only needs to showxλ(n) = 1 (mod p), and xλ(n) = 1 (mod q). xλ(n) ≡ (xp−1) q−1 gcd(p−1,q−1) q−1 gcd(p−1,q−1) (mod p). ≡ (1) ≡ 1 (mod p) (mod p) For q is the same. So complete the proof. Solution: (b) p = 37, q = 79, b = 7. Modiﬁed cryptosystem. λ(n) = 468, a = 67. Original cryptosystem. φ(n) = 2808, a = 2407. 5.13 Proof. (a) Again use the isomorphism Zn Zp ⊕ Zq, → and note that xp−1 ≡ 1 (mod p) and xq−1 ≡ 1 (mod q) for all x 0, we get Zn (mod q)) → Mpqxp + Mqpxq (mod q)) Zp ⊕ Zq (mod p), yd (mod p), ydq Zn (mod n) → (yd = (ydp = (xp, xq) → yd 7 v (mod n)

so complete the proof. (b) p = 1511, q = 2003, and d = 1234577. After some calculation, we get dp = 907, dq = 1345, Mp = 777, and Mq = 973. (c) y = 152702, ydp = 242 (mod 1511), ydq = 1087 (mod 2003), yd = v 1443247 (mod n = 3026533). 5.14 Solution: If gcd(y, n) 1, we get a factor p = gcd(y, n) of n, and another factor q = , consequently, dK and x = dK(y) can be calculated explicitly. n gcd(y, n) Now suppose gcd(y, n) = 1, computer ˆy = y−1 (mod n), which is chosen as the attack allows to know the plaintext ˆx, it is easy to see that x = ˆx−1 (mod n). 5.18 Proof. The isomorphism is used again to show Zn Zp ⊕ Zq eK(x) = xa = x ⇐⇒ (xa mod p, xa mod q) = (x mod p, x mod q). And deduce that p is multiplicative cyclic group of order p − 1, F∗ q is multiplicative cyclic group of order q − 1, F∗ #S p = #{x ∈ F∗ #S q = #{x ∈ F∗ p|xa = x} = gcd(a − 1, p − 1), q|xa = x} = gcd(a − 1, q − 1), so #S = #{x ∈ Zn|x 0, (xa mod p, xa mod q) = (x mod p, x mod q)} = #(S p × S q) = gcd(a − 1, p − 1) × gcd(a − 1, q − 1) = gcd(b − 1, p − 1) × gcd(b − 1, q − 1), the last equation can be easily seen from the equality ab ≡ 1 (mod (p − 1)(q − 1)), i.e. (a − 1)b ≡ −(b − 1) (mod (p − 1)(q − 1)). 8

资料库

《密码学原理与实践》课后习题答案.pdf

相关推荐

安全技术

热门标签

最新资料