課程名稱︰密碼學
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰數學系
考試日期（年月日）︰2008/06/02
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Part I (3 points each)
1.For RSA modulus N=10403=101x103, which can NOT be a public exponent e?
A.11 B.13 C.17 D.19 E.None of the above
2. Apply Fermat's primality test on 21. Which is NOT a witness of compositeness?
A.2 B.4 C.5 D.8 E.None of the above
3.What is the output length (in bits) of the hash function SHA-1?
A.128 B.144 C.160 D.192 E.None of the above
4.The branch number in the case of MixColumn operation of AES is defined by
min[a/=0]W(a)+W(F(a)), where a is a 4-bute vector, F is a linear
transformation, and W is the weight funtion. What is the maximal branch
number?
A.5 B.6 C.7 D.8 E.None of the above
5.Apply the Miller-Rabin test t times to an odd composite number. Which is the
best estimate of the probability of finding at least one witness of
compositeness?
A.(1/2)^t B.(3/4)^t C.1-(3/4)^t D.1-(1/2)^t E.1-(1/4)^t
6.Which item is definitely NOT listed on a certificate?
A.Public key B.Private key C.User name D.Expiry date E.None of the above
7.Which statemant is FALSE about PKI?
A.SSL aims to provide channel security to fulfill commercial requirement
B.X509 defines a structure for public key certificates
C.CA establishes the identity of users, but does not sign certificates
D.CRL is a list of the serial numbers of all the revoked certificates
E.None of the above
8.Which statement is FALSE about Merkle-Damgard construcion of hash functions?
A.Use a collision-resistant compression function f with arbitrary length of
input
B.Add a single one bit to signal the end of a message, then pad with zeros
C.The final block encodes the original length of the unpadded message in bits
D.The internal state H:=f(H||mi) is updated repeatedly with message block mi
E.None of the above
9.Which property is NOT provided by digital signature schemes?
A.Message confidentiality
B.Non-repudiation
C.Authentication
D.Message integrity
E.None of the above
10.A cryptographic hash function should satisgy 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 Pri-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". Which relation is
correct?
A.(c)>(b)>(a) B.(b)>(a)>(c) C.(a)>(c)>(b) D.(c)>(a)>(b) E.None of the
above
Part II (3 points each)
‧Represent F16 by polynomial reptesentations with the irreducible f(x)=x^4+x+1
Choosing g=(0010)as a generator for F16, we list all element of F16 as
follows.
0=(0000) g^0=(0001) g^1=(0010) g^2=(0100)
g^3(1000) g^4=(0011) g^5=(0110) g^6=(1100)
g^7(1011) g^8=(0101) g^9=(1010) g^10=(0111)
g11=(1110) g^12=(1111) g^13=(1101) g^14=(1001)
Consider the elliptic curve group G defined by y^2+xy=x^3+g^4x^2+1 over F16
There are 15 points satisfying the equation as graph
Let P=(1,g^6) and Q=(g^5,g^11)
The group order |G|=11
P+Q=12
-Q=13
2P=14
4P=15
y
0 .
g^14 .
g^13 . . .
g^12 .
g^11 .
g^10 .
g^9
g^8 . . .
g^7
g^6 .
g^5
g^4
g^3 .
g^2
g .
.
g g^2 g^3 g^4 g^5 g^6 g^7 g^8 g^9 g^10 g^11 g^12 g^13 g^14 0 x
The formulas in Part III might help your computations.
Factor n=87463 with the Quadratic Sieve. Define g(x)=x^2-n.
x -1 2 3 13 17 19 29
265 1 1 1 0 1 0 0
278 1 0 1 1 0 0 1
296 0 0 0 0 1 0 0
299 0 1 1 0 1 1 0
307 0 1 0 1 0 0 1
316 0 0 0 0 1 0 0
x 2 3 13 17 19 29 x^2-n splits
261 X X
262 X X
263 X X
264
265 X X X X -2x3x13^2x17
266 X
267 X
268 X X
269 X X
270
271 X X X
272 X
273 X X
274 X
275 X X
276
277 X X
278 X X X
279 X X -3^3x13x29
280 X X
296 X X 3^2x17
297 X
298 X
299 X X X X 2x3x17x19
300
301 X X
302 X X
303 X
304 X X
305 X X
306
307 X X X X 2x3^2x13x29
308 X
309 X X
310 X
311 X X
312
313 X X X
314 X
315 X
316 X X 3^6x17
The integers x1, x2, and b satisfy
g(265) x g(278) x g(x1) x g(x2) = b^2(mod n)
If 0<x1<x2, then x2 = 16
If 0<b<n, then b=17
If a=265x278x(x1)x(x2) (mod n)
and 0<a<n, then a=18
If n=pxq and 0<p<q,
then p=19 and q=20
These congruences might reduce your comprtational effort:
265x307=81355=-6108(mod n)
265x316=83740=-3723(mod n)
278x296=82288=-5175(mod n)
278x299=83122=-4341(mod n)
3^5x13x17x19=-16947(mod n)
3^4x13^2x17x29=14026(mod n)
The solution to the system of congruences
2x=3(mod 7) 3x=6(mod 11) 4x=10(mpd 13)
is x=21(mod 22)
Consider the RSA signature scheme with the prblic key n=85 and e=3.
The private key for signing is d=23
Signing the message m=4, a user obtains its digital signature s=24
In a Diffie-Hellman key exchange scheme on Z31 with the generator g=3,
Alice chooses 9 nd Bob chooses 7 in private. Then Alice sends 25 to Bob,
and the agreed key is 26
Decrypting the ciphertext c=39 of the Rabub public-key cryptosystem c=mx(m+10)
(mod 187), a user obtains four possible corresponding plaintexts m=3, 20, 27,
and 28(in increasing order)
If a message m is divided into t blocks m1, m2, ..., mt, then the CBC-MAC
with a cipger e and a key k is derived by the process I1=m1, O1=ek(I1),
Ii=mi + 29, and Oi=30 for i=2, 3, ..., t.
Part III (Write down all details of your work)
31(5 points)
Derive arithmetic formulas of elliptic curve groups defined by
y^2+xy=x^3+ax^2+b withb/=0 over F2m.
(a)P1=(x1,y1)and P2=(x2,y2) are two distinct points on the curve with P1 /= -P2
If (x3y3)=P1+P2 and s=(y1+y2)/(x1+x2), show that x3=s^2+s+x1+x2+a
and y3=s(x1+x3)+x3+y1
(b)P0=(x0,y0)is a point on the curve with x0/=0. If (x4,y4)=2P, show that
x4=x0^2+(b/x0^2) and y4=x0^2+x4(y0/x0 +x0+1)
32(5 points)
As the MixColumn operation of AES, we work on polynomials of degree 3 over F256
Let a(x)=a3(x+1)^3 + a2(x+1)^2 +a1(x+1)+a0 and
(a)If a(x)b(x)=1(mod(x^4 +1)), show that
(i)b0=a0^-1
(ii)b1=a1b0a0^-1
(Also b2=(a2b0+a1b1)a0^-1 and b3=(a3b0+a2b1+a1b2)a0^-1, but you do not have
to show them.)
(b)Find all self-inverse polynomials. That is, indicate the conditions on a(x)
such that a(x)^2=1(mod(x^4 +1)). Prove your claim.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.80.176