RSA - 기계인간 John Grib

Cryptosystem
Encryption
- 암호화 예제
Decryption
- 복호화 예제
참고문헌

Cryptosystem

RSA 암호시스템에서 각 개인은 공개 키와 개인 키를 갖는다.

공개 키: $(n, e)$
개인 키: $(n, d)$

키를 얻는 방법은 다음과 같다.

200자리 이상의 큰 소수 둘을 찾아 선택하고 $p, q$ 라 한다.
- 단, $p \ne q$ .
$n = p \times q$ 라 한다.
- 이 $n$ 은 암/복호화할 때 modulus로 쓸 것이다.
$(p - 1)(q - 1)$ 을 계산해서, 이것을 $\varphi(n)$ 이라 한다.
$φ (n)$ 과 서로소인 정수 $e$ 를 찾아 선택한다.
- 단, $e \lt \varphi(n)$ .
$d \times e \equiv 1 (mod φ (n))$ 이 성립하는 $d$ 를 구한다.
- 즉 $e$ 모듈로 $\varphi(n)$ 의 역을 구하고, 그것을 $d$ 라고 한다.

이 때 공개키는 $(n, e)$ 이고, 개인 키는 $(n, d)$ 가 된다.

Encryption

평문 $M$ 을 암호화한다고 하자.

평문 $M$ 의 각 알파벳을 두 자리 숫자로 변환한다.
- A는 00, B는 01, C는 02, …
이 숫자들을 붙여 커다란 하나의 숫자열로 만든다.
숫자열을 같은 크기의 블록들로 나눈다.
- 단, 각 블록의 길이는 n을 초과하지 않는 짝수여야 한다.
- 마지막 블록의 길이가 다른 블록보다 짧다면 평문에 더미 문자열을 덧붙여서 길이를 맞춘다.
이제 숫자로 바뀐 평문들의 블록 $m_1, m_2, ..., m_k$ 를 얻었다.
$C = M^e \bmod n$ 을 사용하여 각 블록 $m_i$ 를 암호화된 블록 $c_i$ 로 변환한다.
암호화된 $c_1, c_2, ..., c_k$ 를 암호문의 수신자에게 보낸다.

암호화 예제

Encrypt the message STOP using the RSA cryptosystem with key $(2537, 13)$ . Note that $2537 = 43 \times 59$ , $p = 43$ and $q = 59$ are primes, and $\gcd(e,(p − 1)(q − 1)) = gcd(13,42 \times 58) = 1$ .

다음 조건들을 사용해 공개 키 $(2537, 13)$ 으로 평문 "STOP"을 암호화하시오.

2537 = 43 \times 59 p = 43 q = 59 gcd (e, (p - 1) (q - 1)) = gcd (13, 42 \times 58) = 1

$2537 = 43 \times 59 \\ p = 43 \\ q = 59 \\ \gcd(e,(p − 1)(q − 1)) = \gcd(13,42 \times 58) = 1$

일단 STOP 을 숫자로 변환하자. A 를 00, B를 01 이라 하면…

S	T	O	P
18	19	14	15

블록의 길이를 4로 정했다고 하자. 그러면 이 숫자는 두 개의 블록으로 쪼개지게 된다.

m_{1} = 1819 m_{2} = 1415

$m_1 = 1819 \\ m_2 = 1415 \\$

이제 각 블록을 $C = M^e \bmod n$ 에 넣으면 된다!

공개 키가 $(n, e) = (2537, 13)$ 이므로, $n = 2537$ 이고 $e = 13$ 이다.

\begin{matrix} c_{1} & = (1819)^{13} mod 2537 = 2081 c_{2} & = (1415)^{13} mod 2537 = 2182 \end{matrix}

$\begin{align} c_1 & = (1819)^{13} \bmod 2537 \\ & = 2081 \\ c_2 & = (1415)^{13} \bmod 2537 \\ & = 2182 \\ \end{align}$

직접 계산한다면 숫자가 꽤 크므로 나머지를 구하는 연산은 이진법을 사용해 거듭제곱 수의 나머지를 구하는 알고리즘을 사용하자.

암호화된 메시지는 다음과 같다.

$2081$ $2182$

Decryption

해독키 $d$ 는 $e$ 모듈로 $(p-1)(q-1)$ 의 역이므로, $de ≡ 1 \pmod{(p-1)(q-1)}$ 이다.

( $e$ 와 $(p-1)(q-1)$ 이 서로소이기 때문에 역 $d$ 는 반드시 존재한다.)

따라서 $de = 1 + k (p-1)(q-1)$ 인 정수 k 가 반드시 존재한다.

$C^d ≡ (M^e)^d (\bmod n)$ 이므로, 원문 $M$ 을 얻어내기 위해 다음과 같이 생각할 수 있다.

\begin{matrix} C^{d} & \equiv (M^{e})^{d} (mod n) \equiv M^{e d} (mod n) \equiv M^{1 + k (p - 1) (q - 1)} (mod n) \end{matrix}

$\begin{align} C^d & ≡ (M^e)^d \pmod n \\ & ≡ M^{ed} \pmod n \\ & ≡ M^{1+k(p-1)(q-1)} \pmod n \\ \end{align}$

한편 $p, q$ 가 소수이므로 다음과 같이 페르마의 소정리를 사용할 수 있다.

M^{p - 1} \equiv 1 (mod p) M^{q - 1} \equiv 1 (mod q)

$M^{p-1} ≡ 1 \pmod p \\ M^{q-1} ≡ 1 \pmod q$

그러므로 $C^d, M$ 은 $\bmod p$ 에서 합동이다.

\begin{matrix} C^{d} & \equiv M \times M^{k (p - 1) (q - 1)} (mod p) \equiv M \times 1^{k (q - 1)} (mod p) \equiv M (mod p) \end{matrix}

