课程名称︰密码学 课程性质︰ 课程教师︰陈君明 开课学院： 开课系所︰数学系 考试日期（年月日）︰2007/4/16 考试时限（分钟）：180 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Cryptography Midterm Exam I 2007/04/16 Part I (3 points each) 1. Which value of Legendre symbol or Jacoby symbol is correct? A.(13/53) = -1 B.(15/55) = -1 C.(17/57) = -1 D.(19/59) = -1 E.None of the above 2. Denote h as a hash function, k as a key, m as a message, p1 and p2 as padding strings. Which is the value of HMACk(m)? A.h(k||m) B.h(m||k) C.h(k||p||m||k) D.h(k||p1||h(k||p2||m)) E.None of the above 3. Whose size of the key space is approximately equal to the complexity of finding a collision of SHA-224? A.192-bit AES B.256-bit AES C.2-key Triple-DES D.3-key Triple-DES E.None of the above 4. Which hash function is simply a truncated version of SHA-512, computed with different initial values? A.SHA-384 B.SHA-256 C.MD5 D.RIPEMD-160 E.None of the above 5. In which operation of AES, each set of four bytes in a state is treated as a degree-3 polynomial over F256? A.ByteSub B.MixColumn C.AddRoundKey D.ShifyRow E.None of the above 6. By which mode of operation, a block cipher can be used to construct a self-synchronizing stream cipher? A.ECB B.CBC C.OFB D.CFB E.None of the above 7. Which value of Euler φ-function is NOT equal to 40? A.φ(41) B.φ(75) C.φ(88) D.φ(132) E.None of the above 8. In a Feistel cipher, every encryption round consists of Li = Ri-1 and A.Ri = Li-1⊕f(Ri-1,ki) B.Ri = Li-1⊕f(Li-1,ki) C.Ri = Ri-1⊕f(Li-1,ki) D.Ri = Ri-1⊕f(Ri-1,ki) E.None of the above 9. Which is true about the symmetric group S5? A.|S5| = 60 B.<(1,2,3,4,5)> is a normal subgroup C.(S5:S4) = 10 D.(S5:<(1,2,3),(1,2)>) = 30 E.None of the above 10. Which statement is FALSE about the eSTREAM project? A.The goal is to identify new stream ciphers that might become suitable for widespread adoption B.Profile 1 contains submissions of stream ciphers for hardware applications with high throughput requirements C.Profile 2 contains submissions of stream ciphers for hardware applications with restricted resources such as liited storage, gate count, of power consumption D.Profile 1A or 2A contains stream ciphers satisfying Profile 1 of 2 with an associated authentication method respectively E.None of the above Part II (3 points each) #Consider the elliptic curve group defined by y^2 = x^3 + x over F23. There are 23 points satisfying the equation as the graph below. Let P = (1,5) and Q = (9,18). The order of the elliptic curve group is <11>. P+Q = <12>. -Q = <13>. 2P = <14>. 4P = <15>. 2007P = <16>. graph: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,3) (20,20) (21,6) (21,17) #Since P(x) = x^5 + 2x + 1 is irreducible over F3, the quotient ring K = F3[x]/(P(x)) is a finite field. Let Q(x) = x^2 + 2x + 1. The number of elements in K is |K| = <17>. Q(x)^1213 = 2x^3 + <18> in K. Q(x)^(-1) = x^4 + <19> in K. To prove that P(x) is primitive, it is suffient to show x^m /= 1 and x^n /= 1 in K where m, n>0. We have min(m,n) = <20>. #Consider the integer values of x satisfying x = 11(mod 27) and x = 10(mod 29). The smallest positive solution is x = <21>. The largest negative solution is x = <22>. #For a set G, we denote (G,+) as an additive group and (G,x) as a multiplicative group respectively. Consider the gomomorphism h:(Z,+) → (Z31*,x) defiend by h(x) = 4^x mod 31. (Z/Ker(h),+) is isomorphic to (Zn,+) where n = <23>. The index((Z31*,x) : (Im(h),x)) = <24>. Apparently 4 is not a generator of the cyclic group (Z31*,x). The smallest positive integer generating (Z31*,x) is <25>. #Assume the periedic sequence 1,0,1,1,1,0,0,1,0,1,1,1,0,0, ... of period 7 is generated by an LFSR(Linear Feedback Shify Register). If the connection polynomial is primitive, it is <26>. The linear complexity of the sequence is <27>. #Determine the period of the sequence generated by LFSR of register length 8 with non-zero initial state and connection polynomial C(x). C(x) = x^8 + x^5 + x^3 + x^2 + 1(primitive), then the period is <28>. C(x) = x^8 + x^5 + x^4 + x^3 + 1(irreducible but not primitive), then the period is <29>. (Hint: Less than 30) C(x) = x^8 + x^5 + x^3 + 1(reducible), then the maximal possible period is <30>. Part III (Write down all details of your work) 31.(2 points) Sketch the flow chart of CBC-MAC. 32.(3 points) Sketch the flow chart of OFB mode(Output Feedback), including both encryption and decryption. A cryptographic hash function should satisfy these three assumptions: (A)Pre-image Resistant -Given y, hard to find x such that h(x) = y (B)Collision Resistant -Hard to find any x /= x' such that h(x) = h(x') (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". 33.(2 points) Order the strength of the assumptions (A), (B), and (C). That is, answer in the form of "L>M>N". 34.(3 points) Prove your claim of the relation between (A) and (B). Solution: 1 2 3 4 5 6 7 8 9 10 C D C A B D E A E B 11 12 13 14 15 16 17 18 19 20 24 (16,8) (9,5) (0,0) O(Infinity) (1,18) 243(3^5) x^2+2x+1 x^3+2x+1 22 21 22 23 24 25 26 27 28 29 30 416 -367 5 6 3 x^3+x^2+1 3 255 17 30 <1>a,0,-1,1 <3>.=.2^112 <9>120,[(12)(12345)(12) not belongs to <(12345)>],5,20 <10>Profile I for software applications <16>2007P = -P since 4P = O <18>Q^(242x5+3) = Q^3, note (a+b)^p = a^p + b^p over Fp <19>Extended Euclidean (GCD) algorithm: P(x) = (x^3+x^2+2)Q(x) + (x+2), Q(x) = x(x+2) +1, so 1 = Q(x) = x(x+2) = Q(x) = x[P(x) - (P(x) - (x^3+x^2+2) Q(x))] = -xP(x) + Q(x)(x^4+x^3+2x+1) <20>min(242/2,242,11) <24>Im(h) = {1,2,4,8,16} <27>Shortest length of generating LFSR <28>2^8-1 <29>17|255 and C(x)|(x^17+1) <33>B>C>A <34>Similar but not identical to the proof of Lemma 9.1 --

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