同一个明文发给3个服务器？一文搞懂RSA广播攻击(Hastad)

御网杯 Crypto 赛题详解

本文将详细解析御网杯网络安全竞赛中一道 Crypto 赛题的解题思路，涵盖RSA 广播攻击，此题目从题目分析、漏洞原理、解题脚本到最终 Flag 进行完整讲解，希望对大家的学习有所帮助。

二、ScatterRSA —— 广播攻击

题目信息：分类 CRYPTO | 难度 中级

2.1 题目分析

本题同样使用了 e = 3 的 RSA 加密，但与 BabyRSA 不同的是，本题提供了三组不同的加密参数（n1, a1, b1, c1）、（n2, a2, b2, c2）、（n3, a3, b3, c3），每组参数的加密方式为 c = (a*m + b)^3 mod n。由于相同的明文 m 被三个不同的模数加密，这正是经典的哈维广播攻击的变体。我们需要先将每组参数转化为关于 m 的等价多项式，然后通过中国剩余定理（CRT）合并三个多项式，最后用 Coppersmith 方法求小根得到明文 m。

2.2 解题思路

首先，将每组加密参数转化为关于 m 的等价多项式。对于第 i 组，将 c = (a*m + b)^3 mod n 展开，可以得到一个以 m 为变量的三次多项式。具体做法是：计算 a 的模逆元 inv_a，然后构造多项式 (x + b*inv_a)^3 – c*(inv_a)^3 = 0 模 n，其中 x = m。这样就得到了三个不同模数下的同一个多项式的等价形式。

接下来，利用中国剩余定理合并三个多项式的系数。将三个多项式的对应系数通过 CRT 合并到一个大模数 N = n1 * n2 * n3 下，得到一个新的多项式。最后，对合并后的多项式使用 Coppersmith 的 small_roots 方法求解小根，即可恢复明文 m。该方法需要在 SageMath 环境中运行。

2.3 解题脚本

解题脚本需要在 SageMath 环境中运行，推荐使用在线网站 sagecell.sagemath.org：

e = 3

n1 = 134590028715846226751903719587861090472772080921099504036178613989523328571021119450984313988905557385036821505121612368860436253713267192159612607745301358472400758433053304358101099945515440169672493726615122471822947908806960237079424527450364377187388434878044214423874958715687632702618242260038201552961

a1 = 173235201602700035769143714622479214858

b1 = 58616053309986169433995951615552358657183395855412447208282770965760612937595

c1 = 50192984704229516422576705848426706185707023557654942997226592852562126143797118081125527050565529571702518296053642057549607538952767595537352818598436177372629946093076195084953301667499579328461288560942915342433209991739202980657987347584757491195480319156057361829134996133204059551472598891366688783755

n2 = 68196420818362667184273231820367250019665598198220107894027697404250798750179650739212752171893537136631632644245299647403521159317636479179387396036378651369427323164026037204640004005081098772718308292781228113356944341374614054386589378286349095152732830327900238600877850386212764491160551279660914970501

a2 = 235763128007574771186749199470667788696

b2 = 82833393375329622580640447653813478693484654663680708964473557677310067110872

c2 = 58727033167047203506164797837999819283982869287436076252773072774355826490167620639330797956244757203726547611149611642979362714607329797512143580714003751905301065313982278186988038708909021000691905664629331025167676669052317049958574849948837597306860613961557323523558290710860835719858942854534226001532

n3 = 1041978947222515494173618665626713467184482726534999334123994405129572410542742149319993470219686631218662507052426981529041688912266920273453760904110011289684534871464563352348782346283820734447304134789063563965860082130364230372312070163983650187312362722689902212270815366758596540699197732479604574605717

a3 = 289837185860108823269362666161877095653

b3 = 88038264202304767250178171651729306984925900158278305985019519489525502096874

c3 = 12441437714234741776087648075441633972630237216692770981303759863634569477393643678959437151894987980323367988780311101132662707086178418962311399292280866817688865303206505050428252909551141504556842671029262184318022978671849627397763537173137629868777942717009356259616195047064075877128354789683093509959

print("正在解析等价多项式…")

def get_poly_coeffs(a, b, c, n):

    R = Zmod(n)

    P = PolynomialRing(R, 'x')

    x = P.gen()

    inv_a = R(inverse_mod(a, n))

    poly = (x + R(b) * inv_a) ^ 3 – R(c) * (inv_a ^ 3)

    return poly.list()

coeffs1 = get_poly_coeffs(a1, b1, c1, n1)

coeffs2 = get_poly_coeffs(a2, b2, c2, n2)

coeffs3 = get_poly_coeffs(a3, b3, c3, n3)

print("正在进行中国剩余定理(CRT)合并…")

combined_coeffs = []

for i in range(4):

    c_comb = crt([Integer(coeffs1[i]), Integer(coeffs2[i]),

                   Integer(coeffs3[i])], [n1, n2, n3])

    combined_coeffs.append(c_comb)

N = n1 * n2 * n3

P_N = PolynomialRing(Zmod(N), 'x')

P = P_N(combined_coeffs)

roots = P.small_roots(X=2^600, beta=1)

if roots:

    m = int(roots[0])

    print(bytes.fromhex(hex(m)[2:]).decode())

2.4 解题步骤

第一步，将三组加密参数分别转化为关于 m 的多项式。通过计算 a 的模逆元，将加密等式 c = (a*m+b)^3 mod n 转化为一个以 m 为变量的三次多项式。第二步，使用中国剩余定理将三个多项式的系数合并到统一的大模数 N = n1*n2*n3 下。第三步，对合并后的多项式使用 SageMath 的 small_roots 方法求解小根。将脚本复制到 sagecell.sagemath.org 在线运行即可得到 flag。