RSA暗号の鍵をを手計算してみた
あるFacebookの投稿から、RAS公開鍵が手計算で計算できることを知った私。
何を血迷ったのか、計算をしてみよう!と手計算をしてみた。
RSA公開鍵暗号は、暗号の発明者の3人の名前(ロナルド・リペスト、アディ・シャミア、レオナルド・エーデルマン)の頭文字をつなげて、RSA暗号と呼ばれているそうだ。
簡単に説明をすると、コンピュータでデータをやり取りする時の暗号化の方法の1つ。公開鍵と秘密鍵を作成して、データの送信側には、公開鍵を渡して、それで暗号化をしてもらう。データが届いたら、自分が持っている秘密鍵でデータを復号するというお話。
計算方法
- 2つの素数(1とその数でしか割り切れない数字:1,2,3,5など)p、qを用意する。
- n=p * q としてnを計算する。
- q-1、p-1の最小公倍数(2つの数の共通の倍数の最小のもの:2と4なら、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と2)の最小公倍数となり、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 余り2
d = 3 9/4 = 2 余り 1
となり、d = 3 となる
結果
公開鍵:(e,n) = (3,15)
秘密鍵:(n,d) = (15,3)
最後に
毎週水曜日 21:10分から開催されている「講師を呼ばないプログラミング勉強会」(オンライン開催)で教えてもらった。
ありがとうございました。
Your Message