CSIE编程讲解 、辅导 C++程序设计
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