1. はじめに
この記事では、RSA暗号に対する攻撃が成立する要件と、その対策について述べる。
RSA暗号では2つの大きな素数（$=p, q$）を使って、次の数字を生成する。
- 公開モジュラス $N = p \times q$
- オイラー関数 $\phi(N) = (p - 1) \times (q - 1)$
- 公開指数 $\gcd(e, \phi(N)) = 1$ となるような $e$
- 秘密指数 $ed \equiv 1 \pmod{N}$ を満たす $d$
これらの値は通信ごとに異なるものを使用するのが好ましい。
今回はこれらの数字のうち、公開モジュラス $N$ を共通にした時成立する攻撃について考える。
2. 共通モジュラスに対する攻撃
Aさんが、BさんとCさんそれぞれに共通のメッセージを送ることを考える。このとき、メッセージの暗号化に利用する公開モジュラスを共通にする。それ以外の数値は、それぞれ異なるものを利用する。
2つの公開鍵 $(e_1, N), (e_2, N) $を利用して共通のメッセージ $M$ を暗号化すると、それぞれの暗号文は次のようになる。
- $C_1 = M ^ {e_1} \pmod{N}$
- $C_2 = M ^ {e_2} \pmod{N}$
攻撃者はこの2つの暗号文を得られたとする。このとき、拡張ユークリッドの互除法を利用して
$$
e_1 x_1 + e_2 x_2 = \gcd(e_1, e_2)
$$
この式が成り立つような $x_1, x_2$ を得られた場合、メッセージを復元することができる。
\begin{aligned}
C_1^{x_1} C_2^{x_2}
&\equiv (M^{e_1})^{x_1}(M^{e_2})^{x_2} \pmod{N} \\
&\equiv M^{e_1 x_1 + e_2 x_2} \pmod{N}
\end{aligned}
このとき、$\gcd(e_1, e_2) = 1$ すなわち $e_1, e_2$ が互いに素であるとき、平文 $M$ を取り出せる。
\begin{aligned}
C_1^{x_1} C_2^{x_2} &\equiv M^{e_1 x_1 + e_2 x_2} \pmod{N} \\
&\equiv M
\end{aligned}
3. Pythonによる実装
これらの一連の攻撃を Python で実装したものを次に示す。
import random
def miller_rabin(n, L = 50):
"""与えられた整数 n が素数かどうかを確率的に判定する（Miller–Rabin 素数判定法）
Args:
n (int): 判定対象の整数
L (int): テストの繰り返し回数（多いほど精度が上がる）。デフォルトは50。
Returns:
bool: n が素数と判定された場合は True、合成数と判定された場合は False。
"""
if n == 2:
return True
if (n < 2) or (n % 2 == 0):
return False
t = (n - 1) >> 1
while (t % 2) == 0:
t >>= 1
for _ in range(L):
a = random.randint(2, n - 1)
tmp = t
b = pow(a, tmp, n)
while (tmp != n - 1) and (b != 1) and (b != n - 1):
b = pow(b, 2, n)
tmp <<= 1
if (b != n - 1) and (tmp % 2 == 0):
return False
return True
def generate_prime(bits=16):
"""指定されたビット長のランダムな素数を生成する
Args:
bits (int): 素数のビット長（例：16, 512, 1024など）
Returns:
int: 生成された素数
"""
while True:
candidate = random.getrandbits(bits) | 1
if miller_rabin(candidate):
return candidate
def gcd(a, b):
"""2つの整数の最大公約数をユークリッドの互除法で求める
Args:
a (int): 整数 a
b (int): 整数 b
Returns:
int: a と b の最大公約数
"""
while b:
a, b = b, a % b
return a
def generate_e(phi_n):
"""φ(N) と互いに素な公開指数 e をランダムに生成する
Args:
phi_n (int): φ(N) = (p - 1) * (q - 1)
Returns:
tuple[int, int] (e1, e2)
- e1, e2: φ(N) と互いに素な e1（RSA の公開指数）
"""
while True:
e1 = random.randrange(3, phi_n, 2)
e2 = random.randrange(3, phi_n, 2)
if gcd(e1, phi_n) == 1 and gcd(e2, phi_n) == 1 and gcd(e1, e2) == 1:
return (e1, e2)
def extended_euclid(a, b):
"""拡張ユークリッドの互除法を用いて、ax + by = gcd(a, b) を満たす (g, x, y) を求める
Args:
a (int): 整数 a
b (int): 整数 b
Returns:
tuple[int, int, int]: (g, x, y)
- g: a と b の最大公約数
- x, y: ax + by = g を満たす整数
"""
if b == 0:
return (a, 1, 0)
g, x1, y1 = extended_euclid(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
def generate_m(N):
"""メッセージを作成する（1 <= M < N かつ gcd(M, N) = 1 を満たす）
Args:
N (int): モジュラス N（N > 1 を想定）
Returns:
int: 生成されたメッセージ M（1 <= M < N）
"""
if N <= 1:
raise ValueError("N must be > 1")
while True:
m = random.randrange(1, N)
if gcd(m, N) == 1:
return m
# ----- 2つの素数を作る -----
p = generate_prime(16)
q = generate_prime(16)
print("p =", p)
print("q =", q)
# ----- 公開モジュラスとそのオイラー関数を作る ----
N = p * q
phi_n = (p - 1) * (q - 1)
print(f"N = {N}")
print(f"phi_n = {phi_n}")
# ----- 公開指数 e1, e2 を作る -----
e1, e2 = generate_e(phi_n)
print(f"e1 = {e1}, e2 = {e2}\n")
# ----- メッセージ M を作る -----
M = generate_m(N)
# ---- M の暗号文を2つ、それぞれ異なる公開指数で作成する -----
C1 = pow(M, e1, N)
C2 = pow(M, e2, N)
g, x, y = extended_euclid(e1, e2)
recovered_message = pow(C1, x, N) * pow(C2, y, N) % N
print(f"Recovered M = {recovered_message}")
print(f"Original M = {M}")
if recovered_message == M:
print("✅ success")
else:
print("❌ fail")
コードを実行した結果を次に示す。
p = 2671
q = 11353
N = 30323863
phi_n = 30309840
e1 = 1973899, e2 = 18506453
Recovered M = 16776568
Original M = 16776568
✅ success
結果から元の$M$と、復元された$M$は一致していることがわかる。
4. まとめと対策
この攻撃はRSA暗号自体の脆弱性ではなく、ここまでで述べたように、非常に限定された状況でのみ成立するものである。
- 公開モジュラス$N$が同じ
- メッセージ$M$が同じ
- 異なる公開指数$e_1, e_2$の最大公約数が$1$
これらの条件を満たして、初めて成立する攻撃である。しかし、$N$を共通にすることで攻撃のリスクは確実に上昇するため、共通の公開モジュラス$N$を使用することを避けるのがベストである。
5. 参考資料
[1] Pythonで学ぶ暗号理論