【RSA】Hastad Broadcast Attackの仕組みと実装

投稿日：2022/03/03 更新日:2024/04/19

使える条件

同じ平文 $M$ を異なる $N$ 、同じ $e$ を使って暗号化された文が $e$ 個ある時です。

平文の導出方法

平文を $M$ 、 $e$ 個の公開鍵を $(N_1, e), (N_2, e),...,(N_e, e)$ とし、暗号文を $C_1, C_2,...C_e$ とします。
それぞれの暗号文に対して以下のことが成立します。

\begin{aligned} C_1 &\equiv M^e \mod N_1 \\ C_2 &\equiv M^e \mod N_2 \\ &\vdots \\ C_e &\equiv M^e \mod N_e \end{aligned}

ここで中国剰余定理より

\begin{aligned} x &\equiv C_1 \mod N_1 \\ x &\equiv C_2 \mod N_2 \\ &\vdots \\ x &\equiv C_e \mod N_e \end{aligned}

これを満たす $x$ が $N_1N_2...N_e$ 未満に1つ存在します。
また $C_i \equiv M^e \mod N_i$ であることより満たす $x$ が $M^e$ となるので

x \equiv M^e \mod N_1N_2...N_e

が成立しますまた $M < N_i$ より $M^e < N_1N_2...N_e$ が成立するので
求める平文 $M$ は

M = \sqrt[e]{x}

となり、求めることができました！

Pythonでの実装

def gcd(a, b):
    #最大公約数を求めます
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

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

    q = a//b
    r = a%b

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

def crt(rs, ms):
    #中国剰余定理を計算します
    R = 0
    M = 1
    for r, m in zip(rs, ms):
        g = gcd(M, m)

        assert r%g == R%g
        s, _ = extgcd(M, m)

        lcm = m*M // g
        R += (r - R)//g * M * s
        R %= lcm
        M = lcm
    return [R, M]

def e_rooti(a, e):
    # rのe乗根の切り落としを計算します
    ok = 0
    ng = a
    while ng - ok > 1:
        mid = (ok+ng) >> 1
        if mid**e <= a:
            ok = mid
        else:
            ng = mid
    return ok

def hastad_broadcast_attack(e, pairs):
    #e:公開鍵のe, pairs: (c, N)暗号文とNのペアです
    rs, ms = zip(*pairs)
    r, _ = crt(rs, ms)
    return e_rooti(r, e)

練習問題

以下の3つの暗号文から元の平文（数値）を求めてください。
eはすべて3です。

e=3
c1=1467331094246560737
N1=10397589660261129301
c2=853264173255865627
N2=10696384842761712253
c3=10076556659009855575
N3=12180236767128924457

練習問題解答

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

e=3
paris = [
(1467331094246560737, 10397589660261129301),
(853264173255865627, 10696384842761712253),
(10076556659009855575,12180236767128924457),
]

M = hastad_broadcast_attack(e, pairs)
M = int(M)#小数点切り捨て
print(f"M={M}")

出力

M=1234567890

参考文献

Chennagiri, Abhay. "A Tutorial paper on Hastad Broadcast Attack."　http://koclab.cs.ucsb.edu/teaching/cren/project/2017/chennagiri.pdf
（2022/03/03閲覧）