指数 e 相关攻击

二项式展开相关加密

类似于这种情形：$c=(n+1{)}^{flag}mod{n}^3$

考题： ASIS 2022 Binned 、2023 年春秋杯春季赛 checkin

题目

from Crypto.Util.number import *
from secret import flag, x, y

def keygen(nbit):
    p, q = [getPrime(nbit) for _ in range(2)]
    return (p, q)

p, q = keygen(1024)
n = p * q

t = len(flag)//2
part1 = bytes_to_long(flag[:t])
part2 = bytes_to_long(flag[t:])

D = 1117
x = 
y = 
assert x**2 - D * y**2 == 1

enc1 = pow(233 * n ** 2 + 1, part1, n ** 3)
enc2 = pow(y * n + 1, part2, n ** 3)

print(f'n = {n}')
print(f'enc1 = {enc1}')
print(f'enc2 = {enc2}')

'''
n = 14381700422128582509148801752355744589949207890477326887251636389639477554903212313766087310581920423926674144511237847467160303159477932732842314969782540035709454603184976310835433114879043016737665256729350745769071186849072915716081380191025215059636548339167264601163525017898164466972776553148697204889820118261937316228241099344357088387154112255824092894798716597134811437852876763391697588672779069166285303075312833415574850549277205130215394422655325352478386576833373623679069271857652029364332047485797407322257853316210866532938722911480593571175419708834718860211036796987231227104370259051299799633809
enc1 = 7213976567554002619445032200800186986758840297933991288547009708561953107405266725278346810536664670987171549114913443730366439254199110599202411546254632702440251000149674899033994570393935743323319736976929843596350656674709510612789987746895513057821629144725499933366382123251520676386059405796801097683107223771674383940907066300331503757142088898427893069444164604408189686282018392714450005250018004986102062209998463347007934222341910941474212611569508001910685822097788669516018081617394144015000387497289693096617795809933540456797387940627782045397249431573540932386564021712811633992948508497879189416719996092292320828635490820907122756459412206735413770335545012892724496210585503157766011075566023635046144730429791359690237088629187946232458937292767085665897489251315749496284368726255508362410603108788759785472319449267909859926786774679533591222665476101832482161295321411313525830843915966136814748249906589458905410141906965538387896747375546846618213595165688661941876715858338407833641907024891922856719044736945863722003318526031957256722493189062624177017279248142024760515092698242159769372410662895078523142768353100643884341413944795392762315999109544070401451087596138520908569234305384182336436670714204963907240715652950621301644972412252424876159530992
enc2 = 15954854445966181136742750543358176358186230663706091821454832527034640100670779737656720251005109942306013877086451482243141488450122353285697850016200364912263403464109626937525725210545566742746628476797261121321515812788726862118315480354196115424526212965145342675007815411995594752584377871686965531829990461770047418586001518916553661158567047779694730702789677326905844275827365395845945286695577426050334364557405151339008293258932006267159313380746863008928500607405457044370494583863960981060999695448408234857505591647503423149271589648863473472196402149897680041851877198062464480400493467334040101779732999029043327947071232256187123316057998759518569161852646625701393295408789279678540894319137126821001853808931387200759810381958895695749251834840804088478214013923869059004663359509316215974475427057000629842098545503905230785431115754636129549758888267877395566717448365986552725726428222769339088308242580851434964429627168365161743834285778996916154182286570122208454025753108647581888781783757375011437394936853319184725324597963035778640646869326035848170752766298225095197226934969602554875402243303906613183431896300664684256018886119255870435413622515792072064528098344111446380223430819596310173312668368618931885819458529703118195242890075359424013033800260927722161030183373647798407301688760998313223874318513944409702828538509864933624724225689414495687466779277994989628367119101
'''

分析：

第一部分 Pell 方程，直接秒，解出 x ，y

x = 87897747594260774254246835664214545379849
y = 2629972211566463612149241455626172190220

第二部分涉及到 $c=(n+1{)}^{flag}mod{n}^3$ 形式的加密：

加密代码：

enc1 = pow(233 * n ** 2 + 1, part1, n ** 3)
enc2 = pow(y * n + 1, part2, n ** 3)

