課程名稱︰密碼學
課程性質︰數學系選修
課程教師︰陳君明
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰2010.6.22
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Cryptography Final Exam 2010/06/22
Part I (3 points each)
1.Which is a normal basis of GF64 over GF2 for a proper t belongs to GF64?
A.{t, t^2, t^3, t^4, t^5, t^6}
B.{t, t^2, t^4, t^8, t^16, t^32}
C.{1, t, t^2, t^3, t^4, t^5}
D.{1, t, t^2, t^4, t^8, t^16}
E.None of the above
2.On the elliptic curve group defined by y^2 = x^3 + ax + b over a prime field
(GFp), R = (xR,yR) is the sum of P = (xP,yP) and Q = (xQ,yQ). Which is xR?
(sll modulo p)
A.[(yP - yQ)/(xP - xQ)]^2 - xP - xQ
B.[(yP + yQ)/(xP + xQ)]^2 + xP + xQ
C.(yP - yQ)^2 - xP - xQ
D.(yP + yQ)^2 + xP + xQ
E.None of the above
3.On the elliptic curve group defined by y^2 + xy = x^3 + ax^2 + b over a
binary field (GF2^m), -P is the inverse of P = (xP,yP). Which is -P?
A.(xP,-yP)
B.(-xP,yP)
C.(xP,xP+yP)
D.(xP+yP,yP)
E.None of the above
4.Which is a public-key encryption scheme based on elliptic curves?
A.ECDH
B.ECIES
C.ECDSA
D.ECMQV
E.None of the above
5.Which is NOT a generator of a cyclic mltiplicative group of order 11 in Z89*?
A.3^(89-1)/11
B.6^(89-1)/11
C.9^(90-1)/11
D.12^(89-1)/11
E.None of the above
6.How many square roots of 1 in Z1155? i.e., the number of solutions to
x^2 = 1(mod 1155)
A.8
B.12
C.16
D.20
E.None of the above
7.To generate a large prime, how many times at least should the Miller-Rabin
test be repeated on a candidate integer to make sure the error probability
<= 10^(-12)?
A.8
B.12
C.16
D.20
E.None of the above
8.Which stream cipher is NOT in the portfolio of the eSTREAM project?
A.RC4
B.Trivium
C.Salsa20
D.Rabbit
E.None of the above
9.What is the fixed bit length of all outputs of the hash function SHA-1?
A.128
B.192
C.256
D.384
E.None of the above
10.Which should NOT be listed on a digital certificate?
A.Private key
B.User name
C.Expiry date
D.Serial number
E.None of the above
Part II (3 points each)
Alice and Bob will agree a key by ECDH (Elliptic Curve Diffie-Hellman) on the
group defined by y^2 = x^3 + 5x + 1 over GF23. G = (0,1) is taken as the base
point. Alice chooses a = 27 and sends A = 27G = (22,15) to Bob.
(0,1) (0,22) (4,4) (4,19) (5,6) (5,17) (8,1) (8,22) (9,14) (9,19) (10,4)(10,19)
(12,8) (12,15) (13,3) (13,20) (14,3) (14,20) (15,1) (15,22) (17,10) (17,13)
(18,9) (18,14) (19,3) (19,20) (21,11) (21,12) (22,8) (22,15)
y^2 = x^3 + 5x + 1 over F23
30 solutions
#The order of the clliptic curve group is <11>.
#A + 4G = <12>
#Bob chooses b = 3 and sends B = <13> to Alice.
#The agreed key comes from the x-coordinate of the point nG = <14>, where n =
<15>
An RSA signature scheme is operated with the public modulus n = 133 = 7x19.
#φ(133) = <16>, the value of Euler φ-function for n.
#If the public exponent for verifacation is e = 5, the corresponding private
key for signing is d = <17>.
#Signing the message m = 3, the user obtains its digital signature s = <18>.
In Shamir's secret sharing scheme with threshold 3 over GF19, the secret a0 is
hided as the constant of the polynomial f(x) = a2x^2 + a1x + a0 belongs to
GF19[x].
#The points(1,8), (3,18), (5,6) that f(x) passes are obtained from three
participants, then the secret is recovered as a0 = <19>.
#The point (2,y) is also distributed to another participant, then y = <20>.
Complete the signature generation algorithm of ECDSA(Elliptic Curve Digital
Signature Algorithm). Note that domain parameters for ECDSA are of the form
(q,FR,a,b,G,n,h), where q is the field size, FR is an indication of the basis
used, a and b are two field elements that define the equation of the curve, G
is a base point of prime order on the curve(i.e., G = (xG,yG)), n is the order
of the point G, and h is the cofactor (swhich is equal to the order of the
curve divided by n). Let Ln be the bit length of the group order n.
#The private key d is a randomly selected integer in the interval[1,n-1].
The corresponding public key is a point P on the curve, where P = <21>.
#To sign a message m, the following steps are executed:
1.Calculate e = HASH(m). Let z be the Ln leftmost bits of e.
2.Select a random integer k from [1,n-1].
3.Calculate r = x1(mod n), where (x1,y1) = kG. If r = 0, go back to step 2.
4.Calculate s = k^(-1)(<22>)(mod n). If s = 0, go back to step 2.
5.The signature is the pair(r,s)
#From 12860^2 ≡ 5185^2 (mod 123107), the prime factorization 123107 = pxq is
obtained as p = <23> and q = <24> with p > q.
For a 32-bit machine and 64-bit numbers, x = x1 2^32 + x0 and y = y1 2^32 + y0
are multiplied by Karatsuba technique which requires 3 multiplications instead
of 4.
#Compute A = x1‧y1, B = x0‧y0, and C = <25> (in terms of x0, x1, y0, y1).
#Then x‧y is given by A2^64 + Ds^32 + B, where D = <26> (in terms or A, B, C).
The sequence 1,0,0,1,1,0,1,0,1,1,... is generated by an LFSR(linear feedback
shift register) of linear complexity 4.
#The period of the sequence is <27>.
#The next three bits(11th ~ 13th bit) of the sequence are <28>.
Complete the Left-to-Right binary exponentiation algorithm:
INPUT: P and k = (k[t-1],..., k1, k0)2
OUTPUT:P^k
1.Q←1
2.For i from t-1 downto 0 do
2.1 Q ← <29>
2.2 If k[i] = 1 then Q ← <30>
3.Return(Q)
Part III (Write down all details of your work)
<31>(3 points) Let n = 6601. Show that a^n = a (mod n) for every integer a,
i.e., 6601 is a Carmichael number. Hint:Chinese Remainder Theorem.
<32>(7 points) NSA Suite B is a set of cryptographic algorithms promulated by
NationalSecurity Agency as part of its Cryptographic Modernization Program.
#Describe the components of Suite B for the usage of (1)symmetric encryption,
(2)digital signature, (3)key agreement, and (4) mesage digest, respectively.
#Specify these algorithms with key size, output size, of base field size, such
that they are sufficient for protecting classified information up to the Secret
level.
#Specify these algorithms with key size, output size, or base field size, such
that they are neccessary for the protection of Top Secret information.
Solution
1 2 3 4 5 6 7 8 9 10
B A C B D C D A E A
11 12 13 14 15 16 17 18 19 20
31 O(points at infinity) (13,3) (17,13) 81(or 19) 108 65 125 9 11
21 22 23 24 25 26 27 28 29 30
dG z+rd 401 307 (x1+x0)(y1+y0) C-A-B 15 1,1,0 Q^2 QxP
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.69.180