Crypto入门-RSA

基础概念

公钥与私钥

  1. 随机选择两个不同的大质数$p$和$q$，计算$N=pq$。

  2. 求得$\varphi(N)=\varphi(p)\varphi(q)=(p-1)(q-1)$。

  3. 选择一个$e(e<\varphi(N),e\bot\varphi(N))$，并求得$e$的逆元$d$：$ed\equiv1\pmod{\varphi(N)}$。

  4. 销毁$p,q$的记录，公钥为$(N,e)$，私钥为$(N,d)$。

消息加密：

将消息转化为$m(m<N,m\bot N,m\in\mathbb Z)$，如果消息太长可以分成几段，即块加密。利用以下公式加密：$m^e\equiv c\pmod N$。

消息解密：

利用密钥$d$解密：$c^d\equiv \pmod N$。

共模攻击

攻击条件：两个用户使用相同模数$N$、不同私钥加密同一明文消息时。

设两个用户公钥分别为$e_1$和$e_2$，且$e_1\bot e_2$，明文为$m$，密文分别为：

$$
\begin{cases}
\displaylines{
c_1=m^{e_1}\bmod N\\
c_2=m^{e_2}\bmod N
}
\end{cases}
$$

由$c1,c2$可恢复明文，用扩展欧几里德算法求出$re_1+se_2\equiv1\pmod N$的两个整数$r,s$，可得：

$$
\begin{align*}
\displaylines{
c_1^rc_2^s &\equiv m^{re_1}m^{se_2}\bmod N\\
&\equiv m^{re_1+se_2}\bmod N\\
&\equiv m\bmod N
}
\end{align*}
$$

$c_1^rc_2^s$即为所求明文$m$。

当$e_1\not\bot e_2$时，导致$re_1+se_2\equiv1\pmod N$，即$c_1^rc_2^s\equiv m^{\gcd(e_1,e_2)}\pmod N$，最后对$\gcd(e_1,e_2)$开方即可。

共享素数

模不互素原理：当存在两个公钥$N_1\not\bot N_2$时，可求$\gcd(N_1,N_2)$，然后直接获得$p,q$。

攻击条件：进行了两次RSA加密，已知公钥$(N_1,e),(N_2,e)$和密文$c$。

题目如下：

1
2
3
4
# n1 n2 e m 已知
c=pow(m,e,n1)
c=pow(c,e,n2)
# 泄漏c

攻击脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2
#n1 n2 e c已知
q=gmpy2.gcd(n1,n2)
p1=n1//q
p2=n2//q
phi1=(p1-1)*(q-1)
phi2=(p2-1)*(q-1)
d1=inverse(e,phi1)
d2=inverse(e,phi2)
m=pow(c,d2,n2)
m=pow(m,d1,n1)
print(long_to_bytes(m))

低加密质数广播攻击

攻击条件：使用同一个加密指数$e$加密同一个明文$m$，并发送给了其他$e$个用户。

假设$n_i(1\leqslant i\leqslant e)$不互素，否则可直接分解。同时假设$m<n_i(1\leqslant i\leqslant e)$，否则情况复杂。密文如下：

$$
\begin{cases}
\displaylines{
c_1\equiv m^e\pmod{n_1}\\
c_2\equiv m^e\pmod{n_2}\\
\ \ \ \ \ \vdots\\
c_e\equiv m^e\pmod{n_e}
}
\end{cases}
$$

利用中国剩余定理求解$m^e$再开方即可。

$p-q$过小

攻击条件：当$p,q$相近时，直接开方找数。

题目如下：

1
2
p=getPrime(512)
q=next_prime(p)

攻击脚本：

1
2
p=gmpy2.next_prime(gmpy2.isqrt(n))
q=n//p

低加密指数小明文攻击

攻击条件：$e$特别小。

考虑到$c\equiv m^e\pmod N$，化为一般方程为$m^e=c+kN,k\in\mathbb N$，即可得$m=\sqrt[e]{c+kN}$。直接爆破$k$和$e$即可。

Wiener攻击

