RSA加解密专题 - 私钥 d 相关攻击
在RSA加解密算法中，私钥是一个非常重要的参数，它与公钥指数和模数之间存在着密切的关系。如果私钥的选择不当，或者在某些特定情况下，攻击者可能会利用这些关系来破解RSA加密算法，从而获取到原始消息或者分解出模数。
本文将介绍一些与RSA私钥 $d$ 相关的攻击方法，包括常见的攻击手段如维纳攻击、$d_p$ 泄露攻击等。
$d_p$ 泄露攻击 😸
在RSA算法中，私钥 $d$ 可以通过模数 $n$ 和公钥指数 $e$ 来计算得到。然而，如果攻击者能够获取到私钥的某些部分信息，例如 $d_p$（即 $d \mod (p-1)$），就可能会利用这些信息来破解RSA加密算法。
我们可以使用小费马定理：
如果p是一个质数，整数a不是p的倍数，那么 $a^{p-1} \equiv 1 \mod p$
根据 $d_p$ 的定义，我们有 $d \equiv d_p \mod (p-1)$，因此存在一个整数 $k$ 使得 $d = d_p + k(p-1)$。
带入RSA的加密解密公式，我们可以得到：
带入小费马定理得：
令a = 2，显然与p互质
故找到 $2^{e×dp} - 2$ 和 $n$ 的最大公约数即可得到 $p$。
$d_p$ 泄露攻击例题
from Crypto.Util.number import long_to_bytes, bytes_to_long
from secret import m
n = 110258232065996936040119382717057533219407439132082940253584584843182789072223349906230791856973287972123865907521188214279276036006315106449207819895384374593369624196851954653849023080919521562472625060120241327872006503587923172763038424169766164805827768917668909645409183750383690108690297577306064749501
e = 86358776187347673493647406489815610508873901999008033525516761692023880375437
dp = 2026744663215773394057368328828715466612074334163244052273782180970389150112352609040984669970258057823988294286780317419979188752707883050227364941845499
c = pow(bytes_to_long(m.encode()), e, n)
print("c =", c)
#c = 57824787462538624115079284407485175696376125079926154812508611561859936644607308884917900487579845271493649664537572020799918933437291303394878105158410745800945703317112722575982308950734393152733789992168072260114287421251670816067142160465467661371596611685239421550264474850090840444467287904457322154326
在这个例题中，攻击者可以通过获取到 $d_p$ 的值来计算出 $p$，从而进一步分解出模数 $n$，最终获取到原始消息 $m$。
解题代码示例：
from Crypto.Util.number import long_to_bytes, inverse, GCD
n = 110258232065996936040119382717057533219407439132082940253584584843182789072223349906230791856973287972123865907521188214279276036006315106449207819895384374593369624196851954653849023080919521562472625060120241327872006503587923172763038424169766164805827768917668909645409183750383690108690297577306064749501
e = 86358776187347673493647406489815610508873901999008033525516761692023880375437
dp = 2026744663215773394057368328828715466612074334163244052273782180970389150112352609040984669970258057823988294286780317419979188752707883050227364941845499
c = 57824787462538624115079284407485175696376125079926154812508611561859936644607308884917900487579845271493649664537572020799918933437291303394878105158410745800945703317112722575982308950734393152733789992168072260114287421251670816067142160465467661371596611685239421550264474850090840444467287904457322154326
p = GCD(pow(2, e*dp, n) - 2, n)
q = n // p
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'flag{dp_leak_is_very_dangerous}'
$d$ 泄露攻击 😎
如果攻击者同时知道了公钥指数 $e$ 和私钥指数 $d$，并且我们发现模数的大小与 $e \cdot d$ 之间差值符合爆破范围。
我们由密钥关系推导$e × d = 1 + k × \phi(n)$。
确定 $\phi(n)$ 的范围(用n近似)和 $e \cdot d$ 范围进行爆破 $k$。
当然，我们可以使用 $d$ 泄露攻击来分解模数，获取到 $p$ 和 $q$。这种情况一般会出现在系列题目中，分解模数代表完全掌握了RSA的加密解密过程，后续的题目可能会在此基础上进行一些变形或者增加一些限制条件来增加难度。
首先，已知RSA的公钥 $(e, n)$ 和私钥 $d$ 满足以下关系：
所以，存在整数 $k$，使得
又 $ \forall a \in Z_n^*$，满足 $a^{ed - 1} \equiv 1 \mod n$，令
其中，$t$ 为奇数，可以证明至少一半的 $a$ 满足，存在 $i \in [1, s]$，使得
如果 $a,i$ 满足上述条件，则 $gcd(a^{2^{i-1}t} - 1, n)$ 为 $n$ 的非平凡因子。
代码演示：
def factor(e, d, n):
k = e * d - 1
if k % 2 == 1:
return None
r = 0
t = k
while t % 2 == 0:
t //= 2
r += 1
for i in range(100):
g = random.randint(2, n - 1)
y = pow(g, t, n)
if y == 1 or y == n - 1:
continue
for j in range(r):
x = pow(y, 2, n)
if x == 1:
p = GCD(y - 1, n)
q = GCD(y + 1, n)
if p != n and q != n:
return p, q
if x == n - 1:
break
y = x
return None
$d$ 泄露攻击例题
from Crypto.Util.number import *
from secret import m
def nextPrime(n):
n += 2 if n & 1 else 1
while not isPrime(n):
n += 2
return n
p = getPrime(1024)
q = nextPrime(p)
n = p*q
e = 65537
d = inverse(e, (p-1)*(q-1))
c = pow(bytes_to_long(m.encode()), e, n)
print(f"c = {c}")
print(f"d = {d}")
# c = 2351513466711699961275642938145920567717064187415670287856662165691734583511498511849556884324985836944759340430602518816433675154658136461956198063979927374588752761285276022407348897862403266636524918180127033165885832562693771076754684722731688431429937047605808304439473588318383001177577056016593797108647431975635650094036889708447244444614378357243277541322659755051936643582756858815668485878335755801145194320825814381728758757706480457190526292370291648284303227561156220999669622281957677370592060075572209068255726871622636790395044724399719011386821145933178352805650027741623500937510313518945469155302
# d = 19148105720056666554199884501635824534269326983585168429616104055501403262584188036915335459586648180711891951597484047750673362212665198365799020084440783235574443041732573269843811986291526627281503946572630916067824489440197669541850813141337499242644990995736824092775241919506559628875472249640582214556197841501452934104799319015596870245520721236032106961363621543195345434346863657436265360961414326566644881685137687179094740959374192583443543425968907126818396159939075323461512947503693730501859850872858036346011436175151526444655727243816528687577922841002832868639902639633674684653878564522063533978273
在这个例题中，攻击者可以通过已知的 $e$ 和 $d$ 来计算出 $\phi(n)$，从而获取到 $p$ 和 $q$，最终获取到原始消息 $m$。
重点在于通过bit位成功确定爆破范围，成功爆破出 $k$。
解题代码示例：
from Crypto.Util.number import *
import sympy
import gmpy2 as gp
e = 65537
c = 2351513466711699961275642938145920567717064187415670287856662165691734583511498511849556884324985836944759340430602518816433675154658136461956198063979927374588752761285276022407348897862403266636524918180127033165885832562693771076754684722731688431429937047605808304439473588318383001177577056016593797108647431975635650094036889708447244444614378357243277541322659755051936643582756858815668485878335755801145194320825814381728758757706480457190526292370291648284303227561156220999669622281957677370592060075572209068255726871622636790395044724399719011386821145933178352805650027741623500937510313518945469155302
d = 19148105720056666554199884501635824534269326983585168429616104055501403262584188036915335459586648180711891951597484047750673362212665198365799020084440783235574443041732573269843811986291526627281503946572630916067824489440197669541850813141337499242644990995736824092775241919506559628875472249640582214556197841501452934104799319015596870245520721236032106961363621543195345434346863657436265360961414326566644881685137687179094740959374192583443543425968907126818396159939075323461512947503693730501859850872858036346011436175151526444655727243816528687577922841002832868639902639633674684653878564522063533978273
ed = bin(e*d - 1) [2:]
print("ed =", ed) # 位数2064
# 已知n是2048位的数，e*d-1是2048位的数，所以k的位数为16
for k in range(pow(2,15),pow(2,16)):
if (e*d - 1 ) % k == 0:
phi = (e*d - 1) // k
p = sympy.prevprime(gp.iroot(phi,2) [0])
q = sympy.nextprime(p)
if (p - 1) * (q - 1) == phi:
break
n = p * q
m = pow(c, d, n)
print(long_to_bytes(m))
# b'flag{u_can_catch_flag_without_n}'
wiener攻击 👻
当d比较小（$d<\frac{1}{3}N^\frac{1}{4}$）时,可以使用 Wiener 算法来获取私钥 $d$。
通常出题人为了要使得生成的私钥 $d$ 比较小，通常会先生成一个比较小的 $d$，然后再去求 $e$，从而使得 $e$ 的取值范围位于（$1,\phi(n)$）之间，会导致 $e$ 很大，基本上可以和模数 $n$ 大小相似。
从两条关系出发
带入有
两边同时除以 $nd$，得到
式子左边均已知，右边均未知，右边和左边非常接近。
这种情况可以使用连分数来将左边的比值展开，在连分数的展开式中，很大概率存在 $k$ 和 $d$，从而可以求出私钥 $d$，进行解密。
当然，这个算法也不一定是用来求解 $d$，实际上任何满足的近似值都可以用这个算法直接计算出我们要的解。
wiener攻击例题一
from Crypto.Util.number import *
from secret import m
n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
c = pow(bytes_to_long(m.encode()), e, n)
print("c =",c)
# c = 80101582494604437223741383588717025600300047023426616620891241783981638998150472682835072801153995869502522450301302385220129781465036908562359475679205173120186042784572146009306633860957439559980202876647026507563827608212430617525606857990848945461179334863717971248735308788929007826292228060661672434321
在这个例题中，肉眼可见模数 $n$ 和公钥指数 $e$ 大小相似，说明私钥 $d$ 比较小，那么我们就可以使用 Wiener 攻击来求解出私钥 $d$，从而获取到原始消息 $m$。
解题代码示例：
from Crypto.Util.number import *
from sage.all import *
n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
c = 80101582494604437223741383588717025600300047023426616620891241783981638998150472682835072801153995869502522450301302385220129781465036908562359475679205173120186042784572146009306633860957439559980202876647026507563827608212430617525606857990848945461179334863717971248735308788929007826292228060661672434321
e_sage = Integer(e)
n_sage = Integer(n)
cf = continued_fraction(e_sage / n_sage).convergents()
for k_frac in cf[1:]:
d = k_frac.denominator()
k = k_frac.numerator()
if k == 0 or d == 0:
continue
if (e * d - 1) % k != 0:
continue
m = long_to_bytes(pow(c, d, n))
print(m)
# b'flag{the_big_e_is_dangerous}'
wiener攻击例题二
import sympy
from Crypto.Util.number import *
from secret import flag
flag1 = flag[:19].encode()
flag2 = flag[19:].encode()
assert(len(flag) == 38)
P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)
N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2
E1 = getPrime(1024)
E2 = sympy.nextprime(E1)
m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)
c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)
print("N1=",N1)
print("E1=",E1)
print("c1=",c1)
print("N2=",N2)
print("E2=",E2)
print("c2=",c2)
# N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
# E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
# N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
# E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
# c1 = 14073319586163781679481641179662582612304692176580961784953477838609276616064589846809270198729540715245691991740464261550360788284937834670050775858366101085348280669179408813113362405053335009206731776590481373734764383540364750799676070346518475581682516426563732231616057180451762625401173375609189648138854979940971607994443347332491396247789654295359301772332945336628799244150289351676680721435465563648104813778503434793931626482475134001659540217915771568233343281055830752661539150794979736067742502306279761313481724154724055466231123359431082147305556479579346284553457892479595918187550211451065607322614000006859723843438948537608221042231108152696040678683554497540495126798195723931414990643263282854475908809930686235855491686777629698984201000658669936961615186
# c2 = 7741133573061898991718841569604686293847712651459642535825877765243067060193308133385557355381962779171678392611432953529802863894965082406081770549435804237257142410673170863585027671844837301406995739036818126803525925392123724367462856577481458451934142005470762416077608148210778025980305611228050923521365912250581454107545415887539097404367263553527441676600625832138948968108210407415663388184702852913387236486545458819686141479064069733023490788623703473254743320501358595518028968805977839380155887651172992548200623712353654087865742820046863844682793639042663279707824154464544589525016155769813415003482652443230965612123925078843715142264156868627471931778131372410481557419293475673728501696136293542695689649954773759684775991749503582720389352345218448368591510
在这个例题中，我们发现 $P1$ 和 $P2$ 大小接近，$Q1$ 和 $Q2$ 大小接近，那么我们可以认为 $\frac{N1}{N2} = \frac{P1^2 \cdot Q1}{P2^2 \cdot Q2} \approx \frac{Q1}{Q2}$，从而可以通过连分数来求解出 $Q1$ 和 $Q2$，再解出 $P1$ 和 $P2$，最终获取到原始消息 $m$。
解题代码示例：
from sage.all import *
import gmpy2 as gp
from Crypto.Util.number import *
N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
c1 = 14073319586163781679481641179662582612304692176580961784953477838609276616064589846809270198729540715245691991740464261550360788284937834670050775858366101085348280669179408813113362405053335009206731776590481373734764383540364750799676070346518475581682516426563732231616057180451762625401173375609189648138854979940971607994443347332491396247789654295359301772332945336628799244150289351676680721435465563648104813778503434793931626482475134001659540217915771568233343281055830752661539150794979736067742502306279761313481724154724055466231123359431082147305556479579346284553457892479595918187550211451065607322614000006859723843438948537608221042231108152696040678683554497540495126798195723931414990643263282854475908809930686235855491686777629698984201000658669936961615186
c2 = 7741133573061898991718841569604686293847712651459642535825877765243067060193308133385557355381962779171678392611432953529802863894965082406081770549435804237257142410673170863585027671844837301406995739036818126803525925392123724367462856577481458451934142005470762416077608148210778025980305611228050923521365912250581454107545415887539097404367263553527441676600625832138948968108210407415663388184702852913387236486545458819686141479064069733023490788623703473254743320501358595518028968805977839380155887651172992548200623712353654087865742820046863844682793639042663279707824154464544589525016155769813415003482652443230965612123925078843715142264156868627471931778131372410481557419293475673728501696136293542695689649954773759684775991749503582720389352345218448368591510
N1 = Integer(N1)
N2 = Integer(N2)
c1 = Integer(c1)
c2 = Integer(c2)
E1 = Integer(E1)
E2 = Integer(E2)
cf = continued_fraction(N1 / N2).convergents()
for x_frac in cf[1:]:
Q1 = x_frac.numerator()
Q2 = x_frac.denominator()
if N1 % Q1 == 0 and N2 % Q2 == 0:
P1, ok1 = gp.iroot(N1 // Q1,2)
P2, ok2 = gp.iroot(N2 // Q2,2)
if ok1 and ok2:
if P1 * P1 * Q1 == N1 and P2 * P2 * Q2 == N2:
phi1 = (P1 - 1) * (P1) * (Q1 - 1)
phi2 = (P2 - 1) * (P2) * (Q2 - 1)
if (phi1 != 0):
d1 = inverse(E1, phi1)
m1 = pow(c1, d1, N1)
flag1 = long_to_bytes(m1)
if (phi2 != 0):
d2 = inverse(E2, phi2)
m2 = pow(c2, d2, N2)
flag2 = long_to_bytes(m2)
print(flag1 + flag2)
print("Done")
共私钥攻击
设同一个 RSA 加密系统中有 $r$ 个 RSA 加密共用同一个私钥 $d$，这些加密的公钥分别为 $(e_1,N_1), \cdots ,(e_r,N_r)$。设 $N_i, \cdots ,N_r$ 依次增大，并且由于是同一个系统中的加密，故认为 $N_1, \cdots ,N_r$ 具有近似相同的比特长度，于是有 $N_i < N_2 < \cdots < N_r < 2N_1$。
那我们可以得到一串式子：
其中，$N_1 \lt N_2 \lt \cdots \lt N_r \lt 2N_1$。
构造格：
$\mathcal{B}r = \begin{bmatrix}{M}&{e_1}&{e_2}&{\cdots}&{e{r}}\newline
{0}&{-N_1}&{0}&{\cdots}&{0}\newline{0}&{0}&{-N_2}&{\cdots}&{0}\newline{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\newline{0}&{0}&{0}&{\cdots}&{-N_r}\newline\end{bmatrix}$
其中 $M=\lfloor N_r^{\frac{1}{2}} \rfloor$。
则有 $x_r \mathcal{B}_r = v_r$。注意到$\mathcal{B}_r$的行向量组生成了一个 $r+1$ 维的格，而 $v_r$ 是格中的一个向量。
当不等式 $|v_r| < (\det(\mathcal{B}_r))^{1/(r+1)}$ 成立时，攻击者只要解出格 $\mathcal{L}$ 上的 $SVP$ 问题即可解出$v_r$，从而得到$v_r$ 第一个分量 $dM$。$M$ 已知，因此攻击者可求出$d$，从而攻破这些加密。
共私钥攻击例题
from Crypto.Util.number import *
from random import randint
from secret import m
flag = bytes_to_long(m)
d = getPrime(randint(370, 390))
def enc(i):
print()
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = inverse(d, phi)
c = pow(flag, e, n)
print(f'e_{i} =', e)
print(f'n_{i} =', n)
print(f'c_{i} =', c)
if __name__ == '__main__':
for i in range(3):
enc(i)
# e_0 = 65273226782938365337746916273730336693400864987226527768629555154328678878476135267049386675622260483462220524488000354329161815186124642838496578365092125560635683645652071790968480727817124418736448310995681377289580390945033014829116595493634248909648715641159852982292802459935880193569900887152429411847
# n_0 = 68273324976926984651373562317651913900179693126653185371759797219277881642295726703952462364177190633417720186224603741096752660090376579503727572378024303201815180519953050892027877371422177476434135471869132077433509929481856863664414488106874978031117040155569240599125372440850335176938915089228631971431
# c_0 = 16463194277385538006493566728001486227786740657948067325252587295940494532065739047726911635855222798083564798297575745875829939089155104617971353187283800644588271503369243499488369408980732160648403981697621858247469275317713246150930367274375918283239982926149575828206494609703891781265641859935914641074
# e_1 = 53183464145552802360531688680606198853528727337569529128017476892680955108627614437658132384170885260306496461692012374021037184681776910963904643763330840441120876734164247981352314520467566316707955441110480325303720433156607378590168931447833282902975068598066007058786049095275193605661581759764776542387
# n_1 = 90833211551873588270723217667845249495678823850090802136881865517157637454704099665876807553866070458443591809771270518186644833084553243489440868805023263983493252562278743540874001449613551511883028751718014192333516201168480774970739015419610164062537605779410456513031793199999777014894788382706200020757
# c_1 = 22230407808384569931627303117203531383384351503543847426279650122016349747727471353664420880494793722905388983532487901293245030301420692356478218700042566146940345598488036019164944136859836172333034426475299360977773550746037781230355523685359896051245838911971087469266586191931907778679857463565972955053
# e_2 = 79529912185727957854696598539340243519754783720481234589808002665134740533984846798408244547517529674239903959400216641821295959596895413579323465593465830465480139546555530097368569245288033553150779307023833488210096219439360271707710591508276783814809197507754362030663819911878417169437723245134949158879
# n_2 = 129884915453563769925617783280424054377155108084275359132533095588688005688782127459458645185506079867020438362987468403256647102770553654162232890781552673147712836927912298560902655711987881754839768794787168125599139190546712270501013360266296615603202216855466243614243328596099717542864006193566337698107
# c_2 = 45046520188230821139461613627667404949754182395531112466748475103653526026321780076835632789482008756547877684013753034233663379312517859344427404926219930531928639530079463417386563408726593602509407278834104957286532673590748489716544044445125128760577108367123150435970486466443524388142767285555053802498
这个题目中，攻击者可以通过已知的 $e_i$ 和 $N_i$ 来构造格 $\mathcal{B}_r$，然后直接使用 LLL 算法来求解出格 $\mathcal{L}$ 上的 $SVP$ 问题，从而得到$v_r$，最终获取到原始消息 $m$。
解题代码示例：
from Crypto.Util.number import *
from sage.all import *
e_0 = 65273226782938365337746916273730336693400864987226527768629555154328678878476135267049386675622260483462220524488000354329161815186124642838496578365092125560635683645652071790968480727817124418736448310995681377289580390945033014829116595493634248909648715641159852982292802459935880193569900887152429411847
n_0 = 68273324976926984651373562317651913900179693126653185371759797219277881642295726703952462364177190633417720186224603741096752660090376579503727572378024303201815180519953050892027877371422177476434135471869132077433509929481856863664414488106874978031117040155569240599125372440850335176938915089228631971431
c_0 = 16463194277385538006493566728001486227786740657948067325252587295940494532065739047726911635855222798083564798297575745875829939089155104617971353187283800644588271503369243499488369408980732160648403981697621858247469275317713246150930367274375918283239982926149575828206494609703891781265641859935914641074
e_1 = 53183464145552802360531688680606198853528727337569529128017476892680955108627614437658132384170885260306496461692012374021037184681776910963904643763330840441120876734164247981352314520467566316707955441110480325303720433156607378590168931447833282902975068598066007058786049095275193605661581759764776542387
n_1 = 90833211551873588270723217667845249495678823850090802136881865517157637454704099665876807553866070458443591809771270518186644833084553243489440868805023263983493252562278743540874001449613551511883028751718014192333516201168480774970739015419610164062537605779410456513031793199999777014894788382706200020757
c_1 = 22230407808384569931627303117203531383384351503543847426279650122016349747727471353664420880494793722905388983532487901293245030301420692356478218700042566146940345598488036019164944136859836172333034426475299360977773550746037781230355523685359896051245838911971087469266586191931907778679857463565972955053
e_2 = 79529912185727957854696598539340243519754783720481234589808002665134740533984846798408244547517529674239903959400216641821295959596895413579323465593465830465480139546555530097368569245288033553150779307023833488210096219439360271707710591508276783814809197507754362030663819911878417169437723245134949158879
n_2 = 129884915453563769925617783280424054377155108084275359132533095588688005688782127459458645185506079867020438362987468403256647102770553654162232890781552673147712836927912298560902655711987881754839768794787168125599139190546712270501013360266296615603202216855466243614243328596099717542864006193566337698107
c_2 = 45046520188230821139461613627667404949754182395531112466748475103653526026321780076835632789482008756547877684013753034233663379312517859344427404926219930531928639530079463417386563408726593602509407278834104957286532673590748489716544044445125128760577108367123150435970486466443524388142767285555053802498
M = floor(isqrt(n_2))
Mat = Matrix(ZZ,[
[M,e_0,e_1,e_2],
[0,-n_0,0,0],
[0,0,-n_1,0],
[0,0,0,-n_2]
])
Mat_LLL=Mat.LLL()
d = int(abs(Mat_LLL[0][0])/M)
m = pow(c_0, d, n_0)
print(long_to_bytes(m))
# b'flag{u_gain_deep_insights_into_LLL!!!}'
上一章：RSA加解密专题 - 公钥指数相关攻击 👈
下一章：RSA加解密专题 - 公私钥格式相关攻击 👈
回到开始：关于我 👈
相关链接：
密码学数学基础 - 二次剩余 👈
密码学算法 - Wiener算法 👈
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Alice and Bobの神秘小屋！
相关推荐
2026-03-04
RSA加解密专题 - Coppersmith 相关攻击一
Coppersmith 攻击是一种针对 RSA 加密算法的攻击方法，主要用于在特定条件下恢复 RSA 私钥或解密 RSA 密文。该攻击方法由 Don Coppersmith 在 1996 年提出，利用了 RSA 加密算法中的数学结构和性质。 这里我们并不会深入到 Coppersmith 攻击的数学细节，但我们会介绍一些相关的攻击场景和原理，以帮助你理解 Coppersmith 攻击的基本思想和应用。 部分明文泄露攻击 😋单一变量的情况下，我们主要关注构建一个多项式方程，并使用 Coppersmith 方法来寻找小根。这种方法可以在某些特定条件下成功，例如当明文的某些部分已知或满足特定的数学关系时。 最简单的情况莫过于明文的某些部分已知，不管是哪一种泄露直接套用加密的方程就好： \begin{align*} (m_h + x)^e &\equiv c \pmod{n} \\ (m_h + x \ll m_l.\text{nbits}() + m_l)^e &\equiv c \pmod{n} \\ (x \ll m_l.\text{nbits}() + m_l)^e &\equi...
2026-03-02
RSA加解密专题 - 模数相关攻击
当你在 CTF 赛场遇到 RSA 题型时，模数相关的攻击手法⚔️往往是破解的关键。无论是共模攻击、模重复攻击，还是模数分解的相关漏洞，这些都是 RSA 加解密中常见且高频出现的题型。掌握这些攻击手法，不仅能让你在 CTF 赛场上如鱼得水，还能加深你对 RSA 加解密原理的理解。 暴力分解模数 🥳在 $N$ 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 $p$ 和 $q$。一般来说，使用一些高效的分解工具（如 YAFU、msieve、CADO-NFS 等）可以在合理的时间内完成分解，获取 $p$ 和 $q$。 暴力分解模数例题暴力分解模数例题下载 from Crypto.Util.number import * from secret import M p = getPrime(56) q = getPrime(56) e = 65537 n = p * q long_M = long_to_bytes(M.encode()) C = pow(long_M, e, n) print(C) print(n) #n: 3211733906383171840011...
2026-03-03
RSA加解密专题 - 公私钥格式相关攻击
pem 格式的文件通常用于数字证书认证机构(Certificate Authorities，CA)，其文件形式主要为 base64 编码的文件，头尾有类似于——-BEGIN PUBLIC KEY——-和——-END PUBLIC KEY——-的头尾标记 本文的目的就是如何从 .pem 格式的证书中，获取公钥、私钥信息。在 RSA 加密中，实际上公钥和私钥都是由一系列数字组成的，这些数字在.pem格式的证书中以特定的格式存储。通过解析这些数字，我们可以获取到公钥和私钥的相关信息，从而进行加密和解密操作。 PEM文件生成与使用 🥳在python中，可以通过 from Crypto.PublicKey import RSA 生成想要的公私钥文件。 生成公钥文件的代码如下： from Crypto.PublicKey import RSA from Crypto.Util.number import * p,q = getPrime(512),getPrime(512) n = p * q e = 0x10001 pub = RSA.construct((n,e)) with open...
2026-03-02
RSA加解密专题 - 公钥指数相关攻击
在实际应用中，攻击者可能会利用一些特定的攻击方法来破解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=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819...
2026-03-01
RSA加解密专题 - 前言
当你在 CTF 赛场拆解 RSA 密文🧩、爆破私钥参数🔑、或是还原模分解的隐藏信息📝时，那些看似毫无头绪的密文串、复杂的数论参数，背后其实是 RSA 加解密的核心逻辑在层层嵌套⚙️。 欢迎来到《RSA 加解密专题》的 CTF 攻坚工坊！这里没有晦涩的理论空谈（真的不绕弯😜），只有一把把破解 RSA 题型的实战密钥🗝️。 在 CTF 密码学的赛场上，RSA 绝对是出场率拉满的 “常驻嘉宾”🥇，而数论基础是拆解它的利刃🔪，模运算、大素数分解是攻破它的关键招式，加解密的核心逻辑则是破解各类变种题型的底层密码。本系列专题将带你深耕 RSA 加解密的全维度知识，从最基础的 RSA 原理、密钥生成与加解密流程，到 CTF 中高频出现的低加密指数、模重复、私钥泄露、共模攻击等经典题型，再到进阶的多素数 RSA、盲签名、CRT 加速破解等复杂场景，我们会一步步揭开 RSA 在 CTF 题型中的出题套路与破解技巧🎭。 别担心，我会用 CTF 实战视角（🔍➡️💻），让你发现这些看似复杂的 RSA 题型，其实都是核心原理的变形与拓展。它们不仅考验着数论与模运算的基础功底，更需要灵活...
2026-03-10
RSA加解密专题 - Coppersmith 相关攻击二
上一章我们介绍了 Coppersmith 相关攻击的基本原理和实现方法，帮助大家了解了如何利用 Coppersmith 方法来攻击 RSA 加密算法。接下来，我们将继续深入探讨 Coppersmith 相关攻击的应用。 欢迎来到《密码学核心算法实战》的 Coppersmith 相关攻击二专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 $d_q$ 的低位泄露攻击 🙃这种情况多见于破损pem文件，或者某些特定的实现中，攻击者可能会获得 $d_q$ 的部分低位信息。我们可以利用这些泄露的低位信息来恢复完整的 $d_q$，进而推导出私钥。 和前一篇文章中的私钥低位泄露一样，我们认识到低位，可以理解成原来的方程在取模时的值，然后我们就可以求解另外的参数的低位，最后通过 Coppersmith 方法求解高位。 $d_q$ 的低位泄露攻击例题$d_q$ 的低位泄露攻击例题下载 ''' 破损私钥以及密文 -----BEGIN RSA PRIVATE KEY----- MIICXgIBAAKBgQDXFSUGqpzsBe...
评论
