RSA加解密专题 - 公钥指数相关攻击 | Alice and Bobの神秘小屋

在实际应用中，攻击者可能会利用一些特定的攻击方法来破解RSA加密，尤其是当公钥指数选择不当时。

本文将介绍一些与 RSA 公钥指数相关的攻击方法，包括常见的攻击手段如小公钥攻击、共模攻击等。

共模攻击 😝

对于同一个模数 $n$，用于加密同一个 $m$，但是用不同 $e$ 加密两次

$\begin{align*} m^{e_1} \equiv c_1 \mod n \\ m^{e_2} \equiv c_2 \mod n \end{align*}$

使用裴蜀定理可以破解,构造

$r e_1 + s e_2 = gcd(e_1,e_2)$

则由

$c_{1}^r \cdot c_{2}^s \equiv m^{er_1 + se_2} \mod n$

从而绕过私钥d解密

共模攻击例题

共模攻击例题下载

from Crypto.Util.number import *
from secret import m

n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
e2=9647291
c1=pow(bytes_to_long(m.encode()),e1,n)
c2=pow(bytes_to_long(m.encode()),e2,n)
print("c1=",c1)
print("c2=",c2)
# c1= 790366317276917716093037100691893212049197503039073730961711955448039864232657167573766790435902489218987416033345432295535434340907830576059653129588389135233836704959763784732603854307280897825796829293821089699244606589550689905999360752865586633248545571069424718536350480397506708904105353777714019847026603704906940973023655873113053577161389905208578179532007836298832828616932855035573669965730367452024031424244549158099754154915714597044930116500701707880040556392334392040167123504591683227247869389138456426790241330370554371099743080796833926937422959498423437908845573739316285898375909700396674766321
# c2= 4478228437147112241330288727207043414653440426045870497003424494438532257351016896075282127540792673410751595389118015588892772311255950462483402965089986383679582710285977427903307418218183817805264826906460262820854269348325404657900131315817318564877009830557176260073108040099242211702768455039629577625595469833810558303709929093235956775183074705448641710348260784158331497639337250366911970600020203747263235354753699686026666826062329129036821935202924925003686947876422542100428131746969352587613145920594297604370505030268652906467071393237088678927582520826567309207877633272146060026832148078270532393467

在这个例题中，两个加密使用了同一个模数 $n$，但是使用了不同的公钥指数 $e_1$ 和 $e_2$，攻击者可以通过构造裴蜀定理中的线性组合来破解，获取到原始消息 $m$。

解题代码示例：


from Crypto.Util.number import *
import gmpy2 as gp

n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
e2=9647291
c1= 790366317276917716093037100691893212049197503039073730961711955448039864232657167573766790435902489218987416033345432295535434340907830576059653129588389135233836704959763784732603854307280897825796829293821089699244606589550689905999360752865586633248545571069424718536350480397506708904105353777714019847026603704906940973023655873113053577161389905208578179532007836298832828616932855035573669965730367452024031424244549158099754154915714597044930116500701707880040556392334392040167123504591683227247869389138456426790241330370554371099743080796833926937422959498423437908845573739316285898375909700396674766321
c2= 4478228437147112241330288727207043414653440426045870497003424494438532257351016896075282127540792673410751595389118015588892772311255950462483402965089986383679582710285977427903307418218183817805264826906460262820854269348325404657900131315817318564877009830557176260073108040099242211702768455039629577625595469833810558303709929093235956775183074705448641710348260784158331497639337250366911970600020203747263235354753699686026666826062329129036821935202924925003686947876422542100428131746969352587613145920594297604370505030268652906467071393237088678927582520826567309207877633272146060026832148078270532393467
g,r,s = gp.gcdext(e1, e2)
m_g = pow(c1, r, n) * pow(c2, s, n) % n
m, ok = gp.iroot(m_g,g)
assert ok
print(long_to_bytes(m))
# flag{use_the_same_n_is_dangerous}

小公钥攻击 🤠

如果公钥指数 $e$ 选择得过小（如 $e=3$），攻击者可以直接爆破出正确的结果，获取到原始消息 $m$。

$C \equiv M^e \mod n$

如果 $e$ 较小，则 $C = M^e$，攻击者可以直接计算

$M = \sqrt[e]{C + k n}$

来获取到原始消息 $m$。

小公钥攻击例题

