Common Modulus Attack - crypto-writeup-public

RSAの典型

$n$ と $m$ が共通で $e$ が異なる複数の暗号文 $c_1, c_2$ を与えられた時、 $m$ が復号できるというもの。ただし $gcd(e_1, e_2) = 1$

http://elliptic-shiho.hatenablog.com/entry/2015/12/14/043745

拡張ユークリッドの互除法を用いて $e_1X + e_2Y = 1$ を満たすX, Yを探す。こういうX, Yを使うとmが導出できるらしい。

$c_1^Xc_2^X = (m^{e_1})^X(m^{e_2})^Y$

$= m^{e_1X}m^{e_2Y}$

$= m^{e_1X + e_2Y}$

$= m^1$

pythonによる実装

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = egcd(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = modinv(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = modinv(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m