課程名稱︰密碼學 課程性質︰ 課程教師︰陳君明 開課學院： 開課系所︰數學系 考試日期（年月日）︰2009.6.16 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Cryptography Final Exam 2009/06/16 Part I (3 points each) 1. Apply Fermat's primality test on 33. Which is NOT a witness of compositeness? A.7 B.10 C.13 D.16 E.None of the above 2. Which is the key length (in bits) of two-key Triple-DES? A.112 B.128 C.160 D.192 E.None of the above 3. The S-box of AES is constructed by combining the function f(x) = x^a defined on GF256 with an invertible affine transformation. Which is the value of a? A.254 B.255 C.256 D.257 E.None of the above 4. Which stream cipher is NOT in the portfolio of the eSTREAM project? A.Rabbit B.Trivium C.Salsa20 D.RC4 E.None of the above 5. Which mode of operation has no error propagation? That is, a transmission error of one bit causes a decryption error of only one bit. A.ECB B.CBC C.OFB D.CFB E.None of the above 6. Suite B is a set of algorithms promulgated by National Security Agency(NSA) as part of Cryptographic Modernization Program. Which is NOT included in Suite B? A.ECDH B.ECDSA C.AES-256 D.SHA-256 E.None of the above 7. Let mi's and ci's be plaintext and ciphertext blocks respectively. With a decryption algorithm d and a key k, which is the decryption operation of CBC mode for i>1? A.mi = dk(ci⊕mi-1) B.mi = dk(ci)⊕mi-1 C.mi = dk(ci⊕ci-1) D.mi = dk(ci)⊕ci-1 E.None of the above 8. Which signature scheme based on discrete logarithm problem has the message recovery property? A.ELGamal signature B.DSA C.Nyberg-Rueppel signature D.Schnorr signature E.None of the above 9. Which is NOT one of the operations of IDEA encryption? A.Multiplication modulo 2^16+1 B.Addition mofulo 2^16 C.Exponentiation mofulo 2^16-1 D.Exclusive OR E.None of the above 10. Which statement is FALSE about PKI? A.CRL is a list of the serial numbers of all the revoked certificates B.CA extablishes the identity of users, but does not sign certificates C.SSL aims to provide channel security to fulfill commercial requirement D.X509 defines a structure for public key certificates E.None of the above Part II (3 points each) #To factor 9487 by the quadratic sieve, we define f(x) = x^2-9487. x │ f(x) │-1 2 3 7 11 13 17 19 29 ──┼───┼───────────── 81 │-2926 │ 1 1 0 1 1 0 0 1 0 84 │-2431 │ 1 0 0 0 1 1 1 0 0 85 │-2262 │ 1 1 1 0 0 1 0 0 1 89 │-1566 │ 1 1 1 0 0 0 0 0 1 95 │-462 │ 1 1 1 1 1 0 0 0 0 97 │-78 │ 1 1 1 0 0 1 0 0 0 98 │117 │ 0 0 0 0 0 1 0 0 0 100 │513 │ 0 0 1 0 0 0 0 1 0 101 │714 │ 0 1 1 1 0 0 1 0 0 103 │1122 │ 0 1 1 0 1 0 1 0 0 From the table, (81 x <11> x <12>)^2 = a^2 (mod 9487) where a is an integer. The factorization is 9487 = <13> x <14> #DES and Triple-DES support the data block size of <15> bits. AES supports the data block size of <16> bits. #A cryptographic hash function h should satisfy the following properties. Pri-image Resistance: Given y, hard to find x such that <17>. Collision Resistance: Hard to find any x != x' such that <18>. #Consider the sequences generated by an LFSR with register length 6. The largest possible period of a sequence is <19>. With the connection polynomial x^6 + x^3 + 1, the period of a non-zero sequence is <20>. #Using Diffie-Hellman key exchange scheme on Z37 with the generator g = 2, Alice chooses 12 and Bob chooses 5 in private. The clcment in Z37 that Alice sends to Bob is <21>. The agreed key is <22>. #The following reference code comes from the book "The Design of Rijndail" written by J. Daemen and V. Rijmen: typedef unsigned char word8; word8 Logtable[256] = { 0,0,25,1,50,2,26,198,75,199,27,104,51,238,223,3,100,4,224,14, 52,141,129,239,76,113,8,200,248,105,28,193,125,194,29,181,249,185,39,106 ... }; word8 Alogtable[256] = { 18,,14,9,207,205,55,63,91,209,83,57,132,60,65,162,109,71,20,42,158,93, ... }; /* The tables Logtable and Alogtable are used to perform multiplications in GF(256) */ word8 mul(word8 a, word8 b){ if(a&&b) return Alogtable[(Logtable[a] + Logtable[x])%255]; else return 0; } Gf256 is generated by m(x) = x^8 + x^4 + x^3 + x + 1 in AES. The above above tables (20 entries in each row) are built by the primitive element x+1 of GF2[x]/<m(x)> isomorphic to GF256. (x+1)^n mod m(x) = x^4 + x, then n = <23>. (x+1)^179 mod m(x) = <24> (a polynomial in GF2[x] of degree<8) (x^5 + x^2)^(-1) m(x) = <25> mod (a polynomial in GF2[x] ..<8) Finish the subroutine computing patche multiplicative inverses in GF256: word8 inverse(word8 a){ if(a) return Alogtable[<26>]; else return 0; } #Consider Shamir's Secret Sharing with threshold 3 over GF17. The secret a0 is hided as the constant of the polynomial f(x) = a2x^2 + a1x + a0 belongs to GF17[x]. The points (1,6), (2,10), (4,2) that f(x) passes are obtained from threeparticipants. Then the secret is recovered as a0 = <27>. The point (3,y) is also distributed to another participant, then y = <28>. #Complete the Miller-Tabin test to determine the primality of an integer n: Write n01 = 2^k m where m is odd Choose a belongs to {1, ..., n-1} Compute b = <29> (mod n) If(b !=1 and b !=(n-1)) i = 1 While(i<k and b != (n-1)) b = <30> (mod n) If(b = 1) Output(Composite, a) i = i+1 If(b != (n-1)) Output(Composite, a) Output " Probable Prime" Part III (Write down all details of your work) 31.(4 points) Both 1009 and 10091 are prime numbers. Find an element of the multiplicative group Z10091* whose order is 1009. Explain why your choice is correct. (Hint: The domain parameter selections of DLP-based cryptosystems such as DSA and ELGamal have similar process.) 32.(6 points) In the MixColumns operation of AES, each column is treated as a polynomial over GF256 and is then multiplied modulo x^4 + 1 with a fixed polynomial c(x) = c3x^3 + c2x^2 + c1x + c0. In AES, c(x) = '03'x^3 + '01'x^2 + '02' is selected specifically. This step can also be viewed as a multiplication by a particular matrix, b = Ca over GF256: ┌b0┐ ┌c0 c3 c2 c1┐┌a0┐ │b1│ = │c1 c0 c3 c2││a1│ │b2│ │c2 c1 c0 c3││a2│ └b3┘ └c3 c2 c1 c0┘└a3┘ (a)A polynomial c(x) is called self-invertibla if c(x)^2 = a (mod x^4 + 1). Show that every self-invertible one must be of the form ux^3 + (u+v)x + (u+v+1), where u and v are arbitrary elements of GF256. (b)The diffusion effect of the operation is cvaluated by the branch number: min a!=0 (W(a)+W(Ca)) where a is a 4-byte vector, C is the matrix multiplier, W is the weight of a vector (the number of non-zero entries). Show that the maximal branch number is 5. Remark: c(x) = '03'x^3 + '01'x^2 + '01'x + '02' in AES has branch number 5. (c)Show that the branch number of every self-invertible polynomial is less than or equal to 4. --

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