小公钥攻击例题下载

from Crypto.Util.number import getPrime, bytes_to_long
from secret import m

p = getPrime(512)
q = getPrime(512)
e = 5
n = p * q
print("n = ",n)
c = pow(bytes_to_long(m.encode()), e, n)
print("c = ",c)
# n =  151884658354743631395724585360507748159987284748681837528758493598171633984152168593482231461426893458183687924535172757062309062690802891891728554675548497092710048532926098530490127945685611807130560943577105993562003866576646552381530174936590879602799062588680515873294508600878401809375729119964496068873
# c =  68358389983146861908514174327099913729389440802950325638324116448687159665872062912200362098390297202380605609237336130498725419673621377108679738418963796009518478977346741380680301178771968725758445389936586626869076720616127612057058701

在这个例题中，公钥指数 $e$ 选择得过小（$e=5$），攻击者可以直接计算 $M = \sqrt[5]{C + k n}$ 来获取到原始消息 $m$。

解题代码示例：

from Crypto.Util.number import  long_to_bytes
import gmpy2

n =  151884658354743631395724585360507748159987284748681837528758493598171633984152168593482231461426893458183687924535172757062309062690802891891728554675548497092710048532926098530490127945685611807130560943577105993562003866576646552381530174936590879602799062588680515873294508600878401809375729119964496068873
c =  68358389983146861908514174327099913729389440802950325638324116448687159665872062912200362098390297202380605609237336130498725419673621377108679738418963796009518478977346741380680301178771968725758445389936586626869076720616127612057058701
e = 5

for k in range(0,10000000):
    temp = c + k * n
    m, ok = gmpy2.iroot(temp, e)
    print(f"Trying k={k}...", end="\r")
    if ok:
        print(long_to_bytes(m))
        break
# flag{small_e_is_bad}

实际上，对于这种小根攻击，我们使用 Coppersmith 攻击会更快一些，这里我们只是为了演示小公钥攻击的原理，所以使用了暴力破解的方法。当然，仅限于这个明文较小的例题，如果明文较大，破解的方法就不太适用了。
这里我附上一个使用Coppersmith攻击的解题代码示例，供大家参考：

from sage.all import *
from Crypto.Util.number import *

n =  151884658354743631395724585360507748159987284748681837528758493598171633984152168593482231461426893458183687924535172757062309062690802891891728554675548497092710048532926098530490127945685611807130560943577105993562003866576646552381530174936590879602799062588680515873294508600878401809375729119964496068873
c =  68358389983146861908514174327099913729389440802950325638324116448687159665872062912200362098390297202380605609237336130498725419673621377108679738418963796009518478977346741380680301178771968725758445389936586626869076720616127612057058701
e = 5

R = Zmod(n)
P.<x> = PolynomialRing(R)
f = x^e - c
roots = f.small_roots(bound=2**512,epsilon=1/32)
for m in roots:
    flag = long_to_bytes(int(m))
    print(flag)

Håstad 广播攻击 🧐

如果同一个消息 $M$ 被加密成多个密文 $C_i$，并且使用了相同的公钥指数 $e$，但是不同的模数 $n_i$，攻击者可以通过中国剩余定理（CRT）来破解，获取到原始消息 $M$。

我们以 $e=3$ 为例，同时，我们假设 $m < n_i$，对于每个 $n_i$，我们都有 $m < n_i, \quad 1 \leq i \leq 3$。如果这个条件不满足的话，就会使得情况变得比较复杂，这里我们暂不讨论。

$\begin{align*} C_1 &\equiv M^3 \mod n_1 \\ C_2 &\equiv M^3 \mod n_2 \\ C_3 &\equiv M^3 \mod n_3 \end{align*}$

既然他们互素，那么我们可以根据中国剩余定理，可得

$C \equiv M^3 \mod n_1 n_2 n_3$

此外，既然 $m < n_i, \quad 1 \leq i \leq 3$，那么我们知道 $m^3 < n_1 n_2 n_3$，因此 $C < m^3 < n_1 n_2 n_3$，所以 $C = M^3$，我们可以直接开三次根来获取到原始消息 $M$。

对于较大的 $e$ 来说，我们只是需要更多的明密文对。

Håstad 广播攻击例题

Håstad 广播攻击例题下载

from Crypto.Util.number import getPrime, bytes_to_long
from secret import m

