CSIE编程代做、代写C++程序设计

日期：2024-04-09 09:03

National Taiwan Normal University

CSIE Information Security

Due Date: April 7, 2024, PM 11:59

Assignment

1

Policies:

? Zero tolerance for late submission.

? Please pack all your submissions in one zip file. RAR is not allowed!!

? I only accept PDF. MS Word is not allowed.

? Hand-writing is not allowed.

? Please use Chinese.

1.1 Triple Encryption (10 pts)

In this class, I have shown you why double DES is useless. However, someone argues that an attacker may find one key to simulate three keys. That

is,

Enc(k3, Enc(k2, Enc(k1, x))) = Enc(k

′

, x).

So the attacker may need to brute force k

′

instead of k1, k2, k3. Please

show that the probability is negligible.

1.2 Hybrid Chosen-Plaintext-Attack Construction (10 pts)

Let (E0, D0) be a semantically secure cipher defined over {K0,M, C0} and

(E1, D1) be a CPA secure cipher defined over {K, K0, C1}. Define the following hybrid cipher (E, D) as:

E(k, m) := {k0

R←? K0, c1 ← E1(k, k0), c0 ← E0(k0, m), output (c0, c1)},

D(k,(c0, c1)) := {k0 ← D1(k, c1), m ← D0(c0, k0), output m}.

Prove that (E, D) is CPA secure.

1.3 The malleability of CBC mode (10 pts)

Let c be the CBC encryption of some message m ∈ X l

, where X := 0, 1

n

.

You do not know m. Let △ ∈ X . Show how to modify the ciphertext c to

obtain a new ciphertext c

′

that decrypts to m′

, where m′

[0] = m[0] ⊕ △,

and m′

[i] = m[i] for i = 1, . . . , l. That is, by modifying c appropriately,

you can flip bits of your choice in the first block of the decryption of c,

without affecting any of the other blocks.

1.4 Modular Multiplicative Inverse (10 pts)

Please find the modular multiplicative inverse of the following number.

Please write down how you find it. If you give the answer directly without

the process, you will get zero points.

1. 400 mod 997

2. 472 mod 16651

1.5 Euler’s Theorem and RSA (10 pts)

In this class, I have introduced Euler’s Theorem to you as follows.

Theorem 1.1. For every a and n that are relatively prime, then

a

?(n) ≡ 1(mod n).

However, when we run RSA permutation, m and N = pq may not be

relatively prime. When m and N = pq are not relatively prime, will the

reverse permutation still work? Why or why not?

1.6 Pseudo Prime (10 pts)

In this class, I have told you that in computer science, we often use pseudo

primes instead of real primes. However, when we verify the correctness of

RSA, we always assume that p, q are primes. Is there any conflicts? Of

course not or RSA will not work. Please show that even p, q are pseudo

primes, the correctness of RSA still stands.

Hint: What are pseudo primes?

1-2

Figure 1.1: Elliptic group E23(1, 1).

1.7 Elliptic Curve over Zp (10 pts)

An elliptic curve is defined by an equation in two variables with coefficients.

Elliptic curves are not ellipse. They are named because they are described

by cubic equations, similar to those used for calculating the circumference

of an ellipse. For cryptography, the variables and coefficients are restricted

in a finite field, which results in the definition of a finite abelian group.

For elliptic curves over Zp, we use the following equation to form a

group:

y

2 mod p = (x

3 + ax + b) mod p.

Note that all coefficients and variables are belong to Zp.

For example, given a group Ep where a = 1, b = 1, x = 9, y = 7, p = 23,

we have

7

2 mod 23 = (93 + 9 + 1) mod 23

49 mod 23 = 739 mod 23

3 mod 23 = 3 mod 23

So (9, 7) ∈ Ep. We often use Ep(a, b) to represent the group. All points

are shown in Fig. 1.1. Note that (4a

3+27b

2

) mod p ?= 0 mod p for avoiding

repeated factors.

How about the operation and the identity? In a elliptic curve group,

the identity is defined at infinity O. The operation is defined as follows:

1. For any point P, P + O = P.

2. If P = (x, y), then ?P = (x, ?y).

1-3

Figure 1.2: Elliptic group operation.

3. To ”add” (operation) P and Q, draw a straight line P Q and find the

third intersection R with the curve Ep. We define P + Q + R = O.

Therefore, P +Q = ?R. Note that the computation should be in Zp.

4. For P + P, use the tangent line instead.

You can see Figure 1.2 for reference.

Please show that given P = (xP , yP ), Q = (xQ, yQ), R = P + Q =

(xR, yr),

xR = (λ

2 ? xP ? xQ) mod p

yR = (λ(xP ? xR) ? yP ) mod p

where

λ =

?

?

?

(

yQ ? yP

xQ ? xP

) mod p, if P ?= Q

(

3x

2

P + a

2yP

) mod p, if P = Q

1.8 Lab: Secret-Key Encryption (15 pts)

? Lab: https://seedsecuritylabs.org/Labs_20.04/Crypto/Crypto_

Encryption/

You need to submit a detailed lab report, with screenshots, to describe

what you have done and what you have observed. You also need to provide

explanation to the observations that are interesting or surprising. Please

also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.

1.9 Lab: Padding Oracle Attack (15 pts)

? Lab: https://seedsecuritylabs.org/Labs_20.04/Crypto/Crypto_

Padding_Oracle/

1-4

You need to submit a detailed lab report, with screenshots, to describe

what you have done and what you have observed. You also need to provide

explanation to the observations that are interesting or surprising. Please

also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.

1-5