課程名稱︰
課程性質︰陳君明
課程教師︰
開課學院：
開課系所︰數學系
考試日期（年月日）︰2007/6/11
考試時限（分鐘）：約180分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 : (Midterm Exam II, C )
Part I (3 points each)
1. Which property is not provided by digital signature schemes?
A. Message integrity B. Authentication C. Non-repudiation
D. Message confidentiality E. None of the above
2. Which hard problem is the security of the ElGamal encryption based on?
A. Graph isomorphism B. Integer factoring C. Discrete logarithm
D. Squre root modulo a composite E. None of the above
3. Given an abelian group(G,×) and gεG, consider the following problems.
◆ DDH: Given a = g^x, b = g^y, c = g^z. Determine if z=xy.
◆ DHP: Given a = g^x and b = g^y. Find c = g^(xy).
◆ DLP: Given hεG such that h = g^x. Find x.
A ≦p B means "A is reducible to B in polynomial time".
Which relation is correct? A. DDH ≦p DLP ≦p DHP
B. DHP ≦p DLP ≦p DDH C. DHP ≦p DDH ≦p DLP
D. DLP ≦p DDH ≦p DHP E. None of the above
4. Apply Fermat's primality test on 15. Which is NOT a witness of
compositeness?
A. 2 B. 4 C. 7 D. 8 E. None of the above
5. Assuming the 160-bit security for the group order on elliptic curves, which
is the message size for the SIGNED Diffie-Hellman protocol(EC-DH + EC-DSA)?
A. 160 B.320 C. 480 D. 640 E. None of the above
6. To compute (x1*2^32 + x0 ) × (y1*2^32 + y0 ) with Karatsuba multiplication
where x0,x1,y0, and y1 are 32-bit numbers, which multiplication is NOT
necessary to perform?
A. x1 × y1 B. x0 × y1 C. x0 × y0 D. (x0+x1)×(y0+y1)
E. None of the above
7. Which algorithm for solving the discrete logarithm problem has
sub-exponential time complexity?
A. Index-calculus B. Pohlig-Hellman C.Baby-Step/Giant-Step
D. Pollard's ρ method E. None of the above
8. Which statement is FALSE about Identity Based Cryptography?
A.Its first signature scheme is based on the discrete logarithn problem
B.Its first encryption scheme is based on bilinear paring on elliptic curves
C.It removes the need for storage and transmission of certificates
D.It does not remove the need for a trusted third party
E.None of the above
9. Which statement is FALSE about PKI?
A. PGP aims to provide channel security to fulfill commercial requirement
B. X509 defines a structure for public key certificates
C. CRL is a list of the serial numbers of all the revoked certificates
D. RA established the identity of users, but does not sign certificates
E. None of the above
10.Which statement is FALSE about digital signature schemes?
A. Schnorr signature scheme has provable security
B. Nyberg-Rueppel scheme has the property of message recovery
C. Hash functions make signature schemes efficient for long messages
D. To achieve the same security level, DSA on prime fields has better
efficiency than EC-DSA on elliptic-curves
E. None of the above
Part II (3 points each)
˙ Miller-Rabin primality test
◆ The test is base on this fact: If a≠±1(mod n) but 【11】(mod n),
then n must be a composite.
◆ To generate a large prime, Miller-Rabin test should be repeated on
a candidate integer at least 【12】 times to make sure the error
probability ≦ 10^(-9).
˙ The ciphertext c=66 was encrypted by Rabin public-key cryptosystem
c = m × (m+20) (mod 221). All four possible corresponding plaintexts are
m = 49, 100, 【13】, and 【14】 (increasing order).
˙ Consider the Diffie-Hellman key exange scheme on Z19 with the generator
g=2. If Alice sent Bob 16 and agreed the key was 17, what did Bob send
Alice? There are two possibilities: 【15】 and 【16】.
˙ N = 43739 = p×q satisfies: 296^2 = 138 = 2×3×23 (mod N)
302^2 = 3726 = 2×3^4×23 (mod N)
305^2 = 5547 = 3×43^2 (mod N)
363^2 = 552 = 2^3×3×23 (mod N)
373^2 = 7912 = 2^3×23×43(mod N)
◆ To factor N, we compute gcd(a,N) which is likely to be a proper factor
of N, where a = 【17】 is derived from the above relations.
◆ Assume the prime factors p>q, then p = 【18】.
˙ Let A be a 4×4 invertible matrix over Z7 with the minimal polynomial
4 3
x + 6x + 2x + 4.
2007 2006 2004 2003
◆ Suppose 5A + 2A + 3A + cA = O, then c = 【19】
◆ b and x are two column vectors satisfying Ax = b. Expressing x in terms
i 3
of b and A with i > 0, we have x = 5A b + 【20】
(按: 助教提醒格子內可能有不只一項)
˙ Perform XL algorithm to solve a system of 10 quadratic equations in 7
variables. Select D = 4 to be the degree to reach. Multiply every equation
by all possible monomials of degree≦2.
◆ Now the number of equations is R = 【21】.
◆ The number of monomials of total degree≦D is T = 【22】.
˙ Suppose a user wishes to be authenticated to a building with a smart card
which performs Schnorr signature scheme. Let G = <g> be a group of prime
order q. Let x be the secret key and y = g^x be the public key. Denote the
card as C and the card reader as R. Then the protocl is:
◆[Commitment] C --> R: r = g^k where k is random
◆[Challenge] R --> C: a random value m
◆[Response] C --> R: s = 【23】 (mod q)
◆[Verification] C accepts the signature s if r = 【24】
˙ Fast modular exponentiation:
◆ 18^2007 mod 23 = 【25】.
◆ 524^2007 mod 667 = 【26】. (Hint: Tricks speeding up RSA decryptions)
˙ N = 40741 = p×q has the value of Euler ψ-function ψ(N) = 40300.
◆ Assume the prime factors p>q, then p =【27】
◆ If N is used as an RSA modulus and the public exponet e = 3, then the
private exponent d = 【28】.
˙ Solve 5^x = 219 (mod 307) with Baby-Step/Giant-Step algorithm. Derived
from the tables below, the solution is x =【29】(0<x<307) corresponding to
k = 【30】. Here we have 5^(-18) = 235 (mod 307).
Baby Steps: i 0 1 2 3 4 5 6 7 8
5^i 1 5 25 125 11 55 275 147 121
i 9 10 11 12 13 14 15 16 17
5^i 298 262 82 103 208 119 288 212 139
Giant Steps:
k 0 1 2 3 4 5 6 7 8
219×5^(-18k) 219 196 10 201 264 26 277 11 129
k 9 10 11 12 13 14 15 16 17
219×5^(-18k) 229 90 274 227 234 37 99 240 219
Part III (Write down all details of your work)
【31】(6 points)
Consider the following commitment scheme:
◆ G = <g> is a group of prime order q
◆ h = g^x ε G but neither Alice nor Bob knows x
◆ To commit to a a value aε{0,...,q-1}, Alice generates
bε{0,...,q-1} at random and compute c = g^a h^b
◆ To reveal the commitment, Alice sends Bob a and b
(1) Is the scheme Perfectly Binding or Computationally Binding?
Explain your answer.
(2) Is the scheme Perfectly Concealing or Computationally Binding?
Explain your answer.
【32】(4 points)
Suppose the public exponent e = 3 is used by three users with the public
moduli N1,N2, and N3. If somebody else encrypts the same message m and
sends the ciphertext c1,c2, and c3 to them respectively, explain how an
attacker can obtain the plaintext m from the above ciphertext and the
public information.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.208.23
※ 編輯: agra 來自: 61.230.208.23 (06/16 02:43)