RSA暗号の鍵をを手計算してみた
あるFacebookの投稿から、RAS公開鍵が手計算で計算できることを知った私。
何を血迷ったのか、計算をしてみよう！と手計算をしてみた。
RSA公開鍵暗号は、暗号の発明者の３人の名前（ロナルド・リペスト、アディ・シャミア、レオナルド・エーデルマン）の頭文字をつなげて、RSA暗号と呼ばれているそうだ。
簡単に説明をすると、コンピュータでデータをやり取りする時の暗号化の方法の１つ。公開鍵と秘密鍵を作成して、データの送信側には、公開鍵を渡して、それで暗号化をしてもらう。データが届いたら、自分が持っている秘密鍵でデータを復号するというお話。
計算方法
- ２つの素数（１とその数でしか割り切れない数字：1,2,3,5など）p、qを用意する。
- n=p * q としてnを計算する。
- q-1、p-1の最小公倍数（２つの数の共通の倍数の最小のもの：2と４なら、4）をLとして求める。
- ed = 1 (mod L) を使って、dを求める
eはなんでもいいので素数を1つ選ぶ
とのこと。
1〜3までは、理解できる。
問題は、4 ed = 1 (mod L)
この式を理解しようとすると、「ユークリッドの互除方」「拡張ユークリッドの互除方」を使って計算するという説明がでてくる。
この「ユークリッドの互除方」「拡張ユークリッドの互除方」は、パソコンでプログラムを書いて公開鍵、秘密鍵を求める時には必要だけど、手計算の場合は必要ないので無視。
ed = 1 (mod L) の意味
e*dをLで割った時に余りが1になる数字は何？ということ
手計算の場合、難しいことは考えないで、1つずつ数字をあてはめていけばよい。
実際にやってみる
p = 5 、q = 3 とする
n = p * q = 5*3 = 15
L = q-1、p-1の最小公倍数 なので、5-1と3-1（つまり、４と２）の最小公倍数となり、4*1 = 4 4*2 = 8、、、どれも、2の倍数となるけど、最小のものは、4なので、L = 4
難題のLの計算
eは、1つ素数を選ぶとのことだったので、e = 3 とする
3d = 1 (mod 4)
3dを4で割ったときの余りが1
d = 1 3/4 = 0 余り4
d = 2 6/4 = 1 余り２
d = 3 9/4 = 2 余り 1
となり、d = 3 となる
結果
公開鍵：(e,n) = (3,15)
秘密鍵：(n,d) = (15,3)
最後に
毎週水曜日 21:10分から開催されている「講師を呼ばないプログラミング勉強会」（オンライン開催）で教えてもらった。
ありがとうございました。
Your Message