ＲＳＡ暗号について
1977年にアメリカのリベスト（Rivest）、シャミア（Shamir）、アドルマン（Adleman）の３名により発明されたので、アルファベットのそれぞれの頭文字を取って「RSA暗号」と名付けられました。これが現在インターネットなどで基本になっている暗号です。
以下では素数P, Qを選んで、P×Qとある数K（公開鍵）を一般に公開して、以下にして暗号文をやり取りするのかの事例を見てみましょう。
ここで、少し準備編として素因数分解の性質について復習してみましょう。
例えば６を素因数分解すると2×3ですが、数字が大きくなっていくと素因数分解するのがだんだん難しくなってきます。377がどのように素因数分解されるかぱっと分かりますか？（答：13×29）
反対に、13×29の計算は小学生でも簡単に出来てしまいます。
PやQとして150〜300桁の素数を用いた場合は、現時点で世界最速のコンピューターを使ったとしても、P×QからPとQの値を求めるのに何億年・何兆年とかかるそうです。
このような「PとQからP×Qを作るのは簡単だが、逆は難しい」という一方向性は、「暗号文を作るのは簡単だが、第三者が暗号文を解読するのは難しい」という一方向性に応用出来そうだ、と考えられますね。
ここでは、山田さん（送信者）が「LEMON」という文章を川崎さん（受信者）に送る手順を見てみましょう。
（手順）
（例）
２つの素数P, Qの組を、例えば (P,Q)=(3,11) として、K1＝33。さらにP-1=2とQ-1=10の最小公倍数10の約数でない数としてK2=7とおきましょう。川崎さん（受信者）はあらかじめ世界の人に数字の組 (K1,K2)=(33,7) を公開しておきます。
このとき、山田さん（送信者）が送りたい平文「LEMON」は次のようにして暗号文「LNG+T」に変換されます。
|
文字 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
|
番号 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
| L（12） | ------------> | 12の7乗（35831808）を33で割った余り | ＝ 12（L） |
| E（5） | ------------> | 5の7乗（78125）を33で割った余り | ＝ 14（N） |
| M（13） | ------------> | 13の7乗（62748517）を33で割った余り | ＝ 7（G） |
| O（15） | ------------> | 15の7乗（170859375）を33で割った余り | ＝ 27（＋） |
| N（14） | ------------> | 14の7乗（105413504）を33で割った余り | ＝ 20（T） |
山田さん（送信者）が送った暗号「LNG+T」を受け取った川崎さん（受信者）が、暗号を解読（復号）する方法を見てみましょう。
（手順）
（例）
P-1=2とQ-1=10の最小公倍数Rは10であり、
K3 = (R×n+1)÷K2 = (10×n+1)÷７
の値が整数になるように、例えばn=2とします（注：nは9, 16, …等でも同じ結果になります）。このときK3=3です。
| L（12） | ------------> | 12の3乗（1728）を33で割った余り | ＝ 12（L） |
| N（14） | ------------> | 14の3乗（2744）を33で割った余り | ＝ 5（E） |
| G（7） | ------------> | 7の3乗（343）を33で割った余り | ＝ 13（M） |
| +（27） | ------------> | 27の3乗（19683）を33で割った余り | ＝ 15（O） |
| T（20） | ------------> | 20の3乗（8000）を33で割った余り | ＝ 14（N） |
これで元の文章（LEMON）に戻すことが出来ました。
ここまでの、暗号の受け渡しの手順をまとめると
のようになります。
RSA暗号が、大変強力な暗号であることは理解出来たと思います。その理由は、古典的な暗号では「暗号を作成する鍵」と「暗号を解読する鍵」が同じだったのに対し、公開鍵暗号ではそれらを分離したことでした。
例えば、シーザー暗号では鍵である「ずらす文字数」が、暗号化と復号化のどちらにも使えたため、鍵が暗号を読ませたい人以外の手に渡ることはどうしても避けなければなりませんでした。しかし、公開鍵暗号では最初から公開するための鍵（公開鍵）と自分だけが持てばよい鍵（秘密鍵）に区別されているため、そのようなことを気にする必要はありません。両方の鍵が揃わないと暗号は解読出来ないのですから。
実は、これによっておまけの効果が出てきます。それは、「暗号が発信者の身分を証明する」ということです。これは丁度勘合貿易での勘合符のような役割だと考えても良いでしょう。
実際に計算してみれば分かりますが、実はRSA暗号の公開鍵K2と秘密鍵K3は使用する順番を入れ替えても全く同じ効果を発揮します。つまり、図式的には以下の２通りの暗号の送信方法が存在するのです。
|
公開鍵K2で暗号化
|
秘密鍵K3で復号化
|
||||
| （１） |
[ 平文 ]
|
------------>
|
[ 暗号文 ]
|
------------>
|
[ 平文 ]
|
|
|
|||||
|
秘密鍵K3で暗号化
|
公開鍵K2で復号化
|
||||
| （２） |
[ 平文 ]
|
------------>
|
[ 暗号文 ]
|
------------>
|
[ 平文 ]
|
より具体的に、山田さん（送信者）が川崎さん（受信者）にメールを送る場合を考えてみましょう。
AさんからBさんへ暗号を送る方法は次の２通りあります：
（１）Bさんの公開鍵B2を使って暗号を作成する（この場合、Bさんは自分の秘密鍵B3を使って暗号を解読する）
（２）Aさんの秘密鍵A3を使って暗号を作成する（この場合、BさんはAさんの公開鍵A2を使って暗号を解読する）
それでは、まず（１）の場合を見てみましょう。
|
（Aさん）
|
（ Bさん）
|
|||||
|
[ 平文 ]
|
------------>
|
[ 暗号文 ]
|
============>
|
[ 暗号文 ]
|
------------>
|
[ 平文 ]
|
|
Bさんの公開鍵B2で暗号化
|
送信
|
Bさんの秘密鍵B3で復号化
|
Bさんへ暗号文を送信することは公開鍵B2を用いて誰でも出来ますが、たとえBさん以外の人が送信された暗号文を手に入れたとしても公開鍵B2では暗号文を解読することが出来ません。暗号文をもとの文章に復号出来るのは、秘密鍵B3を持つBさんのみということになります。
まとめ
次に（２）の場合を見てみましょう。
|
（Aさん）
|
（ Bさん）
|
|||||
|
[ 平文 ]
|
------------>
|
[ 暗号文 ]
|
============>
|
[ 暗号文 ]
|
------------>
|
[ 平文 ]
|
|
Aさんの秘密鍵A3で暗号化
|
送信
|
Aさんの公開鍵A2で復号化
|
この場合は、Bさん以外の人が送信された暗号文を手に入れたら公開鍵A2を用いて暗号文を解読出来てしまうことに注意しましょう。ただし、同じ暗号を作成することは秘密鍵A3を持つAさんにしか出来ません。
まとめ