攻击条件：当$d<\dfrac{1}{3}N^{\frac{1}{4}}$时，即$e$过大或过小时。

通过$ed\equiv1\pmod{\varphi(N)}$得到$ed=k\varphi(N)+1$，即$\dfrac{e}{\varphi(N)}=\dfrac{k}{d}+\dfrac{1}{\varphi(N)}$。此时$\varphi(N)\approx N$且$\varphi(N)$非常大，所以对$\dfrac{e}{N}$进行连分数展开，得到的一串分数的分母可能就是$d$。

攻击脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def transform (x,y):
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:
        denominator,numerator=numerator,i*numberator+denominator
    return denominator,numerator
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,res[0:i] for i in range(1,len(res))
    return res
def get_pq(a,b,c): #用p+q和pq通过韦达定理求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2
def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):
        if k==0: #可能第一个连分数为0 排除
            continue
        if (e*d-1)%k!=0: #如果找到了d
            continue
        phi=(e*d-1)//k
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))
            d=gmpy2.invert(e,(p-1)*(q-1))
            return d
    print("该方法不适用")
c=
n=
e=
d=wienerAttack(e,n)
m=pow(c,d,n)

$d$高位泄漏

sage太大了，最新版还要编译，不如在线：https://sagecell.sagemath.org/。

1
2
3
4
#sage
PR.<x>=PolynomialRing(Zmod(n)) #生成以x为符号的一元多项式环
f=x+p #要求解的函数
roots=f.small_roots(X=2^kbits,beta=0x4) #多项式小值根求解+因式分解 X为根的上界

CopperSmith定理：对于任意$a>0$，给定$N=pqr$的高位$\displaystyle\frac{\log_N2}{5}\mathrm{bits}$，可以在多项式时间$O(\log N)$内得到$N$的分解式。

威尔逊定理

$$
\forall p,(p-1)!\equiv-1\pmod p
$$

$d_p$泄漏

攻击条件：设$d_p=d\bmod(p-1)$，泄漏$d_p$时。

推导过程：

$$
\begin{align*}
\displaylines{
c\equiv&m^e\pmod n\\
m\equiv&c^d\pmod n\\
d_p=&d\bmod(p-1)\\
d_pe\equiv&de\pmod{p-1}\\
d=&k_1(p-1)+d_pe,k_1\in\mathbb Z\\
de\equiv&1\pmod{\varphi(n)}\\
de\equiv&1\pmod{(p-1)(q-1)}\\
de\equiv&k_2(p-1)(q-1)+1\\
x=&k_2(q-1)-k_1\\
d_pe=&(p-1)x+1\\
x=\dfrac{d_pe}{p-1}-\dfrac{1}{p-1}
}
\end{align*}
$$

又因$d_p<p-1$，可得$1<x<e$。直接暴力枚举$x$。

$p-1$光滑

攻击条件：$p-1$光滑，即为可以分解为小素数乘积的正整数。

根据Pollard’s p-1算法，当$p$光滑时存在$\displaystyle M=\prod_{q\leqslant B}q^{\lfloor\log_q B\rfloor}$，使得$(p-1)\mid M$成立，则有当$\gcd\left(a^M-1,N\right)$不为$1$或$N$，就已成功分解$N$。

因为只关心$\gcd$的结果，且$N$只包含俩素因子，我们不需要计算$M$，令$M=n!$即可覆盖正确的$M$同时方便计算。

做题

[SWPUCTF 2021 新生赛]ez_rsa

1
2
3
4
5
6
7
import gmpy2,hashlib
p=1325465431
q=152317153
e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(hashlib.md5(str(d).encode()).hexdigest())

[SWPUCTF 2021 新生赛]crypto2

共模攻击。

1
2
3
4
5
6
7
8
9
10
import gmpy2
from Crypto.Util.number import *
c1=100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2=86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1=3247473589
e2=3698409173
n=103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313
g,r,s=gmpy2.gcdext(e1,e2)
m=pow(c1,r,n)*pow(c2,s,n)%n
print(long_to_bytes(m))

[羊城杯 2021]Bigrsa

