数学に自信がないハッカーでも解けるCommon Modulus(共通n攻撃)をやさしく解説

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

同じ金庫をカギの違いで使うとどうなるのか。

もし、同じ金庫を使って、違う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暗号の基本を学ぶ」をぜひご覧いただくことをお勧めします。

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

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)