COMP0025代写、代写Java/c++程序

日期：2023-04-27 09:38

COMP0025: Introduction to Cryptography

Practice Exam

Department of Computer Science

University College London

Question 1: Hash Functions [25 marks]

(a) Consider the hash function H : {0, 1}256` → {0, 1}256 defined by H(m1, . . . ,m`) = m1⊕. . .⊕m`.

Describe an adversary that on input m = (m1,m2) performs a successful second-preimage attack.

[5 marks]

(b) SnakeOil Ltd is suggesting a super fast hash function H : {0, 1}? → {0, 1}100 defined by H(x) =

7x+5 mod 2100. Describe an attack that finds a second-preimage for any message x. [5 marks]

(c) Given a collision-resistant compression function f : {0, 1}512 → {0, 1}256, we define a hash

function H : {0, 1}? → {0, 1}256 as follows:

(a) On input x pad it with 0 . . . 0 such that it has length 256n.

(b) Let xi be the ith 256-bit block of the padded x ‖ 0 . . . 0.

(c) Let z0 = 0

256 and zi = f(zi?1 ‖ xi) for i = 1, . . . , n.

(d) Return zn as the output H(x).

Is this construction collision-resistant? Why or why not? [5 marks]

(d) Let p, q be two large prime numbers such that p = 2q + 1 and let g, h be two random group

elements in Z?p. The function H : Zp?1 × Zp?1 → Z?p defined by

H(x, y) = gxhy mod p

is a hash function mapping (p? 1)2 possible inputs to p? 1 possible outputs. Unfortunately, H

is not collision-resistant. Argue why not. [5 marks]

Hint: You may use the fact that half of the elements in Z?p have order q.

(e) Let p, q bet two large prime numbers such that p = 2q + 1 and let g, h ∈ Zp bet two random

generators for the order q subgroup G ? Z?p. Define the hash function H : Zq × Zq → G by

H(x, y) = gxhy mod p

Show that H is collision-resistant if the discrete logarithm is hard in G. [5 marks]

1

Question 2: Message Authentication Codes [25 marks]

(a) Consider the following one-time message authentication code for 10-bit messages.

Key generation: The secret key is sk = (a, b) where a, b $←? Z1031 are picked at random

(1031 is a prime).

Authentication: To authenticate a message m compute the authentication tag t = am+

b mod 1031.

Verification: To verify an authentication tag t on a message m check whether t = am +

b mod 1031.

Consider an adversary that does not know anything about the secret key but does learn one pair

(m, t) of an arbitrary message and its corresponding authentication tag. What is the probability

that the adversary can find a different message m′ and its corresponding tag t′? [5 marks]

(b) Consider the following message authentication code for 128-bit messages built from AES encryp-

tion function E.

Key generation: Pick a 128-bit secret key k.

Authentication: Given a message m compute the authentication tag t = Ek(m).

Verification: To verify an authentication tag t on message m check whether t = Ek(m).

Assume Ek were a truly random permutation of 128-bit strings. Suppose the adversary learns

pairs of messages and authentication tags (m1, t1), . . . , (m1024, t1024) for 1024 different messages

of its own choosing. What is the probability that it can find a new message m /∈ {m1, . . . ,m1024}

and guess the corresponding message authentication tag t? [5 marks]

(c) Recall that NMAC and HMAC are message authentication codes built from a Merkle-Damgard

type hash function such as for instance SHA256. HMAC computes the message authentication

code as HMAC(k,m) = H(k⊕ opad ‖ H(k⊕ ipad) ‖ m) whereas NMAC computes the message

authentication code as NMAC(k,m) = Hk1(Hk2(m)) with k = (k1, k2). What is an advantage

of NMAC over HMAC and an advantage of HMAC over NMAC? [5 marks]

(d) Consider CBC-MAC for 128`-bit messages with fixed `. We use AES as the underlying block

cipher with 128-bit keys. Let E be the AES encryption function.

Key generation: Pick a 128-bit secret key k.

Authentication: Given a message m = m1 ‖ · · · ‖ m` where m1, . . . ,m` are 128-bit

blocks define t0 = 0 and compute t1, . . . , t` recursively as ti = Ek(ti?1 ⊕mi). Output the

authentication tag t = t`.

Verification: To verify an authentication tag t on a 128`-bit message m compute t` as

above and accept if t = t`.

Suppose we modify CBC-MAC to allow for both 128-bit messages and 256-bit messages by

outputting t = t1 or t = t2. Show that it is possible to forge an authentication tag on a 256-

bit message by combining the authentication tags for two adaptively chosen 128-bit messages.

[5 marks]

(e) Give a formal definition of existential unforgeability for message authentication codes under adap-

tive chosen message attacks. Explain in your own words what the definition means. [5 marks]

2

Question 3: Digital Signatures [25 marks]

(a) A digital signature scheme (Gen,Sign,Verify) is said to be secure if for all probabilistic polynomial

time adversaries A we have

Pr[(vk, sk)← Gen(1λ); (m,σ)← ASignsk(·)(vk) : m /∈ Q ∧ Verifyvk(m,σ) = 1] = negl(λ)

where Q is the set of messages that has been queried to the signing oracle Signsk(·). What is the

name of the security definition? Explain in non-mathematical terms what the goal of the adversary

is in the security definition. Explain in non-mathematical terms what access the adversary has to

