2 Cryptology · 제2장 암호
2.1 Diffie-Hellman key exchange · 디피-헬만 키 교환
디피-헬만 키 교환은 두 사람이 공개 채널을 통해 통신하며 비밀키를 공유하는 알고리즘이다. 편의상 이 두 사람을 앨리스와 밥, 줄여서 A와 B라고 부르자. 공개 채널이라는 것은 “앨리스와 밥이 보낸 메시지를 누구나 알 수 있다”는 뜻이다. 앨리스와 밥은 어떻게 비밀키를 만들어 낼 수 있을까? $a, N \in \mathbb{Z}_{>0}$에 대하여 $a^N \ (\bmod\ n)$을 계산하기는 쉽지만, 주어진 $y \ (\bmod\ n)$과 $a \in \mathbb{Z}_{>0}$에 대하여 $a^N \equiv y \ (\bmod\ n)$을 만족하는 $N$을 찾기는 매우 어렵다는 것을 우리는 알고 있다.
Diffie-Hellman key exchange is the algorithm such that two people communicate through the public channel and share their secret keys. Let’s call above two people Alice and Bob for convenience, simply A and B. Public channel means “Anyone know messages sent by Alice and Bob”. How can Alice and Bod establish a secret key? We know that For $a, N \in \mathbb{Z}_{>0}$, it is easy to calculate $a^N \ (\bmod\ n)$ and for a given $y \ (\bmod\ n)$ and $a \in \mathbb{Z}_{>0}$, it is very hard to find $N$ such that $a^N \equiv y \ (\bmod\ n)$.
주어진 $y \ (\bmod\ n)$과 $a \in \mathbb{Z}_{>0}$에 대하여, $a^N \equiv y \ (\bmod\ n)$을 만족하는 $N$을 찾는 문제를 이산로그 문제라 한다.
For a given $y \ (\bmod\ n)$ and $a \in \mathbb{Z}_{>0}$, the task of finding $N$ such that $a^N \equiv y \ (\bmod\ n)$ is called the discrete logarithm problem.
$2^N \equiv 3 \ (\bmod\ 11)$이라 하자. $N$을 구하라.
| $N$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | $\cdots$ |
|---|---|---|---|---|---|---|---|---|---|
| $2^N$ | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | $\cdots$ |
따라서 $N = 8$이다.
Let $2^N \equiv 3 \ (\bmod\ 11)$. Find $N$.
| $N$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | $\cdots$ |
|---|---|---|---|---|---|---|---|---|---|
| $2^N$ | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | $\cdots$ |
Therefore $N = 8$.
$N$을 구하려면 $0 \le m \le n$인 모든 $a^m \ (\bmod\ n)$을 계산해야 한다. $n, N$의 크기가 대략 $10^{100}$이라 하면, $10^{100}$가지의 가능한 $N$을 확인해야 한다.
To get $N$, compute all $a^m \ (\bmod\ n)$ for $0 \le m \le n$. Suppose that size of $n, N$ about $10^{100}$, then we have to check $10^{100}$ possible $N$.
목표 : A와 B가 도청자가 쉽게 계산할 수 없는 비밀키 $k$를 공유한다.
- A와 B가 큰 소수 $p$와 밑 $a$를 공개적으로 고른다.
- A는 비밀리에 수 $s$를 골라 $a^s \ (\bmod\ p)$를 B에게 보낸다.
- B는 비밀리에 수 $t$를 골라 $a^t \ (\bmod\ p)$를 A에게 보낸다.
- A는 비밀리에 $k \equiv (a^t)^s \ (\bmod\ p)$를, B는 비밀리에 $k \equiv (a^s)^t \ (\bmod\ p)$를 계산한다.
Goal : A and B share secret key $k$ such that not easily calculated by an eavesdropper.
- A and B publicly choose a large prime $p$ and a base $a$.
- A secretly choose a number $s$ and sends $a^s \ (\bmod\ p)$ to B.
- B secretly choose a number $t$ and sends $a^t \ (\bmod\ p)$ to A.
- A secretly calculate $k \equiv (a^t)^s \ (\bmod\ p)$ and B secretly calculate $k \equiv (a^s)^t \ (\bmod\ p)$.
도청자(이브)는 $a$, $p$, $a^s \ (\bmod\ p)$, $a^t \ (\bmod\ p)$만을 안다. 따라서 $k$를 알려면 이브는 $s$ 또는 $t$를 알아야 한다. 그러려면 이브는 이산로그 문제를 풀어야 한다. 그러나 이는 증명하기 쉽지 않다.
Eavesdropper(Eve) only knows $a$, $p$, $a^s \ (\bmod\ p)$, and $a^t \ (\bmod\ p)$. Therefore, to know $k$, Eve need to know $s$ or $t$. Then Eve need to solve the discrete logarithm problem. But it is not easy to proof.
$a = 2$, $p = 11$이라 하자. A는 $s = 4$를, B는 $t = 8$을 택한다. 디피-헬만 키 교환 알고리즘을 계산해 보자.
1. A는 $2^4 \equiv 5 \ (\bmod\ 11)$을 B에게 보낸다.
2. B는 $2^8 \equiv 3 \ (\bmod\ 11)$을 A에게 보낸다.
3. A는 B로부터 3을 받아 $3^s \equiv 3^4 \equiv 4 \ (\bmod\ 11)$을 계산한다.
4. B는 A로부터 5를 받아 $5^t \equiv 5^8 \equiv 4 \ (\bmod\ 11)$을 계산한다.
따라서 비밀키는 4이다.
Assume that $a = 2$ and $p = 11$. A take $s = 4$ and B take $t = 8$. Let’s calculate the Diffie-Hellman key exchange algorithm.
1. A sends $2^4 \equiv 5 \ (\bmod\ 11)$ to B.
2. B sends $2^8 \equiv 3 \ (\bmod\ 11)$ to A.
3. A receives 3 from B, calculate $3^s \equiv 3^4 \equiv 4 \ (\bmod\ 11)$.
4. B receives 5 from A, calculate $5^t \equiv 5^8 \equiv 4 \ (\bmod\ 11)$.
Then secret key is 4.
$3^N \equiv 9 \ (\bmod\ 13)$을 만족하는 $N$을 구하라.
$3$의 거듭제곱을 법 13에 대하여 계산하면 다음과 같다.
| $N$ | 1 | 2 | 3 |
|---|---|---|---|
| $3^N$ | 3 | 9 | 1 |
따라서 $N = 2$일 때 $3^2 \equiv 9 \ (\bmod\ 13)$이 성립한다. 한편 $3^3 \equiv 1 \ (\bmod\ 13)$이므로 법 13에 대한 3의 위수는 3이고, 이후로는 $3^N \ (\bmod\ 13)$이 주기 3으로 $3, 9, 1$을 반복한다. 그러므로 $3^N \equiv 9 \ (\bmod\ 13)$을 만족하는 $N$은 정확히 $N \equiv 2 \ (\bmod\ 3)$을 만족하는 정수들이고, 그중 가장 작은 것은 $N = 2$이다.
Find $N$ such that $3^N \equiv 9 \ (\bmod\ 13)$.
Computing powers of $3$ modulo 13 gives
| $N$ | 1 | 2 | 3 |
|---|---|---|---|
| $3^N$ | 3 | 9 | 1 |
Hence $N = 2$ gives $3^2 \equiv 9 \ (\bmod\ 13)$. Since $3^3 \equiv 1 \ (\bmod\ 13)$, the order of 3 modulo 13 is 3, so $3^N \ (\bmod\ 13)$ cycles through $3, 9, 1$ with period 3. Therefore the solutions of $3^N \equiv 9 \ (\bmod\ 13)$ are exactly the integers $N \equiv 2 \ (\bmod\ 3)$, the smallest of which is $N = 2$.
디피-헬만 키 교환 알고리즘을 서술하라.
디피-헬만 키 교환 알고리즘의 목표는 A와 B가 공개 채널을 통해서만 통신하면서도, 도청자가 쉽게 계산해 낼 수 없는 공통의 비밀키 $k$를 공유하는 것이다. 절차는 다음과 같다.
- A와 B는 먼저 큰 소수 $p$와 밑 $a$를 정하여 공개적으로 공유한다.
- A는 비밀리에 정수 $s$를 골라 $a^s \ (\bmod\ p)$를 계산한 뒤 이를 B에게 보낸다.
- B는 비밀리에 정수 $t$를 골라 $a^t \ (\bmod\ p)$를 계산한 뒤 이를 A에게 보낸다.
- A는 B로부터 받은 값을 자신의 $s$제곱하여 $k \equiv (a^t)^s \equiv a^{st} \ (\bmod\ p)$를 얻고, B는 A로부터 받은 값을 자신의 $t$제곱하여 $k \equiv (a^s)^t \equiv a^{st} \ (\bmod\ p)$를 얻는다. 두 값은 같은 $a^{st} \ (\bmod\ p)$이므로 A와 B는 같은 비밀키 $k$를 공유하게 된다.
도청자는 공개 채널을 통해 $p$, $a$, $a^s \ (\bmod\ p)$, $a^t \ (\bmod\ p)$만을 알 수 있을 뿐, $s$나 $t$ 자체는 알 수 없다. 도청자가 $k$를 알아내려면 이 값들로부터 $s$ 또는 $t$를 구해야 하는데, 이는 이산로그 문제(정의 2.1)를 푸는 것과 같아서 일반적으로 계산이 매우 어렵다.
Give the Diffe-Helliman key exchange algorithm.
The goal of the Diffie-Hellman key exchange algorithm is for A and B to communicate only over a public channel while still ending up sharing a common secret key $k$ that an eavesdropper cannot easily compute. The procedure is as follows.
- A and B first agree on and publicly share a large prime $p$ and a base $a$.
- A secretly chooses an integer $s$, computes $a^s \ (\bmod\ p)$, and sends it to B.
- B secretly chooses an integer $t$, computes $a^t \ (\bmod\ p)$, and sends it to A.
- A raises the value received from B to the power $s$ to get $k \equiv (a^t)^s \equiv a^{st} \ (\bmod\ p)$, and B raises the value received from A to the power $t$ to get $k \equiv (a^s)^t \equiv a^{st} \ (\bmod\ p)$. Since both equal the same $a^{st} \ (\bmod\ p)$, A and B end up sharing the same secret key $k$.
Over the public channel, an eavesdropper can only see $p$, $a$, $a^s \ (\bmod\ p)$, and $a^t \ (\bmod\ p)$, but not $s$ or $t$ themselves. To recover $k$, the eavesdropper would need to determine $s$ or $t$ from these values, which amounts to solving the discrete logarithm problem (Definition 2.1) — a computation that is, in general, very hard.
$p = 13$이고 밑이 3이라 하자. A는 6을, B는 5를 택한다. 이 경우 디피-헬만 키 교환 알고리즘을 단계별로 따라가며 비밀키를 계산하라.
디피-헬만 키 교환 알고리즘(algo04-1)을 $p = 13$, $a = 3$, $s = 6$, $t = 5$에 대하여 단계별로 따라간다.
1. $3^3 = 27 \equiv 1 \ (\bmod\ 13)$이므로 $3^6 = (3^3)^2 \equiv 1^2 \equiv 1 \ (\bmod\ 13)$이다. 따라서 A는 1을 B에게 보낸다.
2. $3^5 = 3^3 \cdot 3^2 \equiv 1 \cdot 9 \equiv 9 \ (\bmod\ 13)$이다(직접 계산해도 $3^5 = 243 = 18 \cdot 13 + 9$). 따라서 B는 9를 A에게 보낸다.
3. A는 B로부터 받은 9를 자신의 $s = 6$제곱하여 $9^6 \equiv (3^5)^6 = 3^{30} = (3^3)^{10} \equiv 1^{10} \equiv 1 \ (\bmod\ 13)$을 계산한다.
4. B는 A로부터 받은 1을 자신의 $t = 5$제곱하여 $1^5 \equiv 1 \ (\bmod\ 13)$을 계산한다.
두 값이 일치하므로 비밀키는 $k = 1$이다.
이 예는 퇴화된 경우이다. 법 13에 대한 3의 위수는 3(연습문제 2.4)으로 매우 작아 3은 법 13의 원시근이 아니므로, $3$의 거듭제곱은 $\{1, 3, 9\}$ 세 값만을 순환하고, 그 결과 비밀키 역시 이 좁은 값들 중 하나로만 정해진다. 실제 응용에서는 이렇게 위수가 작은 밑을 피하고 원시근을 밑으로 사용해야 도청자가 비밀키를 추측하기 어려워진다.
Let $p = 13$ and base 3. A take 6 and B take 5. In this case, by following the Diffie-Hellman key exchange algorithm step by step. Calculate the secret key.
We follow the Diffie-Hellman key exchange algorithm (algo04-1) step by step with $p = 13$, $a = 3$, $s = 6$, $t = 5$.
1. Since $3^3 = 27 \equiv 1 \ (\bmod\ 13)$, we get $3^6 = (3^3)^2 \equiv 1^2 \equiv 1 \ (\bmod\ 13)$. So A sends 1 to B.
2. $3^5 = 3^3 \cdot 3^2 \equiv 1 \cdot 9 \equiv 9 \ (\bmod\ 13)$ (directly, $3^5 = 243 = 18 \cdot 13 + 9$). So B sends 9 to A.
3. A raises the value 9 received from B to the power $s = 6$: $9^6 \equiv (3^5)^6 = 3^{30} = (3^3)^{10} \equiv 1^{10} \equiv 1 \ (\bmod\ 13)$.
4. B raises the value 1 received from A to the power $t = 5$: $1^5 \equiv 1 \ (\bmod\ 13)$.
The two values agree, so the secret key is $k = 1$.
This example is degenerate. The order of 3 modulo 13 is 3 (Exercise 2.4), which is very small, so 3 is not a primitive root modulo 13; the powers of 3 only cycle through the three values $\{1, 3, 9\}$, and consequently the secret key is forced to be one of these few values. In practice, one should avoid a base with such a small order and instead use a primitive root, so that an eavesdropper cannot easily guess the secret key.
2.2 RSA · RSA
1977년, 리베스트, 샤미르, 에이들먼이 RSA 알고리즘을 소개하였다. 이는 권한이 없는 사람은 읽을 수 없도록 메시지를 보내는 암호 방식이다. RSA 이전에는 암호화와 복호화에 같은 키를 사용하였다. 그러나 RSA에서는 암호화에 하나의 키를, 복호화에는 다른 키를 사용한다. RSA는 공개키 암호체계로서, 공개키를 가진 사람은 누구나 메시지를 암호화할 수 있지만 복호화하려면 개인키가 필요하며, 공개키로부터 개인키를 알아내기는 어렵다는 점에 유의하라.
In 1977, Rivest, Shadmir, and Adeleman introduced the RSA algorithm. It is an encryption scheme which is a way of sending message so that no unauthorized person can read it. Before RSA, encryption and decryption with the same key. But, in RSA, one key is used for encryption and different key is used for decryption. Note that RSA is a public-key cryptosystem, anyone with a public key can encrypt a message, but a private key is required for decryption and difficult to know the private key through the public key.
- 큰 소수 $p, q$를 택한다(각각 십진 100자리 이상).
- $N = pq$, $\phi(N) = (p - 1)(q - 1)$을 계산한다. 그리고 $\gcd(e, \phi(N)) = 1$을 만족하는 정수 $e$를 무작위로 고른다.
- 유클리드 호제법을 이용하여 $d \equiv e^{-1} \ (\bmod\ \phi(N))$을 계산한다.
- 공개키 $(N, e)$를 공개한다.
- 공개키 : $(N, e)$
- 메시지 : $x(0 \lt x \lt N)$
- 암호화 : $x^e \ (\bmod\ N)$
- 복호화 : 받은 메시지 $y$에 대하여 $y^d \ (\bmod\ N)$, 즉 $y \equiv x^e \ (\bmod\ N)$
- Take large primes $p, q$ (each with at least 100 decimal digits)
- Compute $N = pq$, $\phi(N) = (p - 1)(q - 1)$. And randomly choose an integer $e$ such that $\gcd(e, \phi(N)) = 1$.
- Using Euclidean algorithm, Compute $d \equiv e^{-1} \ (\bmod\ \phi(N))$.
- Announce public key $(N, e)$.
- Public key : $(N, e)$
- message : $x(0 \lt x \lt N)$
- Encryption : $x^e \ (\bmod\ N)$
- Decryption : $y^d \ (\bmod\ N)$ for $y$ received message i.e., $y \equiv x^e \ (\bmod\ N)$
메시지의 범위는 큰 문제가 아님에 유의하라. 컴퓨터 파일은 수로 이루어져 있고 큰 수는 블록으로 나눌 수 있기 때문이다. 다음을 쉽게 확인할 수 있다.
Note that range of the message is not a big deal. Because computer files consist of numbers and a large number can split into blocks. We can easily check that
$p = 5, q = 11$이라 하자. $N = pq = 55$라 하면 $\phi(N) = 40$이다. 공개키를 $(N, e) = (55, 3)$이라 하면 $d \equiv 27 \ (\bmod\ 40)$이다. $x = 4$를 택하자. 그러면 4의 암호화는 $x^e \equiv 4^3 \equiv 64 \equiv 9 \ (\bmod\ 55)$이고, 9의 복호화는 $9^{27} \equiv 4 \ (\bmod\ 55)$이다.
Take $p = 5, q = 11$. Let $N = pq = 55$. Then $\phi(N) = 40$. Let public key $(N, e) = (55, 3)$. Then $d \equiv 27 \ (\bmod\ 40)$. Choose $x = 4$. Then encryption of 4 is $x^e \equiv 4^3 \equiv 64 \equiv 9 \ (\bmod\ 55)$. And decryption of 9 is $9^{27} \equiv 4 \ (\bmod\ 55)$.
RSA 알고리즘을 생각하자. $(N, e) = (323, 11)$이라 하자. 메시지가 316이라 하자.
1. 개인키를 구하라.
2. 암호화된 메시지를 구하라.
3. 2)에서 얻은 암호화된 메시지를 복호화하는 방법을 설명하라.
1. $N = 323 = 17 \cdot 19$이므로 $\phi(N) = (17-1)(19-1) = 16 \cdot 18 = 288$이다. 개인키 $d$는 $d \equiv 11^{-1} \ (\bmod\ 288)$을 만족해야 하므로, 유클리드 호제법으로 구한다.
역대입하면
따라서 $d \equiv 131 \ (\bmod\ 288)$이다(확인: $11 \cdot 131 = 1441 = 5 \cdot 288 + 1$).
2. 암호화된 메시지는 $316^{11} \ (\bmod\ 323)$이다. $316 \equiv -7 \ (\bmod\ 323)$이므로 $-7$의 거듭제곱으로 계산한다.
$11 = 8 + 2 + 1$이므로
$220 \cdot 49 = 10780 \equiv 121 \ (\bmod\ 323)$이고 $121 \cdot 7 = 847 \equiv 201 \ (\bmod\ 323)$이므로 $7^{11} \equiv 201 \ (\bmod\ 323)$이다. 따라서
이고, 암호화된 메시지는 122이다.
3. 복호화는 $y^d = 122^{131} \ (\bmod\ 323)$을 계산하는 것이다. $131 = 128 + 2 + 1 = (10000011)_2$이므로, $122^2, 122^4, 122^8, \ldots, 122^{128} \ (\bmod\ 323)$을 반복해서 제곱하여 구한 뒤 $122^{131} = 122^{128} \cdot 122^2 \cdot 122$를 계산하는 반복제곱법(정리 1.20)으로 값을 얻을 수 있으며, 그 결과는 $122^{131} \equiv 316 \ (\bmod\ 323)$이다. 이 값이 원래 메시지와 같은 이유는 다음과 같다. $ed = 11 \cdot 131 = 1441 = 1 + 5 \cdot 288 = 1 + 5\phi(N)$이므로
$316 = 4 \cdot 79$이고 $17, 19 \nmid 316$이므로 $\gcd(316, 323) = 1$이고, 정리 1.61(오일러 정리)에 의해 $x^{\phi(N)} \equiv 1 \ (\bmod\ N)$이다. 따라서 $y^d \equiv x \cdot 1^5 \equiv x = 316 \ (\bmod\ 323)$이 성립하여, 복호화하면 원래 메시지 316을 되찾는다.
Consider the RSA algorithm. Let $(N, e) = (323, 11)$. Suppose that the message is 316.
1. Find the secret key.
2. Find the encrypted message.
3. Explain how to decrypt the encrypted message in ii).
1. Since $N = 323 = 17 \cdot 19$, we have $\phi(N) = (17-1)(19-1) = 16 \cdot 18 = 288$. The private key $d$ must satisfy $d \equiv 11^{-1} \ (\bmod\ 288)$, so we find it by the Euclidean algorithm.
Back-substituting,
Hence $d \equiv 131 \ (\bmod\ 288)$ (check: $11 \cdot 131 = 1441 = 5 \cdot 288 + 1$).
2. The encrypted message is $316^{11} \ (\bmod\ 323)$. Since $316 \equiv -7 \ (\bmod\ 323)$, we compute powers of $-7$.
Since $11 = 8 + 2 + 1$,
Now $220 \cdot 49 = 10780 \equiv 121 \ (\bmod\ 323)$ and $121 \cdot 7 = 847 \equiv 201 \ (\bmod\ 323)$, so $7^{11} \equiv 201 \ (\bmod\ 323)$. Therefore
so the encrypted message is 122.
3. Decryption amounts to computing $y^d = 122^{131} \ (\bmod\ 323)$. Since $131 = 128 + 2 + 1 = (10000011)_2$, this can be computed by repeated squaring (Theorem 1.20): square $122^2, 122^4, 122^8, \ldots, 122^{128} \ (\bmod\ 323)$ repeatedly and then compute $122^{131} = 122^{128} \cdot 122^2 \cdot 122$, giving $122^{131} \equiv 316 \ (\bmod\ 323)$. To see why this returns the original message, note that $ed = 11 \cdot 131 = 1441 = 1 + 5 \cdot 288 = 1 + 5\phi(N)$, so
Since $316 = 4 \cdot 79$ and $17, 19 \nmid 316$, we have $\gcd(316, 323) = 1$, so by Theorem 1.61 (Euler's theorem) $x^{\phi(N)} \equiv 1 \ (\bmod\ N)$. Hence $y^d \equiv x \cdot 1^5 \equiv x = 316 \ (\bmod\ 323)$, and decrypting recovers the original message 316.
$N = pq$라 하자. $\dfrac{\phi(N)}{N}$을 어림하라.
$N = pq$이면 $\phi(N) = (p-1)(q-1)$이므로
이다. $p, q$가 큰 소수이면 $1/p$, $1/q$, $1/(pq)$가 모두 매우 작으므로 $\phi(N)/N$은 1에 매우 가깝다. 예를 들어 $p, q$가 각각 십진 100자리 소수이면 $1/p + 1/q - 1/(pq)$는 대략 $2 \times 10^{-100}$이므로 $\phi(N)/N \approx 1 - 2 \times 10^{-100}$이다. 즉 $0 \lt x \lt N$인 정수 중 법 $N$에 대하여 가역이 아닌 것(곧 $p$ 또는 $q$의 배수인 것)의 비율은 극히 작으므로, 거의 모든 메시지 $x$는 법 $N$에 대하여 가역이다.
Let $N = pq$. Estimate $\dfrac{\phi(N)}{N}$.
Since $N = pq$, we have $\phi(N) = (p-1)(q-1)$, so
When $p, q$ are large primes, $1/p$, $1/q$, and $1/(pq)$ are all very small, so $\phi(N)/N$ is very close to 1. For instance, if $p, q$ are each primes with 100 decimal digits, then $1/p + 1/q - 1/(pq)$ is about $2 \times 10^{-100}$, so $\phi(N)/N \approx 1 - 2 \times 10^{-100}$. That is, among the integers $x$ with $0 \lt x \lt N$, only a vanishingly small fraction (namely the multiples of $p$ or $q$) fail to be invertible modulo $N$, so almost every message $x$ is invertible modulo $N$.