ペネトレーションテスト&バグバウンティ
同じ金庫をカギの違いで使うとどうなるのか。
もし、同じ金庫を使って、違う2人がそれぞれ自分のカギでロックしていたら。
その金庫に入っている手紙(秘密のメッセージ)は、実は2つのカギ情報から中身がバレてしまうかもしれません。
これが「Common Modulus Attack(コモン・モジュラス攻撃)」と呼ばれる手法です。
RSAの簡単なおさらい
RSAは「公開鍵暗号」と呼ばれるもので、次の2つの鍵を使います。
・公開鍵 (n, e):みんなに見せてよい鍵
・秘密鍵 d:自分だけが持っておく鍵
記号 意味
m:メッセージ(手紙)
c:暗号文(暗号に変わった手紙)
n:大きな数(暗号ロッカーの番号)
e:公開カギ(みんなに公開していい「暗号ロッカーに手紙をいれるカギ」)
d:秘密カギ(こっそり持ってる「暗号ロッカーから手紙をとりだすためのカギ」)
暗号の流れは以下のとおり。
1.メッセージ m を数に変換
2.c = m^e mod n で暗号化
3.m = c^d mod n で復号
普通は、みんなnをバラバラにして使うのがルールです。
でも、同じnを2人が使って、eだけ違うと危険です。
この時点で頭の中が???の方は先に「数学が苦手なハッカーでもわかる、RSA暗号の基本を学ぶ」をぜひご覧いただくことをお勧めします。
Common Modulus Attackとは
たとえば
Aさん:c1 = m^e1 mod n
Bさん:c2 = m^e2 mod n
同じメッセージ m を送っていたとすると、この2つの暗号文から元の m を計算で取り出せてしまうのです!
そのカギになるのが、この式です。
s1 * e1 + s2 * e2 = 1
この s1, s2 を使って
m = (c1^s1 * c2^s2) mod n
という計算をすると、平文 m が復元されるのです。
※s1とs2はざっくり話すと「ちょうどいい係数」です。
Common Modulus Attackでは、同じメッセージmを2つの違う鍵(e1, e2)で暗号化した暗号文c1、c2があるときに、ある特別な係数 s1、s2を使うと、mを取り戻せるという不思議な性質を使います。
この s1, s2 は、次のような数式を満たす「ちょうどいい係数」です。
s1 × e1 + s2 × e2 = 1
これが成り立つと、数学的な裏技で元の m が復元できるのです。
後のPythonのプログラムより
s1, s2 = extended_gcd(e1, e2)
この1行で s1 × e1 + s2 × e2 = 1 を満たす s1, s2 が見つかります。
拡張ユークリッドの互除法ってなに
「互除法(ごじょほう)」とは、2つの数字の最大公約数(GCD)を求める方法です。
たとえば、12と8の最大公約数は4ですよね。
この「拡張(かくちょう)ユークリッドの互除法」は、ただGCDを求めるだけでなく、
a * x + b * y = GCD(a, b)
という形の x と y も一緒に求めてくれる特別なバージョンです。
Common Modulus Attackでは、これを使って s1, s2 を出しています。
ポイントは
e1とe2を入力にして
s1 * e1 + s2 * e2 = 1 という形の s1, s2 を出す。
これがあるから、2つの暗号文から元のメッセージを復元できるのです。
実際のPythonコードでやってみよう
以下は、Kali Linuxの仮想環境で動作する方法です。
開発環境は、windows11、Oracle virtualBox、Kali Linuxです。
1.ライブラリーの確認
1.pipがあるか確認します。(なければインストールします。)
pip3 --version
もし、command not found と出た場合はインストールしてください。
sudo apt update
sudo apt install python3-pip -y
2.Kali Linuxでpipの制限を解除する。
Kali Linuxでは"pip install"に制限があるため、次のように実行します。
python3 -m pip install --break-system-packages pycryptodome
--break-system-packages は、Kali Linux特有の制限(管理外のパッケージを防ぐ)を解除するためのフラグです。
2.Pythonコード
from Crypto.Util.number import inverse, long_to_bytes
# 拡張ユークリッド互除法
def extended_gcd(a, b):
if b == 0:
return (1, 0)
else:
x1, y1 = extended_gcd(b, a % b)
return (y1, x1 - (a // b) * y1)
# 与えられた値
n = 75073503506540719412054301227834947955487673445810739660116833784947088524942296546957841854159521058545511732524789016201343885266641933998317371754722490961718452590921535903340555859985685178060790652057820861539579191309036345997107241262297007893995335419995643458224378651029479178687039424384042912541
e1 = 17
e2 = 65537
c1 = 71558929902872576473947432418353846466610022039471936574913073406751788651217502686708262933959094874005120378081001737827379173945123827238813081509000271640454552744624980954569333123585876506338082539273262692727155386498445766409263698884798921868995856314226885047747268401460989918796393413809073471312
c2 = 12871376623985602506471535683944200516014765963879996837786713570392187445035169254898047134410580826480245715545456866167509123375717516960160762398524600981956821651550522733833849728163220553325654410159442914475693887231777259695929589249323856265459050363088895935824240667614469280055881010909983504817
# 拡張ユークリッド互除法を使って係数を求める
s1, s2 = extended_gcd(e1, e2)
# s1, s2 の符号を調整
if s1 < 0:
c1 = inverse(c1, n)
s1 = -s1
if s2 < 0:
c2 = inverse(c2, n)
s2 = -s2
# 平文を復元
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
print("復号結果(整数):", m)
print("復号結果(文字列):", long_to_bytes(m).decode())
このコードを実行すると、元のメッセージ(たとえば flag{...})が表示されます。
3.実行結果
python3 rsa_common_modulus.py
復号結果(整数): 42134526936709971499034437707809914912338111740194594855328115581
復号結果(文字列): flag{common_modulus_attack}
Common Modulus Attackの見分け方について
・n が同じなのに、e1, e2 が違う。
・2つの暗号文(c1, c2)が与えられている。
使っている平文が同じ。(と予想できる)
注意点として
・e1 と e2 が互いに素(つまり割り切れない)であることが条件。
・s1 や s2 がマイナスだったら逆数(mod逆元)を使う。
数学に自信がないハッカーでも解けるCommon Modulus(共通n攻撃)をやさしく解説のまとめ
少し難しかったですね。(^^;
同じnで違うeを使うと、メッセージがバレる可能性があります。
数学が苦手でも、Pythonコードでしっかり解けると思います。
CTFでRSAが出てきたら、「nが同じか?」「eが違うか?」をまずチェックしてみましょう。
この攻撃を知っていると、解ける問題が一気に増えると考えます。