개에서도 알았던 RSA

18529 단어 RSA파이썬암호

소개



안녕하세요. 개입니다.
개에서도 알았던 신경이 쓰였으므로 RSA에 대해 씁니다.

RSA란?



자주 사용되는 공개키 암호화 방식의 하나입니다.
(공개 키 암호 방식에 대해서는 아래쪽에 쓰고 있으므로 안심하십시오)

Wikipedia 에는 다음과 같이 쓰여져 있습니다.

RSA 암호란, 자릿수가 큰 합성수의 소인수 분해 문제가 곤란하다는 것을 안전성의 근거로 한 공개키 암호의 하나이다.

요컨대 소인수 분해하면 풀리지만, 대단한 컴퓨터를 사용해도 대단한 시간이 걸리므로, 적어도 살아 있는 동안은 안전이라고 하는 것 같습니다.

RSA 암호는 키 길이가 1024bit 미만이라도 "슈퍼 컴퓨터에서 640개의 노드를 모두 사용한 경우에도 키 데이터를 찾는 데 10년 정도 걸린다"고 합니다.

현재 추천되고 있는 것이 2048bit 이상이라고 생각하면, 매우 살아 있는 시간에 풀 수 있다고는 생각하지 않네요. ※1

전제 지식



공개키



다른 사람에게 보여주는 좋은 열쇠.
이 키로 일반 텍스트를 암호화합니다 (암호화).

비밀키



타인에게 보여줄 수 없는 열쇠.
이 키로 암호문을 바탕으로 평문을 만듭니다 (복호).

공개 키 암호화



공개키로 암호화한 암호문은, 비밀열쇠로 복호할 수 있다고 하는 성질이 있습니다.
(그런 성질을 갖도록 만들어져 있는 것입니다.※2)

그 특성을 사용하여 다음 절차에 따라 암호를 교환합니다.

절차



암호문의 발신자와 수신자와 사용하여 설명합니다.

1. 키 쌍 만들기



공개키와 비공개키를 수령자가 작성합니다.
개인 키는 엄격하게 관리하고 공개 키는 누구나 볼 수 있습니다.

2. 암호화



발신자가 공개 된 수신자의 공개 키를 가져 와서,
그 키를 바탕으로 평문(암호화하고 싶은 문장)을 암호화합니다.

3. 전송



암호문을 보냅니다.

4. 복호



수신자가 암호문을 받고,
비밀키를 사용해 복호를 실시해, 평문을 꺼냅니다.

절차

まずは何も考えず手順を追ってみましょう。
(今回使用する値はすべて自然数です。)

키 쌍 만들기

以下の手順で受け手が公開鍵と秘密鍵を求めます。
求めた公開鍵は送り手に渡します。

1. 두 개의 큰 소수를 준비

適当に大きい素数である $P$ と $Q$ を用意します。
(本来はここでランダムに大きな素数を取り出します。)

P = 17, \quad Q = 13
コード例(Python)
P = 17
Q = 13

2. 공개키 1을 요구한다

上記の素数の積を公開鍵$N$と置きます。
$$N = P \times Q$$

計算例

$$N = P \times Q = 17 \times 13 = 221$$

コード例(Python)
N = P * Q

3. L 계산

서로

$N$との最大公約数が1になる数を$N$と互いに素である数といいます。
例を上げるなら$5$と$7$は互いに素ですし、$3$と$6$は互いに素ではないです。

오일러 함수

今回は$N$より小さい、$N$と互いに素である数字の数$L$を調べます。
このときの数字の数を$\phi(N)$とも表記します。
(オイラー関数と言うやつです。)

$$L = \phi(N)$$

例えば$T = 6$の場合、$T$より小さくて$T$との最大公約数が1になる数字は、
$1$と$5$があるので、$\phi(T) = 2$となります。

두 소수의 곱을 인수로 사용하는 오일러 함수

素数である$P$と$Q$は互いに素なのですが、
$P$と$Q$が互いに素であるとき、

$\phi(P \times Q)$ = $(P-1) \times (Q-1)$であることが知られています。

실천·계산

もう一度いいますが、今回は$N$より小さい$N$と素である数字の数$ L(=\phi(N))$ を求めます。

$N = P \times Q$ですので、

$$L = \phi(N) = \phi(P \times Q) = (P-1)\times(Q-1)$$
となります。

計算例
\begin{align}
P &= 13, \quad Q = 17 \\
\\
L &= \phi(N) \\
&= (P-1)\times (Q-1)  \\
&= (17-1)\times(13-1) \\
&= 16 \times 12 = 192
\end{align}
コード例(Python)
L = (P-1) * (Q-1)

4. 공개키 2를 결정한다

조건

公開鍵$E$は以下の条件を満たさないといけません。

  • $1$より大きく、$L$より小さい
  • $L$と互いに素である
    (つまり$E$と$L$の最大公約数が$1$)
決める例

$L = 192$のとき、
$E = 5$は公開鍵として選ぶことができます。
($E$として選べる数字はいくつもありますが、
今回は$5$を選びます。)

  • $1 < 5 < 192$がなりたつ
  • $5$と$192$は互いに素である
    (つまり$5$と$192$の最大公約数が$1$)

※3

コード例(Python)
'''
Eとして選べる数字はいくつもあるが、
今回は一番小さいものを選んでいる
'''

for E in range(2, L):
    if math.gcd(E, L) == 1:
       break

5. 비밀키를 결정한다

조건

