RSA做题记录

本文将持续收录我做到的RSA有关的题

先是Cryptohack教学局

Cryptohack

Monoprime

n是质数，phi = n-1,e已知，直接求d解密

1
2
3
4
5
6
7
8
9
10
11
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

from Crypto.Util.number import long_to_bytes,inverse

phi = n-1
d = inverse(e, phi)
pt = pow(ct,d,n)
flag = long_to_bytes(pt)
print(flag)

Manyprime

n有多个质因子，直接丢到yafu分解

再用欧拉函数的积性，求phi

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
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

from Crypto.Util.number import long_to_bytes,inverse

primes_list = [
  13099895578757581201, 15998365463074268941, 9389357739583927789,
  12132158321859677597, 11328768673634243077, 16656402470578844539,
  17138336856793050757, 15824122791679574573, 14100640260554622013,
  9303850685953812323, 10638241655447339831, 17281246625998849649,
  11530534813954192171, 14178869592193599187, 11665347949879312361,
  11473665579512371723, 9282105380008121879, 12973972336777979701,
  12834461276877415051, 14523070016044624039, 17174065872156629921,
  11403460639036243901, 16898740504023346457, 15364597561881860737,
  13572286589428162097, 11282698189561966721, 11492065299277279799,
  14963354250199553339, 12955403765595949597, 14278240802299816541,
  15669758663523555763, 10336650220878499841
]
phi = 1
for p in primes_list:
    phi *= p-1 
d = inverse(e,phi)
pt = pow(ct,d,n)
m = long_to_bytes(pt)
print(m)

Salty

指数e过小

很大可能pt小于n，即ct = pt，尝试一下，得到结果

1
2
3
4
5
6
7
8
9
10
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

from Crypto.Util.number import long_to_bytes

pt = ct
m = long_to_bytes(pt)

print(m)

Modulus Inutilis

这里e=3一样过小，和上一题其实一样的

在使用·RSA时，切忌e<=3

1
2
3
4
5
6
7
8
9
10
11
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

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

pt = iroot(ct, 3)

p = long_to_bytes(pt[0])
print(p)

buuctf

RSA1

image-20250718153932165

p、q、c已知，没有e求不了d，但已知dp、dq

直接套公式

1
2
3
h = (m1-m2) mod p
t = h*inv_q mod p
m = m2 + t*q

公式推导参见另一篇博客

RSA详解

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

from Crypto.Util.number import inverse,long_to_bytes

m1 = pow(c,dp,p)
m2 = pow(c,dq,q)

inv_q = inverse(q,p)
h = (m1-m2) % p
t = h*inv_q % p
m = m2 + t*q
flag = long_to_bytes(m)
print(flag)

RSA3

buu

观察题目，本题使用e1和e2两个质数分别在模n下加密m，得到c1和c2两串密文

在RSA的使用过程中，不同用户使用相同的模数n是不规范的

我们有关系

c1 = m^e1 mod n ; c2 = m^e2 mod n

观察m^e1和m^e2，它们的指数显然是互质的，根据贝祖定理 ，一定存在

e1 * s + e2 * t = 1

那么

c1^s * c2^t mod n = m mod n

这样我们只需要先利用拓展的欧几里得算法求出s和t，代入上式就能很简单的求出m

*注意，s和t必然的一正一负，假如s是负数，我们还能有：c1ˢ mod n= (c1⁻¹)⁻ˢ mod n = (inv_c1)⁻ˢ mod n

本题的解题脚本

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
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

from Crypto.Util.number import long_to_bytes,inverse

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, s1, t1 = exgcd(b, a % b)
        s = t1
        t = s1 - (a // b) * t1
        return gcd, s, t
    
gcd,s,t = exgcd(e1,e2)

if s<0:
    s = -s
    c1 = inverse(c1,n)
if t<0:
    t = -t
    c2 = inverse(c2,n)
print('负数情况处理完成')
print('s:',s)
print('t',t)
print('c1:',c1%n)
print('c2:',c2%n)

b1 = pow(c1,s,n)
b2 = pow(c2,t,n)
m = b1*b2 % n
flag = long_to_bytes(m)
print(flag)

RSA2

RSA2

本题给出的量有e、n、dp、c

我们根据已经得到的关系式，猜测本题是求d或者求p？

根据dp≡d(mod(p−1))dp \equiv d\pmod{(p-1)},我们可以写出d=k1(p−1)+dpd = k_1(p-1)+dp，显然d和p是关联的

d还有关系式d≡e−1(modϕ(n))d \equiv e^{-1}\pmod{\phi(n)},把d代入能得到e−1=k2(p−1)(q−1)+d=[k2(q−1)+k1](p−1)+dpe^{-1}=k_2(p-1)(q-1)+d=[k_2(q-1)+k_1](p-1)+dp

但是我们不知道phi，就无法获取e−1e^{-1}的值,为了避免出现e−1e^{-1},改成代入de≡1mod  ϕ(n)de\equiv1\mod{\phi(n)}

最终得到[k2(q−1)−k1e](p−1)=edp−1[k_2(q-1)-k_1e](p-1)=edp-1

把含k2k_2和k1k_1的这一项记为K

p−1显然小于dpp-1显然小于dp，那么K大致位于[1,e]

这样我们就可以通过遍历K来获取p

解题脚本：

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 gmpy2 import is_prime,invert
from Crypto.Util.number import long_to_bytes

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1,e+1):
    t = e*dp - 1
    if t%i ==0:
        h = t//i
        p = h+1
        if is_prime(p):
            print('p=',p)
            q = n//p
            print('q=',q)
            break
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)