lOMoARcPSD|15338780

Homework 1-2015-Fall-Solutions

Introduction to Cryptography (National Taiwan University)

StuDocu is not sponsored or endorsed by any college or university

Downloaded by abrar nahin (mmrnahin@gmail.com)
 lOMoARcPSD|15338780

5233/IOC5063 Theory of Cryptology, Fall 2015 21-Oct-2015

Homework 1 Solutions
Instructor: Prof. Wen-Guey Tzeng Scribe: Amir Rezapour

1. Show that Vernams one-time pad is perfectly secure.

Answer. we need to show ∀m ∈ M, c ∈ C P r[M = m|C = c] = P [M = m]
Assuming key k ∈ K is randomly chosen, we have
P r[C = c|M = m]P r[M = m] P r[k = m ⊕ c]P r[M = m]
P r[M = m|C = c] = =
P r[C = c] P r[C = c]
= P r[M = m]
(1)
✷

2. Assume that a plaintext bit M is given with P r[M = b] = pb , where b ∈ 0, 1. Assume

that random key K of the one-time pad encryption is chosen by P r[K = 0] = 0.45
and P r[K = 1] = 0.55. Consider the one-time pad encryption C = M ⊕ K.
(a) Assume that an adversary A1 guesses M randomly without even examining the
ciphertext C. Show that the success probability of A1 is exactly 0.5.
Answer.

Pr[A1 succeeds]
= Pr[A1 (·) = M ′ ∧ M = M ′ ]
= Pr[A1 (·) = 0 ∧ M = 0] + Pr[A1 (·) = 1 ∧ M = 1]
1 1
= · p0 + · p 1
2 2
1
= · (p0 + p1 )
2
1
=
2
✷
(b) Suggest a good strategy A2 of guessing M if p0 and p1 are known.
Answer.

0.45 · p0
Pr[M = 0|C = 0] =
0.45 · p0 + 0.55 · p1
0.55 · p1
Pr[M = 1|C = 0] =
0.45 · p0 + 0.55 · p1
0.55 · p0
Pr[M = 0|C = 1] =
0.55 · p0 + 0.45 · p1
0.45 · p1
Pr[M = 1|C = 1] =
0.55 · p0 + 0.45 · p1

1-1

Downloaded by abrar nahin (mmrnahin@gmail.com)

 lOMoARcPSD|15338780

When C = 0, A2 guesses M = 0 if 0.45 · p0 > 0.55 · p1 , M = 1 if 0.45 · p0 < 0.55 · p1 ,

or a random bit if 0.45 · p0 = 0.55 · p1 .
When C = 1, A2 guesses M = 0 if 0.55 · p0 > 0.45 · p1 , M = 1 if 0.55 · p0 < 0.45 · p1 ,
or a random bit if 0.55 · p0 = 0.45 · p1 .

3. Discuss the advantages and disadvantages of public-key and symmetric-key cryptosys-

tems.
Answer. public-key:
Advantage: Key management is easy. A user doesn’t need to share a secret with
another user. He just publishes his public key.
Disadvantage: Public-key cryptosystems are based on hard computational problems.
The computation of public-key cryptosystems is more complex than the computation
of symmetric-key cryptosystems.
symmetric-key:
Advantage: The Computational cost is less complex than public-key cryptosystems.
Easy to implement, usually implemented in a hardware level and can handle big
messages.
Disadvantage:Key sharing problem.
✷

4. Describe the polynomial-time reduction A ploy B.

Answer.
A polynomial-time Turing reduction from a problem A to a problem B is an algorithm
that solves problem A using a polynomial number of calls to a subroutine for problem
B, and polynomial time outside of those subroutine calls. ✷

5. The Euclidean algorithm computes gcd(a, b).

(a) Give the algorithm and show that its computation time is polynomial in the total
length m of a and b, where m = len(a) + len(b).
Answer.

Euclidean(a,b)
{
while (b != 0)
{
a = a mod b;
swap (a,b);
}
return a;
}

1-2

Downloaded by abrar nahin (mmrnahin@gmail.com)

 lOMoARcPSD|15338780

The above Euclidean function outputs gcd(a, b). It reduces the length of a and
b alternatively in the while-loop. In each iteration, a = a mod b reduces the
length of a at least one bit. The loop ends when b = 0, i.e., len(b) = 0. In the
worst case, the while-loop takes len(a) + len(b) iterations. The complexity of
computing a = a mod b is O((len(a) − len(b) + 1) ∗ len(b)), and the complexity
of swapping (a, b) is O(len(a) + len(b)). Thus, the computation time of the
Euclidean function is (len(a) + len(b)) ∗ O((len(a) − len(b) + 1) ∗ len(b) + len(a) +
len(b)) = O(m3 + m2 ) = O(m3 ), which is polynomial time of m.
✷

(b) Solve the equation r × 128 + s × 54 = 2.

Answer. Using Euclidean algorithm:
128 = 54 × 2 + 20, 54 = 20 × 2 + 14 ,20 = 14 × 1 + 6 and finally 14 = 6 × 2 + 2.
(We stop here because the remainder is equal to gcd(128, 54)).
Now we compute r, s as following:
From the last equation we have 2 = 14 − 6 × 2 = 14 − 2(20 − 14) = 3 × 14 − 2 × 20
2 = −2 × 20 + 3(54 − 2 × 20) = 3 × 54 − 8 × 20
2 = 3 × 54 − 8(128 − 54 × 2) = 19 × 54 − 8 × 128.
Therefore, the tuple (r = −8, s = 19) is one of many possible solutions.
✷

