RSA暗号の理論・鍵生成・暗号化・復号をPython実装：pow/math.gcd/拡張ユークリッド/ミラーラビン素数判定

RSA暗号とは

RSA暗号は、1977年にRon Rivest、Adi Shamir、Leonard Adleman の3名によって発表された公開鍵暗号方式です。公開鍵暗号とは、暗号化に使う鍵（公開鍵）と復号に使う鍵（秘密鍵）が異なる暗号方式であり、公開鍵を広く公開しても安全性が保たれるという特徴があります。

RSA暗号の安全性は、大きな合成数の素因数分解が計算上困難であるという事実に基づいています。現在でも、鍵交換やデジタル署名など幅広い用途で利用されています。

数学的基礎

RSA暗号を理解するために、いくつかの数学的な概念を整理します。

素因数分解問題

2つの大きな素数 \(p\) と \(q\) を掛け合わせて \(N = p \times q\) を計算することは容易です。しかし、与えられた \(N\) から元の \(p\) と \(q\) を求めること（素因数分解）は、\(N\) が十分に大きい場合、現在のコンピュータでは実用的な時間内に解くことが非常に困難です。この計算量の非対称性がRSA暗号の安全性の根拠となっています。

オイラーのトーシェント関数

オイラーのトーシェント関数 \(\varphi(N)\) は、\(1\) 以上 \(N\) 以下の整数のうち、\(N\) と互いに素であるものの個数を表します。\(N = p \times q\) （\(p, q\) は相異なる素数）の場合、以下が成り立ちます。

オイラーの定理

\(\gcd(a, N) = 1\) （\(a\) と \(N\) が互いに素）であるとき、以下が成り立ちます。

この定理は、RSA暗号の正当性を証明するための核となります。

モジュラ逆元

整数 \(e\) と \(\varphi(N)\) が互いに素であるとき、以下を満たす整数 \(d\) が一意に存在します。

この \(d\) を \(e\) の \(\varphi(N)\) を法とするモジュラ逆元と呼び、\(d \equiv e^{-1} \pmod{\varphi(N)}\) と表記します。\(d\) は拡張ユークリッド互除法を用いて効率的に計算できます。

RSAアルゴリズム

鍵生成 (Key Generation)

1. 2つの大きな素数 \(p, q\) をランダムに選択する
2. \(N = p \times q\) を計算する
3. \(\varphi(N) = (p - 1)(q - 1)\) を計算する
4. \(1 < e < \varphi(N)\) かつ \(\gcd(e, \varphi(N)) = 1\) を満たす整数 \(e\) を選択する（一般的に \(e = 65537\) が使用される）
5. 拡張ユークリッド互除法を用いて \(d = e^{-1} \bmod \varphi(N)\) を計算する
6. 公開鍵: \((N, e)\) 、秘密鍵: \((N, d)\)

暗号化 (Encryption)

平文を整数 \(m\) （\(0 \le m < N\) ）として表現し、公開鍵 \((N, e)\) を用いて暗号化します。

復号 (Decryption)

暗号文 \(c\) を秘密鍵 \((N, d)\) を用いて復号します。

正当性の証明

復号によって元の平文が正しく復元されることを示します。\(\gcd(m, N) = 1\) の場合を考えます。

\(e \cdot d \equiv 1 \pmod{\varphi(N)}\) より、ある整数 \(k\) が存在して \(e \cdot d = 1 + k \cdot \varphi(N)\) と書けます。

オイラーの定理（式 \(\text{(2)}\) ）より \(m^{\varphi(N)} \equiv 1 \pmod{N}\) であるため、

となり、復号が正しく行われることが証明されます。

Pythonによる実装

【注意】 以下のプログラムは、RSA暗号の原理を理解するための教育目的の実装です。実際の暗号通信には使用しないでください。

import random
import math