the signature scheme in the security definition. [5 marks]

(b) We say p is a safe prime if p = 2p′ + 1 and both p and p′ are primes. Consider an RSA modulus

N = pq where p = 2p′+1 and q = 2q′+1 are two different safe primes. The group of quadratic

residues QRN are the elements y ∈ Z?N for which there exists a z such that y = z2 mod N . The

size of QRN is p′q′. What is the size of Z?N? Show that Z?N is not cyclic. Show that QRN is

cyclic. [5 marks]

Hint: You may want to use the Chinese Remainder Theorem and the fact that Z?p and Z?q are

cyclic when p and q are prime.

(c) Camenisch and Lysysanskaya proposed a signature scheme in 2002. A variant of the CL signature

scheme for `m-bit messages works as follows (for suitable choices of `e > 2λ and `r defined in

their paper):

Gen(1λ): Pick two random λ-bit safe primes p and q. Let N = pq and pick at random

a, b, c ∈ QRN . Return the verification key vk = (N, a, b, c) and the secret key sk = (p, q).

Sign(sk,m): To sign an `m-bit message m pick at random a prime 2`e < e < 2`e+1

and additional randomness r

$←? {0, 1}`r . Compute a value s ∈ QRN such that se =

abmcr mod N . Return the signature σ = (e, r, s).

Verify(vk,m, σ): To verify a signature σ on an `m-bit message m check that e > 2`e is a

prime, check that r ∈ {0, 1}`r and check that se = abmcr mod N .

Let vk = (77, 4, 9, 25) be a CL signature scheme verification key. Find the secret key and compute

a CL signature on m = 3 using randomness (e, r) = (103, 8). [5 marks]

Hint: To speed up the calculations, do them modulo p and modulo q and use the Chinese

Remainder Theorem.

(d) Show that if you can guess in advance the number of signing queries t that the adversary will

make, then you can simulate the verification key and simulate the signatures without knowing

the factorization of N . [5 marks]

Hint: Given N pick at random y = z2 mod N . Generate t random primes e1, . . . , et ∈

{2`e , . . . , 2`e+1}. Define E = ∏tj=1 ej and Ei = E/ei. Pick at random α, β $←? {0, 1}3λ.

Let a = yαE mod N , b = yβE mod N , and c = yE mod N .

(e) The strong RSA assumption says that given a safe prime RSA modulus N and a random element

y ∈ QRN , it is hard to find an x ∈ Z?N and an exponent e > 1 such that y = xe mod N .

Consider an adversary At that obtains exactly t signatures (e1, s1, r1), . . . , (et, st, rt) on messages

m1, . . . ,mt in adaptive chosen message attacks and then forges a CL signature σ = (e, s, r) on

a message m /∈ {m1, . . . ,mt} using a prime e /∈ {e1, . . . , et}. Show that such an adversary can

be used to break the strong RSA assumption. [5 marks]

Hint: Write α = α′p′q′ + [α mod p′q′] over the integers. Observe that no information about α′

is leaked when simulating signatures given that gcd(e, α+ βm+ r) = 1 with high probability.

3

Question 4: Private Information Retrieval [25 marks]

In Private Information Retrieval (PIR) a server holds a database of n bits (x1, . . . , xn) and a client

wants to learn the bit xi without revealing the queried index i to anybody else. A naive way to do PIR is

to have the server sending the entire database (x1, . . . , xn) to the client. The client can then extract xi

without revealing the index i to anybody. However, the naive solution requires n bits of communication.

This question is about the Gentry-Ramzan PIR protocol that allows the client to privately extract a bit

from the database using less than n bits of communication with the server.

(a) Let p = 2pir + 1, q = 2s+ 1, and N = pq where 2, pi, r, s, p, and q are different primes. What

is the size of the multiplicative group Z?N? What is the maximal order an element g ∈ Z?N can

have? [5 marks]

(b) Define pi1, . . . , pin to be the first n primes larger than 2n. The Gentry-Ramzan PIR protocol

works as follows:

Query(1λ, i): Send (N, g) to the server, where N is a λ-bit RSA modulus and g ∈ Z?N is a

random element of order piit.

Respond(N, g, x1, . . . , xn): Compute x so that x = xj mod pij for all 1 ≤ j ≤ n. Send

c = gx mod N to the client.

Extract(c): Return 0 if 1 = ct mod N otherwise return 1.

Show that the Gentry-Ramzan protocol is correct, i.e., if both the client and the server are honest,

then the client outputs the desired xi in the extraction steps. [5 marks]

(c) In the protocol given above, the client computes ct mod N which in the worst case requires

approximately 2λ multiplications modulo N . Suggest a way to speed up the client’s computation

in the extraction phase. [5 marks]

(d) We say the protocol is computationally private if for all probabilistic polynomial-time adversaries

A we have

|Pr[i← A(1λ); (N, g)← Query(1λ, i) : A(N, g) = 1]

Pr[i← A(1λ); (N, g)← Query(1λ, 1) : A(N, g) = 1]| ≤ negl(λ)

where A outputs 1 ≤ i ≤ n. What access does the adversary have to the client’s desired index?

What is the adversary’s goal in this definition? How does the definition capture the notion of

privacy for the client? [5 marks]

(e) The client may without the server’s knowledge modify the Query and Extract protocols such that

it can extract two bits xi, xj from the database. How can this be done? [5 marks]