計算機実験　II（塩田・森教官）　No.11

［準備するもの］

1. 先ず大きな素数をふたつ用意し p, q と名前を付ける。

2. n = p * q,　m = (p-1) * (q-1)　と定める。

   (　No.10 の記号で　m = φ(n)　である。 尚、p, q が大きすぎると整数型ではオーバーフローの危険があり、 また p, q が小さすぎても正しく復号できないので注意。)

3. m と互いに素な自然数 e を用意する。

   (　互いに素であるかどうかは、ユークリッドのアルゴリズムを用いて m と e の最大公約数を計算すればわかる。)

4. e d ≡ 1 ( mod m ) となる自然数 d を ユークリッドのアルゴリズム　ver.2　によって計算する。

5. 以上の準備のもと、n と e だけを公開する。

［暗号器］

1. 先ず、送信者と受信者の間でデータの数値化の方法を決めておく。 例えば、テキストファイルを送信したければ １文字ずつアスキーコードに置き換えれば良い。

   (　文字型変数 c のアスキーコードが整数型変数 x ならば、 　x = ord(c),　c = chr(x).　)

2. 送信者は数値 x を y := x^e mod n に置き換えて送信する。 ただし x^e をいきなり計算するとオーバーフローが起こるので、 次のように反復二乗法を用いる

   y := 1;

   z := x;

   while e > 0 do begin

   if e mod 2 = 1 then y := y * z mod n;

   e := e div 2;

   z := sqr(z) mod n

   end;

［復号器］

受信者は数値 y から数値 z := y^d mod n を計算する。 すると No.10 のオイラーの定理により z = x が成り立ち正しく復号される。

(　暗号器の (2) と同様の計算をしてオーバーフローを防ぐ。)

［実用上は］

• 多倍精度の整数データ型を用いて計算する。

  ( 参考文献　:　和田秀男、「コンピュータと素因子分解」(遊星社)、第9章 )

• p, q は 100桁程度の素数を用いる。

  ( 理論的には n を素因子分解すれば p, q, m, d がわかって 復号できるが、現在知られているアルゴリズムでは n の素因子分解に膨大な 時間が掛かるので暗号を破ることができない。)

• p, q は大きさが似ていると素因子分解し易いことがわかっているので、 数桁異なる大きさの方が良い。