def is_prime_miller_rabin(n, k=20):
    """Miller-Rabin素数判定法"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    # n-1 を 2^r * d の形に分解
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def generate_prime(bits):
    """指定ビット長のランダムな素数を生成する"""
    while True:
        # 最上位ビットと最下位ビットを1にして奇数を保証
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime_miller_rabin(p):
            return p


def extended_gcd(a, b):
    """拡張ユークリッド互除法: gcd, x, y を返す（ax + by = gcd）"""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    return gcd, y1 - (b // a) * x1, x1


def mod_inverse(e, phi):
    """e の phi を法とするモジュラ逆元を計算する"""
    gcd, x, _ = extended_gcd(e % phi, phi)
    if gcd != 1:
        raise ValueError("モジュラ逆元が存在しません")
    return x % phi


def generate_keypair(bits=512):
    """RSA鍵ペアを生成する"""
    p = generate_prime(bits)
    q = generate_prime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return (n, e), (n, d)


def encrypt(message, public_key):
    """公開鍵を用いてメッセージを暗号化する"""
    n, e = public_key
    return pow(message, e, n)


def decrypt(ciphertext, private_key):
    """秘密鍵を用いて暗号文を復号する"""
    n, d = private_key
    return pow(ciphertext, d, n)

Pythonの組み込み関数 pow(base, exp, mod) は、内部的に 繰り返し二乗法（バイナリ法） と同等の高速なべき乗剰余計算を行います。

各関数の解説

1. is_prime_miller_rabin: Miller-Rabin素数判定法による確率的素数判定を行います。\(k = 20\) 回のテストにより、合成数を誤って素数と判定する確率は \(4^{-20} \approx 10^{-12}\) 以下に抑えられます。

2. generate_prime: 指定ビット長のランダムなビット列を生成し、最上位ビットと最下位ビットを1に設定（奇数かつ指定ビット長を保証）した上で、素数判定を通過するまで繰り返します。

3. extended_gcd: 拡張ユークリッド互除法を再帰的に実装しています。\(ax + by = \gcd(a, b)\) を満たす \(x, y\) を求めます。このアルゴリズムの正当性の証明とベズーの等式の構成的証明は ユークリッドの互除法の記事 で詳しく解説しています。

4. mod_inverse: 拡張ユークリッド互除法を利用して、\(e \cdot d \equiv 1 \pmod{\varphi(N)}\) を満たす \(d\) を計算します。

5. generate_keypair: 上記の関数を組み合わせて、RSA鍵ペア（公開鍵と秘密鍵）を生成します。\(e = 65537\) （\(2^{16} + 1\) ）は、2進数表現でビットが2つしか立っていないため、べき乗剰余計算が高速になる利点があります。

使用例

# --- 数値の暗号化・復号 ---
public_key, private_key = generate_keypair(bits=512)

message = 12345
ciphertext = encrypt(message, public_key)
decrypted = decrypt(ciphertext, private_key)
print(f"平文:   {message}")
print(f"暗号文: {ciphertext}")
print(f"復号文: {decrypted}")
assert message == decrypted

# --- 文字列の暗号化・復号 ---
text = "Hello RSA"
# 文字列をバイト列に変換し、整数として解釈
m = int.from_bytes(text.encode(), "big")
c = encrypt(m, public_key)
d = decrypt(c, private_key)
# 整数をバイト列に戻し、文字列にデコード
result = d.to_bytes((d.bit_length() + 7) // 8, "big").decode()
print(f"平文:   {text}")
print(f"復号文: {result}")

鍵長ごとの処理時間ベンチマーク

上記の実装を使い、鍵長（128〜1024ビット）ごとに鍵生成・復号（べき乗剰余計算）の処理時間を実測しました（各ビット長で複数回試行した平均値、Miller-Rabin の試行回数 \(k=20\) ）。

import time

for bits in [128, 256, 512, 768, 1024]:
    t0 = time.perf_counter()
    public_key, private_key = generate_keypair(bits=bits)
    keygen_time = time.perf_counter() - t0

    message = 123456789
    t0 = time.perf_counter()
    ciphertext = encrypt(message, public_key)
    enc_time = time.perf_counter() - t0

    t0 = time.perf_counter()
    decrypted = decrypt(ciphertext, private_key)
    dec_time = time.perf_counter() - t0
    assert message == decrypted

    print(f"{bits}bit: keygen={keygen_time*1000:.1f}ms, "
          f"enc={enc_time*1e6:.1f}us, dec={dec_time*1e6:.1f}us")

鍵生成時間は鍵長にほぼ指数的に増加しており、128→1024ビット（8倍）で鍵生成時間は約2,700倍になっています。これは Miller-Rabin 素数判定の試し割り・べき乗剰余計算のコストがビット長の増加とともに重くなることに加え、指定ビット長のランダム奇数が素数である確率が 素数定理 よりおおよそ \(1/\ln(2^{bits})\) で低下し、素数が見つかるまでの試行回数が増えるためです。実務で使われる RSA-2048 では、本記事のような純粋なPython実装では鍵生成に数分〜数十分かかる場合があり、実用ライブラリ（cryptography、OpenSSL等）は GMP 等の多倍長演算ライブラリと最適化されたアルゴリズムで数十ミリ秒〜数百ミリ秒に短縮しています。一方、復号（べき乗剰余）自体は鍵生成ほど急激には増加せず、1024ビットでも約33msに収まっており、鍵生成の重さが実務上のボトルネックであることがわかります。

秘密鍵の運用を誤ると起きる攻撃

RSA暗号の安全性は素因数分解の困難性に基づいていますが、実装や鍵管理を誤ると、素因数分解を一切実行せずに秘密鍵や平文を復元できてしまう攻撃が複数知られています。以下では代表的な4種類の攻撃——Wienerの攻撃・共通法攻撃・パディングオラクル攻撃・タイミングサイドチャネル攻撃——について、その数理的な仕組みを導出した上で、実際に攻撃コードを実装して検証します。

秘密指数dが小さすぎる場合:Wienerの攻撃

復号の計算 \(m = c^d \bmod N\) （式 \(\text{(5)}\) ）を高速化したいという動機から、秘密指数 \(d\) を先に小さい値に固定し、そこから公開指数 \(e\) を逆算する、という誤った最適化を行いたくなることがあります。しかし、Michael Wiener が1990年に示したのは、\(p<q<2p\) かつ \(d < N^{0.25}/3\) 程度まで \(d\) が小さい場合、公開鍵 \((N, e)\) だけから、\(e/N\) の連分数展開を使って \(d\) を効率的に復元できるという事実です。

攻撃の導出

秘密鍵生成の式 \(\text{(3)}\) より \(ed \equiv 1 \pmod{\varphi(N)}\) なので、ある正整数 \(k\) が存在して

が成り立ちます（\(k = (ed-1)/\varphi(N)\) ）。式 \(\text{(8)}\) の両辺を \(d\varphi(N)\) で割ると、

を得ます。ここで、\(k\) と \(d\) の最大公約数を考えると、式 \(\text{(8)}\) より \(\gcd(k, d)\) は \(1\) を割り切るため \(\gcd(k,d)=1\) 、すなわち \(k/d\) は既約分数です（後で使う連分数の定理はこの既約性を要求します）。また \(e < \varphi(N)\) かつ \(ed = 1+k\varphi(N) > \varphi(N)\) より \(d > 1\) なので \(k \ge 1\) が成り立ちます。

攻撃者が知っているのは \(N\) であって \(\varphi(N)\) ではないため、式 \(\text{(9)}\) の \(e/\varphi(N)\) を \(e/N\) に置き換えたときの誤差を評価する必要があります。\(\varphi(N) = N-p-q+1\) なので、\(p+q\) が \(N\) に比べて十分小さければ \(\varphi(N) \approx N\) です。\(p < q < 2p\) という（RSA鍵生成でよく見られる）バランスの取れた素数選択を仮定すると、\(N = pq > p^2\) より \(p < \sqrt{N}\) 、また \(q < 2p\) より

が成り立ちます。つまり \(N - \varphi(N) = p+q-1 < 3\sqrt{N}\) です。これを使って \(e/N - k/d\) を評価します。

三角不等式と \(e < \varphi(N)\) （したがって \(e/\varphi(N) < 1\) ）、および式 \(\text{(10)}\) を使うと、

を得ます。\(\varphi(N)\) は \(N\) とほぼ同じ桁数の巨大な数なので、\(d\) が \(N^{0.25}\) 程度以下である限り第2項 \(1/(d\varphi(N))\) は第1項 \(3/\sqrt{N}\) に比べて無視できるほど小さく、実質的に

という評価が成り立ちます。ここで連分数の最良近似定理（Legendreの定理）を使います。

定理（連分数の最良近似）. 実数 \(x\) と、\(\gcd(h,k)=1\) を満たす整数 \(h,k\) が \(|x - h/k| < 1/(2k^2)\) を満たすならば、\(h/k\) は \(x\) の（単純）連分数展開の収束子（convergent）のいずれかと一致する。

式 \(\text{(13)}\) の評価を \(1/(2d^2)\) と比較すると、\(3/\sqrt{N} < 1/(2d^2)\) すなわち \(d^2 < \sqrt{N}/6\) 、つまり

という範囲で、\(k/d\) が \(e/N\) の連分数展開の収束子として現れることが保証されます。この導出は不等式評価を粗く済ませているため定数がやや緩くなっていますが（Wienerの原論文ではより precise な評価により \(d < N^{0.25}/3 \approx 0.333\, N^{0.25}\) というタイトな定数まで詰めています）、\(d\) が \(N\) の4乗根のオーダーより小さいと、公開鍵だけから連分数展開で \(d\) を復元できてしまうという本質的な仕組みは、この導出で正確に説明できています。

攻撃アルゴリズム

\(e/N\) の連分数展開 \([a_0; a_1, a_2, \ldots]\) の収束子 \(h_i/k_i\) を先頭から順に計算し、各収束子を「\(k\) の候補 \(=h_i\) 、\(d\) の候補 \(=k_i\) 」として式 \(\text{(8)}\) に代入し、\(\varphi(N)\) の候補 \(\hat\varphi = (e\hat d - 1)/\hat k\) を整数として計算できるか（割り切れるか）を確認します。割り切れた場合、\(p+q = N - \hat\varphi + 1\) が分かるので、\(p, q\) は2次方程式

の根として求まります（判別式が完全平方数になり、かつ根の積が \(N\) に一致すれば、その収束子が正しい \(k/d\) です）。

import math


def continued_fraction(num, den):
    """num/den の連分数展開の係数列 [a0, a1, ...] を返す"""
    cf = []
    while den:
        a = num // den
        cf.append(a)
        num, den = den, num - a * den
    return cf


def convergents(cf):
    """連分数係数列から収束子 (h_i, k_i) の列を返す"""
    convs = []
    h_prev2, h_prev1 = 0, 1
    k_prev2, k_prev1 = 1, 0
    for a in cf:
        h = a * h_prev1 + h_prev2
        k = a * k_prev1 + k_prev2
        convs.append((h, k))
        h_prev2, h_prev1 = h_prev1, h
        k_prev2, k_prev1 = k_prev1, k
    return convs


def wiener_attack(e, n):
    """公開鍵 (e, n) のみから、連分数展開の収束子 k/d を全探索してdを復元する"""
    cf = continued_fraction(e, n)
    for (k, d) in convergents(cf):
        if k == 0 or d == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi_candidate = (e * d - 1) // k  # 式(8)を逆算
        s = n - phi_candidate + 1  # p + q の候補（式(15)の係数）
        disc = s * s - 4 * n
        if disc < 0:
            continue
        sqrt_disc = math.isqrt(disc)
        if sqrt_disc * sqrt_disc != disc:
            continue
        p = (s + sqrt_disc) // 2
        q = (s - sqrt_disc) // 2
        if p * q == n:
            return d, p, q
    return None

実行検証1:小さいdを狙った鍵からの復元

前節の generate_prime・mod_inverse を使い、512ビット素数を2つ（\(N\) は約1024ビット）生成した上で、意図的に \(d\) を \(N^{0.25}/3\) の内側になるよう小さく選び、そこから \(e = d^{-1} \bmod \varphi(N)\) を逆算しました（実運用では絶対に行ってはいけない鍵生成です）。

import math
import random

random.seed(42)
bits = 512
p = generate_prime(bits)
q = generate_prime(bits)
n = p * q
phi = (p - 1) * (q - 1)

target_d_bits = int(math.log2(n) / 4) - 2  # N^0.25 よりやや小さいビット長を狙う
while True:
    d = random.getrandbits(target_d_bits) | 1
    if d > 2 and math.gcd(d, phi) == 1:
        e = mod_inverse(d, phi)
        if e > 1:
            break

result = wiener_attack(e, n)
recovered_d, rp, rq = result
message = 123456789
c = pow(message, e, n)
m2 = pow(c, recovered_d, n)
print(recovered_d == d, sorted([rp, rq]) == sorted([p, q]), m2 == message)

実際に実行したところ、\(N\) は 1023ビット、選んだ秘密指数 \(d\) は 253ビット（\(N^{0.25}\) のビット長は約256ビットなので、確かに \(N^{0.25}\) の内側）で、\(N^{0.25}/3 \approx 3.060 \times 10^{76}\) という基準に対して十分小さい値になっていました。この \((N, e)\) だけを入力として wiener_attack を実行した結果、元の \(d\) と完全に一致する値が復元され、\(p, q\) も正しく復元され、復元した \(d\) で実際に暗号文を復号すると元の平文と一致することを確認しました。攻撃者は素因数分解を一切行わず、連分数展開という \(O(\log N)\) 回程度の反復計算だけで秘密鍵を丸ごと手に入れています。

実行検証2:境界付近での成功率スキャン

式 \(\text{(14)}\) の理論的な保証は「この範囲なら必ず成功する」という十分条件であり、それを超えたら必ず失敗するという意味ではありません。そこで、\(d\) の大きさを \(N^{0.25}\) に対する比率として様々に変化させ（256ビット素数2個、\(N\) は約512ビット）、各比率ごとに40〜50回試行して攻撃の成功率を測定しました。

ratios = [0.33, 1, 1.5, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 100]
# 各ratioについて、d = ratio * N**0.25 程度になるようdを選び、
# generate_prime(256) で N を作り直しながら trials_per_ratio=40〜50 回試行し、
# wiener_attack(e, n) が元のdと一致するかどうかで成功率を集計する

結果は図の通りで、理論的保証の境界（\(\text{ratio}=1/3\) ）より内側の比率 \(0.33, 1\) では成功率 100%、境界のすぐ外側の比率 \(1.5, 2\) でも成功率 74%, 78% と高く、比率が大きくなるにつれて緩やかに低下し（比率 \(6, 8\) で20%、比率 \(24\) で2%）、比率 \(100\) で成功率 0% となりました。これは、式 \(\text{(12)}\) の不等式評価が「最悪ケースでも保証される」十分条件であるのに対し、実際の \(p, q, e\) の組み合わせでは誤差項がもっと小さく収まることが多く、境界を多少超えても収束子として \(k/d\) が現れるケースが少なくないためです。理論的な境界は安全側に倒した目安であり、実務上は \(d\) を \(N^{0.25}\) の定数倍程度まで小さくすることさえ危険だと分かります。

実務上の対策

現在推奨されている鍵生成手順（本記事の「鍵生成」節）は \(e = 65537\) をあらかじめ固定し、そこから \(d = e^{-1} \bmod \varphi(N)\) を計算します。この手順で得られる \(d\) は \(\varphi(N)\) とほぼ同じ桁数のランダムな値になり、\(N^{0.25}\) よりはるかに大きくなるため、Wienerの攻撃は原理的に成立しません。危険なのは、復号の高速化を狙って \(d\) を先に小さい値に決め打ちしてしまう実装です（RSA-CRTによる復号高速化とは別の話で、CRTは \(d\) 自体を小さくするものではありません）。NIST SP 800-56B などの標準では、\(d\) が十分大きいこと（目安として \(d > N^{0.5}\) 程度）を鍵生成時にチェックすることが推奨されています。

同じ法Nを使い回すと起きる攻撃:共通法攻撃（Common Modulus Attack）

複数のユーザーで同じ \(N\) （したがって同じ \(p, q\) ）を使い回し、それぞれ異なる公開指数 \(e_1, e_2\) （\(\gcd(e_1, e_2)=1\) ）を使って同じ平文 \(m\) を暗号化すると、 拡張ユークリッドの互除法 だけを使って、\(p, q\) はおろか \(d_1, d_2\) すら知らずに \(m\) を復元できてしまいます。

攻撃の導出

暗号文は

です。\(\gcd(e_1, e_2) = 1\) なので、 ベズーの等式 より、拡張ユークリッドの互除法で

を満たす整数 \(a, b\) （少なくとも一方は負）を効率的に計算できます。ここで注目すべきは、Wienerの攻撃や本記事の正当性の証明（式 \(\text{(6)}\) -\(\text{(7)}\) ）が \(\varphi(N)\) を法とした合同式を経由していたのに対し、この式 \(\text{(17)}\) は \(\varphi(N)\) を一切介さない、整数としての厳密な等式だという点です。したがって、

が、オイラーの定理を使うまでもなく恒等式として成り立ちます。\(a, b\) の少なくとも一方が負の整数になりますが、これは単に \(c_1^{-|a|} \equiv (c_1^{-1})^{|a|} \pmod N\) とモジュラ逆元（本記事の「モジュラ逆元」節）を使って計算すればよいだけです。

実行検証

512ビット素数2つから \(N\) を生成し、同じ \(N\) に対して異なる公開指数 \(e_1, e_2\) （\(\gcd(e_1,e_2)=1\) を確認済み）で同一平文を2通りに暗号化し、攻撃者の視点（\(N, e_1, e_2, c_1, c_2\) のみ既知、\(p, q, d_1, d_2\) は一切使わない）で平文を復元しました。

message = int.from_bytes(b"COMMON MODULUS ATTACK DEMO", "big")
c1 = pow(message, e1, n)
c2 = pow(message, e2, n)

# 攻撃者は n, e1, e2, c1, c2 のみを知っている
g, a, b = extended_gcd(e1, e2)  # 前掲(ユークリッドの互除法の記事と同じ関数)
assert g == 1

c1_term = pow(mod_inverse(c1, n), -a, n) if a < 0 else pow(c1, a, n)
c2_term = pow(mod_inverse(c2, n), -b, n) if b < 0 else pow(c2, b, n)
recovered = (c1_term * c2_term) % n

実行の結果、\(\gcd(e_1, e_2) = 1\) であることを確認した上で、拡張ユークリッドの互除法から得た \(a, b\) は非常に大きな整数（\(e_1, e_2\) とほぼ同じ桁数）で、実際に \(a e_1 + b e_2 = 1\) を満たしていました。この \(a, b\) から式 \(\text{(18)}\) に従って計算した recovered は元の message と完全に一致し、バイト列に戻すと b'COMMON MODULUS ATTACK DEMO' という元の文字列がそのまま復元されました。\(p, q\) の値はおろか、いずれの秘密鍵 \(d_1, d_2\) も一度も使っていません。

教訓と関連する攻撃

この攻撃が成立する根本原因は、「\(N\) を共有した瞬間に、片方の秘密鍵情報がもう片方の暗号文の"解錠"に使えてしまう」という数学的事実にあります。鍵ペアは常に独立した \(N\) （独立した \(p, q\) ）から生成するのが唯一の対策です。よく似た状況として、同じメッセージを異なる \(N\) （ただし小さい共通の \(e\) 、典型的には \(e=3\) ）で複数の受信者に送ると、 中国剰余定理 を使って平文を復元できる Håstadのブロードキャスト攻撃（1988年）も知られています。共通法攻撃とは前提条件も使う数論的道具（拡張ユークリッド互除法 vs 中国剰余定理）も異なりますが、「鍵やメッセージの使い回しが致命傷になる」という教訓は共通しています。

パディングの欠如がもたらす脆弱性:パディングオラクル攻撃

本記事の実装（encrypt/decrypt）は、平文の整数 \(m\) をそのまま \(m^e \bmod N\) するだけの**教科書的RSA（textbook RSA）**です。これには構造的な問題があります。\(m_1, m_2\) の暗号文を \(c_1, c_2\) とすると、

が成り立つため、暗号文の積が平文の積の暗号文になるという乗法準同型性（malleability）を持ちます。これにより暗号文を攻撃者が意味のある形で改ざんできてしまい、実用上は必ずパディング方式を併用します。ここでは歴史的に重要な2つのパディング方式、PKCS#1 v1.5 と OAEP を実装し、両者の安全性の違いを実行検証します。

PKCS#1 v1.5パディングとBleichenbacher攻撃

PKCS#1 v1.5 は、\(k\) バイトの暗号化ブロック（\(k\) は \(N\) のバイト長）を

という形式で構成します。PS は8バイト以上のランダムな非ゼロバイト列（パディング）で、その直後の 0x00 が区切りとしてメッセージ M の開始位置を示します。復号側は、復号結果がこの形式に従っているかを検証してから M を取り出します。

Daniel Bleichenbacher は1998年、この検証処理自体をオラクル（ある暗号文が有効なパディングに復号されるかどうかを教えてくれる関数）として悪用できることを示しました（通称 Million Message Attack）。攻撃者は、ターゲットの暗号文 \(c_0\) （平文 \(m_0\) 、\(m_0\) は未知）に対して、既知の整数 \(s\) を使い

という暗号文を作ります。これは \(s \cdot m_0 \bmod N\) の暗号文になっており、サーバーに \(c'\) を送って「パディングが有効か」だけを聞き出せれば、\(s \cdot m_0 \bmod N\) の先頭バイトが 0x00 0x02 になる範囲を少しずつ絞り込め、最終的に \(m_0\) を再構成できます（式 \(\text{(21)}\) は式 \(\text{(19)}\) と同じ乗法準同型性を利用しており、パディングの検証結果だけがサーバーから漏れる1ビットの情報になっている点がポイントです）。

実行検証

自前でPKCS#1 v1.5のエンコード・デコード・オラクル関数を実装し、以下を検証しました（kバイトの小さめのRSA鍵を使用）。

def pkcs1_v15_pad(msg, k):
    """EB = 0x00 || 0x02 || PS(ランダム非ゼロ,8バイト以上) || 0x00 || M"""
    ps_len = k - len(msg) - 3
    ps = bytes(random.randint(1, 255) for _ in range(ps_len))
    return b"\x00\x02" + ps + b"\x00" + msg


def pkcs1_v15_unpad_oracle(eb):
    """パディングオラクル: 構造(0x00 0x02 ... 0x00 ...)が正しいかだけを返す"""
    if len(eb) < 11 or eb[0] != 0x00 or eb[1] != 0x02:
        return False
    idx = eb.find(b"\x00", 2)
    return idx != -1 and idx >= 2 + 8

まず、ランダムな暗号文がたまたま「有効なパディング」に見える確率を測定しました。\(c^d \bmod N\) は \(c\) が一様乱数のとき \(N\) 上ほぼ一様に分布するため、実際にRSA秘密鍵で復号する方法と復号をバイパスして直接一様乱数をサンプリングする方法は統計的に同じ分布に従います（この等価性を、192ビットの小さい \(N\) に対して30万件ずつ実行し、双方とも0件でクロスチェックしました）。この等価性を使い、実用的な2048ビットのRSA鍵に対して500万件を一様サンプリングで試行したところ、86件が有効なパディングと判定され、観測確率は \(1.72\times10^{-5}\) （約1/58,140）となり、パディション先頭2バイトの一致だけに基づく理論値のオーダー \(2^{-16} \approx 1.53\times10^{-5}\) と近い値が得られました。

次に、Bleichenbacherの攻撃の最初のステップ（式 \(\text{(21)}\) の \(s\) を小さい方から順に試して最初に有効なパディションが得られる \(s\) を探す、いわゆる"blinding"探索）を、秘密鍵を一切使わず、パディングオラクルへの問い合わせだけで実際に再現しました（192ビットの小さいRSA鍵を使用、oracle_query の内部で毎回本物の秘密鍵復号を実行）。

s = 2
while True:
    c_candidate = (c0 * pow(s, e, n)) % n
    if oracle_query(c_candidate):  # 内部でpow(c_candidate, d, n)を実行しパディションを判定
        break
    s += 1

実行の結果、\(s = 1{,}265{,}823\) で初めて有効なパディションが見つかり、それまでに実際のRSA復号を伴うオラクル問い合わせが1,265,822回必要でした。この「100万回オーダーの問い合わせが必要」という規模感こそが、Bleichenbacherの攻撃が"Million Message Attack"と呼ばれる所以です。実際の攻撃では、この最初の絞り込みに続いて区間の二分探索的な絞り込みを繰り返すため、鍵長やサーバーの応答速度次第では数千〜数百万回のオラクル問い合わせで秘密鍵を使わずに暗号文全体を復号できてしまいます。

OAEP:ランダムオラクルモデルでの解決

OAEP（Optimal Asymmetric Encryption Padding、Bellare–Rogaway, 1994） は、ハッシュ関数 \(H\) とマスク生成関数 \(\text{MGF1}\) （ハッシュを繰り返し適用して任意長のマスクを作る関数）を使い、ランダムなシード \(\text{seed}\) でメッセージ全体を撹拌します。

PKCS#1 v1.5との決定的な違いは、有効性の判定がハッシュ値 \(H(\texttt{label})\) とのビット単位の完全一致に帰着する点です。PKCS#1 v1.5では「先頭2バイトが固定値、かつどこかに0x00がある」という緩い構造チェックだったのに対し、OAEPでは（SHA-256を使う場合）256ビットのハッシュ値が丸ごと一致しない限り無効と判定されます。ランダムオラクルモデル（ハッシュ関数を理想的なランダム関数とみなす解析手法）のもとで、OAEPはRSAが一方向性トラップドア置換であるという仮定だけから IND-CCA2安全性（選択暗号文攻撃に対する識別不可能性、復号オラクルを持つ攻撃者でも平文の情報を一切引き出せないという強い安全性）を達成できることが証明されています。

実行検証

hashlib.sha256 と自前実装の MGF1 でOAEPのエンコード・デコードを実装し、実際のRSA暗号化・復号を通した正当性を確認した上で、以下を検証しました（SHA-256を使うためオーバーヘッドが \(2 \times 32 + 2 = 66\) バイト必要になり、300ビット素数2つ、\(N\) を約599ビットとして実験しました）。

def oaep_unpad(em, k, label=b""):
    """全チェックを単一のブール値にまとめ、途中でreturnしない
    (早期returnで失敗理由を分岐させるとManger攻撃の糸口になるため)"""
    l_hash = hashlib.sha256(label).digest()
    y = em[0]
    masked_seed, masked_db = em[1:1+32], em[1+32:]
    seed = xor_bytes(masked_seed, mgf1(masked_db, 32))
    db = xor_bytes(masked_db, mgf1(seed, k - 33))
    l_hash_prime, rest = db[:32], db[32:]
    sep_idx = rest.find(b"\x01")
    ps_ok = sep_idx != -1 and all(b == 0 for b in rest[:sep_idx])
    valid = (y == 0) and (l_hash_prime == l_hash) and ps_ok
    return valid, (rest[sep_idx+1:] if valid else None)

この599ビットの鍵に対して、実際のRSA秘密鍵復号を経由したランダム暗号文5万件のうち、有効なOAEPパディションと判定されたものは0件でした（lHash の256ビット完全一致という条件だけで確率 \(2^{-256}\) のオーダーになるため、天文学的な試行回数がなければ偶然の一致は事実上起こりません）。さらに、正当な暗号化・復号を通した後の平文ブロック EM の1ビットだけを反転させたものを2,000パターン用意し、いずれもデコード後のオラクル判定を通るかを確認したところ、2,000件すべてで無効と判定されました。PKCS#1 v1.5では PS 領域深くのバイトを変えても先頭2バイトと区切り文字だけを見る検証は影響を受けませんが、OAEPでは \(\text{MGF1}\) による拡散のおかげで、暗号文のどの1ビットを変えても復号結果全体が予測不能に変化し、ハッシュ一致という強い検証をほぼ確実に破壊することが、この実験から定量的に確認できました。

Manger攻撃とROBOT攻撃:実装の落とし穴

OAEPの安全性証明は「復号オラクルが有効/無効の1ビットしか返さない」ことを前提にしています。しかし2001年、James Manger は、OAEPの検証をif y != 0: raise ...、if l_hash_prime != l_hash: raise ...のように複数の早期returnに分けて実装すると、「先頭バイト \(Y\) が0かどうか」という1ビットだけがエラーの種類や応答時間の違いとして漏れてしまい、Bleichenbacherの攻撃と同種の絞り込みが可能になることを示しました。前節のコードで valid = (y == 0) and (l_hash_prime == l_hash) and ps_ok と全チェックを単一の式にまとめ、途中でreturnしない実装にしていたのはこのためです。さらに2018年には、ROBOT攻撃（Böck, Somorovsky, Young）が、F5・Citrix・IBMなど9社以上の実装で、20年前のBleichenbacherの攻撃がTLSサーバー上でそのまま再現できることを実証しました。パディング方式そのものの安全性証明と、それを実装したコードの安全性は別問題であり、後者は定数時間性・エラーハンドリングの一様性という実装レベルの規律によってのみ担保される、というのがこの2つの攻撃が残した教訓です。

タイミングサイドチャネルへの言及:復号は定数時間でなければならない

パディングオラクル攻撃が「サーバーの応答内容の違い」を悪用する攻撃だったのに対し、タイミングサイドチャネル攻撃は「サーバーの応答"時間"の違い」を悪用します。 繰り返し二乗法とモンゴメリラダーの記事 で詳しく検証した通り、素朴な二進法べき乗算 \(c^d \bmod N\) の乗算回数は秘密指数 \(d\) のハミング重みに依存するため、実行時間の統計的な差が秘密鍵のビットパターンに関する情報を漏らします（Paul Kocher, 1996年、RSA/DH/DSSに対する原理実証）。同記事の実測では、2048ビット相当の法のもとで**素朴な二進法べき乗算は条件間で最大121.6%の実行時間差が生じたのに対し、モンゴメリラダーはわずか0.1%**とほぼ完全にビットパターンから独立していました。

興味深いことに、本記事のBleichenbacher攻撃の実装で使った「\(s\) を小さい方から順に試す」操作も、暗号業界では慣習的に “blinding” と呼ばれる操作です。しかし意味は正反対です。攻撃者側のblinding（Bleichenbacherの攻撃）は、既知の \(s\) を掛けてサーバーに問い合わせを繰り返すことで秘密情報を引き出す操作である一方、防御側のRSA blinding（Kocherのタイミング攻撃への対策として提案）は、復号の直前に \(c' = c \cdot r^e \bmod N\) （\(r\) は攻撃者に予測できないランダム値）としてから復号し、最後に \(r^{-1}\) を掛けて補正することで、実行時間が攻撃者の制御下にない乱数 \(r\) に依存するようになり、秘密指数 \(d\) のビットパターンとの相関を破壊するという対策です。同じ数学的操作（乗法準同型性の利用）が、攻撃にも防御にも使われるという対比は、RSAの構造的な特徴（式 \(\text{(19)}\) ）が諸刃の剣であることをよく表しています。実務では、モンゴメリラダーによる演算回数の均一化とRSA blindingによる乱数化を併用し、実行時間から秘密鍵の情報が一切漏れないようにするのが標準的な設計です。

現在の安全性評価と耐量子暗号への移行

最後に、RSAの安全性に関する最新の状況を整理します。

古典計算機による素因数分解の記録は、2020年にGNFS（一般数体篩法）で分解された RSA-250（829ビット） が現時点でも最大であり、実用的なRSA-2048（2048ビット）は未だ分解されていません。2024年前後にはD-Wave等の量子アニーラによる「RSA-2048を解いた」という趣旨の主張が話題になりましたが、これらは実際にはショアのアルゴリズムとは異なる手法によるものであり、いずれも実用的なRSA鍵の脅威にはなっていません（ショアのアルゴリズムを厳密に実装した量子回路での素因数分解の実績は、2025年時点でも48ビット程度の小さな数にとどまります）。一方、理論面では2025年5月にCraig Gidneyが、RSA-2048を分解するのに必要な物理量子ビット数の見積もりを、誤り訂正のオーバーヘッドを含めても100万個未満・実行時間1週間未満まで引き下げる論文を発表しており（2019年時点の見積もり約2,000万量子ビットから大幅に改善）、アルゴリズム・ハードウェア両面での改善が着実に進んでいることを示しています。現状の量子コンピュータの物理量子ビット数はこれよりまだ数桁小さく、直ちにRSA-2048が脅かされる状況にはありませんが、この傾向を踏まえた移行の準備が各国で進められています。

標準化の面では、NISTは2024年8月、格子暗号ベースの耐量子暗号標準 FIPS 203（ML-KEM、旧CRYSTALS-Kyber、鍵カプセル化）・FIPS 204（ML-DSA、旧CRYSTALS-Dilithium、署名）・FIPS 205（SLH-DSA、ハッシュベース署名）を正式に確定し、2016年から続いた標準化プロセスに区切りをつけました。続く2024年11月のNIST IR 8547（移行計画のドラフト）では、RSA-2048やECC P-256など112ビット安全性の暗号は2030年までに非推奨化、2035年までに使用禁止という移行スケジュールが示されています。RSAが破られる根拠となる数論的問題（素因数分解）が量子コンピュータ上のショアのアルゴリズムで多項式時間で解けてしまう仕組みと、格子問題（Learning With Errors）がなぜ量子コンピュータにも耐性を持つと考えられているかについては、 耐量子暗号入門の記事 でRegev暗号のフルスクラッチ実装とともに詳しく解説しています。

セキュリティに関する注意（まとめ）

本記事の実装は教育目的であり、以下の理由から実用環境では使用すべきではありません。

• パディングの欠如: 教科書的RSAは乗法準同型性（式 \(\text{(19)}\) ）を持ち、選択暗号文攻撃に脆弱です。実務では前節で検証したOAEPなど、証明可能安全性を持つパディング方式を使う必要があります。
• 秘密指数dの大きさ: \(d\) を高速化のために小さくすると、Wienerの攻撃で公開鍵だけから復元されてしまいます。\(e=65537\) から \(d\) を逆算する標準的な手順に従う限り問題は生じません。
• Nの使い回し: 同じ法 \(N\) を複数の鍵ペアで共有すると、共通法攻撃で平文が復元されます。鍵ペアは必ず独立した \(p, q\) から生成する必要があります。
• タイミングサイドチャネル: 定数時間性のない実装は、復号処理の実行時間から秘密鍵の情報が漏れます。実務ではモンゴメリラダーとRSA blindingを組み合わせた実装が必要です。
• 鍵長: 本実装のデフォルト512ビットは現在では安全ではありません。実用上は最低でも 2048ビット が推奨されており、2030年代にはRSA自体からの移行が求められています。
• 量子コンピュータの脅威: ショアのアルゴリズムにより、十分な規模の量子コンピュータが実現すればRSAは多項式時間で解読されます。耐量子暗号（Post-Quantum Cryptography）への移行が各国で進行中です。

関連記事

• OAuth 2.0/OIDC入門 - RSAがJWT署名に使われるOAuth 2.0/OIDCプロトコルを解説しています。
• ゼロトラストセキュリティの概要と導入 - RSA暗号が基盤技術として使われるゼロトラストアーキテクチャを解説しています。
• 耐量子暗号入門：Learning With Errors（LWE）とRegev暗号をPythonで実装 - 本記事の素因数分解問題がShorのアルゴリズムで量子コンピュータに破られる理由と、その代替となるLWE問題を解説しています。
• セキュリティ資格比較：CISSP vs 情報処理安全確保支援士 - 暗号技術が試験範囲に含まれるセキュリティ資格の比較を解説しています。
• Diffie-Hellman鍵交換プロトコル：理論とPython実装 - RSAとは異なるアプローチで安全な鍵交換を実現するDHプロトコルを解説しています。
• ユークリッドの互除法と拡張ユークリッドの互除法のpythonプログラム - 本記事の秘密鍵生成で使うモジュラ逆元計算（拡張ユークリッドの互除法）の正当性証明・ベズーの等式の構成的証明・計算量を詳しく解説しています。
• 繰り返し二乗法による高速べき乗剰余計算のPython実装 - RSA暗号の暗号化・復号で使われるべき乗剰余計算のアルゴリズムを解説しています。
• 楕円曲線ElGamal暗号の原理とPythonによる簡易実装 - RSAとは異なる数学的基盤（楕円曲線上の離散対数問題）に基づく公開鍵暗号を解説しています。
• 暗号ロードマップ：対称鍵・公開鍵・ハッシュ・鍵交換の体系ハブ — RSA を「公開鍵暗号（素因数分解）」枠で位置づけ、DH・楕円曲線暗号・ハッシュとの関係を俯瞰するメタハブ。
• Diffie-Hellman 鍵交換の理論と Python 実装（離散対数問題） — RSA とは異なる「離散対数問題」を安全性根拠とする鍵交換プロトコル。素因数分解 vs 離散対数の対比で理解が深まります。
• 楕円曲線暗号（ECC）の数学と Python 実装 — 256 bit 鍵で RSA 3072 bit 相当の安全性を実現する現代の主流方式。点加算・ECDLP・ECDH・ECDSA・X25519 を詳解。
• AES / ChaCha20 対称鍵暗号の理論と Python 実装 — RSA が遅いからこそハイブリッド構成で本体を担う対称鍵暗号。ラウンド構成・GF(2^8)・暗号モード・AEAD を詳解。
• デジタル署名（ECDSA / EdDSA / RSA-PSS）の理論と Python 実装 — RSA の「秘密鍵で署名・公開鍵で検証」を実用化した署名スキーム。RSA-PSS のランダムパディングと hash-then-sign パラダイムを詳解。

関連ツール

• ハッシュ生成ツール（DevToolBox） - MD5・SHA対応のハッシュ生成ツール

参考文献

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). “A method for obtaining digital signatures and public-key cryptosystems”. Communications of the ACM, 21(2), 120-126.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.