RSA暗号の具体的な手順

準備

１．ボブは、まず二つの素数p,qを用意する。
暗号化はp×qより小さい数値が可能なので、送りたい数値に合わせて適当に大きな素数を選ぶ。
例えば、アルファベットの対応番号はA=65,Z=90なので、アルファベットの大文字で通信するなら、pqが90以上になるようにする。

p=7
q=13
n=pq=91
としよう。

２．ボブは

ed ÷ (p-1)(q-1))=N　余り1

となるようなeとdを用意する。
余りが1にあるようなら、Nは何でもよい。
e=5
d=29
ed=145=72×2+1＝(7-1)(13-1)×2+1

なので、eとdは上記の条件を満たす。

暗号化の公開

ボブは、自分宛の通信の変換方式を公開する。
(但し、公開するのは上記のnとeだけである。p,q,dは公開しない。)
「みなさーん、私に暗号で送るときは、送りたい数値を5乗して91で割った余りを送信してください」

暗号化

アリスはその指定された方法で数値を変化して送る。 例えば、CATはC=67、A=65、T＝84。

675＝1350125107=14836539×91+58
655＝1160290625=12750446×91+39
845＝4182119424=45957356×91+28


なので、「58,39,28を送りまーす」

複合化

ボブは、自分宛の通信の変換方式の逆変換を使って解読する。
これは、送られてきた数値をd乗してnで割った余りを求めればよい。

5829＝1378516006777431104836763434029972462511887354953728
=15148527547004737415788609165164532555075685219271×91+67

3929＝13831637670618865315545398098596852261222647559
=151996018358449069401597781303262112760688434×91+65

2829＝928074647171094496152036391094208962756608
=10198622496385653803868531770266032557764×91+84

なので、67,85,84が取り出せた。
数字と文字の対応表で、これはCATである。
「はーい、受信できましたー！」

通信終了。

解説

解読に使うのはdとnの値である。
nは公開されているので、dがわかればよい。
ed ÷ (p-1)(q-1))=N　余り1
となるようになっているので、p,qがわかればdが見つけられる。
n=pqなので、公開されているnが、二つの素数pとqに分解できればよい。

今の場合、n=91から91=7×13を見つけるのはそれほど難しくない。
だから、公開されているnとeからdを見つけるのは比較的簡単である。

しかし、素数には桁数が大きなものもある。
たとえば、二つの素数、1151と1213の積1396163を計算するのは用意だが
1396163=1151×1213
と分解するのは難しい。

例えば、144483604528043653279487は何と何の積だろうか？
(答え、2147483647　と　67280421310721　の積)