RSAアルゴリズムの鍵生成手順を徹底解説｜公開鍵・秘密鍵の作り方

RSA暗号とは

RSAは公開鍵暗号方式を実現する暗号システムであり、インターネットをはじめとする信頼できないネットワーク上で機密情報を送受信する際のセキュリティ確保に広く活用されています。

RSA暗号では、公開鍵と秘密鍵のどちらでもメッセージを暗号化でき、復号には暗号化に使用した鍵と対になるもう一方の鍵が用いられます。この特性こそが、RSAが最も広く利用されている非対称暗号アルゴリズムとなった理由の一つです。RSAは、デジタル通信やデータ保存における機密性・完全性・真正性・否認防止性を保証する仕組みを提供します。

鍵生成に必要な数学的基盤

RSAの鍵生成には、乗法群 G = < Z_φ(n), *, X > が必要です。この群では乗算と除算のみが定義されており、これらは公開鍵と秘密鍵の生成に不可欠な演算です。この群の法数である φ(n) は外部に秘匿されるため、群そのものも公開されません。

公開鍵および秘密鍵を生成するアルゴリズムは、RSA暗号の中核となる最も重要な要素です。まず、ラビン・ミラー素数判定法などの手法を用いて、2つの大きな素数 p と q を生成します。

鍵生成の具体的な流れ

1. 法数 n の計算

p と q を掛け合わせて法数 n を求めます。この n は公開鍵と秘密鍵の両方で共有され、両者の関係性を支える重要な値です。n のビット長は「鍵長」と呼ばれ、暗号強度を左右します。

2. 公開鍵の構成要素

公開鍵は、法数 n と公開指数 e から構成されます。e には通常 65537 が用いられます。これは大きすぎない素数であり、計算効率と安全性のバランスに優れているためです。公開鍵は誰とでも共有されるため、e を秘密裏に選んだ素数とする必要はありません。

3. 秘密鍵の構成要素

秘密鍵は、法数 n と秘密指数 d から構成されます。d は拡張ユークリッド互除法を用いて、φ(n) に対する e の乗法的逆元として計算されます。

n を法とする剰余演算において、e が φ(n) と互いに素である整数であるとき、d は φ(n) を法とした e の乗法的逆元となります。各記号の定義は以下の通りです。

• n：剰余演算における法数
• φ(n)：n のオイラー関数（トーシェント）
• e：φ(n) と互いに素な整数（これにより、e は φ(n) を法とした乗法的逆元を持つことが保証される）
• d：φ(n) を法とした e の乗法的逆元となる整数

鍵生成の計算ステップ一覧

1. 異なる2つの素数 p と q を生成する。
2. 法数 n = p × q を計算する。
3. オイラー関数 φ(n) = (p − 1) × (q − 1) を計算する。
4. 1 < e < φ(n) かつ gcd(φ(n), e) = 1 を満たす整数 e を公開指数として選ぶ。
5. d = e⁻¹ mod φ(n) を満たす値 d を秘密指数として計算する。
6. 公開鍵 = [e, n]
7. 秘密鍵 = [d, n]