先进行一个多项式公式推导：

$(ax+1{)}^3=a^3{x}^3+3a^2{x}^2+3ax+1$

两边同时模 $x^3$ ，得：$(ax+1{)}^3\equiv (3a^2{x}^2+3ax+1)mod{x}^3$

得：$(ax+1{)}^3\equiv (3a^2{x}^2+3ax+1)+k\ast x^3$

两边同时模 $x^2$，得：$(ax+1{)}^3\equiv (3ax+1)mod{x}^2$

得到计算通式 ：$c=(ax+1{)}^{flag}\equiv (flag\ast ax+1)mod{x}^2$

得：$flag=((cmod{x}^2)-1)//ax$

公式推导：

$c1=(233\ast n^2+1{)}^{part1}mod{n}^3$ ，$c2=(y\ast n+1{)}^{part2}mod{n}^3$

注意 c1 中的是 $n^2$ ，所以 $c1=(233\ast n^2+1{)}^{part1}\equiv (part1\ast 233\ast n^2+1)mod(n^2{)}^2$

$c2=(y\ast n+1{)}^{part2}\equiv (part2\ast y\ast n+1)mod(n^2)$

EXP关键代码：

part1 = (c1 % n**4 -1) // (233 * n ** 2)
part2 = (c2 % n**2 -1) // (y * n)

print(long_to_bytes(part1))
print(long_to_bytes(part2))

flag{11e89e28-4e27-47f0-a7c7-8e66c18881be}

低加密指数攻击

e=3

1、明文过小时，导致明文的三次方仍然小于 n，通过直接对密文开三次方即可得到明文。即：$C\equiv m^{e}modn$,且 $m^e<n$，则：$C=m^e,m=\sqrt[3]{c}$

2、如果明文的三次方比n大，但不是足够大，那么设k有：$C=m^e-k\ast n$ 通过爆破k，对 $C+k\ast n$ 开三次根式，来得到明文m。

#1.
m=iroot(c,3)[0]
print(long_to_bytes(m))

#2.
i=0
while 1:
    if(iroot(c+i*n,3)[1]==1):
        print(iroot(c+i*n,3)[0])
        break
    i=i+1

例题实现：

buuctf：DangerousRSA

n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
e:  0x3
c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

EXP:

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

n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
e = 3

i=0
while 1:
    if(iroot(c+i*n,3)[1]==1): 
        print(long_to_bytes(iroot(c+i*n,3)[0]))
        break
    i=i+1

e=2

直接将密文C开方得到明文m

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

e=2
c=......
m=iroot(c,2)[0]

print(long_to_bytes(m))

e=1

$c=mmodn,m=c+k\ast n,\mathrm{通}\mathrm{过}\mathrm{爆}\mathrm{破}k\mathrm{解}\mathrm{得}m$

from Crypto.Util.number import *

n=....
c=....
e=1

for k in range(10000):
    m = c + n*k
    print(long_to_bytes(m))

中国剩余定理 CRT

给出几组n和c，以及指数e。

$\{\begin{array}{l}{C}_1\equiv m^{e}mod{n}_1\\ C_2\equiv m^{e}mod{n}_2\\ C_3\equiv m^{e}mod{n}_3\end{array}$

变换得：

$\{\begin{array}{l}{m}^e\equiv C_{1}mod{n}_1\\ m^e\equiv C_{2}mod{n}_2\\ m^e\equiv C_{3}mod{n}_3\end{array}$

由中国剩余定理：

$n_1,n_2,n_3$ 两两互素，$M=n_1\ast n_2\ast n_3$ 是正整数 n1,n2,n3 的乘积

$\mathrm{设}{M}_i=\frac{M}{n_i}(i=1,2,3)$

设 $y_i=M_i^{-1}$ 为 $M_i$ 模 $n_i$ 的数论倒数：$y_i\ast M_i\equiv 1(mod{n}_i)(i=1,2,3)$

解得： $m^e=X\equiv C_1{M}_1{y}_1+C_2{M}_2{y}_2+C_3{M}_3{y}_3(modM)$

其中 $(M_i{y}_i\equiv 1mod{n}_i，i=1,2,3)$

在进行开方，即可得到 $m$

题型1

题目：

N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

直接用 CRT 公式解决

EXP:

from gmpy2 import*
from Crypto.Util.number import*
from functools import reduce

N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)
N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)
N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
e=3

