程序代写案例-COMP322301

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
So
lu
tio
ns
Module Code: COMP322301
Module Title: Cryptography c© UNIVERSITY OF LEEDS
School of Computing Semester 2 2019/2020
Calculator instructions:
- You are allowed to use a non-programmable calculator only from the following list of approved models in
this examination: Casio FX-82, Casio FX-83, Casio FX-85.
Dictionary instructions:
- You are not allowed to use your own dictionary in this examination. A basic English dictionary is available
to use: raise your hand and ask an invigilator, if you need it.
Examination Information
- There are 2 hours to complete the examination.
- There are 6 pages to this examination.
- Answer all 3 questions.
- The number in brackets [ ] indicates the marks available for each question or part question.
- You are reminded of the need for clear presentation in your answers.
- The total number of marks for this examination paper is 40.
with solutions
Page 1 of 6 Turn the page over
So
lu
tio
ns
Module Code: COMP322301
Question 1
Consider a symmetric cryptosystem (M,C,K,E,D), where M is the plaintext space, C is the ciphertext space,
K is the key space, E : K ×M → C is the encryption function, and D : K ×C →M is the decryption function.
(a) Describe Kerckhoff’s principle: (i) in general, and (ii) applied specifically to this cryptosystem.
Solution:
(i) Kerckhoff’s principle states that we should assume the adversary knows the details of the cryptosystem
used [1 mark].
(ii) In this case, we assume that the adversary knows (at least) the cryptotext y ∈ C [1 mark] and the
encryption and decryption functions E and D [1 mark].
[3 marks]
(b) Define the key space K and the encryption function E in the Hill cipher with block size L.
Give an example of a chosen plaintext attack against the Hill cipher.
Solution:
In the Hill cipher, the key is an L × L matrix with elements in Zm [1 mark] that has to have determinant
that is invertible [1 mark], i.e. K ∈ GL(L,Zm).
The encryption function for plaintext vector x = (x1, . . . , xL) is [1 mark]: y = E(x,K) = xK.
A chosen plaintext attack against the Hill cipher is to take the elementary basis vectors e1 = (1, 0, 0, . . .),
e2 = (0, 1, 0, . . .) etc. and compute E(ej, K) = kj to obtain each column of K, revealing the key [1 mark].
[4 marks]
(c) Explain what we mean by a computationally secure cryptosystem.
Solution:
A cryptosystem is computationally secure if the best possible attack [1 mark] against it requires computational
resources that are excessive compared to the potential benefit for the adversary [1 mark].
[2 marks]
(d) Explain how we can obtain the 3DES cryptosystem from the DES (Data Encryption Standard) cryptosystem.
What is the theoretical computational security level of 3DES (in bits)?
Give an example of a ciphertext only attack against 3DES that reduces its security level.
Solution:
If Ek denotes encryption with the DES cipher using key k, then 3DES is obtained by creating three keys
k1,k2,k3 as a composition of three rounds of DES [1 mark]:
3DESk1,k2,k3 := Ek1 ◦Dk2 ◦ Ek3 .
The security of DES is 56 bits [1 mark], so the theoretical security of 3DES is 3 × 56 = 168 bits [1 mark].
However, due to the meet-in-the-middle attack the real security is only 112 bits [1 mark].
[4 marks]
[Question 1 Total: 13 marks]
Page 2 of 6 Turn the page over
So
lu
tio
ns
Module Code: COMP322301
Question 2
Alice and Bob want to agree on a common key to encrypt and exchange data using a symmetric cryptosystem.
(a) Explain the Diffie-Hellman key exchange protocol. State all the computations and the information that Alice
and Bob need to exchange to agree on the common key.
Solution:
(i) Need: prime p and a generator g of Z∗p
(ii) Alice and Bob exchange p, g over an open channel [1 mark]
(iii) Alice chooses a random number a ∈ Zp
(iv) Alice computes
f = ga mod p
and sends f to Bob [1 mark]
(v) Bob chooses a random number b ∈ Zp
(vi) Bob computes
h = gb mod p
and sends h to Alice [1 mark]
(vii) Alice and Bob compute the joint key
k = gab mod p [1 mark] (1)
= f b mod p [1 mark] (2)
= ha mod p [1 mark] (3)
[6 marks]
(b) Explain the one-time pad cryptosystem in terms of the key and the encryption function used. Under which
conditions does the one-time pad have perfect information-theoretical security? Explain why the one-time
pad cryptosystem is not practical in most applications.
Solution:
The one-time pad uses a pre-negotiated key stream k1, k2, . . . that has to be at least as long as the message
[1 mark].
The encryption function is: yi = E(ki, xi) = xi + ki (mod m) [1 mark].
The one-time pad has perfect information-theoretical security if the key stream is truly random [1 mark] and
only used once [1 mark].
In practice, distributing arbitrarily long random key streams securely is too cumbersome [1 mark].
[5 marks]
(c) Alice and Bob have a quantum channel following the BB84 protocol that allows them to exchange a sequence
of secret bits. Explain why the quantum channel is a secure way to exchange a key stream even if Eve is
potentially eavesdropping on their channel. Estimate how likely it is that Alice and Bob will notice if Eve
attempts to eavesdrop on one bit of information in the channel.
Page 3 of 6 Turn the page over
So
lu
tio
ns
Module Code: COMP322301
Solution:
A quantum channel transmits information encoded in quantum bits (qbits). According to the No-Cloning
Theorem of quantum physics, qbits cannot be cloned without measuring them, which collapses them to that
basis [1 mark].
Therefore; Eavesdropping on the channel is equal to measuring a qbit in a random basis, which is the wrong
one with probability 1/2 [1 mark].
As Alice and Bob choose bits randomly from the stream with probability 1/2, the chance to detect eaves-
dropping in one bit is 1/4 [1 mark].
[3 marks]
[Question 2 Total: 14 marks]
Page 4 of 6 Turn the page over
So
lu
tio
ns
Module Code: COMP322301
Question 3
Bob wishes to receive a message from Alice which has been authenticated via a digital signature.
(a) Alice uses the RSA signature protocol and chooses the modulus n = 161 and the public key e = 5. Explain
how the private key d is chosen in RSA. Use the extended Euclidean algorithm to compute the private key.
Solution:
In RSA, the key pairs are (d, n) and (e, n), where ed ≡ 1 (mod ϕ(n)). To find the private key, we need to
find d [1 mark for idea].
Since n = 23× 7, we have ϕ(n) = 22× 6 = 132 [1 mark]. We use the extended Euclid’s algorithm to find
the multiplicative inverse of e−1 ≡ d (mod 132). First we compute gcd(132, 5) by Euclid’s algorithm:
(1) 132 = 5× 26 + 2,
(2) 5 = 2× 2 + 1,
(3) 2 = 2× 1 + 0.
so that gcd(132, 5) = 1 [1 mark]. Now we need to find x, y such that 1 = x e+y ϕ(n). Reversing the above,
1 = 5− 2× 2 from (2)
= 5− (132− 5× 26)× 2 from (1)
= 5 + 5× 26× 2− 132× 2
= 53× 5− 132× 2
so that x = 53 and y = −2 [2 marks for correct result]. So (5)−1 ≡ 53 (mod 132) and the private RSA key
is d = 53 [1 mark]. [6 marks]
(b) Bob receives x = 14 and y = xd ≡ 21 (mod 161) as the RSA signature. Bob has the modulus n = 161 and
the public key e = 5, but does not know Alice’s private key. Verify using the square-and-multiply algorithm
that Alice’s signature is correct. Show all steps.
Solution:
To verify the signature, Bob has to check that ye = xed ≡ x (mod n) [1 mark]. He computes 215 (mod 161)
by the square-and-multiply algorithm [2 marks]:
212 = 441 ≡ 119 (mod 161),
214 = 1192
= 14161
≡ 154 (mod 161)
Therefore, Bob finds [1 mark]
215 = 21× 214 = 21× 154
≡ 14 (mod 161),
which verifies the signature to be correct. [4 marks]
Page 5 of 6 Turn the page over
So
lu
tio
ns
Module Code: COMP322301
(c) Describe an algorithm for using a birthday attack to find a collision against a hash function h : X → Y .
Approximately how many random samples q do we need to find a collision with probability p = 0.5 with the
birthday attack, assuming the co-domain size is |Y |?
Solution:
The birthday attack is: choose q different random elements xi from X and compute yi = h(xi) for i =
1, . . . , q. [1 mark]. Then compare each pair (yi, yj) for i 6= j until you find a collision [1 mark].
The probability to find a collision is approximately p = 0.5 as soon as q ≈√|Y | [1 mark].
[3 marks]
[Question 3 Total: 13 marks]
[Grand Total: 40 marks]
Page 6 of 6 End

欢迎咨询51作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468