RSA暗号の原理とPythonによる実装

RSA暗号の数学的原理（素因数分解問題、オイラーの定理）から鍵生成・暗号化・復号のアルゴリズムまで解説し、Pythonで実装します。

4 min read

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\) は相異なる素数）の場合、以下が成り立ちます。

\[ \varphi(N) = (p - 1)(q - 1) \tag{1} \]

オイラーの定理

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

\[ a^{\varphi(N)} \equiv 1 \pmod{N} \tag{2} \]

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

モジュラ逆元

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

\[ e \cdot d \equiv 1 \pmod{\varphi(N)} \tag{3} \]

この \(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)\) を用いて暗号化します。

\[ c = m^e \bmod N \tag{4} \]

復号 (Decryption)

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

\[ m = c^d \bmod N \tag{5} \]

正当性の証明

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

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

\[ c^d = (m^e)^d = m^{ed} = m^{1 + k \cdot \varphi(N)} = m \cdot (m^{\varphi(N)})^k \tag{6} \]

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

\[ c^d \equiv m \cdot 1^k \equiv m \pmod{N} \tag{7} \]

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

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}")

セキュリティに関する注意

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

  • パディングの欠如: 実際のRSA暗号では、OAEP（Optimal Asymmetric Encryption Padding）などのパディング方式を適用します。パディングなしのRSA（教科書的RSA）は、選択暗号文攻撃などの複数の攻撃手法に対して脆弱です。
  • 鍵長: 本実装のデフォルト512ビットは現在では安全ではありません。実用上は最低でも 2048ビット が推奨されています。
  • 量子コンピュータの脅威: ショアのアルゴリズム（Shor’s algorithm）を用いれば、十分な規模の量子コンピュータで素因数分解を多項式時間で解くことが可能です。これにより、将来的にRSA暗号は安全ではなくなる可能性があり、耐量子暗号（Post-Quantum Cryptography）への移行が進められています。

関連記事

関連ツール

参考文献

  • 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.

関連記事