p1 = getPrime(1024)
p2 = getPrime(1024)
p3 = getPrime(1024)
q1 = getPrime(1024)
q2 = getPrime(1024)
q3 = getPrime(1024)
n1 = p1 * q1
n2 = p2 * q2
n3 = p3 * q3
e = 3
c1 = pow(bytes_to_long(m.encode()), e, n1)
c2 = pow(bytes_to_long(m.encode()), e, n2)
c3 = pow(bytes_to_long(m.encode()), e, n3)
print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"n3 = {n3}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")
# n1 = 21180112366275308792707198865461302488559205693127557021721507567406658951027484893183971746874386346549344017657780496423609870191100125206162930591509951158158895313786384410078334087373942711313704671415169591259711219172542673857746853640129378392407801833076846765791915529766486673221298820251490327058865256315102761890119503763324479969189120347374788296228439421010724923476231379022998720352792854596487066187715900286865855673410192615524429078338954151715726776929439932040633058951481065598837709559391701919303564132940137424657515472160189726163543109080323384612138592271850712993603287137677507275371
# n2 = 26298692870046419603854209107106438626626364322119633807665057835205077716901148443766353934040185822955892086743845239542911306720672775951179579233523497436530727494678487971265695182505161985229279355999100651830529513900383767281291762278091913698101895553459847468191806086109066122848275034046679346214591398371960794960928446173802863362768056449148080873128801237014636371466461105802242018480278524831090013751334363547633971239825548849102143384730044030187903043701396605393326607857727105149463605439271849673250355049751794904386124840390758363224179076896253944395507179538229841566514339776966378699671
# n3 = 12869245342475181303320296924755202819753541797517717539596064095556108493576385999354161121731642352002540447701060344408122911146469189736765677092104255335613300039538354090648284374737637720058242853559989339600163385950025982705089661378793053705329618987830223564779324941385061454586426419929951975212520146873738260085179715217979995535362995225493010874118526395325025302743041973441408932644128476440939321271157322933582064335494518736514896863501417816715050783307592053908471995029904208083874643331646961543050595330178883620466733870718886642963399595471133909399884799882277656325390344541700992326753
# c1 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125
# c2 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125
# c3 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125

这个例题中，同一个消息 $M$ 被加密成了三个密文 $C_1$、$C_2$ 和 $C_3$，并且使用了相同的公钥指数 $e=3$，但是不同的模数 $n_1$、$n_2$ 和 $n_3$，攻击者可以通过中国剩余定理来破解，获取到原始消息 $M$。

解题代码示例：

from sage.all import *
import gmpy2 as gp

n1 = 21180112366275308792707198865461302488559205693127557021721507567406658951027484893183971746874386346549344017657780496423609870191100125206162930591509951158158895313786384410078334087373942711313704671415169591259711219172542673857746853640129378392407801833076846765791915529766486673221298820251490327058865256315102761890119503763324479969189120347374788296228439421010724923476231379022998720352792854596487066187715900286865855673410192615524429078338954151715726776929439932040633058951481065598837709559391701919303564132940137424657515472160189726163543109080323384612138592271850712993603287137677507275371
n2 = 26298692870046419603854209107106438626626364322119633807665057835205077716901148443766353934040185822955892086743845239542911306720672775951179579233523497436530727494678487971265695182505161985229279355999100651830529513900383767281291762278091913698101895553459847468191806086109066122848275034046679346214591398371960794960928446173802863362768056449148080873128801237014636371466461105802242018480278524831090013751334363547633971239825548849102143384730044030187903043701396605393326607857727105149463605439271849673250355049751794904386124840390758363224179076896253944395507179538229841566514339776966378699671
n3 = 12869245342475181303320296924755202819753541797517717539596064095556108493576385999354161121731642352002540447701060344408122911146469189736765677092104255335613300039538354090648284374737637720058242853559989339600163385950025982705089661378793053705329618987830223564779324941385061454586426419929951975212520146873738260085179715217979995535362995225493010874118526395325025302743041973441408932644128476440939321271157322933582064335494518736514896863501417816715050783307592053908471995029904208083874643331646961543050595330178883620466733870718886642963399595471133909399884799882277656325390344541700992326753
c1 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125
c2 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125
c3 = 27986825396866988547862724357202658730691167333564612684951165687800210126707967163602150013745798355893557986277872052045351674932828898392362316022217536592578822801708792807726846802836702174268667149603691471355321662500021629469435803425125

