课程名称︰密码学 课程性质︰选修 课程教师︰陈君明 开课学院：理学院 开课系所︰数学系 考试日期（年月日）︰2012/06/19 考试时限（分钟）：150分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Part I(3 points each) 1.To compute a^43 by "Square-and-Multiply",how many "Multiply" are required? A.3 B.4 C.5 D.6 E.None of the above 2.For RSA modulus N=185617=419*443,which is a possible public exponent e? A.11 B.13 C.17 D.19 E.None of the above 3.Which is a generator of a cyclic multiplicative group of order 5 in Z41*? A.3^((41-1)/5) B.9^((41-1)/5) C.14^((41-1)/5) D.31^((41-1)/5) E.None of the above 4.Which is NOT a legitimate output length of the family of SHA-2 hash functions? A.128 B.256 C.384 D.512 E.None of the above 5.Which hash function is a first-round candidate of the SHA-3 competition, but is NOT selected to advance to the third(final) round? A.Skein B.Grøst C.Keccak D.MD6 E.None of the above 6.Which service is provided by digital signature schemes but NOT by message authentication codes? A.Message authentication B.Message integrity C.Non-repudiation D.Message confidentiality E.None of the abov 7.A cryptographic hash function should satisfy these three assumptions: (a) Collision Resistant-Hard to find any x!=x' such that h(x) = h(x') (b) Pre-image Resistant-Given y, hard to find x such that h(x) = y (c) Second Pre-image Resistant-Given h(x), hard to find x(!=x) with h(x) = h(x') Denote "M > N" as "M is a stronger assumption than N". Which relation is correct? A.(c) > (b) > (a) B.(a) > (c) > (b) C.(c) > (a) > (b) D.(a) > (b) > (c) E.None of the above 8.According to Prof. Ron Rivest, which can be described as “I can convince you that I know a solution to a hard problem while telling you nothing about my solution even if you are very skeptical”? A. Random oracle B. Homomorphic encryption C. Oblivious transfer D. Zero-knowledge proof E. None of the above 9.Which statment is FALSE about RC4? A.The most widely-used software stream cipher B.Its internal state is an array of 128 bytes C.Its internal state evolves in an unpredictable and non-linear way D.Known attacks can be defended by discarding the initial portion of the keystream E.None of the above 10.Which is NOT proved or disproved yet about RSA with modulus n=p*q, public exponent e, and private exponent d? A.Knowing d is equivalent to factoring n B.Knowing φ(n)is equivalent to factoring n C.Breaking RSA is equivalent to factoring n D.Secure against chosen plaintext attack assuming the RSA-Problem is hard E.None of the above Part II(3 points each) ●The RSA signature scheme performed with Chinese Remainder Theorem(CRT) is implemented in many low-cost chips. Suppose p=11 and q=29 are kept private, and the public modulus is n=319=11*29. ◆The value of Euler φ-function for n is φ(319)=[11]. ◆If the public exponenet for verification is e=3, the corresponding private key for signing is d=[12], where 0<d<φ(319). ◆Sign the message m=89 by CRT as follows. => m^d mod p=(m mod p)^(d mod φ(p))mod p =[13]=A,where 0<=A<p. => m^d mod q=(m mod q)^(d mod φ(q))mod q =[14]=B,where 0<=B<q. =>Solve the system of equations by CRT:m^d≡A(mod p);m^d≡B(mod q). The digital signature of m is S=m^d mod n=[15],where 0<=S<n. ◆Verify the signature S as follows. =>Compute m'=[16]mod n.(Fill in a formula related to S and e) =>If m=m',then the digital signature S is accepted.Otherwise S is rejected. Note that the correctness of your answers to the values of A,B, and S can be confirmed in a similar way. ●Assume the periodic sequence 1,1,0,0,1,0,1,1,1,0,0,1,0,1...of period 7 is generated by and LFSR(Linear Feedback Shift Register). ◆The connection polynomial of the LFSR is [17]. ◆The linear complexity of the sequence is [18]. ●Complete the following algorithm of scalar multiplication on a given elliptic curve group. It is similar to the left-to-right square-and-multiply exponentiation. INPUT:a point P on the curve,a positive integer k=(kt-1,...,k1,k0)2 OUTPUT:the point kP on the curve 1. R←∞(O: point at infinity) 2. For i from t-1 down to 0 do 2.1 R←[19] 2.2 If ki=1 then R←[20] 3. Return(R) ●In the 2nd homework,you are asked to find a point of prime order in an elliptic curve(EC) group.Such a base point generating a cyclic group is a part of domain parameters of an elliptic curve cryptosystem(ECC). This set of problems will show you that if the order of the base point is not prime, then the discrete logarithm problem(DLP) on the EC group can be reduced to easier ones by the Pohlig-Hellman Attack.Let's solve the DLP Q=xP where P is a base point on the EC group indicated by the fiqure.P(2,6),Q(13,4) ◆Note that the order is the EC group is 30=2*3*5. We have 6P=(16,14),10P=(1,2),15P=(8,0).2Q=(9,9),4Q=[21], 6Q=(16,9), 10Q=[22], 15Q=16Q-Q=[23]. ◆First,solve the DLP(30/5)Q=6Q=x(6P). Note that both 6P and 6Q lie in the subgroup of order 5. Writing x=5k5+x5 where x5 is Z5, we find x5=4 since 6Q=24P,hence x≡4(mod 5). ◆Secone,solve the DLP(30/3)Q=10Q=x(10P). Note that both 10P and 10Q lie in the subgroup of order 3. Writing x=3k3+x3 where x3 is Z3,we find x3, hence x≡[24](mod 3) ◆Third,solve the DLP(30/2)Q=15Q=x(15P). Note that both 15P and 15Q lie in the subgroup of order 2. Writing x=2k2+x2 where x2 is Z2, we find x2, hence x≡[25](mod 2) ◆Combining the result by Chinese Remainder Theorem, we obtain x=[26]. ●Using Diffie-Hellman key exchange scheme on Z37 with the generator g=2, Alice chooses 17 and Bob chooses 11 in private. ◆The element in Z37 that Alice sends to Bob is [27]. ◆The agreed key is [28]. ●If a random number generator (RNG) is not good enough, the public moduli of RSA generated by such RNG might be factored with a chance much higher than expected. A paper published in February 2012 claimed that 0.2% of millions of RSA moduli collected on the internet can be factored without knowing private keys. Suppose n1=9397331 and n2=9794783 with an unfortunate common prime factor generated by a lousy RNG, then both moduli are factored easily. Assume p>q are the prime factors of n1, then p=[29] and q=[30]. Part III(write down all details of your work) [31](5 points) Decrypt the ciphertext c=54 encrypted by the Rabin public-key cryptosystem c=m*(m+16)(mod 437). [32](5 points) Which finalist of SHA-3 competition did you introduce in the 2nd homework? Describe this hash function as detailed as possible. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 111.249.2.238