6. In the SubBytes of AES, f (x) = x−1 mod X8 + X4 + X3 + X + 1. Compute

f (11101001).
Answer.
The extended Euclidean algorithm computes gcd(a, b) and (x, y) such that ax + by =
gcd(a, b). If gcd(a, b) = 1, x is the inverse of a under modulo b. We use the algorithm
to compute f (11101001) under GF (28 ) as follows:

• Compute gcd(a, b)

# a b ⌊a/b⌋
1 X8+ X4
+ X3 + X + 1 X7 + X6
+ X5 + X3 + 1 X +1
2 X + X + X5 + X3 + 1
7 6 X5 X2 + X + 1
3 X5 X3 + 1 X2
4 X3 + 1 X2 X
5 X2 1 X2

• Compute (x, y) reversely

# x y
5 0 1
4 1 X
3 X X3 + 1
2 X3 + 1 X + X + X3 + X2 + 1
5 4

1 X5 + X4 + X3 + X2 + 1 X6 + X3 + X2 + X

1-3

Downloaded by abrar nahin (mmrnahin@gmail.com)

 lOMoARcPSD|15338780

We have X 6 + X 3 + X 2 + X is the inverse of X 7 + X 6 + X 5 + X 3 + 1 under GF (28 )

and f (11101001) = 01001110. ✷

7. Compute 291/2 mod 151, where 151 is prime.

Answer.
Observe that in case p = 4k + 3: a1/2 = a(p+1)/4 mod p. p = 151 = 4.37 + 3, hence,
291/2 = 29(151+1)/4 mod 151 = 86. ✷

8. Find a group of prime order 23.

Answer.
We have prime q = 23 and prime p = 2 × 23 + 1 = 47. The multiplicative cyclic group
Z∗p has the following properties:

• |Z∗p | = 46
• 3 is a generator of Z∗p

Then we can define the cyclic group (Fq , ×) of order q as below:

• 4 is a generator of Fq
• Multiplication × is under modulo 47

9. Consider group Z∗19 . What are the orders of 5 and 11? Find all generators for Z∗19 .
Find subgroups of orders 2, 3, 6, 9 if they exist. Find QR19 .
Answer.
We have ord(5) = 9 and ord(11) = 3. 2, 3, 10, 13, 14, 15 are generators of Z19 ∗ . We have

subgroups F2 = h18i, F3 = h7i, h11i, F6 = h8i, h12i, F9 = h4i, h5i, h6i, h9i, h16i, h17i.
QR19 = {1, 4, 5, 6, 7, 9, 11, 16, 17} ✷

10. Use the Chinese Remainder Theorem to compute 0 ≤ x < 352 for x mod 3 = 1,
x mod 11 = 3, and x mod 16 = 13.
Answer.

• Compute the inverses

(11 ∗ 16)−1 mod 3 = 2

(3 ∗ 16)−1 mod 11 = 3
(3 ∗ 11)−1 mod 16 = 1

• Compute x ≤ 168

x ≡ 1 ∗ 11 ∗ 16 ∗ 2 + 3 ∗ 3 ∗ 16 ∗ 3 + 13 ∗ 3 ∗ 11 ∗ 1 (mod 528)
≡ 352 + 432 + 429 (mod 528)
≡ 157 (mod 528)

1-4

Downloaded by abrar nahin (mmrnahin@gmail.com)

 lOMoARcPSD|15338780

11. Apply the Rabin-Miller primality test for n1 = 133 and n2 = 257.
Answer.
We test n1 = 133 and n2 = 257 for 10 rounds as follows:

• Test n1 = 133 (133 − 1 = 22 × 33)

2 ×33
– 22 ≡ 64 (mod 133)
Therefore, n1 = 133 is not a prime.
• Test n2 = 257 (257 − 1 = 28 )
8 7 6 5
– 22 ≡ 1 (mod 257), 22 ≡ 1 (mod 257),22 ≡ 1 (mod 257), 22 ≡ 1 (mod
4 3
257), 22 ≡ 1 (mod 257),22 ≡ −1 (mod 257)
8 7
– 32 ≡ 1 (mod 257), 32 ≡ −1 (mod 257)
8 7 6 5
– 42 ≡ 1 (mod 257), 42 ≡ 1 (mod 257),42 ≡ 1 (mod 257), 42 ≡ 1 (mod
4 3 2
257), 42 ≡ 1 (mod 257),42 ≡ 1 (mod 257)42 ≡ −1 (mod 257)
8 7
– 52 ≡ 1 (mod 257), 52 ≡ −1 (mod 257)
8 7
– 62 ≡ 1 (mod 257), 62 ≡ −1 (mod 257)
8 7
– 72 ≡ 1 (mod 257), 72 ≡ −1 (mod 257)
8 7 6 5
– 82 ≡ 1 (mod 257), 82 ≡ 1 (mod 257),82 ≡ 1 (mod 257), 82 ≡ 1 (mod
4 3
257), 82 ≡ 1 (mod 257),82 ≡ −1 (mod 257)
8 7 6
– 92 ≡ 1 (mod 257), 92 ≡ 1 (mod 257), 92 ≡ −1 (mod 257)
8 7
– 102 ≡ 1 (mod 257), 102 ≡ −1 (mod 257)
8 7 6 5
– 112 ≡ 1 (mod 257), 112 ≡ 1 (mod 257), 112 ≡ 1 (mod 257), 112 ≡ −1
(mod 257)
Therefore, n2 = 257 may be a prime.

1-5

Downloaded by abrar nahin (mmrnahin@gmail.com)