C = crt([c1, c2, c3], [n1, n2, n3])
flag = int(gp.iroot(C, e)[0])
print(long_to_bytes(flag).decode())
# flag{e_quals_3_has_been_abandoned}

Rabin 加密算法 😎

Rabin 加密算法是 RSA 加密算法的一个变种，它使用了平方运算来加密消息。Rabin 加密算法的安全性基于大数分解的困难性，与 RSA 加密算法类似。可以直接将他看作 RSA 加密算法中 $e=2$ 的特殊情况。

Rabin 加密算法 😎

Rabin 解密过程：

加密:

$C \equiv M^2 \mod n$

解密:
计算出模 $p$ 和模 $q$ 下的平方根，得到4个候选值，然后用 CRT 合并这4个候选值，最终还原出正确的明文。

$\begin{cases} m_{p_1} \equiv \sqrt{C} \mod p \\ m_{p_2} \equiv -\sqrt{C} \mod p \\ m_{q_1} \equiv \sqrt{C} \mod q \\ m_{q_2} \equiv -\sqrt{C} \mod q \\ \end{cases}$

扩展欧几里得算法计算出 $q$ 在模 $p$ 下的逆元 $q^{-1}$ 和 $p$ 在模 $q$ 下的逆元 $p^{-1}$，然后用 CRT 合并这4个候选值，得到4个明文候选值：

$\begin{cases} m_1 \equiv m_{p_1} \cdot q \cdot q^{-1} + m_{q_1} \cdot p \cdot p^{-1} \mod n \\ m_2 \equiv m_{p_1} \cdot q \cdot q^{-1} + m_{q_2} \cdot p \cdot p^{-1} \mod n \\ m_3 \equiv m_{p_2} \cdot q \cdot q^{-1} + m_{q_1} \cdot p \cdot p^{-1} \mod n \\ m_4 \equiv m_{p_2} \cdot q \cdot q^{-1} + m_{q_2} \cdot p \cdot p^{-1} \mod n \\ \end{cases}$

然后遍历这4个候选值，尝试解码，成功解码的那个就是正确的明文。

Rabin 加密算法例题

Rabin 加密算法例题下载

from Crypto.Util.number import getPrime, bytes_to_long
from secret import m

p = getPrime(256)
while p % 4 != 3:
    p = getPrime(256)
q = getPrime(256)
while q % 4 != 3 or q == p:
    q = getPrime(256)
n = p * q
e = 2

c = pow(bytes_to_long(m.encode()), e, n)
print("n =", n)
print("c =", c)
# p = 85456561857487541706156138220614376877735385707364349049681146831137409802611
# q = 75122157510403898788703795042660745097752300792713827867823026882894316079263
# c = 1468508928651076555882997390203921809955789362208256690325971247724971060869686807252565486180911155882249

这个例题中，模数 $n$ 是由两个满足 $p \equiv 3 \mod 4$ 和 $q \equiv 3 \mod 4$ 的素数 $p$ 和 $q$ 组成的，攻击者可以通过计算模 $p$ 和模 $q$ 下的平方根来获取到原始消息 $m$。

解题代码示例：