n = [N1,N2,N3]
c = [c1,c2,c3]

def CRT(a,n):
    sum = 0
    N = reduce(lambda x,y:x*y,n)

    for n_i, a_i in zip(n,a):
        N_i = N // n_i
        sum += a_i*N_i*invert(N_i,n_i)
    return sum % N 

x = CRT(c,n)
m = iroot(x,e)[0]
print(long_to_bytes(m))

题型2

题目:

from Crypto.Util.number import *
import random

flag=plaintext = 'NSSCTF{****************}'
charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
padding_length = 100 - len(plaintext)

for _ in range(padding_length):
    plaintext += random.choice(charset)

public_exponent = 31413537523
message = bytes_to_long(plaintext.encode())
assert message > (1 << 512)
assert message < (1 << 1024)

prime_p = getPrime(512)
prime_q = getPrime(512)
prime_r = getPrime(512)
n1 = prime_p * prime_q
n2 = prime_q * prime_r
ciphertext1 = pow(message, public_exponent, n1)
ciphertext2 = pow(message, public_exponent, n2)
print('c1=', ciphertext1)
print('c2=', ciphertext2)
print('p=', prime_p)
print('r=', prime_r)


'''
c1= 36918910341116680090654563538246204134840776220077189276689868322808977412566781872132517635399441578464309667998925236488280867210758507758915311644529399878185776345227817559234605958783077866016808605942558810445187434690812992072238407431218047312484354859724174751718700409405142819140636116559320641695
c2= 15601788304485903964195122196382181273808496834343051747331984997977255326224514191280515875796224074672957848566506948553165091090701291545031857563686815297483181025074113978465751897596411324331847008870832527695258040104858667684793196948970048750296571273364559767074262996595282324974180754813257013752
p= 12101696894052331138951718202838643670037274599483776996203693662637821825873973767235442427190607145999472731101517998719984942030184683388441121181962123
r= 10199001137987151966640837133782537428248507382360655526592866939552984259171772190788036403425837649697437126360866173688083643144865107648483668545682383
'''

题目分析：

已知 e、c1、c2、p、r，其中明文 m 大于 512bit ，小于 1024bit ，$m^e$ 的值很大；p、q、r 都是 512bit

$$\begin{gathered} c_1\equiv m^{e}modp\ast q \\ {c}_2\equiv m^{e}modr\ast q \end{gathered}$$

解： 原同余式组可化为

$$\begin{gathered} c_1=m^e+k_1\ast p\ast q \\ {c}_2=m^e+k_2\ast r\ast q \end{gathered}$$

等式两边分别同时模 p 和 r，得到：

$$\begin{gathered} c_1\equiv m^{e}modp \\ {c}_2\equiv m^{e}modr \end{gathered}$$

由中国剩余定理可得：

$$M=p\ast r$$$$M_1=r$$$$M_2=p$$$$\begin{gathered} M_1\ast M_1^{-1}\equiv 1modp \\ {M}_2\ast M_2^{-1}\equiv 1modr \end{gathered}$$

即：

$$\begin{gathered} M_1\ast M_1^{-1}\equiv 1+k_3\ast p \\ {M}_2\ast M_2^{-1}\equiv 1+k_4\ast r \end{gathered}$$

解得：$X=c1\ast M_1\ast M_1^{-1}+c2\ast M_2\ast M_2^{-1}(modp\ast r)$

由一般同余式定理可得：

$$\begin{gathered} X=c_1\ast M_1\ast M_1^{-1}+c_2\ast M_2\ast M_2^{-1}(modp) \\ X=c_1\ast M_1\ast M_1^{-1}+c_2\ast M_2\ast M_2^{-1}(modr) \end{gathered}$$

结合上面的式子，推导得 =>

