課程名稱：密碼學 期末考 課程性質： 課程教師：陳君明 開課學院： 開課系所：數學系 考試日期(年月日)：2011/6/21 考試時限(分鐘)：180分鐘 是否需發放獎勵金：yes (如未明確表示，則不予發放) 試題： PartⅠ (three points each) The right figure shows the graph of an elliptic curve over R. The line BC is tangent to the curve at C.Both AB and CD are vertical lines. On the elliptic curve group denoted as an additive group, indicate the specified point on the figure in each of the following three questions. 1.Which point is 2C? 2.Which point is B+C? 3.Which point is B-2D? 4.Which equation does not define an elliptic curve group over GF23? A. y^2 = x^3 + 6x + 5 B. y^2 = x^3 + 7x + 5 C. y^2 = x^3 + 8x + 5 D. y^2 = x^3 + 9x + 5 E. None of the above 5.For which prime numbers p and q, a multiplicative cyclic group of order q can be constructed as a subgroup of(Zp*,×)?Cryptographic primitives based on the discrete logarithm problem are operated on such groups. A. p = 1831,q = 331 B. p = 1847,q = 317 C. p = 1861,q = 313 D. p = 1867,q = 311 E. None of the above 6.Whose seccurity is NOT based on the difficulty of the discrete logarithm problem? A. ElGamal encryption B. Diffie-Hellman key exchange scheme C. Rabin encryption D. DSA(Digital Signature Algorithm) E. None off the above 7.Which is the first primality-proving algorithm to be simultaneously polynomai -l, deterministic, general, andd unconditional? A. Fermat's test B. Miller-Rabin test C. ECPP test D. AKS test E. None of the above 8.NSA Suite B is a set of cryptographic algorithms promulgated by NSA(National Security Agency) of USA as part of its Cryptographic Modernization Program. Which algorithm is NOT included in NSA Suite B? A. RSA B. AES C. SHA-2 D. ECDH E. None of the above 9.Which statement is FALSE about Public Key Infrastucture? A. PKI provides theauthentic channels used to distribute keys B. A digital certificate binds an entity and iss public key C. Time stampings are signed by the public key of a trusted third party D. HTTP, FTP, TELNET protocols can be transparently layered on top of SSL E. None of the above 10.Which statement is FALSE about Identity Based Cryptography? A. Its first signature scheme is based on the RSA problem B. Its first encryption scheme is based on bilinear pairings on elliptic curv -es C. It removes the need for a trusted third party D. It removes the need for storage and transmission of certificates E. None of the above PartⅡ (three points each) p.s.?為填空處 ● The RSA signature scheme applied with Chinese Remainder Theorem(CRT)is performed in many low-cost chips. Suppose p = 17 & q = 23 are kept private and the public modulus is n = 391 = 17 x 23. $ The value of Eulerψ-function for n isψ(391) = ? $ Sign the message m = 124 by CRT as follows. % m^d mod p = (m mod p)^d modψ(p) mod p = ? = A, where 0 ≦ A ＜ p. % m^d mod q = (m mod q)^d modψ(q) mod q = ? = B, where 0 ≦ B ＜ q. % Solve tje system of equations by CRT： m^d ≡ A(mod p);m^d ≡ B(mod q). The ddigital signature of m is S = m^d mod n = ?, where 0 ≦ S ＜ n. $ Verify the signature S as follows. % Compute m' = ? mod n. (Fill in aformula related to S and e) % If m = m', then the digital signature S is accepted. Otherwise S is rejected. Note that the correctiness of your answers to the values of A, B, and S can be confirmed in a similar way $ Alice and Bob will agree a key by the Diffie-Hellman key exchange scheme on Z53 with the generator g = 2. Evaluate the following values of A and K in Z53. % Alice selects a = 21 randomly in private, then Alice sends A = ? to Bob. % Bob selects b = 8 randomly in private and sends the corresponding B to Alice, then the agreed key is K = ? $ N = 79567 = p x q has the valueψ(N) = 79000 of Eulerψ-function.Assume the prime factors p > q, then p = ? and q = ?. $ N = 43739 = p x q satisfies：296^2≡138 = 2 x 3 x 23 (mod N) 302^2≡3726 = 2 x 3^4 x 23 (mod N) 305^2≡5537 = 4 x 43^2 (mod N) 363^2≡552 = 2^3 x 3 x 23 (mod N) 373^2≡7912 = 2^3 x 23 x 43 (mod N) Assume the prime factors p > q, then p = ? and q = ?. $ Perform ECDSA on the elliptic curve group defined by y^2 = x^3 + 7x + 3 over F23 as the figure. The base point is G = (7,2). % The order of G is n = ?. % 2G = ?. % Choose x = 3 randomly as y^2 = x^3 + 7x + 3 over F23 the private key, then the 30 solutions pulblic key is p = ?. % To sign a message m, the following steps are excuted： * Calculate e = HASH(m). Assume z = 19 is the Ln leftmost bits of e. * Choose k = 5 randomly as an ephemeral key. * Calculate r = x1 mod n, where(x1,y1) = KG = ? * Calculate s = k^-1 (z + rx)mod n = ? * The signature is the pair(r,s) $ To verify the signature(r,s), the following steps are executed： * Calculate t = zs^-1 mod n * Calculate u = rs^-1 mod n * Calculate V = tG + uP = (x2,y2) = ?. * The signature(r,s) is accepted if x2 = r. $ This example demonstrates how to solve discrete logarithm problems by Shank's Baby-Step/Giant-Step algorithm. To solve 5^x≡219(mod 307), write x = i + 18k where 0 ≦ i,k ＜ 18. Note that 18 is the least integer greater ___ than ˇ307. List(i,5^i) and (k,219 x 5^-18k) by way of 5^-18≡235(mod 307) as follows. Baby steps： i 0 1 2 3 4 5 6 7 8 5^i 1 5 25 125 11 55 275 147 121 ----------------------------------------------------------------------------- i 9 10 11 12 13 14 15 16 17 5^i 298 262 82 103 208 119 288 212 139 ============================================================================= Giant steps： k 0 1 2 3 4 5 6 7 8 219x5^-18k 219 196 100 201 264 26 277 11 129 ---------------------------------------------------------------------------- k 9 10 11 12 13 14 15 16 17 219x5^-18k 229 90 274 227 234 37 99 240 219 ============================================================================= Determine i and k such that 5^i≡219 x 5^-18k(mod 307)from the tables. We obtain 5^i+18k≡219(mod 307) for i = ?. The solution is x = ? where 0 ＜ x ＜ 307. Shank's Baby-Step/Giant-Step algortithm takes __ O(√n)space and O(ˇ n)time to solve a discrete logarihm problem in a cyclic group of order n. PartⅢ (Write down all details of your work) (5 points) Miller-Rabin Probabilistic primality Test is recommended & specified in FIPS 186-3 and many other documents. It is widely implemented. (a)Explain the concept behind the test. (b)Describe its algorithm as precise as possible. (5 points) Elliptic Curves over 256-bit and 384-bit prime fields are required in NSA Suite B for key agreements and digital signatures. The coefficients of the equation defining an elliptic curve must be selected carrefully. (a)Show that the polynomial x^3 + ax + b has no repeated roots if and only if 4a^3 + 27b^2 ≠ 0. (b)Why the equations y^2 = x^3 + ax + b with 4a^3 + 27b^2 = o must be avioded for ECC(Elliptic Curve Cryptography)? -- 解方塊不需要思考 但是思考會讓解方塊更有意義 by aegius1r --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.167.78.172