RSA暗号方式を使用してください １． 必要なアルゴリズム (1)素数の求め方 ｐやｑの素数は256bit前後が一般的です。素数にしてもあくまで素数である確率がある程度以上ということでやっています。 乱数を使って見つけてください。約数の有無を調べればいいわけだが・・2からqまでなんて調べないこと、ほとんどが不要な無駄な計算になります。 2からsqrt(q)で十分です。 ① システムが用意している乱数を作る関数を使い適当な整数を得る。 ② これを今日は３桁以内になるように変換する ③ それが素数かどうかを調べる ④ ２つの素数が見つかるまで(pとqに設定)上記①からの処理を繰り返す n=p*qとm=(p-1)*(q-1)を計算する
(2)eの見つけ方(最大公約数gcd(e,m)ただm=(p-1)*(q-1)) 次にgcd(e,m)=1となるeを見つける ここで最大公約数(gcd)を見つける必要がありますがこれには有名なユーグリッドの互助法というのがあります。 ここでもまた適当に乱数eを発生させ(２桁以内),gcd(e,m)が１かどうかを調べる。gcd(e,m)が１ではない場合は１になるまで乱数を発生させる。 ユーグリットの互助法によりxとyのgcdを求める手順 ① 常にx>yとなるように、場合によってはxとyの値を交換する ② z = x mod y を計算する。zが0だったら終了(gcdはy) ③ yとx – yを比較して大きいほうをx小さいほうをyとする →②へ
(3)dの見つけ方 eが決まりm=(p-q)*(q-1)が決まると(e*d) mod m = 1となるdを計算する必要がある (2)よりeとmは互いに素(gcd(e,m)=1)であるとき 1=e*d(mod m)となるdが存在する。(法mに関するeの乗法的逆元存在する) このdを求めるためには不定方程式e*d+m*n=1を解くことになる そのために今度はユーグリッドの互助法の拡張定理を使う