$$\begin{gathered} X=c_1+c_2\ast p\ast M_2^{-1}(modp) \\ X=c_1\ast r\ast M_1^{-1}+c_2(modr) \end{gathered}$$

=>

$$\begin{gathered} X=c_1(modp) \\ X=c_2(modr) \end{gathered}$$

=>

$$\begin{gathered} X=(m^e+k_1\ast p\ast q)(modp) \\ X=(m^e+k_2\ast r\ast q)(modr) \end{gathered}$$

=>

$$\begin{gathered} X=m^e(modp) \\ X=m^e(modr) \end{gathered}$$

=>

$X\equiv m^{e}mod(p\ast r)$

由RSA算法解得：

$ed\equiv 1mod(q-1)\ast (p-1)$ ，$X^d\equiv m^{ed}mod(p\ast r)$

由欧拉定理得： $X^d\equiv mmod(p\ast r)$

所以 $m=X^{d}mod(p\ast r)$

EXP：

第一种解法，先用中国剩余定理算出一个使用 p*r 为公钥进行加密，得到的 c 值，然后对这个 c 值进行RSA解密即可。

from Crypto.Util.number import *
from gmpy2 import *
from libnum import *

c1= 36918910341116680090654563538246204134840776220077189276689868322808977412566781872132517635399441578464309667998925236488280867210758507758915311644529399878185776345227817559234605958783077866016808605942558810445187434690812992072238407431218047312484354859724174751718700409405142819140636116559320641695
c2= 15601788304485903964195122196382181273808496834343051747331984997977255326224514191280515875796224074672957848566506948553165091090701291545031857563686815297483181025074113978465751897596411324331847008870832527695258040104858667684793196948970048750296571273364559767074262996595282324974180754813257013752
p= 12101696894052331138951718202838643670037274599483776996203693662637821825873973767235442427190607145999472731101517998719984942030184683388441121181962123
r= 10199001137987151966640837133782537428248507382360655526592866939552984259171772190788036403425837649697437126360866173688083643144865107648483668545682383
e = 31413537523

n = [p, r]
c = [c1, c2]
x = solve_crt(c, n)  # 中国剩余定理
# print(x)

d = invert(e, (p - 1) * (r - 1))
m = pow(x, d, p * r)
print(long_to_bytes(m))

e、phi不互素

RSA计算私钥 d，前提条件需要满足 gcd(e , phi) == 1 ，phi = (q-1)*(p-1)，即 e ,phi 互素；如果不互素，则无法计算出私钥d。

当 m^t < N时

首先找出 t == gcd(e,phi) ，找到满足条件的 $e1=e//t$ 使得 $gcd(e1,phi)==1$

$e\ast d=1+k\ast phi$