from Crypto.Util.number import long_to_bytes, inverse
mp1 = pow(c, (p + 1) // 4, p)
mp2 = (p - mp1) % p
mq1 = pow(c, (q + 1) // 4, q)
mq2 = (q - mq1) % q

inv_q_mod_p = inverse(q, p)  # q在模p下的逆元
inv_p_mod_q = inverse(p, q)  # p在模q下的逆元

candidates = [
    (mp1 * q * inv_q_mod_p + mq1 * p * inv_p_mod_q) % n,
    (mp1 * q * inv_q_mod_p + mq2 * p * inv_p_mod_q) % n,
    (mp2 * q * inv_q_mod_p + mq1 * p * inv_p_mod_q) % n,
    (mp2 * q * inv_q_mod_p + mq2 * p * inv_p_mod_q) % n,
]

# 遍历候选值，还原出正确的明文
flag = None  # 初始化flag
for idx, candidate in enumerate(candidates):
    try:
        # 尝试解码
        decoded_str = long_to_bytes(candidate).decode()
        # 只有成功解码的才赋值给flag
        flag = decoded_str
        print(flag)
    except (UnicodeDecodeError, ValueError):
        continue
# flag{u_know_the_rabin}

Rabin 算法也可以进一步扩展，不一定要 $e = 2$，我们也可以选择 $e = 4$，甚至更大的偶数 $e$，我们的思路也是一样的，计算出模 $p$ 和模 $q$ 下的 $e$ 次根，然后用 CRT 合并这些根，最终还原出正确的明文。不过难度就变成了怎么计算出模 $p$ 和模 $q$ 下的 $e$ 次根了，这个时候我们就可以使用 Adleman-Manders-Miller 算法来计算出模 $p$ 和模 $q$ 下的 $e$ 次根了。

相关密文攻击 🫠

相关明文意思是我们用同一个模数 $n$ 和同一个公钥指数 $e$ 加密了两个不同的明文 $m_1$ 和 $m_2$，得到两个密文 $c_1$ 和 $c_2$，而且这两个明文之间存在某种关系，比如 $m_2 = m_1 + k$，其中 $k$ 是一个已知的常数。

这个时候攻击者就可以利用这个关系来破解，获取到原始消息 $m_1$ 和 $m_2$。当然这种情况一般用于 $e$ 较小的情况，如果 $e$ 较大，这种攻击就不太适用了。

相关明文攻击例题

相关明文攻击例题下载

from Crypto.Util.number import *
from secret import m

e = 5
n = 0xf2e5339236455e2bc1b1bd12e45b9341a3b223ddb02dec11c880fa4aa8835df9e463e4c446292cd5a2fe19b10017856654b6d6c3f3a94a95807712329f7dae2e1e6506094d5d2f9c8a05c35cbf3366330996db9bff930fe566016d5e850e232057d419292ce30df9c135d56ef1bb72c38838d4b127aa577ceb4aba94d4e0d55
c1 = pow(2*m + 1, e, n)
c2 = pow(3*m + 2 , e, n)
print("c1 =", c1)
print("c2 =", c2)

# c1 = 7641445753073898116827007164793381913392637757517918471003493172096039864745138859395162416166331018059670821487306307100317707328139395788231065689104033478291350670060313374875050515453520864469812221890996287381307066698453475729302664778430397377134780758018837387332598584435841888914421644231089685984
# c2 = 167093247921785025551869982469106575631142864056525551417902883782425700355834225006036652059228820657628419198963259510127624586265812555108445743014018325690532163094506166009746619463293864352220499567472463409933060040516110759121216801644457250422763864380123004793281546395406406223721828567329161640

首先这一题我们可以将已知的信息转换一下，我们有

$2m_1 + 1= 3m_2 + 2 \mod n$

再变换一下

$m_1 = 3 \cdot 2^{-1} \cdot m_2 + 2^{-1} \mod n$

设 $M1 = x$，那么 $M2 = 3 \cdot 2^{-1} \cdot x + 2^{-1}$
如果我们有映射关系 $f(x) = ax + b$,，那么就有 $M_2 = f(M_1)$，因此题面

$\begin{align*} (2m + 1)^e - c_1 &= 0 \mod n \\ (3m + 2)^e - c_2 &= 0 \mod n \end{align*}$

可以变成求解一个方程组：

$\begin{align*} X^e - c_1 = 0 \mod n \ ① \\ f(X)^e - c2=0 \mod n \ ② \end{align*}$

显然对于这两个多项式有一个公共解：$M_1$，因此两条式子都可以化简：

$\begin{align*} (X - M_1) \cdot K_1 = 0 \mod n \\ (X - M_1) \cdot K_2 = 0 \mod n \end{align*}$

$K_i$ 时是多项式方程，由①、②的单调性可知，两式在实数域下仅由唯一解，因此 $K_1$、$K_2$ 两式均不可再因式分解，因此其彼此互素。

从而我们对这两个多项式求一个 $gcd$ 就可以得到 $(X - M_1)$,但由于在模 $n$ 下,得到的将是 $X+M’$的形式（$M’ = -M_1 \mod n$）,所以最终

$M_1 = -M' \mod n$

最后我们就可以通过 $M_1$ 来计算出 $m$ 的值了。最后补充，这种攻击方法也被称为 Franklin-Reiter 攻击。

解题代码示例：

from Crypto.Util.number import *
from sage.all import *

def franklin_reiter(n,e,a,b,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (a*X + b)^e - c2
    m_ = GCD(f1,f2).coefficients()[0] # 返回的是首一多项式，coefficients()返回多项式各项式的系数，项式次数递增，所以第0项是常数
    return Integer(n - m_) # 由于tmp其实是 -m % n,所以这里给他转换回去。

def GCD(a, b):
    if(b == 0):
        return a.monic()# 返回首一多项式，即多项式最高次的项式系数为1
    else:
        return GCD(b, a % b)
e = 5
n = 0xf2e5339236455e2bc1b1bd12e45b9341a3b223ddb02dec11c880fa4aa8835df9e463e4c446292cd5a2fe19b10017856654b6d6c3f3a94a95807712329f7dae2e1e6506094d5d2f9c8a05c35cbf3366330996db9bff930fe566016d5e850e232057d419292ce30df9c135d56ef1bb72c38838d4b127aa577ceb4aba94d4e0d55
b = 1 * pow(2, -1, n)
a = 3 * pow(2, -1, n)
c1 = 7641445753073898116827007164793381913392637757517918471003493172096039864745138859395162416166331018059670821487306307100317707328139395788231065689104033478291350670060313374875050515453520864469812221890996287381307066698453475729302664778430397377134780758018837387332598584435841888914421644231089685984
c2 = 167093247921785025551869982469106575631142864056525551417902883782425700355834225006036652059228820657628419198963259510127624586265812555108445743014018325690532163094506166009746619463293864352220499567472463409933060040516110759121216801644457250422763864380123004793281546395406406223721828567329161640
M1 = franklin_reiter(n,e,a,b,c1,c2)
print("M1 =", M1)
m = (M1 - 1) // 2
print("m =", m)
flag = long_to_bytes(int(m))
print(flag)
# b'flag{u_know_the_franklin_reiter!}'

我们按照这个思路扩展一下，实际上可以不将其中一条式子归一化处理也行，我们直接对两条式子求 $gcd$ 就可以了，得到的结果也是 $X - M_1$ 的形式，最终我们还是可以通过这个结果来计算出 $m$ 的值的。

from Crypto.Util.number import *
from sage.all import *

def franklinReiter(n,e1,e2,c1,c2,noise1,noise2,a,b):
    # 在模n的多项式环上定义变量x
    R.<x> = PolynomialRing(Zmod(n))

    # 构造两个多项式：
    # g1 = (a * x + noise1)^e1 - c1
    # g2 = (b * x + noise2)^e2 - c2
    # 当x = q时，这两个多项式都等于0
    g1 = (a * x + noise1)^e1 - c1
    g2 = (b * x + noise2)^e2 - c2

    def gcd(g1, g2):
        # 计算两个多项式的最大公因式
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 返回首一多项式

    # 最大公因式应该是(x - q)，所以取常数项的相反数就得到q
    return -gcd(g1, g2)[0]

e = 5
n = 0xf2e5339236455e2bc1b1bd12e45b9341a3b223ddb02dec11c880fa4aa8835df9e463e4c446292cd5a2fe19b10017856654b6d6c3f3a94a95807712329f7dae2e1e6506094d5d2f9c8a05c35cbf3366330996db9bff930fe566016d5e850e232057d419292ce30df9c135d56ef1bb72c38838d4b127aa577ceb4aba94d4e0d55
b = 3
noise2 = 2
a = 2
noise1 = 1
c1 = 7641445753073898116827007164793381913392637757517918471003493172096039864745138859395162416166331018059670821487306307100317707328139395788231065689104033478291350670060313374875050515453520864469812221890996287381307066698453475729302664778430397377134780758018837387332598584435841888914421644231089685984
c2 = 167093247921785025551869982469106575631142864056525551417902883782425700355834225006036652059228820657628419198963259510127624586265812555108445743014018325690532163094506166009746619463293864352220499567472463409933060040516110759121216801644457250422763864380123004793281546395406406223721828567329161640
M = franklinReiter(n,e,e,c1,c2,noise1,noise2,a,b)
print("M =", M)
flag = long_to_bytes(int(M))
print("Flag =", flag)
# Flag = b'flag{u_know_the_franklin_reiter!}'

上一章：RSA加解密专题 - 模数相关攻击 👈
下一章：RSA加解密专题 - 私钥 d 相关攻击 👈
回到开始：关于我 👈