【RSA】Common Modulus Attackの仕組みと実装

投稿日：2022/03/01 更新日:2022/03/01

使える条件

同じ平文 $M$ を $N$ が共通かつ $\gcd(e_1, e_2)=1$ の公開鍵 $(N, e_1)$ , $(N, e_2)$ で暗号化されたときに使えます。

平文の導出方法

まず暗号文 $C_1, C_2$ は以下の式で示されます。

C_1 = M^{e_1} \mod N \\ C_2 = M^{e_2} \mod N

$\gcd(e_1, e_2)=1$ より以下の式を満たす整数 $(a, b)$ が存在します。

a \times e_1 + b\times e_2 = 1

${C_1}^a, {C_2}^b$ を考えていくと

\begin{aligned} {C_1}^a {C_2}^b &= M^{a \times e_1}M^{b \times e_2} \mod N \\ &= M^{a \times e_1 + b\times e_2} \mod N \end{aligned}

ここで $a \times e_1 + b\times e_2=1$ であったので

\begin{aligned} {C_1}^a {C_2}^b &\equiv M^{1} \mod N \\ &\equiv M \mod N \end{aligned}

となり、平文 $M$ が導出できました！

Pythonでの実装

多倍長に対応しているので簡単に大きな数の計算ができます！

def extgcd(a, b):
    #拡張ユークリッド互除法
    #ax + by = gcd(a, b)となる(x, y)を求めます
    if b == 0:
        return [1, 0]

    q = a//b
    r = a%b
    
    s, t = extgcd(b, r)
    y = s - q*t
    return [t, y]

def common_modulus_attack(c1, c2, e1, e2, n):
    #c1:暗号文1, c2:暗号文2
    a, b = extgcd(e1, e2)# a*c1 + b*c2 = 1 となる(a, b)を計算する
    m1 = pow(c1, a, n)# c1^a mod N の計算
    m2 = pow(c2, b, n)# c2^a mod N の計算
    return (m1 * m2) % n

練習問題

$N$ は共通です。 $e_1$ で暗号化したものが $C_1$ 、 $e_2$ で暗号化したものが $C_2$ です！
平文 $M$ を出してください。 ※答えは数値です

N=60963434132501314035336447525947508568978923800339967543702272746525205013233
e1=58757
C1=27726517759308413313356903988967832327531954882576351327358580190426923118280
e2=61333
C2=11271012342421722589415390254769559241378949949302863047216142534228523047931

練習問題の解答

紹介したPythonのコードを使って解きます！

n = 60963434132501314035336447525947508568978923800339967543702272746525205013233  
e1 = 58757  
c1 = 27726517759308413313356903988967832327531954882576351327358580190426923118280  
e2 = 61333  
c2 = 11271012342421722589415390254769559241378949949302863047216142534228523047931  

ans = common_modulus_attack(c1, c2, e1, e2, n)

print(f"M = {ans}")

出力

M = 1234

参考文献

Karakra, Abdallah, and Ahmad Alsadeh. "A-RSA: Augmented RSA." 2016 SAI Computing Conference (SAI). IEEE, 2016.