$(e//t)\ast (d\ast t)=1+k\ast phi$

$e^{\prime }\ast (d\ast t)=1+k\ast phi$

由RSA加密算法知：

$c=m^{e}modn，\Rightarrow m=c^d+K\ast n$

两边同时 t 次方： $m^t=c^{d\ast t}+K\ast n\Rightarrow m^t=c^{d\ast t}modn$

所以 m^t 要小于 n ，否则会在 mod n 运算中丢失数据

例题 ：

def encrypt1(m):
    while 1:
        e = random.randint(100, 1000)
        p = getPrime(1024)
        q = getPrime(1024)
        phi_n = (p - 1) * (q - 1)
        t = gmpy2.gcd(e, phi_n)
        if gmpy2.invert(e // t, phi_n) and t != 1:
            break
    n = p * q
    c = pow(m, e, n)
    print({'c': format(c, 'x'), 'p': format(p, 'x'), 'q': format(q, 'x'), 'e': format(e, 'x')})

# {'c': '27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e', 'p': 'bb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd', 'q': 'bb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1', 'e': '292'}

这里 e 、phi不互素，但 e // t, phi 互素

$c\equiv (m^t{)}^{\frac{e}{t}}modN$，通过计算 $d=invert(e//t,phi)\Rightarrow e1\ast d\equiv 1modphi$

$\mathrm{由}{c}^d\equiv (m^t{)}^{e1\ast d}modN\Rightarrow c^d\equiv (m^t{)}^{1+k\ast phi}modN$

由欧拉定理，若 a 与 m 互质，则：$a^{\phi (m)}\equiv 1modm$

得：$c^d\equiv (m^{t}modN)\ast (m^{k\ast phi}modN)\Rightarrow m^t\equiv c^{d}modN$

且这里 $m^t<N$，所以对 m^t 开 t 次方根即可。

EXP：

c = 0x27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e
p = 0xbb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd
q = 0xbb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1
e = 0x292
t = gcd(e,(q-1)*(p-1))
d = invert(e//t,(q-1)*(p-1))

m = iroot(pow(c,d,p*q),t)[0]
print(long_to_bytes(m))

当 m^t > N时

1、这种情况需要结合中国剩余定理求解，尝试在有限域内开根。

2、当 m^t > N时，对于 $m^t=c^{d\ast t}+K\ast n$ 如果 K 值较小的话也可以尝试爆破 K，类似于低加密指数攻击

m = 2

2^2 % 11 = 2^2

2^2 % 3 = 1

例题

p = 141755878485521250585193526506481835647909733133264484491826506533095411036871187581787386511037412174342774745629361598256663156186634190655768748475210357241858257598757038958971434010720283092093970656262829235604751943313758736375629372244903654343619477366460118493729379823214225182978297539467629343751
q = 105791326767350254361775085198789512601280034667878018736203482690296402930705105880941292311523491531268219920304105707946817881385239201060719345266176935014448981721004118085446297034921832910808404583724823060617037938408978927482413705465188767091927899538738934603096246585672422519596415454996951648933
n = p * q
e = 33
c = 1406397112339697711604857959634535602308393200925612487282395712494883971454736568217895405105641804234918132815025852520686132492440369381524536605289927570796848067004330389550235386191718059158797682686883851836520235452554108372524737561747360657926629011197101279036266730814165126504183746702642346930678406881723781517084042121908048000756941192812817934470545903542277748760076963885109519709405907055218814798421840231218418875714770702389870687977272565851870471136169739851824446107960081481505725577148169000576421732034715421196693795925511463683392371022845041003197960494696500662560942126741476511550

按照常规解法：

phi = (q - 1) * (p - 1)
t = gcd(e, phi)
d = invert(e // t, phi)
m_t = pow(c, d, n)
m = iroot(m_t,t)

我们会发现 m^t < n，并且无法对 m^t 开 t 次方根

m_t > n
Out[5]: False
iroot(m_t,t)[1]
Out[6]: False

这里表明， m^t 实际上是大于 n 的，无法开根是因为进行了模 n 运算,导致得到的 m_t 小于真正的 m^t 值

应该满足 m^t = m^t + K*n

EXP：爆破 k 值

from Crypto.Util.number import long_to_bytes
from gmpy2 import *

p = 141755878485521250585193526506481835647909733133264484491826506533095411036871187581787386511037412174342774745629361598256663156186634190655768748475210357241858257598757038958971434010720283092093970656262829235604751943313758736375629372244903654343619477366460118493729379823214225182978297539467629343751
q = 105791326767350254361775085198789512601280034667878018736203482690296402930705105880941292311523491531268219920304105707946817881385239201060719345266176935014448981721004118085446297034921832910808404583724823060617037938408978927482413705465188767091927899538738934603096246585672422519596415454996951648933
n = p * q
e = 33
c = 1406397112339697711604857959634535602308393200925612487282395712494883971454736568217895405105641804234918132815025852520686132492440369381524536605289927570796848067004330389550235386191718059158797682686883851836520235452554108372524737561747360657926629011197101279036266730814165126504183746702642346930678406881723781517084042121908048000756941192812817934470545903542277748760076963885109519709405907055218814798421840231218418875714770702389870687977272565851870471136169739851824446107960081481505725577148169000576421732034715421196693795925511463683392371022845041003197960494696500662560942126741476511550

phi = (q - 1) * (p - 1)
t = gcd(e, phi)
d = invert(e // t, phi)
m = pow(c, d, n)
for k in range(1,100000):
    if(iroot(m+k*n,t)[1] == 1):
        print(long_to_bytes(iroot(m+k*n,t)[0]))
        break

EXP：使用 有限域开根的方法计算

sagemath 相关学习网站：https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html

利用中国剩余定理使用 CRT_list() 或者crt() 都可以

Zmod(n) ：模运算

f.roots() : 计算多项式的根值

#sage
from Crypto.Util.number import *
import gmpy2
p = 141755878485521250585193526506481835647909733133264484491826506533095411036871187581787386511037412174342774745629361598256663156186634190655768748475210357241858257598757038958971434010720283092093970656262829235604751943313758736375629372244903654343619477366460118493729379823214225182978297539467629343751
q = 105791326767350254361775085198789512601280034667878018736203482690296402930705105880941292311523491531268219920304105707946817881385239201060719345266176935014448981721004118085446297034921832910808404583724823060617037938408978927482413705465188767091927899538738934603096246585672422519596415454996951648933
n = p * q
e = 33
c = 1406397112339697711604857959634535602308393200925612487282395712494883971454736568217895405105641804234918132815025852520686132492440369381524536605289927570796848067004330389550235386191718059158797682686883851836520235452554108372524737561747360657926629011197101279036266730814165126504183746702642346930678406881723781517084042121908048000756941192812817934470545903542277748760076963885109519709405907055218814798421840231218418875714770702389870687977272565851870471136169739851824446107960081481505725577148169000576421732034715421196693795925511463683392371022845041003197960494696500662560942126741476511550

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(q)[]
f = x ^ e - c
f = f.monic()
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt(int(i[0]),int(j[0]),p,q)
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)

[例题] random RSA

题目文件：

from os import urandom
from gmpy2 import next_prime
from random import randint
from functools import reduce
from Crypto.Util.number import bytes_to_long
from secret import flag

assert flag[:4] == b'flag'

def padding(m, length):
    return m + urandom((length >> 3) - len(m))

def generate_p(base):
    return next_prime(base + randint(1, 500000))

def generate_e():
    return reduce(lambda x, y: x * y, [randint(1, 100) for _ in range(randint(2, 5))])

def generate_pubkey():
    base = 1 << randint(128, 256)
    
    n = reduce(lambda x, y: x * y, [generate_p(base) ** randint(1, 5) for _ in range(randint(2, 10))])
    e = generate_e()
    
    return (n, e)

n, e = generate_pubkey()

m = bytes_to_long(padding(flag, n.bit_length()))
assert m < n
c = pow(m, e, n)

with open ("./data.txt","w") as f:
    f.write("n = {}\ne = {}\nc = {}".format(n, e, c))
    f.close()
    
n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
e = 57564
c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702

EXP:

# %%
from tqdm import tqdm
from Crypto.Util.number import *
from gmpy2 import *
from random import randint
from functools import reduce

#%%
# n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
# 
# base_prime = []
# for i in tqdm(range(128, 257)):
#     base = 1 << i
#     while (base <= (1 << i) + 500000):
#         if n % base == 0:
#             base_prime.append(base)
#         base = next_prime(base)
# print(base_prime)

# %%
base_prime = [
    47890485652059026823698344598447161988085597568251161,
    47890485652059026823698344598447161988085597568297951,
    47890485652059026823698344598447161988085597568338059,
    47890485652059026823698344598447161988085597568363667,
    47890485652059026823698344598447161988085597568398337,
    47890485652059026823698344598447161988085597568433917,
    47890485652059026823698344598447161988085597568484111,
    47890485652059026823698344598447161988085597568667099,
    47890485652059026823698344598447161988085597568729849]

n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702
e = 57564

power = []  # 幂数
for i in base_prime:
    x = 0
    N = n
    while N % i == 0:
        N //= i
        x += 1
    power.append(x)
# print(power)
# [5, 4, 3, 4, 3, 5, 1, 2, 3]

NN = 1
N_list = []
for i in range(len(base_prime)):
    NN *= base_prime[i] ** power[i]
    N_list.append(base_prime[i] ** power[i])
assert NN == n
# print('N_list =',N_list)

# 计算欧拉函数值
phi = 1
for j in range(len(base_prime)):
    phi *= (base_prime[j] - 1) * (base_prime[j] ** (power[j] - 1))

g = gcd(e,phi)
# print("g =",g)  # e,phi 不互素


X = []
for p in N_list:
    K = Zmod(p)
    d = invert(e // 108, euler_phi(p))
    m = int(pow(c, d, p))
    x = K(m).nth_root(108, all=True)
    X.append(x)  # 存储所有的可能解

for i in tqdm(X[0]):
    for j in X[1]:
        for k in X[2]:
            for l in X[3]:
                for r in X[4]:
                    for s in X[5]:
                        for t in X[6]:
                            for a in X[7]:
                                for b in X[8]:
                                    c1 = [int(i),int(j),int(k),int(l),int(r),int(s),int(t),int(a),int(b)]
                                    m = crt(c1,N_list)
                                    m = long_to_bytes(m)
                                    if b"flag" in m:
                                        print(m)

flag{U_ar3_The_K1ng_oF_rand0m_kin9Dom!}

AMM 算法(Adleman-Manders-Miller rth root extraction method)

对于 e、phi 不互素问题，当 e | p-1 ，即 e 和 p-1（或 q-1）的最大公因数就是 e 本身时，需要对 c 开 e 次方才能才行。可以将 $c\equiv m^{e}modn$ 化为如下：

$c\equiv m^{e}modp$，$c\equiv m^{e}modq$

然后分别在GF(p)和GF(q)上对c开e次方根，再用CRT组合一下即可得到在mod n下的解。

相关信息

具体讲解参考祥哥的博客：https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#easyrsa909pt-2solvers

实现在有限域内开根，在这里论文中有给出具体的实现算法：Adleman-Manders-Miller Root Extraction Method Revisited

image-20230603193645741

例题：[NCTF 2019]easyRSA

from flag import flag

e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q

assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)

c = pow(m, e, n)
print(c)
# 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

由题目条件可知： gcd(e,p-1) = e ，明显的 e , phi 不互素问题

EXP：

方法一：

• 先用Adleman-Manders-Miller rth Root Extraction Method在GF(p)和GF(q)上对c开e次根，分别得到一个解。大概不到10秒。
• 然后去找到所有的0x1336个primitive nth root of 1，乘以上面那个解，得到所有的0x1337个解。大概1分钟。
• 再用CRT对GF(p)和GF(q)上的两组0x1337个解组合成mod n下的解，可以得到0x1337**2==24196561个mod n的解。最后能通过check的即为flag。大概十几分钟。

# -*- coding:utf8 -*-
from gmpy2 import *
from Crypto.Util.number import *
import random
import math

def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def calc(mp, mq, e, p, q):
    i = 1
    j = 1
    t1 = invert(q, p)
    t2 = invert(p, q)
    for mp1 in mp:
        for mq1 in mq:
            j += 1
            if j % 1000000 == 0:
                print(j)
            ans = (mp1*t1*q+mq1*t2*p) % (p*q)
            if check(ans):
                return
    return


def check(m):
    try:
        a = long_to_bytes(m).decode('utf-8')
        if 'NCTF' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li


if __name__ == '__main__':
    c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
    p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
    q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
    e = 0x1337
    cp = c % p
    cq = c % q

    mp = AMM_rth(cp, e, p)
    mq = AMM_rth(cq, e, q)

    rt1 = ALL_ROOT2(e, p)
    rt2 = ALL_ROOT2(e, q)

    amp = ALL_Solution(mp, p, rt1, cp, e)
    amq = ALL_Solution(mq, q, rt2, cq, e)

    calc(amp, amq, e, p, q)

方法二：直接用 sagemath 求 e 次方根

from sage.all import PolynomialRing
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
n = p*q

P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()
print(mps)
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()
print(mqs)

for i in mps:
    for j in mqs:
        m = crt(int(i[0]),int(j[0]),p,q)
        flag = long_to_bytes(m)
#         if b'flag' in flag:
        print(flag)