﻿ 现代密码学代考 CRYPTOGRAPHY代写 - 考试助攻

# 现代密码学代考 CRYPTOGRAPHY代写

2021-11-17 12:21 星期三 所属： 考试助攻 浏览：42

## 13:00  to 15:00

### INSTRUCTIONS TO CANDIDATES

1. Answerany TWO of the three  If more than two questions are answered, only QUESTION 1 and QUESTION 2 will be marked.
2. Allthree questions carry equal total weight of 25  marks.
1. Thisis an OPEN BOOK examination

THIS EXAMINATION WILL BE MARKED ANONYMOUSLY

### 1. Symmetric-keyCryptography  现代密码学代考

1.1(Pseudorandom Functions) Let Fkbe a keyed function and consider the [10 marks] following experiment:

#### Definition 1 The PRF indistinguishability experiment PRFA,F(n):

1 A uniform bit b ∈ {0, 1} is chosen.

If b = 1 then choose uniform k ∈ {0, 1}n.

2 A is given 1nfor  input.

If b = 0  then A is given access  to a uniform function f .   现代密码学代考   If b = 1 then A is instead given access to Fk.

3 A outputs a bitbj.

The output of the experiment is defined to be 1 if bj= b, and 0

Give a definition of a PRF using this experiment, and prove that your defi- nition is equivalent to the definition of a PRF presented in class:

#### Definition2FisapseudorandomfunctionifFk,foruniformkeyk 0, 1 n, issuchthatforallPPTdistinguishersA:

|Prk←{0,1}n [AFk (·) = 1]  Prf←Fn [Af(·) = 1]|  s(n)

1.2(Mode of Operation) Does CTR mode of operation yield a CCA-secure en- [5 marks] cryption scheme (assuming that the underlying PRF F is secure)? Proveor give an attack. 现代密码学代考

1.3(Message Authentication Codes) Let F be a PRF. Let Gen output a uniform [10marks]k  0, 1  n and let n be even.  By  i  denote an n/2-bit encoding of the   integer i. Consider the following MAC: to authenticate a message m =  m1, . . . , ml, where mi  {0, 1}n/2, choose uniform r  {0, 1}n, compute

t = Fk(r) Fk((1)||m1) . . . Fk((l)||ml),

and let the tag be (r, t). Is this a secure MAC? Prove or demonstrate an attack.

### 2. Public-keyCryptography  现代密码学代考

2.1(ElGamal)

Consider the following modification of the ElGamal encryption scheme. The key generation algorithm is as in ElGamal: a group generation algorithm on input 1n outputs the description of a cyclic group G, its order q and a generator g.  For  a uniformly chosen x Zq the private key is (G, q, g, x) and the public key is (G, q, g, h), where h := gx.

A message M is encrypted by choosing a uniform r Zq and computing

c = (gr, hr · gM ) .

(a)How can the receiver compute gMfrom c? [5 marks]   现代密码学代考

(b)Computing discrete logarithms is hard relative to . In general, the receiver is not able to recover M from gM. Assume the sender only sends messages from the set 1, . . . , 100 . Show that the receiver can recover M . [8 marks]

(c)Supposec1 = (gr, hr1   gM1 ) is a ciphertext for unknown message Mand c2 = (gr2 , hr2 · gM2 ) is a ciphertext for unknown message M2. Find a ciphertext c for a message M = M1 + M2 mod q using c1 and c2. [5 marks]

#### 2.2(Keyexchange) Consider the following key-exchange protocol: [7marks]

(1)Alice chooses uniform k, r ∈ {0, 1}r, and sends s := k r to Bob.

(2)Bob chooses uniform t ∈ {0, 1}n, and sends u := s t to Alice.

(3)Alicecomputes w := u  r, and sends w to Bob.

(4)Alice outputs k and Bob outputs w t.

Show that Alice and Bob output the same key. Analyze the security of the scheme (i.e., either prove its security or show a concrete attack).

### 3. Symmetric-key and Public-keyCryptography    现代密码学代考

3.1 (EAV- and CPA-secure encryption) Let F be a PRF, and G a PRG with [4 marks] expansion factor l(n) = n + For each of the following encryption schemes,state whether the scheme is: (1) EAV-secure and (2) CPA-secure, while providing supporting arguments (not necessarily a proof). In each case, the shared key is a random k ∈ {0, 1}n.

(a)To encrypt m ∈ {0, 1}n+1, choose uniform r ∈ {0, 1}n and output c = (r, G(r) m) as the ciphertext.

(b)To encrypt m ∈ {0, 1}n, output the ciphertext m Fk(0n).

3.2 (a) (Hash functions) Let (Gen, H) be a collision-resistant hash function. Is [4marks] (Gen, Hˆ )  defined  by  Hˆ (x)  =  H(H(x))  necessarily  collision  resistant?

Prove or demonstrate an attack.   现代密码学代考

(b) (Pseudorandom Functions) Consider the following keyed function F : for [7 marks] security parameter n, the key is an n n boolean matrix A and an n-bit

boolean vector b. Define:

FA,b : {0, 1}n ›→ {0, 1}n : FA,b(x) = Ax + b ,

where all operations are done modulo 2. Is F a PRF? Prove or give an attack.

3.3(Keyexchange) Diffie-Hellman (DH) is a key exchange protocol for two par- [10 marks] ties, that works in one round. Describe a two-round key exchange protocol for three parties based on the same idea as DH. Namely, the three par- ties A, B, C choose private values x, y, z respectively, and at the end of the protocol execution they all agree on a key gxyz.