Håstad's broadcast attack

はじめに

はじめまして高校二年のもちもちと言います。
自分はセキュリティキャンプ全国大会'21の暗号のゼミの修了生で、またSECCON BEGINNERS(ctf4b)ではcrypto(暗号)の作問をしています。
ここではRSAの問題でたびたび見られる、同じm,e、異なるnを用いた暗号文e個を用いることでmを復元することができるHåstad's broadcast attackの話をしていきます。
モチベーションとしては中国剰余定理でがっちゃんこしたらLow public exponent attackと同じ感じになるよねって話

0. 中国剰余定理

$m_1​,m_2​,…,m_n​$ をそれぞれ互いに素な整数とする。このとき、

\begin{align*}
x &\equiv a_1 \mod m_1 \\
x &\equiv a_2 \mod m_2 \\
&\vdots \\
x &\equiv a_n \mod m_n \\
\end{align*}

を満たす$x∈Z$が$mod\ M=m_1m_2...m_n$においてただ一つ存在する

証明
$M/m_i,m_i$​ は互いに素であるから、$M/m_is_i+m_is_i′​=1$ となる $s_i,s_i′∈Z$ が存在する。
$x=∑a_iM/m_is_i$​ とする。$i \neq j$なら $M/m_j≡0(mod\ m_i)$ なので、
$x≡a_iM/m_is_i=a_i(1−m_is_i′)≡a_i\ mod\ m_i$
より、存在性は示せた。
また$x,y$が共に条件をみたしている時、

x−y≡a_i−a_i≡0\ mod\ m_i

よりx≡yなので一意性についても証明ができた。

1. アルゴリズム

\begin{align*}
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{align*}

が与えられたとき中国剰余定理より

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

を満たす$x$が$mod\ N=N_1N_2...N_e$でただ一つ存在する。
これらより、$x \equiv M^e\ mod\ N$となり、また$M<N_i$より$M^e<N$なので

M= \sqrt[e]{x}

となる。

2. 実装

import gmpy2
from Crypto.Util.number import long_to_bytes
from itertools import combinations

import sys

sys.setrecursionlimit(10000)


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


def CRT(pairs):
    M = 1
    for a, m in pairs:
        M *= m
    result = 0
    for a, m in pairs:
        Mi = M // m
        s, _, _ = extgcd(Mi, m)
        result += a * Mi * s
    return result % M


def HBR(e, pairs):
    try:
        r = CRT(pairs)
        return gmpy2.iroot(r, e)
    except Exception as error:
        print(f"An error occurred: {error}")
        return None, False


n_values = []
c_values = []
e = 3
for combo in combinations(range(len(n_values)), 3):
    pairs = [(c_values[i], n_values[i]) for i in combo]
    flag, exact = HBR(3, pairs)
    if flag is not None and exact:
        print(long_to_bytes(int(flag)))

参考