課程名稱︰密碼學 課程性質︰ 課程教師︰陳君明 開課學院： 開課系所︰數學系 考試日期（年月日）︰2008/06/02 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Part I (3 points each) 1.For RSA modulus N=10403=101x103, which can NOT be a public exponent e? A.11 B.13 C.17 D.19 E.None of the above 2. Apply Fermat's primality test on 21. Which is NOT a witness of compositeness? A.2 B.4 C.5 D.8 E.None of the above 3.What is the output length (in bits) of the hash function SHA-1? A.128 B.144 C.160 D.192 E.None of the above 4.The branch number in the case of MixColumn operation of AES is defined by min[a/=0]W(a)+W(F(a)), where a is a 4-bute vector, F is a linear transformation, and W is the weight funtion. What is the maximal branch number? A.5 B.6 C.7 D.8 E.None of the above 5.Apply the Miller-Rabin test t times to an odd composite number. Which is the best estimate of the probability of finding at least one witness of compositeness? A.(1/2)^t B.(3/4)^t C.1-(3/4)^t D.1-(1/2)^t E.1-(1/4)^t 6.Which item is definitely NOT listed on a certificate? A.Public key B.Private key C.User name D.Expiry date E.None of the above 7.Which statemant is FALSE about PKI? A.SSL aims to provide channel security to fulfill commercial requirement B.X509 defines a structure for public key certificates C.CA establishes the identity of users, but does not sign certificates D.CRL is a list of the serial numbers of all the revoked certificates E.None of the above 8.Which statement is FALSE about Merkle-Damgard construcion of hash functions? A.Use a collision-resistant compression function f with arbitrary length of input B.Add a single one bit to signal the end of a message, then pad with zeros C.The final block encodes the original length of the unpadded message in bits D.The internal state H:=f(H||mi) is updated repeatedly with message block mi E.None of the above 9.Which property is NOT provided by digital signature schemes? A.Message confidentiality B.Non-repudiation C.Authentication D.Message integrity E.None of the above 10.A cryptographic hash function should satisgy 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 Pri-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.(b)>(a)>(c) C.(a)>(c)>(b) D.(c)>(a)>(b) E.None of the above Part II (3 points each) ‧Represent F16 by polynomial reptesentations with the irreducible f(x)=x^4+x+1 Choosing g=(0010)as a generator for F16, we list all element of F16 as follows. 0=(0000) g^0=(0001) g^1=(0010) g^2=(0100) g^3(1000) g^4=(0011) g^5=(0110) g^6=(1100) g^7(1011) g^8=(0101) g^9=(1010) g^10=(0111) g11=(1110) g^12=(1111) g^13=(1101) g^14=(1001) Consider the elliptic curve group G defined by y^2+xy=x^3+g^4x^2+1 over F16 There are 15 points satisfying the equation as graph Let P=(1,g^6) and Q=(g^5,g^11) The group order |G|=11 P+Q=12 -Q=13 2P=14 4P=15 y 0 . g^14 . g^13 . . . g^12 . g^11 . g^10 . g^9 g^8 . . . g^7 g^6 . g^5 g^4 g^3 . g^2 g . . g g^2 g^3 g^4 g^5 g^6 g^7 g^8 g^9 g^10 g^11 g^12 g^13 g^14 0 x The formulas in Part III might help your computations. Factor n=87463 with the Quadratic Sieve. Define g(x)=x^2-n. x -1 2 3 13 17 19 29 265 1 1 1 0 1 0 0 278 1 0 1 1 0 0 1 296 0 0 0 0 1 0 0 299 0 1 1 0 1 1 0 307 0 1 0 1 0 0 1 316 0 0 0 0 1 0 0 x 2 3 13 17 19 29 x^2-n splits 261 X X 262 X X 263 X X 264 265 X X X X -2x3x13^2x17 266 X 267 X 268 X X 269 X X 270 271 X X X 272 X 273 X X 274 X 275 X X 276 277 X X 278 X X X 279 X X -3^3x13x29 280 X X 296 X X 3^2x17 297 X 298 X 299 X X X X 2x3x17x19 300 301 X X 302 X X 303 X 304 X X 305 X X 306 307 X X X X 2x3^2x13x29 308 X 309 X X 310 X 311 X X 312 313 X X X 314 X 315 X 316 X X 3^6x17 The integers x1, x2, and b satisfy g(265) x g(278) x g(x1) x g(x2) = b^2(mod n) If 0<x1<x2, then x2 = 16 If 0<b<n, then b=17 If a=265x278x(x1)x(x2) (mod n) and 0<a<n, then a=18 If n=pxq and 0<p<q, then p=19 and q=20 These congruences might reduce your comprtational effort: 265x307=81355=-6108(mod n) 265x316=83740=-3723(mod n) 278x296=82288=-5175(mod n) 278x299=83122=-4341(mod n) 3^5x13x17x19=-16947(mod n) 3^4x13^2x17x29=14026(mod n) The solution to the system of congruences 2x=3(mod 7) 3x=6(mod 11) 4x=10(mpd 13) is x=21(mod 22) Consider the RSA signature scheme with the prblic key n=85 and e=3. The private key for signing is d=23 Signing the message m=4, a user obtains its digital signature s=24 In a Diffie-Hellman key exchange scheme on Z31 with the generator g=3, Alice chooses 9 nd Bob chooses 7 in private. Then Alice sends 25 to Bob, and the agreed key is 26 Decrypting the ciphertext c=39 of the Rabub public-key cryptosystem c=mx(m+10) (mod 187), a user obtains four possible corresponding plaintexts m=3, 20, 27, and 28(in increasing order) If a message m is divided into t blocks m1, m2, ..., mt, then the CBC-MAC with a cipger e and a key k is derived by the process I1=m1, O1=ek(I1), Ii=mi + 29, and Oi=30 for i=2, 3, ..., t. Part III (Write down all details of your work) 31(5 points) Derive arithmetic formulas of elliptic curve groups defined by y^2+xy=x^3+ax^2+b withb/=0 over F2m. (a)P1=(x1,y1)and P2=(x2,y2) are two distinct points on the curve with P1 /= -P2 If (x3y3)=P1+P2 and s=(y1+y2)/(x1+x2), show that x3=s^2+s+x1+x2+a and y3=s(x1+x3)+x3+y1 (b)P0=(x0,y0)is a point on the curve with x0/=0. If (x4,y4)=2P, show that x4=x0^2+(b/x0^2) and y4=x0^2+x4(y0/x0 +x0+1) 32(5 points) As the MixColumn operation of AES, we work on polynomials of degree 3 over F256 Let a(x)=a3(x+1)^3 + a2(x+1)^2 +a1(x+1)+a0 and (a)If a(x)b(x)=1(mod(x^4 +1)), show that (i)b0=a0^-1 (ii)b1=a1b0a0^-1 (Also b2=(a2b0+a1b1)a0^-1 and b3=(a3b0+a2b1+a1b2)a0^-1, but you do not have to show them.) (b)Find all self-inverse polynomials. That is, indicate the conditions on a(x) such that a(x)^2=1(mod(x^4 +1)). Prove your claim. --

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