課程名稱︰密碼學
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰
考試日期（年月日）︰2009/4/14
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Cryptography Midterm Exam 2009/04/14
Part I (3 points each)
1. For a group homomorphism f:(Z10, + mod 10)→(Z11, x mod 11), which
assignment of the value of f(1) makes f an isomorphism?
A.3 B.5 C.7 D.9 E.None of the above
2. For RSA modulus N = 4087 = 61 x 67, which can NOT be a public exponent e?
A.11 B.13 C.17 D.19 E.None of the above
3. Which group is isomorphic to the Klein-4 group (Z8*,x)?
A.(Z4,+) B.(Z5*,x) C.(Z10*,x) D.(Z12*,x)
E.None of the above
4. Which multiplicatie group is NOT of order 12?
A.Z13* B.Z21* C.Z28* D.Z36* E.None of the above
5. Which is a normal basis of GF(2^5) over GF(2) with t belongs to GF(2^5)?
A.{1,t,t^2,t^3,t^4} B.{t,t^2,t^4,t^6,t^8}
C.{1,t,t^2,t^4,t^8} D.{t,t^2,t^4,t^8,t^16}
E.None of the above
6. Which quotient ring is isomorphic to GF(2^5)?
A.GF(2)[x]/<x^5+x^2+1> B.GF(2)[x]/<x^5+x^3+x^2+1>
C.GF(2)[x]/<x^5+x+1> D.GF(2)[x]/<x^5+x^3+x+1>
E.None of the above
7. Which irreducible ploynomial is primitive over GF(2)?
A.x^6+x^5+x^4+x^2+1 B.x^6+x^3+1 C.x^6+x^4+x^2+x+1
D.x^6+x+1 E.NOne of the above
8. A cipher E encrypts 6 hexadecimal digits in the way of E(123456) = 416235
and E(1C5A3F) = A1FC53. Which category does this cipher belong to?
A.Substitution cipher B.Permutation cipher
C.Vigenere cipher D.Shift cipher E.None of the above
9. Which assumption ensures the security of ELGamal encryption against
chosen plaintext attacks?
A.Discrete Logarithm Problem is hard B.Square Root Problem is hard
C.Diffie-Hellman Problem is hard D.Factoring Problem is hard
E.None of the above
10. Which is NOT proved or disproved yet about Rabin of RSA encryption schemes
with mofulus n = pq, public exponent e, and private exponent d?
A.Breaking Rabin encryption is equivalent to factoring n
B.Breaking RSA encryption is equvalent to factoring n
C.Knowing d is equivalent to facoring n
D.Knowing ψ(n) is equivalent to factoring n
E.None of the above
Part II (3 points each)
#x = <11> (mod <12>) is the solution to the system of congruences
4x = 1 (mod 7) 5x = 4 (mod 9) 6x = 9 (mod 11)
#The prime numbers p = <13> and q = <14> with p>q satisfy
n = pxq = 43423 and ψ(n) = 43000.
#In the multiplicative group (Z33*,x):
26^(-1)(the multiplicatie inverse of 26) = <15>
0(4)(the order of 4) = <16>
#GL2(Z13) is the group of inertible 2x2 matrices with entries in Z13, and
SL2(Z13) is its subgroup consisting of the matrices with determinant 1.
Their group orders are |GL2(Z13)| = <17> and |SL2(Z13)| = <18>
#Complete the following algorithm of scalar multiplication on a given elliptic
curve group. It is similar to the right-to-left square-and- multiply
exponentiation.
INPUT:a point P on the curve, a positive integer
k = (k[t-1], ... , k1, k0)2
OUTPUT:the point kP on the curve
1.R←∞ (O:point at infinity)
2.For i from 0 to t-1 do
2.1 If ki = 1 then R←<19>
2.2 P←<20>
3.Return (R)
#Consider RSA encryption with the public key n = 187 and e = 3.
The private key for decryption is d = <21>
The ciphertext c = <22> is obtained by encrypting the message m = 11.
#Consider ELGamal encryption with the domain paramters p = 47, and g = 4 as a
generator of the subgroup with order 23 of Z47*.
Alice;s private key is a = 3, then her public key is
(p,g,h) = (47,4,<23>)
The ciphertext(c1,c2) = (37,11) is obtained from Bob, where
c1 = g^k mod p and k is a random ephemeral key chosen by him. Then
the corresponding plaintext is m = <24>
#Break the Hill cipher with a knownn-plaintext attack. Its encryption is
defined by c = pM mod 5, where M belongs to GL2(Z5), p = [p1 p2] and
c = [c1 c2] are plaintext and ciphertext respectively.
Two known pairs of plaintexts and ciphertestx p1 = [1 4] → c1 = [1 1]
and p2 = [3 0] → c2 = [1 2] are obtained. Then M = <25>
Suppose the a ciphertext c3 = [1 0] is intercepted. Then the
corresponding plaintext is p3 = <26>
#Consider the elliptic curve group defined by y^2 = X^3+x over F23.
There are 23 points satisfying the equation as the grapg. Let P = (18,10)
and Q = (19,1).
The order of the elliptic curve group is <27>
P-Q = <28>
3P = <29>
2009P = <30>
y
22 .
21
20 .
19
18 . . . .
17 .
16
15 .
14
13 . . .
12
11
10 . . .
9
8 .
7
6 .
5 . . . .
4
3 .
2
1 .
0 .
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 x
Part III (write down all details of your work)
31.(4 points)
Over GF(3), suppose p(x) = x^3+2x^2+x+2 and q(x) = x^4+2x^3+2x^2+1.
Write gcd(p(x),q(x)) as a monic polynomial, i.e., the leading
coefficient is 1.
Find polynomials f(x) and g(x) such that
f(x)p(x) + g(x)q(x) = gcd(p(x),q(x)).
32.(3 points)
Show that using a small public exponent for RSA may not be secure as
follows.
Suppose the public exponent e = 3 is taken 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.
33.(3 points)
Show that RSA is not secure against (adaptive) chosen ciphertext
attacks as follows. Suppose the message m that Eve wants to break is
from c = m^e (mod N).
Eve creates the 'related' ciphertext c' = 2^e c and asks an oracle to
decrypt c' to give m'. Express m in terms of what Eve has obtained
and prove your answer.
Solution:
1 2 3 4 5 6 7 8 9 10
C A D E D A D B C B
11 12 13 14 15
359 693 251 173 14
16 17 18 19 20
5 168x156(=26208) 163x13(=2184) P+R 2P
21 22 23 24 25
107 22 17 10 ┌24┐
└13┘
26 27 28 29 30
[4 3] 24 (15,3) Point at Infinity(O, ∞) (18,13)
31 gcd = x+2, f(x) = 2x^2+2x+2, g(x) = x+1
33 m = m'/2 mod N
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.24.181