共享素数攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2
n1=103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2=115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e=65537
c=60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
q=gmpy2.gcd(n1,n2)
p1=n1//q
p2=n2//q
phi1=(p1-1)*(q-1)
phi2=(p2-1)*(q-1)
d1=inverse(e,phi1)
d2=inverse(e,phi2)
m=pow(c,d2,n2)
m=pow(m,d1,n1)
print(long_to_bytes(m))

[SWPU 2020]happy

z3约束求解$p,q$，得$N,\varphi(N)$，进而得$d,m$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import z3,gmpy2
c=0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e
e=0x872a335
s=z3.Solver()
p,q=z3.Ints('p q')
s.add(q+q*p**3==1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586)
s.add(q*p+q*p**2==1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594)
s.check()
ans=s.model()
p1=ans[p].as_long()
q1=ans[q].as_long()
n=p1*q1
phi=(p1-1)*(q1-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[鹤城杯 2021]Crazy_Rsa_Tech

低加密指数广播攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
import gmpy2
e=9
n_list=[71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799,92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949,100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919,59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847,66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147,120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377,72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281,69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951,76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585,46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900,85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198,14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656,1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839,2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981,16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376,31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996,25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
#CRT
N=1
summary=0
M_list=[]
t_list=[]
for n in n_list:
    N*=n
for n in n_list:
    M_list.append(N//n)
for i in range(len(n_list)):
    t_list.append(inverse(M_list[i],n_list[i]))
for i in range(len(n_list)):
    summary=(summary+c_list[i]*t_list[i]*M_list[i]%N)%N

m=gmpy2.iroot(summary,e)[0]
print(long_to_bytes(m))

[AFCTF 2018]你能看出这是什么加密么

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2
p=0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f
q=0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061
e=0x10001
c=0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6
phi=(p-1)*(q-1)
n=p*q
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[LitCTF 2023]家人们！谁懂啊，RSA签到都不会 (初级)

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
p=12567387145159119014524309071236701639759988903138784984758783651292440613056150667165602473478042486784826835732833001151645545259394365039352263846276073
q=12716692565364681652614824033831497167911028027478195947187437474380470205859949692107216740030921664273595734808349540612759651241456765149114895216695451
c=108691165922055382844520116328228845767222921196922506468663428855093343772017986225285637996980678749662049989519029385165514816621011058462841314243727826941569954125384522233795629521155389745713798246071907492365062512521474965012924607857440577856404307124237116387085337087671914959900909379028727767057
e=65537
phi=(p-1)*(q-1)
n=p*q
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[SWPUCTF 2021 新生赛]crypto4

$p-q$过小。

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2
c=10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
n=52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153
e=0x10001
p=gmpy2.next_prime(gmpy2.isqrt(n))
q=n//p
phi=(p-1)*(q-1)
n=p*q
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[SWPUCTF 2021 新生赛]crypto5

低加密指数小明文攻击。

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2
flag=25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n=134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419
for e in range(2,2**16):
    for k in range(0,10):
        c=flag+k*n
        m=gmpy2.iroot(c,e)
        if m[1]==1:
            print(long_to_bytes(m[0]))
            exit()

[BJDCTF 2020]rsa

对$e$进行爆破，而$q=\gcd(N_1,N_2)$，即可解出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2
c1=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
t=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c2=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  
n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
for e_enum in range(2,100000):
    if pow(294,e_enum,n1)==t:
        e=e_enum
        break
q=gmpy2.gcd(n1,n2)
p=n1//q
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c1,d,n1)
print(long_to_bytes(m))

[SWPUCTF 2021 新生赛]crypto1

共模攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2,sympy
c1=463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
c2=130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n=609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1e2=3087
divisor=[i for i in sympy.divisors(e1e2)]
for e1 in divisor:
    e2=e1e2//e1
    d,r,s=gmpy2.gcdext(e1,e2)
    if d==1:
        m=pow(c1,r,n)*pow(c2,s,n)%n
    else:
        m=gmpy2.iroot(pow(c1,r,n)*pow(c2,s,n)%n,d)[0]
    flag=long_to_bytes(m)
    if flag[:6]=="NSSCTF".encode():
        print(flag)

[BJDCTF 2020]EasyRSA

高等数学符号运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from sympy import *
import gmpy2
c=7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z=32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n=15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e=65537
p,q=symbols('p q')
const1=(1/diff(atan(p),p))-(1/diff(atanh(q),q))-z
const2=p*q-n
solutions=solve((const1,const2),(p,q))
for solution in solutions:
    p1=gmpy2.mpz(solution[0])
    q1=gmpy2.mpz(solution[1])
    phi=(p1-1)*(q1-1)
    d=inverse(e,phi)
    m=pow(c,d,n)
    print(long_to_bytes(m))

[HDCTF 2023]Normal_Rsa

共模攻击。

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
import gmpy2
n=21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1=2767
e2=3659
c1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
d,r,s=gmpy2.gcdext(e1,e2)
m=pow(c1,r,n)*pow(c2,s,n)%n
print(long_to_bytes(m))

[HDCTF 2023]Normal_Rsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2
P=6773247693445539441213578786581644136043035242620265251725630106817272212428325283262417364786451280269516220237289567904055371962564710888510272312707201
Q=44943699913039047357456835559925378512493523252980366265686899925123157887149890185055864945749408514100461655676474535153113631214288057465776668291975220848776401405531599573114898492452990847774628035552581539370236080368457643523158920565504112005843410442573511095306233906498204203659537135943420051121
n=4785613888465991171479248142015453309149548888755453367991501772592797686075465426815591528773123474962122102667475893532087343900904799831474817826058951265607078893487357878501280782935653048309499430170214015422492927323961394806106719569168457890040223027119115392961801582406287167644266319898276785787730947633037300317098453409851410936140488150390919951503767522517809035474567
c=2247027561636791381460194811205520085150851211795956750955965051548230844233212462525163107917067768507367576366327035846089534916090521357212722275045521111077106695721780943857231570836500588468487620819893688830570842176795906808347617421353983094639290979158413935035603633331786978227439155042365130799647385116773171906670409535157184391352888875130028955334874727206292146950544
q=6704006258427795304220450411280948926213189680360135534636452074716135019217911134480777251273836898349926894302122011679095979445240343891749741039976761
e=65537
p=gmpy2.isqrt(P)
r=n//p//q
phi=(p-1)*(r-1)
d=inverse(e,phi)
m=pow(c,d,r*p)
print(long_to_bytes(m))

[闽盾杯 2021]decode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
import gmpy2
n1=15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2=28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3=18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1=65537
e2=27751
e3=65537
c1=5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2=21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3=13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486
p1=p2=gmpy2.gcd(n1,n2)
q1=n1//p1
q2=p3=n2//p2
q3=n3//p3
phi1=(p1-1)*(q1-1)
phi2=(p2-1)*(q2-1)
phi3=(p3-1)*(q3-1)
d1=inverse(e1,phi1)
d2=inverse(e2,phi2)
d3=inverse(e3,phi3)
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
m3=pow(c3,d3,n3)
print(long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3))

[HGAME 2022 week3]RSA attack 3

Wiener攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import ContinuedFractions,Arithmetic,RSAvulnerableKeyGenerator,gmpy2
from Crypto.Util.number import *
n=507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e=77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c=165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
def wienerAttack(e,n):
    frac=ContinuedFractions.rational_to_contfrac(e,n)
    convergents=ContinuedFractions.convergents_from_contfrac(frac)
    for (k,d) in convergents:
        if k!=0 and (e*d-1)%k==0:
            phi=(e*d-1)//k
            b=n-phi+1
            delta=b*b-4*n
            if delta>=0:
                delta2=Arithmetic.is_perfect_square(delta)
                if delta2!=-1 and (b+delta2)%2==0: #即韦达定理能够正除2a
                    return d
d=wienerAttack(e,n)
m=pow(c,d,n)
print(long_to_bytes(m))

[CISCN 2022 西南]rsa

这里模数直接使用的是$\lambda(N)=\operatorname{lcm}{(p-1,q-1)}=\dfrac{\varphi(N)}{\gcd(p-1,q-1)}$，其实这个跟$\varphi(N)$差不多…

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
lcm=4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c=4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N=17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
e=65537
d=inverse(e,lcm)
m=pow(c,d,N)
print(long_to_bytes(m))

[CISCN 2021初赛]rsa

重点在$d$高位泄漏。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import *
import gmpy2,hashlib
flag=b''

#Part1 低加密指数小明文攻击
e1=3
n1=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
c1=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
k=0
while True:
    m1=gmpy2.iroot(c1+k*n1,e1)
    if m1[1]==True: #能正好开方
        break
    k+=1
flag+=long_to_bytes(m1[0])

#Part2 共模攻击
e2_1=17
e2_2=65537
n2=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
c2_1=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c2_2=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
g,r,s=gmpy2.gcdext(e2_1,e2_2)
m2=pow(c2_1,r,n2)*pow(c2_2,s,n2)%n2
flag+=long_to_bytes(m2)

#Part3 d高位泄漏
#sage begin
p3_HIGH=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p3_bits=512
kbits=p3_bits-p3_HIGH.nbits()
p3_HIGH=p3_HIGH<<kbits
PR.<x>=PolynomialRing(Zmod(n3))
f=x+p3_HIGH
x0=f.small_roots(X=2^kbits,beta=0.4)[0]
p=p3_HIGH+x0
print(str(hex(int(p))))
# 0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7
#sage end
e3=65537
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
c3=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
p3=int('0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7',16)
q3=n3//p3
phi3=(p3-1)*(q3-1)
d3=inverse(e3,phi3)
m3=pow(c3,d3,n3)
flag+=long_to_bytes(m3)

print(hashlib.md5(flag).hexdigest())

[GWCTF 2019]babyRSA

推导如下：
$$
\begin{align*}
\displaylines{
m_2=&F_1^3+F_2^3\\
=&(F_1+F_2)\left(F_1^2-F_1F_2+F_2^2\right)\\
=&m_1(F_1^2-F_1F_2+F_2^2)\\
=&m_1\left((F_1+F_2)^2-3F_1F_2\right)\\
=&m_1\left(m_1^2-3F_1F_2\right)
}
\end{align}
$$
以及：
$$
\begin{align*}
\displaylines{
&F_1F_2=\dfrac{m_1^2-\dfrac{m_2}{m_1}}{3}\\
\Rightarrow&F_1^2-m_1F_1+\dfrac{\left(m_1^2-\dfrac{m_2}{m_1}\right)}{3}=0\\
\Rightarrow&3m_1F_1^2-3m_1^2F_1+m_1^3-m_2=0
}
\end{align*}
$$

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import sympy,sympy.abc
n=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
c1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
c2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
e=0x10001
factors=sympy.factorint(n)
prime_factors=[factor for factor in factors if sympy.isprime(factor)]
p=prime_factors[0]
q=prime_factors[1]
m1=pow(c1,inverse(e,(p-1)*(q-1)),n)
m2=pow(c2,inverse(e,(p-1)*(q-1)),n)
res=sympy.solve([3*m1*pow(sympy.abc.x,2)-3*pow(m1,2)*sympy.abc.x+pow(m1,3)-m2],[sympy.abc.x])
for i in range(len(res)):
    print(long_to_bytes(res[i][0])+long_to_bytes(m1-res[i][0]))

[LitCTF 2023]yafu (中级)

这道题分解质因数应该拿yafu搞，但是yafu的linux版本实在太难编译了，就采用笨办法：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import sympy
n=15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c=12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
e=65537
factors=sympy.factorint(n)
res=[factor for factor in factors if sympy.isprime(factor)]
phi=1
for i in range(len(factors)):
    phi*=res[i]-1
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[RoarCTF 2019]babyRSA

推导过程：

$$
\begin{align*}
\displaylines{
(A-1)!\equiv&-1\pmod A\\
(A-1)(A-2)\cdots(B!)\equiv&-1\pmod A\\
(A-2)\cdots(B!)\equiv&1\pmod A
}
\end{align*}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
import gmpy2
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
def slv(a,b):
    tmp=1
    for i in range(b+1,a-1):
        tmp*=i
        tmp%=a
    tmp_inv=inverse(tmp,a)
    result=gmpy2.next_prime(tmp_inv)
    return result
p=slv(A1,B1)
q=slv(A2,B2)
r=n//p//q
phi=(p-1)*(q-1)*(r-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[RoarCTF 2019]RSA

本来是个很麻烦的爆破，结果$n$直接factordb嗦了。（狗头保命

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
p=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
c=41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
e=65537
phi=(p-1)*(q-1)
n=p*q
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[HUBUCTF 2022 新生赛]RSAaaa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
n=536970330703
e=65537
p=540961
q=992623
m=[473878130775,40132555282,40132555282,94619939727,72818765591,208015808884,42561234694,159353248388,27748063975,159353248388,159353248388,278953790403,410746718603,496849210942,27748063975,142521857906,103632267191,17774494147,328684046745,278953790403,129956887006,129956887006,366275425558,328684046745,142521857906,410746718603,142521857906,129956887006,379067009467,328684046745,159353248388,366275425558,129956887006,103632267191,27748063975,27748063975,17774494147,160623996897,278953790403,182341799525]
phi=(p-1)*(q-1)
n=p*q
d=inverse(e,phi)
flag=b''
for i in range(len(m)):
    tmp_m=pow(m[i],d,n)
    flag+=long_to_bytes(tmp_m)
print(flag)

[黑盾杯 2020]Factor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import sympy,gmpy2
n=3454083680130687060405946528826790951695785465926614724373
e=3
c=1347530713288996422676156069761604101177635382955634367208
n1=1
phi=1
tmp=sympy.factorint(n)
tmp=[factor for factor in tmp if sympy.isprime(factor)]
for i in range(len(tmp)):
    if gmpy2.gcd(tmp[i]-1,e)==1:
        phi*=tmp[i]-1
        n1*=tmp[i]
d=inverse(e,phi)
m=pow(c,d,n1)
print(long_to_bytes(m))

[LitCTF 2023]P_Leak

$d_p$泄漏。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
dp=5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n=50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c=39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
e=65537
for x in range(1,e):
    if (dp*e-1)%x==0:
        pp=((dp*e-1)//x)+1
        if n%pp==0:
            p=pp
            q=n//p
            phi=(q-1)*(p-1)
            d=inverse(e,phi)
            m=pow(c,d,n)
            print(long_to_bytes(m))

[NCTF 2019]childRSA

$p-1$光滑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import gmpy2
N=32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c=26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
e=0x10001

a=2
n=2
while True:
    a=pow(a,n,N)
    p=gmpy2.gcd(a-1,N)
    if p!=1 and p!=N:
        q=N//p
        phi=(p-1)*(q-1)
        d=inverse(e,phi)
        m=pow(c,d,N)
        print(long_to_bytes(m))
        break
    n+=1

[LitCTF 2023]factordb (中级)

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from factordb.factordb import FactorDB
e=65537
n=87924348264132406875276140514499937145050893665602592992418171647042491658461
c=87677652386897749300638591365341016390128692783949277305987828177045932576708
f=FactorDB(n)
f.connect()
p,q=f.get_factor_list()
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[HDCTF 2023]Normal_Rsa(revenge)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2
P=8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q=112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n=12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c=7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
e=65537
p=gmpy2.iroot(P,2)[0]
q=gmpy2.iroot(Q,2)[0]
r=n//p//q
phi=(p-1)*(q-1)*(r-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[HGAME 2022 week2]RSA Attack2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
import gmpy2
e1=65537
n1=14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553
c1=965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479
n2=20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363
c2=11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090
flag=b''
q1=gmpy2.gcd(n1,n2)
p1=n1//q1
phi1=(p1-1)*(q1-1)
d1=inverse(e1,phi1)
m1=pow(c1,d1,n1)
flag+=long_to_bytes(m1)
e2=7
n=14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537
c3=10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625
m2=gmpy2.iroot(c3,e2)[0]
flag+=long_to_bytes(m2)
n4=18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729
e3=2519901323
c1=3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870
e4=3676335737
c2=940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861
_,s,r=gmpy2.gcdext(e3,e4)
m3=pow(c1,s,n4)*pow(c2,r,n4)%n4
flag+=long_to_bytes(m3)
print(flag)

[HGAME 2022 week3]Multi Prime RSA

多重RSA，当$n=p^2q^3r^5s^7$时，相应的$\varphi(n)=p^{2-1}(p-1)q^{3-1}(q-1)r^{5-1}(r-1)s^{7-1}(s-1)$。

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
p=61789932148719477384027458333380568978056286136137829092952317307711908353477
q=91207969353355763685633284378833506319794714507027332929290701748727534193861
r=105471299607375388622347272479207944509670502835651250945203397530010861809367
s=83153238748903772448138307505579799277162652151244477391465130504267171881437
n=1039344372165087100001063920598151812324151064684841845250974758525265148567706103784958424873181721352440209284812493753972556519482026327282644619091466886523804841248277210353173383407944598453848113815866908595335619458549486958764490103808475329598085842184963065068499489886467911087295087163762599284622055185456905774507245781667293199205317692029829495961487347944813874415423771980660778986211145841712412631156369129146470119135136378158203459576596246169191419488560832734046076107673091995860021863239882608638458149930255944184863801278386551031980146460231515747754411678651752698881001464973981424240781413084941947261875289725538959720572496329348499870580057997540844488309111059240745081048324762866572948371222839278718034435739827677190025500802453626872356208612718417249649474571197167076916403582394186357812640566250930361276229969553128128312736245440129556020108188835966131425956431796417720436474093381770796431629523054378258497546013222494974549262140415585158985940966415459478150722832119691308697510189026447359189994055885090735411738332296254011208547676914004864732327863884217733456287369771087094514708468685641820375220835485053482570852619363091173324203334503461823983610886849930944250553928855506012684504211525542998575275626784129736345142772399109273619522445919
e=65537
c=844677395496466411520394190869787261209960246734415406217975986418865760680024542119231873259131861208878522030009923057991526761346423130242121884493257732067700857897379859545356609151834223804262174935191718271211809221730601602827122249238086030580971376104724987801049500689134122609834321586609223761140538079460830213824674361601046367637227094018381901291488659642720549583856812747877519600804325570421770575999289389175021646347371879234023647657507178519047236746071420327155188213839293382288787853777540226192644761028822256165706787395891134765908229036044468473519166141610604791485071702808854944672418124203289328124793348198048601338476086482318248264508789781967910205393740835345086784345145351367491197717933757414967811594913692588314161669333147733048171044386546892346475181197482702164468542430187885074163177843285948999943328049159021873821254267471067523609151007885131921896462161216356454116929796355815756642621369974260365378070336290542971599886325232821981080341858950609157813769416455337935096696635623426418166316737131174435618543058086342714723330814586496030805366321181723292731710369013923285787724941830672247377301048663929453294620044701627159066468762709113137517559435822623284148112827473010030736329596829357275518641576798298066541516764673029908084962144713
phi=p**1*(p-1)*q**2*(q-1)*r**4*(r-1)*s**6*(s-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[LitCTF 2023]e的学问

当$e$非素数时，先将$e^{‘}=\dfrac{e}{\gcd(e,\varphi(N))}
$，最后再将得到的$m^{‘}=\sqrt[t]m$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import *
p=86053582917386343422567174764040471033234388106968488834872953625339458483149
q=72031998384560188060716696553519973198388628004850270102102972862328770104493
c=3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123
e=74
n=p*q
phi=(p-1)*(q-1)
t=gmpy2.gcd(e,phi)
d=inverse(e//t,phi)
m=gmpy2.iroot(pow(c,d,n),t)
if m[1]==1:
    print(long_to_bytes(m[0]))