課程性質︰數學系選修
課程教師︰陳君明
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰2018 年 5 月 8 日
考試時限（分鐘）：15:30 ~ 18:20 (不延長)
注意事項：考試時會發一張標準期考作答卷當作計算紙，答案則是填在題本的最後一頁。
試題 :
Cryptography Midterm Exam 2018/05/08
Part I (3 points each)
1. Which can NOT be the number of elements of a Galois field?
A. 21 B. 23 C. 25 D. 27 E. None of the above
2. How many irreducible polynomials of degree 9 over GF_2?
Hint: Factor x^(2^9) - x.
A. 53 B. 55 C. 57 D. 59 E. None of the above
3. Suppose α ∈ GF_8 is a root of x^3 + x + 1. Whose minimal polynomial is
x^3 + x^2 + 1?
A. α^2 B. α^3 + α^2 C. α^4 D. α^4 + α^2 E. None of the above
4. Which group is isomorphic to the Klein-4 group (Z_8*, *)?
A. (Z_4, +) B. (Z_5*, *) C. (Z_10*, *) D. (Z_12*, *) E. None of the above
5. Which ideal is NOT the same as the principal ideal <6> in Z?
A. <-6, 42> B. <36, 48> C. <18, -24> D. <30, 60, 72> E. None of the above
6. Which is NOT a finalist of the AES (Advanced Encryption Standard)
competition?
A. Rijndael B. Serpent C. Twofish D. RC4 E. None of the above
7. 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
8. 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 ⊕ m{i-1}) B. mi = dk(ci) ⊕ c{i-1}
C. mi = dk(ci ⊕ c{i-1}) D. mi = dk(ci) ⊕ m{i-1} E. None of the above
9. Which can NOT replace the square matrix in the affine transformation
constructing the S-box of AES to become a new block cipher?
A. [10001110] B. [11010110] C. [10001001] D. [01010010]
[01000111] [01101011] [11000100] [00101001]
[10100011] [10110101] [01100010] [10010100]
[11010001] [11011010] [00110001] [01001010]
[11101000] [01101101] [10011000] [00100101]
[01110100] [10110110] [01001100] [10010010]
[00111010] [01011011] [00100110] [01001001]
[00011101] [10101101] [00010011] [10100100]
E. None of the above
10. In a Feistel cipher, every encryption round consists of Li = R{i-1} and
A. Ri = R{i-1} ⊕ f(L{i-1}, ki) B. Ri = R{i-1} ⊕ f(R{i-1}, ki)
C. Ri = L{i-1} ⊕ f(R{i-1}, ki) D. Ri = L{i-1} ⊕ f(L{i-1}, ki)
E. None of the above
Part II (3 points each)
* Euclidean Algorithm
* GCD(80837, 88603) = ___.
* a = ___ and b = ___ is the pair of integers satisfying 17 a + 43 b = 1
where a is the least positive one.
* The least positive solution to the equation 85 x ≡ 10 (mod 43) is ___.
* Consider the multiplicative group G = (Z_15*, * mod 15).
* The order of the group, |G| = ___.
* G has 4 elements of order 4: 2, 8, 13, and ___.
* G has 3 subgroups with 2 elements: {1, 4}, {1, 14}, and ___.
* G has 3 subgroups with 4 elements: {1, 2, 4, 8}, {1, 4, 11, 14}, and ___.
* Consider the quotient ring Rm = GF_5[x] / <x^2 + 4x + m> where m ∈ GF_5.
* For any specific value of m, the number of the elements in Rm is ___.
* Rm is a field for m = 2 and m = ___.
* The multiplicative inverse of x + 2 in R_2 (for m = 2) is ___.
* To show that x^2 + 4x + 2 is a primitive polynomial over GF_5, it suffices
to verify x^8≠1 and x^n≠1 in R^2 where n = ___.
* Complete the table for DES, Triple DES (3DES), and AES:
_______________________________________________________________
| |
| | DES | Triple DES | AES |
| Key Length (bits) | 56 | 112 | 168 | 128 192 256 |
| Block Length (bits) | ????? | 128 |
| Number of Rounds | 16 | 48 | ??? 12 14 |
| Number of Different S-box(s) | 8 | 1 |
|_______________________________________________________________|
* A simple PRNG, Linear Congruential Generator, is generated by a recursive
formula S{i+1} = A * S{i} + B mod m, where A, B, and the seed S{0} are kept
secret. Suppose m = 31, and the first three outputs S{1} = 18, S{2} = 4, and
S{3} = 17 are obtained, then S{4} = ___ and S{5} = ___. All the following
output Si's are predictable, which's very bad for cryptographic applications.
* The following reference 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 (20 entries in each row) are built by the primitive element x+1 of
GF_2[x] / < m(x) > ~= GF_256. (~=: isomorphic).
* (x + 1)^n mod m(x) = x^4 + x^2 + x, then n = ___.
* (x + 1)^100 mod m(x) = ___ (a polynomial in GF_2[x] of degree < 8)
* (x^5 + x^3)^(-1) mod m(x) = ___ (a polynomial in GF_2[x] of degree < 8)
* Complete the subroutine computing patched multiplicative inverses in
GF_256:
word8 inverse(word8 a) {
if (a) return Alogtable[ ___ ];
else return 0;
}
Part III (Write down all details of your work)
31. (3 points) Prove that the identity element e in a group G is unique.
32. (3 points) In the design of AES, the Galois field GF_256 ~= GF_2[x] /
< x^8 + x^4 + x^3 + x + 1 > is represented with the polynomial basis {1, x,
x^2, x^3, x^4, x^5, x^6, x^7}. The normal basis might be a better choice
for hardware implementation. Show that the square operation of an element
in GF_256 represented with the normal basis {x, x^2, x^(2^2), x^(2^3),
x^(2^4), x^(2^5), x^(2^6), x^(2^7)} is executed as a rotation by one bit.
33. (4 points) To show that the Galois field GF_8 is unique up to isomorphism,
construct an isomorphism between the quotient rings
R1 = GF_2[x] / < x^3 + x^2 + 1 > and R2 = GF_2[x] / < x^3 + x + 1 >.
That is, determine h(x) ∈ GF_2[x] such that the homomorphism f: R1 → R2
defined by f([0]) = [0], f([1]) = [1], and f([x]) = [h(x)] is one-to-one
and onto, where [t] denotes the coset which t belongs to. Explain why your
choice is correct.