COMP0025: Introduction to Cryptography
Coursework
Department of Computer Science
University College London
Released: December 14, 2021
Due: January 11, 2022 at 16:00 UK time
Instructions
• This assignment is part of the mandatory assessment of the COMP0025: Introduction to Cryptography
module and will count 25% towards your final overall mark.
• Assignment submission is due via Moodle through the TurnItIn interface on January 11, 2022 at 16:00
UK time. Late submissions will be accepted with deductions according to UCL’s late submission policy.
• Only PDF submissions that are typeset with LaTeX, e.g., via https://www.overleaf.com/edu/ucl,
will be accepted. Submissions must not include screenshots, e.g., of handwritten or drawn solutions,
unless explicitly permitted. Students with disability accommodations are excluded from this requirement.
• This assignment is open note, open book, and open course resources. You must identify sources as
accurately and fully as possible. UCL plagiarism policies will be strictly enforced. For more details, see
http://www.ucl.ac.uk/current-students/guidelines/plagiarism.
• You are not allowed to consult other people (outside of course staff) on this work. Each student has to
work on the assignment individually.
• Your answers will be judged in terms of their quality, the depth of understanding, and also their brevity.
Explain your answers clearly, but succinctly. Partial credit may be awarded.
• The assignment has a maximum of 100 marks allocated as follows:
Q1 Q2 Q3 Q4 Q5 Total
Marks 20 20 20 20 20 100 marks
1
Question 1: Cryptographic Software [20 marks]
OpenSSL is a widely used open source cryptography library that allows you to generate keys, encrypt
messages, sign messages, etc. In many cases the OpenSSL tool comes already pre-installed with your
operating system. If that’s not the case, you can usually install it through your favorite package manager
or download it, e.g., at https://www.openssl.org/. Make sure you have the latest stable version
OpenSSL 3.0.0 from September 07, 2021. Use OpenSSL to answer the following questions:
(a) Save the two passphrases enc-cryptorulez2600 and mac-cryptorulez2600 in the text files
enc.pw and mac.pw, respectively. What are the SHA256 fingerprints of these passphrases?
[2 marks]
(b) You received the following encrypted message:
pCSUbwVFZxGM1SsJCtQRZmDcd5zyC2ygMVG64oJjtoNYGGzQnhI=
This ciphertext was produced with the ChaCha20 stream cipher using the SHA256 fingerprint
of enc-cryptorulez2600 as a key and c0dec0dec0dec0dec0dec0dec0dec0de as an IV. What
was the message? [2 marks]
(c) Next to the above ciphertext you also received the following authentication tag for it:
b1086574bd1100947e32ed9e8f56be85cd49274b7e5b9669e126fda1b7a9c72a
It was created with the HMAC-SHA256 message authentication code using the SHA256 fingerprint
of mac-cryptorulez2600 as a key. Is it correct? What OpenSSL command did you use to verify
it? [2 marks]
(d) Consider the following RSA public key:
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1Zi1M5x6TUmjpf8sV4Op
3RpfjAs0CFvzjzE+C6HxJeMYj8KCZfyuBcVFwz5zaLOYULTPjzz+l98cVIZE5FN/
2t+2mXFbJN+0vvi5A43JY9YHt81FMsc+MF7XQoLpXwUhkSw3TkrMIhjCmoexCB9V
r+lUE3sWamEPh61d2pnwm2L2ZyU3BikNPgUUO6U7hd8h/urBIZLkDUsxOaD2HTYg
HqHwLRELS3ewGbQqx9idEkKVtfZgpkIa8GiIpB1m+WqHX2zqlwyGLPAhzgCbBiP9
RpO/0DlI+jnZzuQ+Drd1zXyPSxezMKhoXspXoxuT0IP9CQaUmUnYUxsRFfiYvI1M
jQIDAQAB
-----END PUBLIC KEY-----
Create a plaintext file containing the string Alan Turing and encrypt it towards the above RSA
public key. What is the ciphertext in base64 format? [4 marks]
(e) Consider the following Diffie-Hellman parameters and public key:
-----BEGIN DH PARAMETERS-----
MIGHAoGBAL0S3BTNhjlcy2ChLWCxyMzdMEoCY2MOu9VmxlGoiPcLNkUAmCptJD4F
1d95FOswggSgdDCTgaDWizZaefyhH8X1bYNqNrtUyZVjw1KjSzSt/Cq0Cy7h0BvI
qtmfviCcAnovb3CgAp9WuLmagruqv+s2/SgpmebHQAIW/qnH2DMLAgEC
-----END DH PARAMETERS-----
-----BEGIN PUBLIC KEY-----
MIIBIDCBlQYJKoZIhvcNAQMBMIGHAoGBAL0S3BTNhjlcy2ChLWCxyMzdMEoCY2MO
u9VmxlGoiPcLNkUAmCptJD4F1d95FOswggSgdDCTgaDWizZaefyhH8X1bYNqNrtU
yZVjw1KjSzSt/Cq0Cy7h0BvIqtmfviCcAnovb3CgAp9WuLmagruqv+s2/SgpmebH
QAIW/qnH2DMLAgECA4GFAAKBgQCEUQc+0TuYPrnNP7KP/1tR1X0tV4B/GtbKrCFU
863vMPHzozchNvxz+uI2OJGet0evMnz7xCOoZ+w5fE00sldFegAwIaC4QW6BBZcO
V2Twtbggz+95r7yKfNRM2ty0SV5CE8fdCeRBoMPver9gJk4uN7KyHFXWbOUzt9YR
tiJVTQ==
-----END PUBLIC KEY-----
Assume the DH parameters and public key are stored in files dhp.pem and dhpub1.pem, respec-
tively. Describe the steps to setup your own DH key pair and do a DH key exchange using the
given DH parameters and public key. [4 marks]
2
(f) The following command sequence allows to download TLS certificates:
echo | openssl s_client -connect HOST:PORT |\
sed -ne ’/-BEGIN CERTIFICATE-/,/-END CERTIFICATE-/p’ > certificate.pem
Consider the following TLS certificate downloaded from a website:
-----BEGIN CERTIFICATE-----
MIIE7zCCBJSgAwIBAgIQD9WF1Et9s39cPmU79LIm9zAKBggqhkjOPQQDAjBKMQsw
CQYDVQQGEwJVUzEZMBcGA1UEChMQQ2xvdWRmbGFyZSwgSW5jLjEgMB4GA1UEAxMX
Q2xvdWRmbGFyZSBJbmMgRUNDIENBLTMwHhcNMjAwNzA0MDAwMDAwWhcNMjEwNzA0
MTIwMDAwWjBmMQswCQYDVQQGEwJVUzELMAkGA1UECBMCQ0ExFjAUBgNVBAcTDVNh
biBGcmFuY2lzY28xGTAXBgNVBAoTEENsb3VkZmxhcmUsIEluYy4xFzAVBgNVBAMT
DmNsb3VkZmxhcmUuY29tMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEG8yJrKWY
lPQG6J3KgKis4XeOY3/cL5qEQ+mP3zgl4ylipgX7/XJLiQ5361b8fJhj/UjIudFJ
0xL9ibOrs6JTDqOCAz4wggM6MB8GA1UdIwQYMBaAFKXON+rrsHUOlGeItEX62SQQ
h5YfMB0GA1UdDgQWBBTUxXwi2+exV6YsgMeQajzIlUvqnTBxBgNVHREEajBoghAq
LmNsb3VkZmxhcmUuY29tgg5jbG91ZGZsYXJlLmNvbYIUKi5kbnMuY2xvdWRmbGFy
ZS5jb22CFCouYW1wLmNsb3VkZmxhcmUuY29tghgqLnN0YWdpbmcuY2xvdWRmbGFy
ZS5jb20wDgYDVR0PAQH/BAQDAgeAMB0GA1UdJQQWMBQGCCsGAQUFBwMBBggrBgEF
BQcDAjB7BgNVHR8EdDByMDegNaAzhjFodHRwOi8vY3JsMy5kaWdpY2VydC5jb20v
Q2xvdWRmbGFyZUluY0VDQ0NBLTMuY3JsMDegNaAzhjFodHRwOi8vY3JsNC5kaWdp
Y2VydC5jb20vQ2xvdWRmbGFyZUluY0VDQ0NBLTMuY3JsMEwGA1UdIARFMEMwNwYJ
YIZIAYb9bAEBMCowKAYIKwYBBQUHAgEWHGh0dHBzOi8vd3d3LmRpZ2ljZXJ0LmNv
bS9DUFMwCAYGZ4EMAQICMHYGCCsGAQUFBwEBBGowaDAkBggrBgEFBQcwAYYYaHR0
cDovL29jc3AuZGlnaWNlcnQuY29tMEAGCCsGAQUFBzAChjRodHRwOi8vY2FjZXJ0
cy5kaWdpY2VydC5jb20vQ2xvdWRmbGFyZUluY0VDQ0NBLTMuY3J0MAwGA1UdEwEB
/wQCMAAwggEDBgorBgEEAdZ5AgQCBIH0BIHxAO8AdQD2XJQv0XcwIhRUGAgwlFaO
400TGTO/3wwvIAvMTvFk4wAAAXMbCD9JAAAEAwBGMEQCIGvGTxZeBYgdbs+vnp0c
9y45gwRMOZnKz4eE1d4LdagwAiARwrwO1jORk0C5/VTj+RPxK5HRwK169bwkdVL8
0pB7lAB2AFzcQ5L+5qtFRLFemtRW5hA3+9X6R9yhc5SyXub2xw7KAAABcxsIP38A
AAQDAEcwRQIhAMWV1BR5WmEVEfpfyBAJErAa7zbUmn9yqwLzdVDesRcuAiAePxqr
LJBQ5ysyisJOIt6GzfUOg1rDmsgmmdj7zz9lgDAKBggqhkjOPQQDAgNJADBGAiEA
42x0wUe7wq/QbXOvyaYX8IXvORQ0L+/cOM4TrVCEG9ECIQDaDyZCKGGpi+MqdDmy
dLIonPk4USKu95+gu0CQPQTglQ==
-----END CERTIFICATE-----
Answer the following questions:
(i) Which HOST and PORT parameters were used to download the above certificate? [2 marks]
(ii) What is the certificate’s serial number? [1 mark]
(iii) Until when is the certificate valid? [1 mark]
(iv) What signature algorithm was used to sign the certificate? [1 mark]
(v) What is the certificate’s fingerprint? [1 mark]
3
Question 2: Semantic Security [20 marks]
Let λ denote a security parameter. Let Π1 and Π2 be two encryption schemes for which it is known
that at least one of them is IND-CPA secure with respect to λ. However, you do not know which one
is definitely IND-CPA secure and which one may be not.
(a) Build a correct and IND-CPA secure encryption scheme Π using Π1 and Π2. [8 marks]
(b) Prove that Π is IND-CPA secure with respect to λ. [12 marks]
Remark: Both encryption schemes can be assumed to leak the exact length of the input message.
4
Question 3: Hash Functions [20 marks]
(a) Let E : {0, 1}λ × {0, 1}b → {0, 1}b be a block cipher. Assume λ = b. Consider the following
compression function:
f(x, y) = E(x, x⊕ y)⊕ x .
Is f second-preimage resistant? Justify your answer either by constructing a collision or by
providing a security proof. [6 marks]
(b) Let F and G be hash functions one of which one is collision-resistant and let
H(x) = F (G(x) ‖ x) ‖ G(F (x) ‖ x) .
Is H collision-resistant? Justify your answer either by constructing a collision or by providing a
security proof. [7 marks]
(c) Let G be a collision-resistant hash function with output length b and let H denote a function which
iterates G in a CBC-like manner as follows: Parse input message m as pad(m) = m1, . . . ,mn
such that |mi| = b for all 1 ≤ i ≤ n. Compute chaining values hi = G(mi ⊕ hi−1) for all
1 ≤ i ≤ n with h0 = 0b. Finally, set H(m) := hn.
G G G
0b
m1 m2 mn
hn
Is H collision-resistant? Justify your answer either by constructing a collision or by providing a
security proof. [7 marks]
5
Question 4: Message Authentication Codes [20 marks]
(a) Let MAC = (Gen,Tag,Verify) be a fixed-length CBC-MAC for messages of length s blocks each
of size b bits. Prove or disprove that the following CBC-MAC variants are EUF-CMA secure.
(i) MAC.Tagk(m) uses a random IV t0
$←− {0, 1}b and returns t := (t0, ts) as the CBC-MAC
tag where ts is output of the last block cipher call. [5 marks]
(ii) MAC.Tagk(m) uses the IV t0 := 0
b and returns t := (t1, . . . , ts) as the CBC-MAC tag,
where ti is the output of the i-th block cipher call. [5 marks]
(b) Weak existential unforgeability under adaptive chosen-message attacks (wEUF-CMA) is a variant
of the EUF-CMA security notion of a message authentication code MAC = (Gen,Tag,Verify)
which requires that for all PPT adversaries A there is a negligible function negl such that for all
n ∈ N:
Pr[k
$←− Gen(1n); (m, t)← ATagk(·)(1n) : m /∈ Q ∧ Verifyk(m, t) = 1] = negl(n) ,
where Q is the set of messages the adversary has queried to its message authentication oracle
Tagk(·). Note that A does not have access to the verification oracle here unlike in EUF-CMA.
Suppose that MAC is wEUF-CMA secure. Separate the two security notions by constructing a
message authentication code MAC′ = (Gen′,Tag′,Verify′) using MAC that is also wEUF-CMA
secure, but is not EUF-CMA secure. Argue why it is wEUF-CMA secure. Describe an attack that
shows it is not EUF-CMA secure. [10 marks]
6
Question 5: Digital Signatures [20 marks]
(a) Let DSRSA = (Gen,Sign,Verify) denote the textbook RSA signature scheme with n = 77 and
e = 11.
(i) What are φ(n) and d? [2 marks]
(ii) What is the message for signature σ = 3? [2 marks]
(iii) Given e = 59, what is the signature for message m = 3? [2 marks]
(b) Let DSRSA = (Gen,Sign,Verify) denote the textbook RSA signature scheme. Assume we have
two public keys pk1 = (e1, n) and pk2 = (e2, n) for DSRSA where e1 and e2 are coprime. Let
m1,m2 be two messages in Zn. Suppose there exists a signature σ that is valid on m1 and m2
under pk1 and pk2, respectively. Describe how you can find σ. [7 marks]
(c) Consider the FDH-RSA digital signature algorithm. Show that an adversary can break EUF-CMA
security of FDH-RSA if it can find collisions in the used hash function H. [7 marks]
7

欢迎咨询51作业君