개에서도 알았던 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の仕組みについて解説しました。
このような仕組みによって、世の中の通信の安全性が保たれていると思うと、なんだかおもしろいですね。
以下に今回使った数式、処理、コード等についてまとめてあるので、ぜひ使ってください。
값
자주 사용되는 공개키 암호화 방식의 하나입니다.
(공개 키 암호 방식에 대해서는 아래쪽에 쓰고 있으므로 안심하십시오)
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, \quad Q = 13
P = 17
Q = 13
$$N = P \times Q$$
N = P * Q
例を上げるなら$5$と$7$は互いに素ですし、$3$と$6$は互いに素ではないです。
このときの数字の数を$\phi(N)$とも表記します。
(オイラー関数と言うやつです。)
$1$と$5$があるので、$\phi(T) = 2$となります。
$P$と$Q$が互いに素であるとき、
となります。
\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}
L = (P-1) * (Q-1)
(つまり$E$と$L$の最大公約数が$1$)
$E = 5$は公開鍵として選ぶことができます。
($E$として選べる数字はいくつもありますが、
今回は$5$を選びます。)
(つまり$5$と$192$の最大公約数が$1$)
'''
Eとして選べる数字はいくつもあるが、
今回は一番小さいものを選んでいる
'''
for E in range(2, L):
if math.gcd(E, L) == 1:
break
- 式を変形すると、$E \times D \bmod L = 1$
つまり$E \times D$を$L$で割ったあまりが$1$である。
秘密鍵$D$として$77$が成り立ちます。
for D in range(2, L):
if (E * D) % L == 1:
break
公開鍵($N$と$E$)をもとに行います。
\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$を使って復号を行います。
$$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}')
これらを使って平文$M$、または$D$を求めることができれば、この暗号が危険といえます。
鍵ペア作成と同じ手順で暗号鍵$D$が計算できます。
しかし、あまりにも$P$と$Q$が大きいため、計算時間上困難です。
このような仕組みによって、世の中の通信の安全性が保たれていると思うと、なんだかおもしろいですね。
名前 | 式 | 意味 | 例 | 機密情報であるか |
---|---|---|---|---|
$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 本当はもっとうまい方法で、計算しているのですが今回は説明しません。気が向いたら書くかもです。
참고
Reference
이 문제에 관하여(개에서도 알았던 RSA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/akakou/items/700e00a715593966cbfa텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)