COMP0025代写、代写Java，Python程序

日期：2022-01-02 03:27

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?

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.

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]