情報セキュリティとアルゴリズム（公開鍵暗号）

高校生の太郎さんと花子さんは、情報セキュリティの授業で、インターネット上で安全にデータをやり取りするための「公開鍵暗号方式」について学んでいる。先生は、その代表的なアルゴリズムであるRSA暗号を簡略化した例で説明した。

【鍵の生成】

1. 2つの異なる素数 $p$ と $q$ を選ぶ。（例： $p=5$, $q=11$）
2. $N = p \times q$ を計算する。（例： $N = 5 \times 11 = 55$）
3. $L = (p-1) \times (q-1)$ を計算する。（例： $L = (5-1) \times (11-1) = 4 \times 10 = 40$）
4. $L$ と互いに素な（1以外に公約数を持たない）$E$ を選ぶ。（例： $E=7$）
5. $(E \times D) \div L$ の余りが 1 となる $D$ を見つける。（例： $(7 \times D) \mod 40 = 1$。$D=23$ のとき $7 \times 23 = 161 = 4 \times 40 + 1$ なので $D=23$）

この結果、2種類の鍵が生成される。

• 公開鍵 (N, E): (55, 7) （暗号化に使い、全員に公開してよい）
• 秘密鍵 (N, D): (55, 23) （復号に使い、受信者（自分）だけが秘密に持つ）

【暗号化と復号】

• 送信者は、平文（データ） $M$ を、受信者の公開鍵 $(N, E)$ を使って暗号文 $C$ に変換する。 $C = M^E \mod N$
• 受信者は、暗号文 $C$ を、自分の秘密鍵 $(N, D)$ を使って平文 $M$ に戻す。 $M = C^D \mod N$

太郎：「$M=2$ というデータを送る場合、$C = 2^7 \mod 55$ を計算するんだね。でも、$C=18$ を受け取ったとき、復号するには $M = 18^{23} \mod 55$ の計算が必要だけど、$18^{23}$ はものすごく大きな数になってしまう。」

先生：「そうだね。そこで、コンピュータでは $A^B \mod C$ のような計算（べき乗の剰余）を、桁あふれ（オーバーフロー）せずに効率よく行うためのアルゴリズム（プログラム1）が使われるよ。」

プログラム1：べき乗の剰余を計算する手続き（繰り返し二乗法）

// base の exp 乗を mod で割った余り (base^exp mod mod) を計算する
手続 ModPowFast(base, exp, mod)
  result = 1
  temp_base = base % mod
  temp_exp = exp
  
  // temp_exp が 0 になるまで繰り返す
  反復 (temp_exp > 0)
    // (1) temp_exp を 2 で割った余りが 1 か (exp の 2進数表現で、現在のビットが 1 か)
    もし (temp_exp % 2 == 1) ならば
      result = (result * temp_base) % mod
    
    // (2) 次のビットの準備
    temp_base = (temp_base * temp_base) % mod
    temp_exp = temp_exp // 2  // "//" は整数除算（商の整数部分）
  
  戻る result