[AFCTF 2018]可怜的RSA

给了flag.enc、public.key

先从public.key获取n和e的值

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA

with open('./res/可怜的RSA/public.key', 'r') as f:
    pubkey = RSA.importKey(f.read())
n = pubkey.n
e = pubkey.e
print(n, e)

得到了n和e的值，需要对n因式分解

1
2
p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

知道了p😭q，用pow函数计算私钥

1
2
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

需要注意的是，读取密文后要先base64解码

1
2
3
4
import base64 
with open('./res/可怜的RSA/flag.enc', 'r') as f:
    c = f.read()
    c = base64.b64decode(c)

最终exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64 

with open('./res/可怜的RSA/public.key', 'r') as f:
    pubkey = RSA.importKey(f.read())
n = pubkey.n
e = pubkey.e

p = ...
q = ...
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
key = RSA.construct((n, e, d, p, q))
key = PKCS1_OAEP.new(key)
with open('./res/可怜的RSA/flag.enc', 'r') as f:
    c = f.read()
    c = base64.b64decode(c)
m = key.decrypt(c)
print(m)

[BJDCTF 2020]rsa_output

给了一大串数据

很明显这是要用到共模攻击

共模是指：就是明文m,相同。用两个公钥e1,e2加密得到两个私钥d1,d2 和两个密文c1,c2
共模攻击：即当m不变的情况下，知道n,e1,e2,c1,c2, 可以在不知道d1,d2的情况下，解出m

参考链接：https://www.cnblogs.com/gwind/p/8013154.html

先了解一下拓展欧几里得

展欧几里得算法（简称扩欧）是欧几里得算法（又称辗转相除法）的扩展。扩欧可以在求得 a、b的最大公约数的同时，能找到整数 x、y，使它们满足贝祖等式：ax+by = gcd(a, b)

最终payload： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2

n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1 = 2767
e2 = 3659
message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

# 拓展欧几里得
s, s1, s2 = gmpy2.gcdext(e1, e2)

m = (pow(message1, s1, n) * pow(message2, s2, n)) % n

print(long_to_bytes(m))

[SWPU 2020]happy

c的值后多了个大写L，直接删掉即可，望周知

a = q + q * p^3 = q * (1 + p^3) = q * (1 + p) * (1 - p + p^2)

b = q * p + q * p^2 = q * (1 + p) * p

由此可见，a和b的最大公约数为q*(1+p)，所以有

q*(1+p) = gcd(a, b)

p = b / q*(1+p)

q = b / (1+p^3)

所以有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2

c = int(0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e)
e = int(0x872a335)
a =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
b = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594

gift = gmpy2.gcd(a, b)
p = b // gift
q = a // (1+p**3)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

m = pow(c, d, n)
print(long_to_bytes(m))

[SWPUCTF 2021 新生赛]crypto4

由题可知，p 和 q非常接近，这适用于费马定理

直接将n开平方再取附近质数，判断相乘是否等于n就可以求出p和q

1
2
3
4
5
6
7
8
9
10
import gmpy2
n = 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153

p = q = 0

if n != p * q:
    q = gmpy2.next_prime(gmpy2.iroot(n, 2)[0])
    p = n // q
print('p = ', p)
print('q = ', q)

求出了p和q接下来就是正常流程，最终payload：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2

flag = 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
n = 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153

e = 65537
q = gmpy2.next_prime(gmpy2.iroot(n, 2)[0])
p = n // q

n_ = (p - 1) * (q - 1)
d = pow(e, -1, n_)
m = pow(flag, d, n)
print(long_to_bytes(m))

[羊城杯 2021]Bigrsa

打开附件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from flag import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)

print("c = %d" % c)

# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

1
n是模  e是公钥  c是密文  m是明文  d是私钥
  • 已知的是两个模n1n2，公钥e和密文c

根据两个模求得p和q（p😭q）

1
2
3
4
5
6
# 求两个模的最大公约数
p = GCD(n1, n2)

# 求q1和q2
q1 = n1 // p
q2 = n2 // p

由此可得欧拉函数的值

1
2
3
# 求欧拉函数值
_n1 = (p - 1) * (q1 - 1)
_n2 = (p - 1) * (q2 - 1)

再求得私钥

1
2
3
# 求私钥
d1 = inverse(e, _n1)
d2 = inverse(e, _n2)

因为明文是先后分两次加密的，所以先用d2解

1
2
m = pow(c, d2, n2)
m = pow(m, d1, n1)

最后转换一下

1
print(long_to_bytes(m))

最终payload

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
from Crypto.Util.number import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

# 求两个模的最大公约数
p = GCD(n1, n2)

# 求q1和q2
q1 = n1 // p
q2 = n2 // p

# 求欧拉函数值
_n1 = (p - 1) * (q1 - 1)
_n2 = (p - 1) * (q2 - 1)

# 求私钥
d1 = inverse(e, _n1)
d2 = inverse(e, _n2)

m = pow(c, int(d2), n2)
m = pow(m, d1, n1)

print(long_to_bytes(m))

[GWCTF 2019]babyRSA

先通过N求p和q

因为p和q极为接近所以直接开方取得p再用gmpy2.next_prime函数取值即可

计算得到私钥d后，先求得c1c2，然后有：

c1 = F1 + F2

c2 = F1^3 + F2^3

由此可得：

3 * c1 * F1^2 - 3 * c1^2 * F1 - c2 + c1^3 = 0

解方程即可

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
from sympy import solve
from sympy.abc import x

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
e=int(0x10001)

p = gmpy2.next_prime(gmpy2.iroot(N, 2)[0])
q = N // p

phi = (p - 1)*(q - 1)
d = pow(e, -1, phi)
c1 = pow(m1, d, N)  # c1 = F1+F2 
c2 = pow(m2, d, N)  # c2 = F1^3+F2^3 = (F1+F2)(F1^2+F1*F2+F2^2) = c1(F1^2+F1*F2+F2^2)

# 3 * c1 * F1^2 - 3 * c1^2 * F1 - c2 + c1^3 = 0
res = solve([3*c1*pow(x,2)-3*pow(c1,2)*x-c2+pow(c1,3)], [x])

F2 = res[0][0]
F1 = c1 - F2
m = long_to_bytes(F1) + long_to_bytes(F2)
print(m)