[試題] 95下 陳君明 密碼學 期中考
課程名稱︰密碼學
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰數學系
考試日期（年月日）︰2007/4/16
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Cryptography Midterm Exam I 2007/04/16
Part I (3 points each)
1. Which value of Legendre symbol or Jacoby symbol is correct?
A.(13/53) = -1 B.(15/55) = -1 C.(17/57) = -1
D.(19/59) = -1 E.None of the above
2. Denote h as a hash function, k as a key, m as a message, p1 and p2 as
padding strings. Which is the value of HMACk(m)?
A.h(k||m) B.h(m||k) C.h(k||p||m||k)
D.h(k||p1||h(k||p2||m)) E.None of the above
3. Whose size of the key space is approximately equal to the complexity of
finding a collision of SHA-224?
A.192-bit AES B.256-bit AES C.2-key Triple-DES
D.3-key Triple-DES E.None of the above
4. Which hash function is simply a truncated version of SHA-512, computed with
different initial values?
A.SHA-384 B.SHA-256 C.MD5 D.RIPEMD-160 E.None of the above
5. In which operation of AES, each set of four bytes in a state is treated as
a degree-3 polynomial over F256?
A.ByteSub B.MixColumn C.AddRoundKey D.ShifyRow
E.None of the above
6. By which mode of operation, a block cipher can be used to construct a
self-synchronizing stream cipher?
A.ECB B.CBC C.OFB D.CFB E.None of the above
7. Which value of Euler φ-function is NOT equal to 40?
A.φ(41) B.φ(75) C.φ(88) D.φ(132) E.None of the above
8. In a Feistel cipher, every encryption round consists of Li = Ri-1 and
A.Ri = Li-1⊕f(Ri-1,ki) B.Ri = Li-1⊕f(Li-1,ki)
C.Ri = Ri-1⊕f(Li-1,ki) D.Ri = Ri-1⊕f(Ri-1,ki)
E.None of the above
9. Which is true about the symmetric group S5?
A.|S5| = 60 B.<(1,2,3,4,5)> is a normal subgroup C.(S5:S4) = 10
D.(S5:<(1,2,3),(1,2)>) = 30 E.None of the above
10. Which statement is FALSE about the eSTREAM project?
A.The goal is to identify new stream ciphers that might become suitable
for widespread adoption
B.Profile 1 contains submissions of stream ciphers for hardware applications
with high throughput requirements
C.Profile 2 contains submissions of stream ciphers for hardware applications
with restricted resources such as liited storage, gate count, of power
consumption
D.Profile 1A or 2A contains stream ciphers satisfying Profile 1 of 2 with
an associated authentication method respectively
E.None of the above
Part II (3 points each)
#Consider the elliptic curve group defined by y^2 = x^3 + x over F23.
There are 23 points satisfying the equation as the graph below.
Let P = (1,5) and Q = (9,18).
The order of the elliptic curve group is <11>.
P+Q = <12>.
-Q = <13>.
2P = <14>.
4P = <15>.
2007P = <16>.
graph: (0,0)
(1,5) (1,18)
(9,5) (9,18)
(11,10) (11,13)
(13,5) (13,18)
(15,3) (15,20)
(16,8) (16,15)
(17,10) (17,13)
(18,10) (18,13)
(19,1) (19,22)
(20,3) (20,20)
(21,6) (21,17)
#Since P(x) = x^5 + 2x + 1 is irreducible over F3, the quotient ring
K = F3[x]/(P(x)) is a finite field. Let Q(x) = x^2 + 2x + 1.
The number of elements in K is |K| = <17>.
Q(x)^1213 = 2x^3 + <18> in K.
Q(x)^(-1) = x^4 + <19> in K.
To prove that P(x) is primitive, it is suffient to show x^m /= 1
and x^n /= 1 in K where m, n>0. We have min(m,n) = <20>.
#Consider the integer values of x satisfying
x = 11(mod 27) and x = 10(mod 29).
The smallest positive solution is x = <21>.
The largest negative solution is x = <22>.
#For a set G, we denote (G,+) as an additive group and (G,x) as a
multiplicative group respectively. Consider the gomomorphism
h:(Z,+) → (Z31*,x) defiend by h(x) = 4^x mod 31.
(Z/Ker(h),+) is isomorphic to (Zn,+) where n = <23>.
The index((Z31*,x) : (Im(h),x)) = <24>.
Apparently 4 is not a generator of the cyclic group (Z31*,x).
The smallest positive integer generating (Z31*,x) is <25>.
#Assume the periedic sequence 1,0,1,1,1,0,0,1,0,1,1,1,0,0, ...
of period 7 is generated by an LFSR(Linear Feedback Shify Register).
If the connection polynomial is primitive, it is <26>.
The linear complexity of the sequence is <27>.
#Determine the period of the sequence generated by LFSR of register length 8
with non-zero initial state and connection polynomial C(x).
C(x) = x^8 + x^5 + x^3 + x^2 + 1(primitive), then the period is <28>.
C(x) = x^8 + x^5 + x^4 + x^3 + 1(irreducible but not primitive), then
the period is <29>. (Hint: Less than 30)
C(x) = x^8 + x^5 + x^3 + 1(reducible), then the maximal possible
period is <30>.
Part III (Write down all details of your work)
31.(2 points)
Sketch the flow chart of CBC-MAC.
32.(3 points)
Sketch the flow chart of OFB mode(Output Feedback), including both
encryption and decryption.
A cryptographic hash function should satisfy 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 Pre-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".
33.(2 points)
Order the strength of the assumptions (A), (B), and (C).
That is, answer in the form of "L>M>N".
34.(3 points)
Prove your claim of the relation between (A) and (B).
Solution:
1 2 3 4 5 6 7 8 9 10
C D C A B D E A E B
11 12 13 14 15 16 17 18 19 20
24 (16,8) (9,5) (0,0) O(Infinity) (1,18) 243(3^5) x^2+2x+1 x^3+2x+1 22
21 22 23 24 25 26 27 28 29 30
416 -367 5 6 3 x^3+x^2+1 3 255 17 30
<1>a,0,-1,1 <3>.=.2^112 <9>120,[(12)(12345)(12) not belongs to <(12345)>],5,20
<10>Profile I for software applications <16>2007P = -P since 4P = O
<18>Q^(242x5+3) = Q^3, note (a+b)^p = a^p + b^p over Fp
<19>Extended Euclidean (GCD) algorithm: P(x) = (x^3+x^2+2)Q(x) + (x+2),
Q(x) = x(x+2) +1, so 1 = Q(x) = x(x+2) = Q(x) = x[P(x) - (P(x) - (x^3+x^2+2)
Q(x))] = -xP(x) + Q(x)(x^4+x^3+2x+1)
<20>min(242/2,242,11) <24>Im(h) = {1,2,4,8,16} <27>Shortest length of
generating LFSR
<28>2^8-1 <29>17|255 and C(x)|(x^17+1)
<33>B>C>A <34>Similar but not identical to the proof of Lemma 9.1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.79.198
推
07/28 00:48, , 1F
07/28 00:48, 1F
推
07/28 13:15, , 2F
07/28 13:15, 2F
推
07/28 14:28, , 3F
07/28 14:28, 3F
推
07/29 16:18, , 4F
07/29 16:18, 4F