公開鍵$D$は以下の条件を満たさないといけません。

  • $E \times D = L \times n + 1 \quad(nは任意の整数)$
    • 式を変形すると、$E \times D \bmod L = 1$
      つまり$E \times D$を$L$で割ったあまりが$1$である。
  • $1$より大きく、$L$より小さい
計算例

$L = 192, \quad E = 5$のとき、
秘密鍵$D$として$77$が成り立ちます。

  • $5 \times 77 \div 192 = 3 ... 1$

※3

コード例(Python)
for D in range(2, L):
    if (E * D) % L == 1:
       break

암호화

以下の操作は送り手が受け手から受け取った、
公開鍵($N$と$E$)をもとに行います。

6. 암호화

暗号文$C$は、$M$を$E$乗したものを$N$で割った余りとなります。

$$ C = M^E \bmod N $$

計算例
\begin{align}
N &= 221 \\
E &= 5 \\
M &= 11\\
C &= 11^5 \bmod 221 \\
  &= 163
\end{align}
コード例
# 公開鍵N、公開鍵Eは
# 受け手からもらったものを使う
N = 221
E = 5

# 平文Mを用意
M = 11

# 暗号化
C = M ** E % N
print(f'暗号文 C = {C}')

해독

以下の操作は受け手が送り手から受け取った、
暗号文$C$と受け手が持っていた秘密鍵$D$、公開鍵$N$を使って復号を行います。

7. 복호

平文$M$は$C$を$D$乗したものを$N$で割った余りとなります。
$$M = C^D \bmod N$$

計算例
\begin{align}
C &= 163 \\
N &= 221 \\
D &= 77 \\
M &= 163^{77}\bmod{221}\\
  &= 11
\end{align}
コード例
# 暗号文Cは
# 送り手からもらっている
C = 163

# 公開鍵N、秘密鍵Dは
# 既に計算したものを使う
N = 221
D = 77

# 復号
M = C ** D % N
print(f'平文(復号後) M = {M}')

안전성에 대하여

機密でない情報は、公開鍵$E$、$N$と暗号文$C$です。
これらを使って平文$M$、または$D$を求めることができれば、この暗号が危険といえます。

Mを求める

$M = C^D \bmod N$より、平文$M$を求めるためには暗号鍵$D$が必要です。

Dを求める

二つの大きな素数$P$と$Q$が分かれば、$P$と$Q$と公開鍵$E$をもとに、
鍵ペア作成と同じ手順で暗号鍵$D$が計算できます。

PまたはQ求める

$N = P \times Q$なので、二つの大きな素数$P$と$Q$は公開鍵$N$を素因数分解することで求められます。
しかし、あまりにも$P$と$Q$が大きいため、計算時間上困難です。

요약

今回は名前は知っているけど、仕組みはわかってないことが多い、RSAの仕組みについて解説しました。
このような仕組みによって、世の中の通信の安全性が保たれていると思うと、なんだかおもしろいですね。

以下に今回使った数式、処理、コード等についてまとめてあるので、ぜひ使ってください。

名前 意味 機密情報であるか
$P$ - 大きな素数 $17$ Yes
$Q$ - 大きな素数 $13$ Yes
$N$ $N = P \times Q$ 公開鍵1 $17 \times 13 = 221$ No
$L$ $L=\phi(N) = (P-1) \times (Q-1)$ $N$より小さい、$N$と互いに素である数字の数 $(17-1)\times(13-1) = 192$ Yes
$E$ $1 < E < L,\quad gcd(E, L) = 1$ 公開鍵2 $5$ No
$D$ $E \times D = 1 + L$を満たす$D$ 復号鍵 $77$ Yes
$M$ $M = C^D \bmod N$(復号) 平文 $11$ Yes
$C$ $C = M^E \bmod N$(暗号化) 暗号文 $163$ No

처리

名前 処理 意味
暗号化処理 $C = M^E \bmod N$ $M$を暗号化した$C$を計算する
復号処理 $M = C^D \bmod N$ $C$を復号した$M$を計算する

코드

Pythonのコードはまとめると以下のようになります。

import math


print("-- 鍵ペア生成 --")

# 大きな素数PとQ
P = 17
Q = 13
print(f'大きな素数 P={P}, Q={Q}')

# 公開鍵Nの値を計算
# N = 221
N = P * Q
print(f'公開鍵 N = {N}')

# Lの値を計算
# L = 192
L = (P-1) * (Q-1) 

# 公開鍵Eの値を決める
# E = 5
for E in range(2, L):
    if math.gcd(E, L) == 1:
       break

print(f'公開鍵 E = {E}')

# 秘密鍵Dの値を計算
# D = 77
for D in range(2, L):
    if (E * D) % L == 1:
       break

print(f'秘密鍵 D = {D}')

print("-- 暗号化 --")

# 平文M
# M = 11
M = 11
print(f'平文 M = {M}')


# 暗号文Cを計算
# C = 163
C = M ** E % N
print(f'暗号文 C = {C}')

print("-- 復号 --")

# 平文Mを計算
# M = 11
M = C ** D % N
print(f'平文(復号後) M = {M}')

비고

※1 サマーウォーズのケンジ君はこれを解きます。すごいですね。
※2 そういうように秘密鍵と公開鍵を作るのがRSAの仕事です。
※3 本当はもっとうまい方法で、計算しているのですが今回は説明しません。気が向いたら書くかもです。

참고

  • Wikipedia - RSA 암호
  • LINE 암호화 정보
  • 공개키 암호와 RSA 암호의 작동 방식
  • 암호화 기술 입문 제3판
  • 좋은 웹페이지 즐겨찾기