課程名稱︰密碼學 課程性質︰選修 課程教師︰陳君明 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰2012/5/1 考試時限（分鐘）：180 min 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Part I (3 points each) 1. Which multiplicative group is NOT cyclic? A. Z9* B. Z10* C. Z11* D. Z12* E. None of the above 2. Which can NOT be the number of element of a Galois Field? A. 100 B. 101 C. 121 D. 125 E. None of the above 3. Which is NOT a legitimate key length (in bits) of AES? A. 128 B. 160 C. 192 D. 256 E. None of the above 4. Which of the following is a public-key cryptosystem? A. RSA B. DES C. AES D. Caesar cipher E. None of the above 5. For a ring homomorphism f: GF2[x]/<x^3+x^2+1> -> GF2[x]/<x^3+x+1> between two quotient rings(=GF8), which assignment of f(x) makes f an isomorphism? A. f(x)=x B. f(x)=x^2 C. f(x)=x+1 D. f(x)=x^2+x E. None of the above 6. Except "Key Addition", what is the correct order of operations in a typical round of AES? (P) MixColumn (Q) SubByte (R) ShiftRow A. RPQ B. RQP C. QPR D. PRQ E. None of the above 7. Which quotient ring is NOT isomorphic to GF32? A. GF2[x]/<x^5+x^2+1> B. GF2[x]/<x^5+x^4+x^2+x+1> C. GF2[x]/<x^5+x+1> D. GF2[x]/<x^5+x^3+x^2+x+1> E. None of the above 8. Which of the following is TRUE? A. There are exactly φ(2^2012-1)/2012 primitive polynomials of degree 2012 over GF2 B. There are exactly 2^2012-1 grnerators of (GF(2^2012)*, ×) C. There are exactly 2^2012 roots of x^(2^2012)=1 in GF(2^2012) D. There are exactly 2012 subfields in GF(2^2012) E. None of the above 9. Which statement is true for GF9[x]? A. A ring but not a commutative ring B. A commutative ring but not an integral domain C. An integral domain but not a principle ideal domain D. A principle ideal domain but not a field E. A field 10. Which statement is true for historical ciphers? (To avoid possible confusion,a polyalphabetic substitution cipher is not considered as a substitution cipher) A. A Vigenere cipher is a special case of substitution ciphers B. A Substitution cipher is a special case of Hill ciphers C. A Hill cipher is a special case of permutation ciphers D. A permutation cipher is aspecial case of Vigenere ciphers E. None of the above Part II (3 points each) a=[11] and b=[12] is the pair of integers satisfying 56a+71b=1 where a is the least positive one. The solution to the equation 56x≡4(mod 71) is x≡[13](mod 71) (between 0 and 71) Complete the table Block cipher DES/3DES AES Block size(bits) [14] [15] x≡[16](mod [17]) is the solution to the system of congruences x≡5(mod 9) x≡2(mod 8) x≡4(mod 7) Euler's Theorem and Fermat Little Theorem The least positive integer m satisfying 52^m≡1(mod 2011) is m≡[18] 2^2012 mod 41 = [19] (between 0 and 41) 2^2012 mod 42 = [20] (between 0 and 42) Applying the secret permutation ╭1 2 3 4 5 6╮ │ │belongs to S6 on the plaintext CRYPTO, we obtain the ╰4 6 3 1 2 5╯ ciphertext PTYCOR. Suppose the permutation σbelongs to S6 is applied on CRYPTO to obtain OCTYPR, then σ^2 = [21] and σ^-1 = [22] The following regerence code comes from the book "The Design of Rijndael" 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, 77,228,166,114,154,201, 9,120, 101, 47,138, 5, 33, 15,225, 36, 18,240,130, 69, 53,147,218,142, 150,143,219,189, 54,208,206,148, 19, 92,210,241, 64, 70,131, 56, 102,221,253, 48,191, 6,139, 98,179, 37,226,152, 34,136,145, 16, 126,110, 72,195,163,182, 30, 66, 58,107, 40, 84,250,133, 61,186, 43,121, 10, 21,155,159, 94,202, 78,212,172,229,243,115,167, 87, 175, 88,168, 80,244,234,214,116, 79,174,233,213,231,230,173,232, 44,215,117,122,235, 22, 11,245, 89,203, 95,176,156,169, 81,160, 127, 12,246,111, 23,196, 73,236,216, 67, 31, 45,164,118,123,183, 204,187, 62, 90,251, 96,177,134, 59, 82,161,108,170, 85, 41,157, 151,178,135,144, 97,190,220,252,188,149,207,205, 55, 63, 91,209, 83, 57,132, 60, 65,162,109, 71, 20, 42,158, 93, 86,242,211,171, 68, 17,146,217, 35, 32, 46,137,180,124,184, 38,119,153,227,165, 103, 74,237,222,197, 49,254, 24, 13, 99,140,128,192,247,112, 7}; word8 Alogtable[256] = { 1, 3, 5, 15, 17, 51, 85,255, 26, 46,114,150,161,248, 19, 53, 95,225, 56, 72,216,115,149,164,247, 2, 6, 10, 30, 34,102,170, 229, 52, 92,228, 55, 89,235, 38,106,190,217,112,144,171,230, 49, 83,245, 4, 12, 20, 60, 68,204, 79,209,104,184,211,110,178,205, 76,212,103,169,224, 59, 77,215, 98,166,241, 8, 24, 40,120,136, 131,158,185,208,107,189,220,127,129,152,179,206, 73,219,118,154, 181,196, 87,249, 16, 48, 80,240, 11, 29, 39,105,187,214, 97,163, 254, 25, 43,125,135,146,173,236, 47,113,147,174,233, 32, 96,160, 251, 22, 58, 78,210,109,183,194, 93,231, 50, 86,250, 21, 63, 65, 195, 94,226, 61, 71,201, 64,192, 91,237, 44,116,156,191,218,117, 159,186,213,100,172,239, 42,126,130,157,188,223,122,142,137,128, 155,182,193, 88,232, 35,101,175,234, 37,111,177,200, 67,197, 84, 252, 31, 33, 99,165,244, 7, 9, 27, 45,119,153,176,203, 70,202, 69,207, 74,222,121,139,134,145,168,227, 62, 66,198, 81,243, 14, 18, 54, 90,238, 41,123,141,140,143,138,133,148,167,242, 13, 23, 57, 75,221,124,132,151,162,253, 28, 36,108,180,199, 82,246, 1}; /* 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[b])%255]; else return 0; } GF256 is generated by m(x)=x^8+x^4+x^3+x+1 in AES. The above tables are built by the primitive element x+1 of GF2[x]/<m(x)> = GF256. To show that x+1 is a primitive element GF2[x]/<m(x)>, it is sufficient to verity that (x+1)^u≠1, (x+1)^v≠1, and (x+1)^w≠1. If 1<u<v<w<256, then v=[23] and w=[24]. If x^8+x^4+g(x) is primitive polynomial over GF2, then the degree-3 polynomial g(x)=[25] Experss the elements of GF256 in hexadecimal as AES does, then '8A'+'5F'=[26], '8A'*'5F'=[27], ('8A')^100=[28], ('5F')^-1=[29] (all in hexadecimal) Finish the subroutine computing patched multiplicative inverses in GF256: word8 inverse(word8 a) { if(a) return Alogtable[ [30] ]; else return 0; } Part III (Write down all details of your work) [31] (3 points) Prove that thedientity e in a group G is unique. [32] (7 points) (i) Find the minimal number A>1, such that A is NOT the order of a finite field (ii) Find the minimal number B>1, such that 4B is NOT the order of the multiplicative group(Zn*, ×) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.138 ※ 編輯: fei6409 來自: 140.112.30.138 (05/02 15:09)