1.

1) Please draw the general structure inside Round 1 of DES (i.e., the Feistel network for Round 1).

2) Please draw the general structure of AES within one round.

2.

Multiplication in GF($2^4$): Compute A(x)B(x) mod P(x) in GF($2^4$) using the irreducible polynomial P(x) = $x^4$ + x + 1, where A(x) = $x^2$ + 1, and B(x) = $x^3$ + x + 1

3.

1) What is the drawback of Electronic Code Book (ECB) mode? Please justify that with an example.

2) Why is Cipher Block Chaining (CBC) mode better than ECB?

4.

1) Briefly explain why double DES is not secure, but triple DES is.

2) What is the effective key length of 3DES?

5.

Calculations:
1) Fast exponentiation: how to efficiently calculate $x^{21}$ = ? Please explicitly show the calculation procedure.

2) What are the possible element orders in $Z_{13}$?
What are the primitive elements/generators in this group?

먼저 $\mathbb{Z}_{13}^*$ 은 $13$과 서로소인 양의 정수들의 곱셈군입니다. $13$이 소수이므로, $1$부터 $12$까지의 모든 숫자가 이 그룹에 포함됩니다.$\mathbb{Z}_{13}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$따라서 이 그룹의 크기(기호로는 $|G|$)는 $12$가 됩니다.

Possible Element Orders
수업 시간에 배운 순환군의 중요한 성질에 따르면, "어떤 원소의 위수(Order)는 반드시 전체 그룹 크기의 약수(Divisor)여야 한다"는 법칙이 있습니다.현재 그룹의 크기가 $12$이므로, $12$의 약수들을 구하면 됩니다.

정답 1: 가능한 원소의 위수는 $1, 2, 3, 4, 6, 12$ 입니다.

생성자(Generator)란, 거듭제곱을 통해 그룹 내의 모든 원소(12개)를 전부 만들어낼 수 있는 원소를 말합니다. 즉, 원소의 위수가 그룹의 크기와 똑같은 $12$인 원소를 찾아야 합니다.

작은 숫자부터 직접 거듭제곱(모듈러 $13$)을 해보며 찾아봅시다.

위수가 될 수 있는 후보($1, 2, 3, 4, 6$)승에서 모두 $1$이 나오지 않았고 정확히 $12$승에서 최초로 $1$이 나왔습니다. 따라서 $2$는 생성자가 맞습니다.

[나머지 생성자 찾는 팁]
생성자를 하나($2$) 찾았다면 나머지는 쉽게 구할 수 있습니다. $2^k \pmod{13}$ 에서 지수 $k$가 그룹 크기인 $12$와 서로소일 때 그 결과값들도 모두 완벽한 생성자가 됩니다.

$12$와 서로소인 지수 $k$ 값은 $1, 5, 7, 11$ 입니다. 이를 각각 계산해 봅니다.

$k=1$: $2^1 = 2$
$k=5$: $2^5 = 2^4 \cdot 2 \equiv 3 \cdot 2 = 6$
$k=7$: $2^7 = 2^6 \cdot 2 \equiv 12 \cdot 2 = 24 \equiv 11 \pmod{13}$
$k=11$: $2^{11} = 2^6 \cdot 2^5 \equiv 12 \cdot 6 = 72 \equiv 7 \pmod{13}$

정답 2: $\mathbb{Z}_{13}^*$ 의 모든 원시 원소(생성자)는 $2, 6, 7, 11$ 입니다.

6.

Let the two primes p = 41 and q = 17 be given as set-up parameters for RSA.

1) Which of the parameters $e_1$ = 32, $e_2$ = 49 is a valid RSA exponent (i.e., is a valid public key, $e_1$ or $e_2$)? Justify your choice.

2) Compute the corresponding private key $K_{pr}$ = (p, q, d). Use the extended Euclidean algorithm for the inversion and point out every calculation step.