数学が苦手なハッカーでもわかる、RSA暗号の落とし穴「Small e Attack」をやさしく深掘りしてみた

ペネトレーションテスト&バグバウンティ

RSA暗号は、セキュリティの世界で広く使われています。

しかし、使い方を間違えると簡単に破られてしまうという特性があります。

「Small e Attack(スモール・イー・アタック)」は、その典型的な例です。

そこで数学が得意でない人でも理解できるように、わかりやすく説明いたします。

RSAの簡単なおさらい

RSAは「公開鍵暗号」と呼ばれるもので、次の2つの鍵を使います。

・公開鍵 (n, e)：みんなに見せてよい鍵

・秘密鍵 d：自分だけが持っておく鍵

暗号の流れは以下のとおり。

1.メッセージ m を数に変換

2.c = m^e mod n で暗号化

3.m = c^d mod n で復号

※MOD関数とは、数値を除数で割ったときの余りを求める関数です。例えば、MOD(10, 3)は1を返します。これは、10を3で割ったときの余りが1だからです。

ここで使われる"e"の値はたいてい"65537″をつかわれますが、CTFではあえて"e = 3″などの小さい値が使われます。これが攻撃の入り口になります。

この時点で頭の中が？？？の方は先に「数学が苦手なハッカーでもわかる、RSA暗号の基本を学ぶ」をぜひご覧いただくことをお勧めします。

https://whitemarkn.com/penetrationtest/basics-of-rsa-encryption/

Small e Attackとは

「Small e Attack」は、RSAで"e"が小さすぎて、modの効果が働かないときに発生します。

記号意味

m：メッセージ(手紙)

c：暗号文(暗号に変わった手紙)

n：大きな数(暗号ロッカーの番号)

e：公開カギ(みんなに公開していい「暗号ロッカーに手紙をいれるカギ」)

d：秘密カギ(こっそり持ってる「暗号ロッカーから手紙をとりだすためのカギ」)

たとえば

c = m^3 mod n

のとき、もし m^3 < n なら、mod n してもそのまま c = m^3 になります。

この場合、暗号文"c"は"m"を3回かけた結果そのままの値、ということになります。

つまり、暗号文から元のメッセージ m を見つけるには、

“c"の3乗根(m³の逆)」を求めるだけでよいのです。

※"cの3乗根"とは、3回かけてcになるような数のことです。

例えば、8の3乗根は2です(2 x 2 x 2 = 8)。

実際の攻撃手順(pythonコード)

以下は、Kali Linuxの仮想環境で動作する方法です。

開発環境は、windows11、Oracle virtualBox、Kali Linuxです。

1.仮想環境の作成および、ライブラリーインストール

# 任意のディレクトリで仮想環境を作成

python3 -m venv rsa_env

# 仮想環境を有効化

source rsa_env/bin/activate

# ライブラリをインストール

pip install pycryptodome gmpy2

2.Pythonコード

from gmpy2 import iroot

from Crypto.Util.number import long_to_bytes

# テスト用：暗号文を作る

from Crypto.Util.number import bytes_to_long

m = bytes_to_long(b"flag{easy}")

print(“m =", m)

c = m**3

print(“c =", c)

# e の値(今回は 3)

e = 3

# 暗号文 c の e乗根(整数)を求める

m, exact = iroot(c, e)

# 結果を表示

print(“[+] 復号に成功しました！")

print(“整数としてのメッセージ:", m)

# バイト列に変換して、文字として表示(flag{…} など)

try:

print(“文字列に変換:", long_to_bytes(m).decode())

except:

print(“文字列に変換できませんでした(バイナリ出力):", long_to_bytes(m))

3.実行&出力結果

実行および出力結果は以下の通りです。

python3 rsa_small_e_attack.py
m = 483680648326884080449917
c = 113155621913751543279005755939626029123651673207827018786859868159578213
[+] 復号に成功しました！
整数としてのメッセージ: 483680648326884080449917
文字列に変換: flag{easy}

攻撃の原理として、なぜm³だけで暗号がバレるのか

RSAの安全性は、「m^e が n より大きくなる」ことを前提にしています。

ところが、m が小さいと m^e も小さくなってしまい、modの意味がなくなります。

このとき、攻撃者は次のように考えます。

c = m^e だとしたら、

m = e乗根(c) を求めるだけで復号完了

これは数学的には"整数のn乗根を求める"という処理ですが、Pythonの gmpy2.iroot() を使えばできます。

CTFでの見分け方とひっかけ問題に注意

CTF問題で「Small e Attack」を見分けるヒントとして

・e = 3 と書かれている(またはやけに小さい)

・メッセージのサイズが小さい(flagや単語など)

・"パディングなし" と説明に書かれている

※パディングとは「メッセージに余分なデータをくっつけて、安全にするテクニック。

逆に、次のようなケースは注意が必要です。

・メッセージが長い(m3 が n を超える)

・RSA-OAEPなどの"パディングあり"の場合(これは防御策)