$\begin{align} C^d & ≡ M \times M^{k \color{red}{(p-1)}(q-1)} \pmod p \\ & ≡ M \times 1^{k(q-1)} \pmod p \\ & ≡ M \pmod p \\ \end{align}$

같은 방법으로, $C^d, M$ 은 $\bmod q$ 에서도 합동이다.

\begin{matrix} C^{d} & \equiv M \times M^{k (p - 1) (q - 1)} (mod q) \equiv M \times 1^{k (p - 1)} (mod q) \equiv M (mod q) \end{matrix}

$\begin{align} C^d & ≡ M \times M^{k(p-1) \color{red}{(q-1)}} \pmod q \\ & ≡ M \times 1^{k(p-1)} \pmod q \\ & ≡ M \pmod q \\ \end{align}$

따라서 다음과 같이 정리할 수 있다.

C^{d} \equiv M (mod p q)

$C^d ≡ M \pmod{pq}$

복호화 예제

We receive the encrypted message 0981 0461. What is the decrypted message if it was encrypted using the RSA cipher from Example 8?

암호화된 메시지 $0981, 0461$ 가 위의 암호화 예제와 같은 조건으로 암호화되었다고 하자.
원문은 무엇인가?

위의 예제에서는 공개 키 $(n, e) = (2537, 13)$ 을 제공했다. 그러나 개인 키 $(d, e)$ 는 제공하지 않아서 $d$ 가 무엇인지 모른다.

$d$ 부터 구하자.

\begin{matrix} d \cdot e & \equiv 1 (mod φ (n)) \equiv 1 (mod (p - 1) \cdot (q - 1)) d \cdot 13 & \equiv 1 (mod (43 - 1) \cdot (59 - 1)) \equiv 1 (mod 2436) \end{matrix}

$\begin{align} d \cdot e & ≡ 1 (\bmod \varphi(n)) \\ & ≡ 1 (\bmod (p-1) \cdot (q-1)) \\ d \cdot 13 & ≡ 1 (\bmod (43-1) \cdot (59-1)) \\ & ≡ 1 (\bmod 2436) \\ \end{align}$

$d$ 는 13 모듈로 2436 의 역이다.

역을 구하는 방법을 사용해서 역을 구해보자.

\begin{matrix} d \cdot 13 = 1 (mod 2436) \end{matrix}

$\begin{align} d \cdot 13 = 1 (\bmod 2436) \end{align}$

먼저 유클리드 호제법을 사용해 $gcd(13, 2436)$ 을 찾도록 하자.

\begin{matrix} 2436 & = 13 \times 187 + 5 13 & = 5 \times 2 + 3 5 & = 3 \times 1 + 2 3 & = 2 \times 1 + 1 2 & = 1 \times 1 + 1 1 & = 1 \times 1 + 0 \end{matrix}

$\begin{align} 2436 & = 13 \times 187 + 5 \\ 13 & = 5 \times 2 + 3 \\ 5 & = 3 \times 1 + 2 \\ 3 & = 2 \times 1 + 1 \\ 2 & = 1 \times 1 + 1 \\ 1 & = 1 \times 1 + 0 \\ \end{align}$

$\gcd(13, 2436) = 1$ 이다.

베주의 항등식을 만들면 사칙연산만으로 쉽게 역을 구할 수 있다.

1 = s \times 13 + t \times 2436

$1 = s \times 13 + t \times 2436$

\begin{matrix} 1 & = 3 - 2 = 3 - (5 - 3) = 2 \times 3 - 5 = 2 \times 3 - (2436 - 13 \times 187) = 2 \times (13 - 5 \times 2) - (2436 - 13 \times 187) = (2 + 187) \times 13 - 4 \times 5 - 2436 = 189 \times 13 - 4 \times (2436 - 13 \times 187) - 2436 = (189 + 4 \times 187) \times 13 + (- 4 - 1) \times 2436 = 937 \times 13 - 5 \times 2436 \end{matrix}

$\begin{align} 1 & = 3 - 2 \\ & = 3 - (5 - 3) \\ & = 2 \times 3 - 5 \\ & = 2 \times 3 - (2436 - 13 \times 187) \\ & = 2 \times (13 - 5 \times 2) - (2436 - 13 \times 187) \\ & = (2 + 187) \times 13 - 4 \times 5 - 2436 \\ & = 189 \times 13 - 4 \times (2436 - 13 \times 187) - 2436 \\ & = (189 + 4 \times 187) \times 13 + ( -4 -1 ) \times 2436 \\ & = \color{red}{937} \times 13 -5 \times 2436 \\ \end{align}$

따라서 $13 \times d$ 를 $2436$ 으로 나누었을 때 나머지 1 이 나오게 하는 수 $d$ 는 $937$ 이다.

이제 블록 $C$ 를 해독하기 위해 다음 식에 입력만 하면 된다.

\begin{matrix} M & = C^{d} mod p q = C^{937} mod 2537 \end{matrix}

$\begin{align} M & = C^d \bmod pq \\ & = C^{937} \bmod 2537 \\ \end{align}$

$0981, 0461$ 을 넣어보자.

\begin{matrix} m_{1} & = 981^{937} mod 2537 = 704 m_{2} & = 461^{937} mod 2537 = 1115 \end{matrix}

$\begin{align} m_1 & = 981^{937} \bmod 2537 \\ & = 704 \\ m_2 & = 461^{937} \bmod 2537 \\ & = 1115 \\ \end{align}$

$0704, 1115$ 가 나왔다.

A 가 00 이고, B 가 01 이었으므로, 다음과 같이 원문을 알아낼 수 있다.

07	04	11	15
H	E	L	P

참고문헌

Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일