→ SilentHell :好像很缺p幣的樣子 07/22 19:29
課程名稱︰密碼學
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰數學系
考試日期（年月日）︰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