Xenny的RSA题单

题目地址：

Xenny的RSA题单 | NSSCTF

[柏鹭杯 2021]试试大数据分解?

题目

public.pem

1
2
3
4
-----BEGIN PUBLIC KEY-----
MEEwDQYJKoZIhvcNAQEBBQADMAAwLQImB7P6jgDCkl34tsJ1D1oiGKDHVvftOEqX
/N1kT/dj9UyNNJkEELECAwGGlw==
-----END PUBLIC KEY-----

flag.enc1

1
BhUXO8RZzppFl7Fw72jbGkEIaH/6/D5c00bYx1HEAPfN5+BeRII=

flag.enc2

1
BSiVik1bo999kG2eHzZaVt056rh74oRbbU99OrIE48ds9kQ6AR4=

flag.enc3

1
BbGPmOvTr8OYCIgwyEpu5b26jGUY2EHZRu2FUSK/cdUmK0Wqkhc=

flag.enc4

1
Axun6PS3aheoX8o3G8e3mtAxHC+C6r95oV84OQ8dxsFsxnYcfo0=

分析

题目给了公钥文件，然后四个密文，经过了base64编码

我们先读取公钥文件，得到e和n，看到n比较小，在facetordb中可以进行分解，可以得到p,q

后面进行常规的rsa解密

但是打印出m后发现不是直接的flag

观察到第一串\00字节后面666c开头，应该就是flag

手动提取了一下每一串\00后面的就行了

exp

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 *
from gmpy2 import *
from Crypto.PublicKey import RSA
from base64 import *
from factordb.factordb import FactorDB
public_key=RSA.importKey(open("./public.pem",'rb').read())

E=public_key.e
N=public_key.n
print(E)
print(N)

f=FactorDB(N)
f.connect()
p,q=f.get_factor_list()
c=[]
for i in range(4):
    c.append(bytes_to_long(b64decode((open("flag.enc{}".format(i+1),'rb').read()))))
for i in c:
    print(long_to_bytes(pow(i,invert(E,(p-1)*(q-1)),N)))
"""b'\x02\x88b4Kt\xe4\x1cI\xcf\x8fw/"\x00666c61677b495345432d49'
b'\x02\x1b\xf3\x18\xaf\xe1\xe3\xc7\x19\xa0\x05\xac\xe0N\x007235574d5f473441666276'
b'\x025\x89;\xb0\xbd\x96\tU@\xf2\x0b\xe7+\x00785f6d534d5f556766387a'
b'\x02\xfcu\xcb\n\xcf\x97\x0f\x9e\xbbC\x11\xd7\xdbw\xd9\x0052416f4d6b594350787d'"""
a=0x666c61677b495345432d497235574d5f473441666276785f6d534d5f556766387a52416f4d6b594350787d
print(long_to_bytes(a))
#b'flag{ISEC-Ir5WM_G4Afbvx_mSM_Ugf8zRAoMkYCPx}'
#NSSCTF{ISEC-Ir5WM_G4Afbvx_mSM_Ugf8zRAoMkYCPx}

[黑盾杯 2020]Factor

题目

1
2
3
n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208

分析

给了n,e,c

可以直接分解n,得到三个因数,记为p,q,r

可以发现直接计算phi_n是跟n不互素的，无法求解d，这时候我们就利用n的因子，也是可以求解的，具体原理跟用n解密是一样的过程，利用费马小定理。

这里看p,q,r的欧拉函数跟e哪个是互素，可以发现p,r和e互素的，这里我们就计算p*r的欧拉函数跟e进行求解d，然后就是正常的rsa解密

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *
from factordb.factordb import FactorDB
n = 3454083680130687060405946528826790951695785465926614724373
f=FactorDB(n)
f.connect()
p,q,r=f.get_factor_list()
e = 3
c = 1347530713288996422676156069761604101177635382955634367208

print(gcd(e,p-1)) #1
print(gcd(e,q-1)) #3
print(gcd(e,r-1)) #1

print(long_to_bytes(pow(c,invert(e,(p-1)*(r-1)),p*r)))

[羊城杯 2021]Bigrsa

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

分析

给了我们两个n，一般这种时候我们就可以知道是公用素数问题了，求解n1和n2的公约数就可以求解出一个素数

然后c是经过了两次rsa加密，求解两次就好了

exp

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
"""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
"""
from Crypto.Util.number import *
from gmpy2 import *
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p=gcd(n1,n2)

if p != 1 and isPrime(p):
    c1=pow(c,invert(e,(p-1)*(n2//p-1)),n2)
    print(long_to_bytes(pow(c1,invert(e,(p-1)*(n1//p-1)),n1)))
#b'SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}'
#NSSCTF{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}

[闽盾杯 2021]decode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n1:
15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2:
28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3:
18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1:
65537
e2:
27751
e3:
65537
c1:
5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2:
21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3:
13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

分析

跟上题一样的思路，公用素数问题

p足够大就直接用p解密了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *
n1=15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2=28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3=18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1=65537
e2=27751
e3=65537
c1=5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2=21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3=13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

p1=gcd(n1,n2)
print(long_to_bytes(pow(c1,invert(e1,p1-1),p1)))
print(long_to_bytes(pow(c2,invert(e2,p1-1),p1)))
#b"hahaha, you've got the flag didn't you !the front part is :flag{G00d_w4"
#b"hahaha, you've got the flag didn't you !the middle part is :y_tO_cR"
p3=gcd(n3,n2)
print(long_to_bytes(pow(c3,invert(e3,p3-1),p3)))
#b"hahaha, you've got the flag didn't you !the last part is :4ck_RS4}"
#flag{G00d_w4y_tO_cR4ck_RS4}
#NSSCTF{G00d_w4y_tO_cR4ck_RS4}

[鹤城杯 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
22
23
24
from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
1
2
n_list: [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list: [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]

分析

多个n对一个明文进行加密，而且e比较小，可以用中国剩余定理求解，求解出来是me，然后再开根就好了

（另外如果e比较大n比较多，还有一种是广播攻击，也是共用素数的一种，用O(n2)的时间去嵌套遍历n_list，看看有没有公用的素数）

exp

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory.modular import crt
n_list=[71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
e=9
m=crt(n_list,c_list)[0]
print(long_to_bytes(iroot(m,e)[0]))
#b'flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16'
#NSSCTF{H0w_Fun_13_HAstads_broadca5t_AtTack!}

[广东强网杯 2021 个人组]EzRSA

题目

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
52
53
#coding=utf-8
from Crypto.Util.number import *
from random import randint
from math import gcd
from flag import FLAG
assert len(FLAG)==47
def get_pub_key(bit_n, bit_lucky):
    assert 2*bit_lucky < bit_n
    while True:
        ran_num1, ran_num2 = randint(pow(2,bit_lucky-1),pow(2,bit_lucky)), randint(pow(2,bit_n // 2 - bit_lucky-1),pow(2,bit_n // 2 - bit_lucky))
        g = ran_num1 * ran_num2 + 1
        if isPrime(g):
            while True:
                ran_num3, ran_num4 = randint(pow(2,bit_lucky-1),pow(2,bit_lucky)), randint(pow(2,bit_n // 2 - bit_lucky-1),pow(2,bit_n // 2 - bit_lucky))
                j = ran_num1 * ran_num4 + 1
                t = ran_num3 * ran_num4 + 1
                if isPrime(j) and isPrime(t):
                    while True:
                        e = randint(pow(2,bit_lucky-1),pow(2,bit_lucky))
                        if gcd(e, ran_num1 * ran_num2 * ran_num3 * ran_num4) == 1:
                            phi = (g - 1) * (t - 1)
                            d = inverse(e, phi)
                            k = (e * d - 1) // phi
                            o = k * ran_num2 + 1
                            if isPrime(o):
                                n1, n2 = g * t, j * o
                                return (e, n1, n2)

def encrypt(msg, e,n):
    return pow(msg, e, n)

bit_n, bit_lucky = 1024, 256

e, n1, n2 = get_pub_key(bit_n, bit_lucky)

FLAG = bytes_to_long(FLAG.encode())

c1 = encrypt(FLAG, e, n1)
c2 = encrypt(FLAG, e, n2)

print('e =', e)
print('n1 =', n1)
print('n2 =', n2)

print('c1 =', c1)
print('c2 =', c2)


#e = 77493305850606946966866586869701562747566137421194857276849326558383863716599
#n1 = 38214712801044280452242029022307023900010505700133304226967361821658293768459754887223522190673421124166486124464596635967747405359806642464884601455285823454970604600165907209542618963333642882524596571019916658676095313436156240684679902251615046617153094607425987125749225956361360222801251450373042579071
#n2 = 11918534754165556595562303500191427316052163288557481525821438608864207524482981704928088272082867228651327063972728644192877335261376841505970220897803876176646736511250339814035116162036800063521023303060582016775080988747746487028664050144843952770605999675734459531886474293242344088869877433555271258269
#enc1 = 15808757304442558489652709164051631267713593320560967145595438513675108079906680505924179038743563463272753097766933667737349956243897214853643343110837736923623483907392474855188388096345292952323482631367759757699216716624973244377786699291503949070419765404840454938181818882998235566160193218211345167102
#enc2 = 6376686158682997059741103218078544724010800198504747162290763103690338182777916072489234933936183210135919268370502287963945937266836059808775864844630371956704383598114953698187649635431791980376016420776898290168916806683089572655387949425292390749405301644222442142567586889975355029412203353803624681004

分析

参考xenny师傅的wp

文章列表 | NSSCTF

利用连分数处理

有

n1=r1∗r2∗r3∗r4+.....n_1=r_1*r_2*r_3*r_4+.....

n2=r1∗r3∗k∗r2+...n_2=r_1*r_3*k*r_2+...

n2n1≈kr3\frac{n_2}{n_1}≈\frac{k}{r_3}

然后有

kφ(n1)+1≡0mod(e)kφ(n_1)+1\equiv0\quad mod(e)

kφ(n1)+(−kr)≡0mod(e)kφ(n_1)+(-kr)\equiv0\quad mod(e)

φ(n1)≡rmod(e)φ(n_1)\equiv r\quad mod(e)

又有

φ(n1)≡0mod(r3)φ(n_1)\equiv0\quad mod(r_3)

这样就可以利用中国剩余定理求解φ(n1)φ(n_1)了

crt求解出来的是满足解的最小值，显然不符合要求

所有我们需要对其加上x个(e∗r3)/gcd(e,r3)(e*r_3)/gcd(e,r_3)

exp

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
"""
a,b,c,d,e=2**255,2**256
g=ab+1
j=ac+1
t=cd+1

phi=(g-1)(t-1)
o=((ed-1)//phi)*b+1=kb+1

n1=gt
n2=jo
"""
#sage
from Crypto.Util.number import *
e = 77493305850606946966866586869701562747566137421194857276849326558383863716599
n1 = 38214712801044280452242029022307023900010505700133304226967361821658293768459754887223522190673421124166486124464596635967747405359806642464884601455285823454970604600165907209542618963333642882524596571019916658676095313436156240684679902251615046617153094607425987125749225956361360222801251450373042579071
n2 = 11918534754165556595562303500191427316052163288557481525821438608864207524482981704928088272082867228651327063972728644192877335261376841505970220897803876176646736511250339814035116162036800063521023303060582016775080988747746487028664050144843952770605999675734459531886474293242344088869877433555271258269
enc1 = 15808757304442558489652709164051631267713593320560967145595438513675108079906680505924179038743563463272753097766933667737349956243897214853643343110837736923623483907392474855188388096345292952323482631367759757699216716624973244377786699291503949070419765404840454938181818882998235566160193218211345167102
enc2 = 6376686158682997059741103218078544724010800198504747162290763103690338182777916072489234933936183210135919268370502287963945937266836059808775864844630371956704383598114953698187649635431791980376016420776898290168916806683089572655387949425292390749405301644222442142567586889975355029412203353803624681004

cf = continued_fraction(n2 / n1)
convers = cf.convergents()
for pkd in convers:
    k,r3=pkd.as_integer_ratio()
    if gcd(k, e) != 1:
        continue
    r = inverse_mod(-k, e)
    phi = crt([r, 0], [e, r3])
    md = e*r3 // gcd(e, r3)
    st = phi + (n1//md) * md #预处理一下
    
    for i in range(-100, 100):
        if gcd(e, st+i*md) != 1:
            continue
        d = inverse_mod(e, st + i*md)
        m = long_to_bytes(power_mod(enc1, d, n1))
        if b'flag' in m:
            print(phi)
            print(m)
            break
#b'flag{C0ngra4u1ation!!!_You_R3a1ly_Kn0w_Lat2ic3}'
#NSSCTF{C0ngra4u1ation!!!_You_R3a1ly_Kn0w_Lat2ic3}

[湖湘杯 2021]signin

题目

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
#sage
from Crypto.Util.number import *
from secret import flag
import random

m1 = bytes_to_long(flag[:len(flag) // 2])
m2 = bytes_to_long(flag[len(flag) // 2:])

def gen(pbits, qbits):
    p1, q1 = getPrime(pbits), getPrime(qbits)
    n1 = p1**4*q1
    q2 = getPrime(qbits)
    bound = p1 // (8*q1*q2) + 1
    p2 = random.randrange(p1, p1 + bound)
    while not isPrime(p2):
        p2 = random.randrange(p1, p1 + bound)
    n2 = p2**4*q2
    return (n1, n2), (p1, q1), (p2, q2)

e = 0x10001
pbits = int(360)
qbits = int(128)
pk, sk1, sk2 = gen(pbits, qbits)
c1 = pow(m1, e, pk[0])
c2 = pow(m2, e, pk[1])
print(f'pk = {pk}')
print(f'c1, c2 = {c1, c2}')

"""
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
"""

分析

连分数原理不太懂‘

xenny师傅说看到这种多因子+大数都可以考虑连分数分解

n1=p14∗q1n_1=p_1^4*q_1

n2=p24∗q2n_2=p_2^4*q_2

p2p_2略大于p1p_1

有：

n1n2≈p14∗q1p24∗q2\frac{n_1}{n_2}≈\frac{p_1^4*q_1}{p_2^4*q_2}

利用连分数可以求解q1和q2q1和q_2

exp

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
#sage
from Crypto.Util.number import *
from gmpy2 import *
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
e = 0x10001
n1=pk[0]
n2=pk[1]
cf = continued_fraction(n1 / n2)
convers = cf.convergents()
for pkd in convers:
    q1,q2=pkd.as_integer_ratio()
    if q1==0 or q2==0:
        continue
    if n1 % q1 == 0 and n2 % q2 == 0 and is_prime(q1) and is_prime(q2):
        if iroot(n1//q1, 4)[1]:
            p1=iroot(n1//q1, 4)[0]
            p2=iroot(n2//q2, 4)[0]
            d1=invert(e,(p1**4-p1**3)*(q1-1))
            d2=invert(e,(p2**4-p2**3)*(q2-1))
            m1=pow(c1,d1,n1)
            m2=pow(c2,d2,n2)
            print(long_to_bytes(int(m1))+long_to_bytes(int(m2)))
            break
#b'flag{8ef333ac-21a7-11ec-80f1-00155d83f114}'
#NSSCTF{8ef333ac-21a7-11ec-80f1-00155d83f114}

[NCTF 2019]easyRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

分析

AMM

exp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from Crypto.Util.number import *
from gmpy2 import *
import random
import math

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

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 % 100000 == 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)
        if b'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

cp = c % p
cq = c % q

mp = AMM_rth(cp, e, p)  # AMM算法得到一个解
mq = AMM_rth(cq, e, q)

rt1 = ALL_ROOT2(e, p)  # 得到所有的ri，即(ri*mp)^e%p = 1
rt2 = ALL_ROOT2(e, q)

amp = ALL_Solution(mp, p, rt1, cp, e)  # 得到所有的mp
amq = ALL_Solution(mq, q, rt2, cq, e)

a=calc(amp, amq, e, p, q)  # 俩俩CRT

#22400000
#b'NCTF{T4k31ng_Ox1337_r00t_1s_n0t_th4t_34sy}e$71N{D]0su{ZDEKfEnY>TTQ(=qR?GBpN\\U{3@O\\/I8ZsxW.Uw)3&&s&xD-<Uf*pKXOkV0~oiWubv<VAD9roRJU9:9S?>MyZ<wMN~T||%PC*j]inkgus4f9t:g:O9!FsIas^?M*q:BU{_J*r"*6Fi94hdRUW#s0=N+][l}Js7j,c5kiLB+/f<_1*N=V3Eq%~s^!5Gh8*'
#NSSCTF{T4k31ng_Ox1337_r00t_1s_n0t_th4t_34sy}

[NISACTF 2022]rrssaa2

题目

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 random
import libnum
import gmpy2

def gen():
    p = 1801 * random.getrandbits(1012) + 1
    while not isPrime(p):
        p = 1801 * random.getrandbits(1012) + 1
    return p
p=gen()
q=gen()
e=1801
n=p*q
flag='NSSCTF{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'
flag=flag+'yhe92871899hihiohh97709ujojl;lhdiwoqu903YE98Y299HDY8W9EYRW8!$$%!$!$FSR@#$@%FSEGDRYERYHRWER@$%^$^DGTW%$^&GRWR@$%@FASFSFQFSTGW#TWGARWQ$@%WGVDSGADQR@%TGVDSFASDATWEGHWE%@$GSDVSFQATY$^#^%@$!RAFSDGDRTW'

c = pow(m, e, n)
print('e=',e)
print('p=',p)
print('q=',q)
print('c=',c)

#e= 1801
#p= 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
#q= 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
#c= 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199

分析

同上

exp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from Crypto.Util.number import *
from gmpy2 import *
import random
import math

e= 1801
p= 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
q= 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
c= 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199
n=p*q

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 % 100000 == 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)
        if b'NSSCTF' 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

cp = c % p
cq = c % q

mp = AMM_rth(cp, e, p)  # AMM算法得到一个解
mq = AMM_rth(cq, e, q)

rt1 = ALL_ROOT2(e, p)  # 得到所有的ri，即(ri*mp)^e%p = 1
rt2 = ALL_ROOT2(e, q)

amp = ALL_Solution(mp, p, rt1, cp, e)  # 得到所有的mp
amq = ALL_Solution(mq, q, rt2, cq, e)

a=calc(amp, amq, e, p, q)  # 俩俩CRT
#2900000
#b'NSSCTF{2he_amm_13_r12lly_hard_f0r_me}yhe92871899hihiohh97709ujojl;lhdiwoqu903YE98Y299HDY8W9EYRW8!$$%!$!$FSR@#$@%FSEGDRYERYHRWER@$%^$^DGTW%$^&GRWR@$%@FASFSFQFSTGW#TWGARWQ$@%WGVDSGADQR@%TGVDSFASDATWEGHWE%@$GSDVSFQATY$^#^%@$!RAFSDGDRTW'

[长安杯 2021]checkin

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

分析

威尔逊定理：

(p−1)!=−1mod(p)(p-1)!=-1\quad mod(p)

有:

m0=m∗(p−1−q)!m_0=m*(p-1-q)!

2e=c2mod(n)2^e=c2\quad mod(n)

m0e=c1mod(n)m_0^e=c1\quad mod(n)

由二式可以得到k倍的n

q是一个比较小的数，我们可以直接爆破，然后求到kp

我们去在线网站进行分解，可以得到p

然后求解得m0m_0

最后根据威尔逊定理,我们对m0从p-q乘到p-1可以得到-m mod(p)

然后对-1求逆元就可以得到m

exp

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 *
c2=4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c1=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
e=1049
kn=2**1049-c2
"""for i in range(1<<15,1<<16):
    if isPrime(i) and kn%i==0:
        q=i
        print(q)
        print(kn//q)
        break
        #34211
        #176187289150514462046172630174700088525221325866312783639426750020851677271339945780081598171833449310803326466412109196489585032131454474980855474525268996498728189708770015967359856986040467410546755834813513311041394212977692161618099683277808044775858602607121850124014360450965062461065243304016148002474085
"""
q=34211    
p=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231

assert pow(2,e,p*q)==c2

m0=pow(c1,invert(e,(p-1)*(q-1)),p*q)
for i in range(p-q,p):
    m0=(m0*i)%p
print(long_to_bytes((int(m0)*invert(-1,p))%p))
#b"flag{7h3_73rr1b13_7h1ng_15_7h47_7h3_p457_c4n'7_b3_70rn_0u7_by_175_r0075}"
#NSSCTF{7h3_73rr1b13_7h1ng_15_7h47_7h3_p457_c4n'7_b3_70rn_0u7_by_175_r0075}

[GKCTF 2021]RRRRsa

题目

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

flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))

p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))

p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))

#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

分析

目的是求解加密flag的p和q

求解p：

hint1=(2020∗p1+q1)202020mod(n1)hint1=(2020*p_1+q_1)^{202020}\quad mod(n_1)

hint2=(2021∗p1+212121)q1mod(n1)hint2=(2021*p_1+212121)^{q_1}\quad mod(n_1)

将二式都变成mod(q1)mod(q_1)

根据二项式定理，出了第一项外，其他项都有q1q_1都可以消掉

hint1=(2020∗p)202020mod(q1)hint1=(2020*p)^{202020}\quad mod(q_1)

根据费马小定理有

hint2=2021∗p1+212121mod(q1)hint2=2021*p_1+212121\quad mod(q_1)

凑一下项得：

hint1∗2021202020=(2021∗2020∗p1)202020mod(q1)hint1*2021^{202020}=(2021*2020*p_1)^{202020}\quad mod(q_1)

((hint2−212121)∗2020)202020=(2020∗2121∗p1)202020((hint2-212121)*2020)^{202020}=(2020*2121*p_1)^{202020}

两式相减可以得(k1−k2)∗q1(k_1-k_2)*q_1

跟n求gcd即可得到q1q_1

求解q：

原理同上

exp

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
from Crypto.Util.number import *
from gmpy2 import *
c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
e=65537
#一
q1=gcd(n1,(hint1*(2021**202020)-pow((hint2-212121)*2020,202020,n1)))
p1=n1//q1

p=pow(c1,invert(e,(p1-1)*(q1-1)),n1)

#二
q2=gcd(n2,pow(hint3*2021**202020,212121,n2)-pow(hint4*2020**212121,202020,n2))
p2=n2//q2

q=pow(c2,invert(e,(p2-1)*(q2-1)),n2)

print(long_to_bytes(pow(c,invert(e,(p-1)*(q-1)),p*q)))
#b'GKCTF{f64310b5-d5e6-45cb-ae69-c86600cdf8d8}'
#NSSCTF{f64310b5-d5e6-45cb-ae69-c86600cdf8d8}

[黑盾杯 2020]Change

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from flag import FLAG
from Crypto.Util.number import *
import gmpy2
import random

while True:
    p = int(gmpy2.next_prime(random.randint(10**399, 10**400-1)))
    q = int(str(p)[200:]+str(p)[:200])
    if gmpy2.is_prime(q):
        break

m = bytes_to_long(FLAG)
n = p*q
e = 65537
c = pow(m,e,n)

with open("enc","wb") as f:
    f.write(str(c))
    f.write("\n")
    f.write(str(n))
#182812482972168423884795132699225934365072979206288632257180603530046820174392675977209758378734399146216742345585898385168866887000708558119959898992294085847474548306743585711154035585848291290988967352517174312220756638881837930962458861193652684492265539096477345065113556380573776423787885892688197584678128636231428194711357642971544417113415626331810909274966752557628893585198569815939514862013512237657828262360291726912615575646318630641527418369988268899879152029186728850816178597399494254385226049249357897840618728804680238123954207656671747782543031545429711152272581734051959578453680011676521727918037340906791388178004979453256050227967701258768070039292546964652071924183467364467145178290753361477912582242961929982420950384199259355122986865808523351306098081481072454093823090
#438980397031315392229453908048509540832246041631432878509579665664182747463100230160823865621798053164989325086085003940181731721089701380743698761443812523024144817205902380903062054138730658451286904347536210833160924917347633148983052015550354913154312162901555870494273903714349869746793861874257201085777893961715468950661641778512110325457371446203379767458862059193946434683324578530163650541637261158037041205642428802942295011562277084687025213626698849526240663754073508102229066475773893638716845176469070938803298515155140240970836387785401085919369741520890271902332951669953411373633688944162470994856654604872287103746922041844065053274059990595496159866206551119361036237431289830985174384522423364811997241255005514248198447925396378192915553898993758660041223393168707380580012437

分析

p=ph∗10200+plq=pl∗10200+phn=10400∗ph∗pl+10200∗ph2+10200∗pl2+ph∗plp=p_h*10^{200}+p_l \\ q=p_l*10^{200}+p_h \\ n=10^{400}*p_h*p_l+10^{200}*p_h^2+10^{200}*p_l^2+p_h*p_l

ph和pl都是200位的,所以n第一项大约800位p_h和p_l都是200位的,所以n第一项大约800位

可以得：

(ph∗pl)h=n10600(ph∗pl)l=nmod(10200)(p_h*p_l)_h=\frac{n}{10^{600}} \\ (p_h*p_l)_l=n\quad mod(10^{200})

这样我们就有了ph∗plp_h*p_l的高200位和低200位

也就得到了ph∗plp_h*p_l

结合n的表达式，我们就可以求解二元方程组了

exp

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

c = 182812482972168423884795132699225934365072979206288632257180603530046820174392675977209758378734399146216742345585898385168866887000708558119959898992294085847474548306743585711154035585848291290988967352517174312220756638881837930962458861193652684492265539096477345065113556380573776423787885892688197584678128636231428194711357642971544417113415626331810909274966752557628893585198569815939514862013512237657828262360291726912615575646318630641527418369988268899879152029186728850816178597399494254385226049249357897840618728804680238123954207656671747782543031545429711152272581734051959578453680011676521727918037340906791388178004979453256050227967701258768070039292546964652071924183467364467145178290753361477912582242961929982420950384199259355122986865808523351306098081481072454093823090
n = 438980397031315392229453908048509540832246041631432878509579665664182747463100230160823865621798053164989325086085003940181731721089701380743698761443812523024144817205902380903062054138730658451286904347536210833160924917347633148983052015550354913154312162901555870494273903714349869746793861874257201085777893961715468950661641778512110325457371446203379767458862059193946434683324578530163650541637261158037041205642428802942295011562277084687025213626698849526240663754073508102229066475773893638716845176469070938803298515155140240970836387785401085919369741520890271902332951669953411373633688944162470994856654604872287103746922041844065053274059990595496159866206551119361036237431289830985174384522423364811997241255005514248198447925396378192915553898993758660041223393168707380580012437
e = 0x10001

pqh = n // pow(10, 600)
pql = n % pow(10, 200)
pq = pqh*pow(10, 200) + pql

n -= pow(10, 400)*pq + pq

from z3 import *
h=Int('h')
l=Int('l')
s=Solver()
s.add(h*l==pq)
s.add(pow(10, 200)*h*h+pow(10, 200)*l*l==n)
s.check()
s=s.model()
h=s[s.decls()[0]].as_long()
l=s[s.decls()[1]].as_long()
p = h*pow(10, 200) + l
q = l*pow(10, 200) + h

d = invert(e, (p-1)*(q-1))

print(long_to_bytes(powmod(c, d, p*q)))
#b'CMISCCTF{easy_math_game_hhhhhhh}'
#NSSCTF{easy_math_game_hhhhhhh}

[MTCTF 2021]hamburgerRSA

题目

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

flag = open('flag.txt').read()
nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PP = int(str(p) + str(p) + str(q) + str(q))
    QQ = int(str(q) + str(q) + str(p) + str(p))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
#n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
#c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096

分析

原理同上题

64位的十进制大约19-20位

p*q大约38位？

（但是我还是不咋理解

exp

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
from gmpy2 import *
from Crypto.Util.number import *
from itertools import product
from string import digits
from factordb.factordb import FactorDB
n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
e = 65537

pqh = str(n)[:19]
pql = str(n)[-18:]

for i,j in product(digits, repeat=2):
    pq = pqh + i + j + pql
    tp = FactorDB(int(pq))
    tp.connect()
    tp=tp.get_factor_list()
    if tp and len(tp) == 2 and tp[0].bit_length() == 64:
        p, q = tp
        break
PP = int(str(p) + str(p) + str(q) + str(q))
QQ = int(str(q) + str(q) + str(p) + str(p))

d = invert(0x10001, (PP-1)*(QQ-1))
print(long_to_bytes(powmod(c, d, n)))
#b'flag{f8d8bfa5-6c7f-14cb-908b-abc1e96946c6}'
#NSSCTF{f8d8bfa5-6c7f-14cb-908b-abc1e96946c6}

[第五空间 2021]signin

题目

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 *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
x = (p ^ q) & ((1 << 400) - 1)

m = bytes_to_long(flag)

c = pow(m,e,n)

print("c = " + str(c))
print("e = " + str(e))
print("n = " + str(n))
print("x = " + str(x))

'''
c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788
'''

分析

进阶版的p异或q

只给了p和q的低400位

利用dfs剪枝计算可能的p和q

然后coppersmith计算p和q

(具体原理我也说不清，可以当作板子题把，直接拿xenny师傅的wp了)

(注意点，sage环境中异或是^^)

exp

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

c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788

plist = [0]
qlist = [0]

mask = 0
for i in range(400):
    tmpp, tmpq = [],[]
    for p,q in [(0,0),(0,1),(1,0),(1,1)]:
        if p^^q == ((x>>mask)&1):
            for j in range(len(plist)):
                if ((p<<mask) + plist[j]) * ((q<<mask) + qlist[j]) % (2<<mask) == n % (2<<mask):
                    tmpp.append((p<<mask) + plist[j])
                    tmpq.append((q<<mask) + qlist[j])
    plist,qlist = tmpp, tmpq
    mask += 1

for pbar in plist:
    PR = PolynomialRing(Zmod(n), 'x')
    x = PR('x')
    ZmodN = Zmod(n)
    f = x*ZmodN(2**400) + pbar
    f = f.monic()
    r = f.small_roots(X=2**112, beta=0.4)
    if r:
        p = int(pbar+r[0]* 2**400)
        if n%p == 0:
            break

q = n // p
d = inverse_mod(e, (p-1)*(q-1))
print(long_to_bytes(power_mod(c, d, n)))
#b'flag{59sm5gzl-8wbm-v2lj-w7m2-4op2lyr8wjz8}'
#NSSCTF{59sm5gzl-8wbm-v2lj-w7m2-4op2lyr8wjz8}

[CISCN 2021初赛]rsa

题目

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
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200


19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
(3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L)
54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
(17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
(65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
(65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

分析

将text分成了三个部分，最后计算text的md5值作为flag

第一部分

e较小，且推测m也较小，可以直接开根

第二部分

使用了两个e进行加密，且两个e互素

有：

me2=c2mod(n)me3=c3mod(n)m^{e_2}=c_2\quad mod(n)\\ m^{e_3}=c_3\quad mod(n)\\

利用扩展欧基里德计算：

s1∗e2+s2∗e3=1(me2)s1∗(me3)s2=c2s1∗c3s2mod(n)me2∗s1+e3∗e2=c2s1∗c3s2=mmod(n)s_1*e_2+s_2*e_3=1\\ (m^{e_2})^{s_1}*(m^{e_3})^{s_2}=c_2^{s_1}*c_3^{s_2}\quad mod(n)\\ m^{e_2*s_1+e3*e_2}=c_2^{s_1}*c_3^{s_2}=m\quad mod(n)

第三部分

我们知道p的高312位，利用coppersmith进行高位攻击

(可以直接当板子题)

exp

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
#sage
from hashlib import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime
from gmpy2 import *

c1=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1=3
n1=12381447039455059836328051884891454693813773102677797588584673367249449397570306976005386747183624947329082879996258685589268590290205063001831293901056494567669971224624982034171215593839806873286664642282661947718043485814893823566209248205899907910545013618168514189595557454867166732016774164107233025900

msg1=long_to_bytes(iroot(c1,e1)[0])


c22=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c23=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e2=17
n2=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
e3=65537

_,s1,s2=gcdext(e2,e3)
msg2=long_to_bytes(int((pow(c22,s1,n2)*pow(c23,s2,n2))%n2))

c3=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
high_p=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
unknown_bits=200
high_p=high_p<<unknown_bits
R.<x> = PolynomialRing(Zmod(n3))
f = high_p + x
x = f.small_roots(X = 2^unknown_bits,beta = 0.4)
p=int(high_p+x[0])
msg3=long_to_bytes(int(pow(c3,invert(e3,(p-1)*(n3//p-1)),n3)))

text=msg1+msg2+msg3
print(text)
print(md5(text).hexdigest())
#b" \nO wild West Wind, thou breath of Autumn's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, and black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n"
#3943e8843a19149497956901e5d98639
#NSSCTF{3943e8843a19149497956901e5d98639}

[鹏城杯 2022]easy_rsa

题目

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
import gmpy2
from Crypto.Util.number import *
import random
from secret import flag

m1 = flag[0:12]
m2 = flag[12:24]
m3 = flag[24:]

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')})


def encrypt2(m):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    c = gmpy2.powmod(m, e, n)
    print({'c': format(c, 'x'), 'p': format((p >> 60) << 60, 'x'), 'e': format(e, 'x'), 'n': format(n, 'x')})


def encrypt3(m):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    M = 2022 * m * 1011 * p
    c = pow(M, e, n)
    print({'c': format(c, 'x'), 'n': format(n, 'x'),'e':format(e, 'x')})


if __name__ == '__main__':
    encrypt1(bytes_to_long(m1))
    encrypt2(bytes_to_long(m2))
    encrypt3(bytes_to_long(m3))

# {'c': '27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e', 'p': 'bb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd', 'q': 'bb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1', 'e': '292'}
# {'c': '3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f', 'p': 'a9cb9e2eb43f17ad6734356db18ad744600d0c19449fc62b25db7291f24c480217d60a7f87252d890b97a38cc6943740ac344233446eea4084c1ba7ea5b7cf2399d42650b2a3f0302bab81295abfd7cacf248de62d3c63482c5ea8ab6b25cdbebc83eae855c1d07a8cf0408c2b721e43c4ac53262bf9aaf7a000000000000000', 'e': '10001', 'n': '841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65'}
# {'c': '1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df', 'n': 'c2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069', 'e': '10001'}

分析

将flag分成了三个部分，一一来看

第一部分

给了p和q，但是经过计算e和ϕ(n)\phi(n)并不互素

但是最大公约数是2

我们计算e//2，当作新的e来解密，最后求解出来开2次根就结果了

证明：

c=memod(n)e=2e′d′e′=1mod(ϕ(n)cd′=med′=m2e′d′=m2mod(n)c=m^e\quad mod(n)\\ e=2e'\\ d'e'=1\quad mod(\phi(n)\\ c^{d'}=m^{ed'}=m^{2e'd'}=m^2\quad mod(n)

第二部分

知道p的高位，利用coppersmith，同上题第三部分套板子就行了

第三部分

经过模p推导可以得到c等于k倍的p，那么我们知道n，就可以跟n求最大公约数得到p

M=2022∗m∗1011∗pmod(n)M=0mod(p)c=Me=0mod(p)c=kpM=2022*m*1011*p\quad mod(n)\\ M=0 \quad mod(p)\\ c=M^e=0\quad mod(p)\\ c=kp

exp

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

c1=0x27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e
p1=0xbb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd
q1=0xbb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1
e1=0x292
phi1=(p1-1)*(q1-1)
g1=gcd(e1,phi1)
te1=e1//g1
td1=invert(te1,phi1)
tm1=int(pow(c1,td1,p1*q1))
m1=long_to_bytes(iroot(tm1,2)[0])

c2=0x3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f
high_p2=0xa9cb9e2eb43f17ad6734356db18ad744600d0c19449fc62b25db7291f24c480217d60a7f87252d890b97a38cc6943740ac344233446eea4084c1ba7ea5b7cf2399d42650b2a3f0302bab81295abfd7cacf248de62d3c63482c5ea8ab6b25cdbebc83eae855c1d07a8cf0408c2b721e43c4ac53262bf9aaf7a000000000000000
e2=0x10001
n2=0x841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65

unknown_bits=60
R.<x> = PolynomialRing(Zmod(n2))
f = high_p2 + x
x = f.small_roots(X = 2^unknown_bits,beta = 0.4)
p2=int(high_p2+x[0])
m2=long_to_bytes(int(pow(c2,invert(e2,(p2-1)*(n2//p2-1)),n2)))

c3=0x1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df
n3=0xc2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069
e3=0x10001
p3=int(gcd(n3,c3))
m3=int(pow(c3,invert(e3,(p3-1)*(n3//p3-1)),n3))
m3=long_to_bytes(m3//(p3*2022*1011))
print(m1+m2+m3)
#b'PCL{16745c3b0c134c83b74f977260aae9b5}'
#NSSCTF{16745c3b0c134c83b74f977260aae9b5}

[红明谷CTF 2022]easy_ya

题目

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

from flag import flag
def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return
p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)
'''
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
'''

分析

还是利用CopperSmith

具体原理我也不清楚，只知道能这么做（哭

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#sage
from gmpy2 import *
from Crypto.Util.number import *
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282

PR.<x> = PolynomialRing(Zmod(n))
f = (M+x*r)^e-c
f = f.monic()
x = f.small_roots()
if x:
    print(x)
    m=int(M+x[0]*r)
    print(long_to_bytes(m))
#[810968823598060539864535]
#b'flag{53a2e494-964d-4506-a2c4-c34b9475dedd}W\xf1X6\xacP\x9bc~9\xfd\x0f\x96\xbf\x92\xb9+\xe5\xebPJ\x17\xc4\xb2\xe8\xad\x01\n\xf2j\xae\x15'
#NSSCTF{53a2e494-964d-4506-a2c4-c34b9475dedd}

[强网杯 2019]copperstudy

题目

没有附件，nc上去看

分析

（建议先看[GWCTF 2019]BabyRSA2，学会直接在vscode里执行sage，因为涉及到nc，然后可以自己试试直接在一个exp里完成）

越做越疯，很糟糕

全是找板子，想看原理看具体exp里然后取搜吧

这里是有板子

exp

第一步

nc连接，然后直接爆破

之后保持连接，后面就手动输入了

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
from pwn import *
from Crypto.Util.number import *
import hashlib
p=remote("node4.anna.nssctf.cn",28421)
print(p.recvline())
p.recvuntil(b'hexdigest()=')
sha=(p.recvline().decode()).strip()
print(sha.encode())
p.recvuntil(b"skr[0:5].encode('hex')=")
pre_skr=(p.recvline().decode()).strip()
print(pre_skr.encode())
print(p.recvuntil(b"skr.encode('hex')="))
temp="0123456789abcdef"
fl=0
for i in temp:
    for j in temp:
        for k in temp:
            for l in temp:
                for m in temp:
                    for n in temp:
                        skr=int(pre_skr+i+j+k+l+m+n,16)
                        skr=long_to_bytes(skr)
                        if str(hashlib.sha256(skr).hexdigest()) == sha:
                            print(skr.hex())
                            p.sendline(str(skr.hex()).encode())
                            fl=1
                            break
                    if fl:
                        break
                if fl:
                    break
            if fl:
                break
        if fl:
            break
    if fl:
        break
p.interactive()

第二步

m的高位攻击

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

n=16017962047981034439379147851871655991715523372130499591852000402972024053592619510623839612271064518084046813489696243662115859838347110076313512984252332977601217689166917112436536161737721874651780063000862202462029857462549195260675764694966296233199436592988341616312096302239910999510720139029804993110147203819277344583064534236243526036059624654235721115483341283815742379122011040983246073311540204563363560614990222916022071722333723544827566195478776465318605614524315368708097920766178242152179015998515592146063110842222141971840122508556233670514825282525191089330615519445235293437744571216306171297139
e= 3
m_high=653524334392227600570363162383764937305248031854419023410931365363426067123844229856737844264960
c=279116358436840580445598969421610529050633733034686489455738062242484915123166426001912178374020325810905517077211915812323425704202427412835294016600968491811813422933962866712907267434038126911651594486545661906271625545257899553405201093150339568388337402642643112619054191820421155173
unknown_bits=72

R.<x> = PolynomialRing(Zmod(n))
m = m_high + x
f = m^e - c
x = f.small_roots(X = 2^unknown_bits,beta = 0.4)
if x:
    m = m_high + x[0]
    print(long_to_bytes(int(m)).hex())
#4e53534354467b35643366363566366163303966613064303162383838626336643335616234347d

第三步

p高位攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#sage
from Crypto.Util.number import *
from gmpy2 import *
n=23412744196435681035016886220643400350970797545501310013304272571425348967576484268142400640552976798425045608274973517284025831498467236341911890721102753724816097043557304340791745423642403094886324667586890743441181879275819905523857289371181975206153946416492759491324890990771260876302417738635652747674766470906230972589393979314947350143584541009374774851236081699644040090877016127125997472439169352089823014941009458298353952133084702487229994974065020835757669357061533853531708873378901690969236981895123027779256185848480947387458247076558510061941953938352870386545064169169200268143031918794825270298631
e=65537
c=9398872900480694514053766636015808474916722324451384224067138680826665766000870773107410167898882406270257015221891892085001459713583625341362117117871802743137635415088841771727308157301268300094318585426138274238719361978001009950762135079902183427948096280119330118607820781873262983642485251440958841901313115939514261290900440121234463088422361021316299407329969835177481638764778578537907012916110360538977789500099230565812930941982075719936200613719978050626787999136833805067940187341360786050332115552930420848777154904971863171308444262963588775160727678158622484428491558915905860791139989357158989913050
high_p=136232996027545975004563119617198627048065138315684770279122430141624103589614249447456579821863618044683199820893874027883593009896002870850519475109346672955929930383822711173403482003043608577119957883570354552011936964395584718847162648784196596548570670949314203035203058272377061576666254342055958413312
unknown_bits=128
R.<x> = PolynomialRing(Zmod(n))
f = high_p + x
x = f.small_roots(X = 2^unknown_bits,beta = 0.4)
if x:
    p=int(high_p+x[0])
    q=n//p
    phi=(p-1)*(q-1)
    d=invert(e,phi)
    print(long_to_bytes(int(pow(c,d,n))).hex())
#4e53534354467b32393537633039333964393165633765633331306462356630616130303637627d

第四步

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
#sage    
from Crypto.Util.number import *
import gmpy2
def getFullP(low_p, n):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = x * 2 ^ bit + low_p
    root = (p - n).monic().small_roots(X=2 ^ 128, beta=0.4)
    if root:
        return p(root[0])
    return None


def phase4(low_d,n,c,e):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)
        maybe_p += [int(x[0]) for x in p0]
    # print(maybe_p)

    for x in maybe_p:
        P = getFullP(x, n)
        if P: break

    P = int(P)
    Q = n // P

    assert P * Q == n
    print("P = ",P)
    print("Q = ",Q)

    d = inverse_mod(3, (P - 1) * (Q - 1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)).hex())

low_d = 9973904680412152570138003136466059609611257944928836300634423080561298749075958309067426603113525684100417494741123226214436236190592552869975926519409611
bit = low_d.nbits()
n = 114977856718774899746007273258142027119221291891045313370664580956945773892016230637680441795343679791416907107771431518072494779758596070931073345264743927090857036312767418019303974408803896285561003981790474474879254339898650912349447554900342592699419248042230565484734565275290033575309907770959979249441
e = 3
c = 279116358436840580443869403482689523417926943370283952754967172903129298280404573580346506496192282092683784627132866212050801891387341516024550585731142831756181412863049450540988286305848774162564019517973339661098414905264661903203165067354388671494408807585235845183100544469908026469

phase4(low_d,n,c,e)
print("over")

#P =  9391440826233377371336657018726228044955035660871483031200545194209412258251390818401701331464535153201228754160435275219818869242505918168666443009326573
#Q =  12242834602929509975987801546676877090198837325930397169155103539567125515140067665313945532401676516599948815186229719968852154887325536081734280242134917
#4e53534354467b35613766336538663162393366623031373734353635393137353330373233657d

第五步

中国剩余定理

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

n1=70150782017106744702286811194970924795928560711094108957698212389450273692062768369571246611319149038648327761674152952339905197695826737596960300577409503979703942545335432723800249192593500405582765931990758208650822157232981240732073491803602882507450974334286908867409590191359365352766613583499469290527
c1=279116358436840580122801369030860797071717129802018282437018488673976577326106718472074964408957326212618048865436045226170032031901019679413199602348078729644581348770787396528963958874221694545619137696961058855467066695666042795471835004925286023187346469299975149390451496495239926629
n2=162923886897767641573990199711208966404485491217179966579970401560714596746048441376917770043182383221870895215113078186461513007410215100878491414297440280939964180092659379220178207225568061030068648967857348433089303371603266843183223035463682063557841392298863456665960447294704243819193928375408330671631
c2=279116358436840580122801369030860797071717129802018282437018488673976577326106718472074964408957326212618048865436045226170032031901019679413199602348078729644581348770787396528963958874221694545619137696961058855467066695666042795471835004925286023187346469299975149390451496495239926629
n3=64753773112870123671946228401261981403081286742676725931583667929772070753859231199873341111781336775967007272149447053104007491713851164173612962580712278731622434533504364107395371718249464189400149469043191006088911663789316310304257096522277791717333432302300795390616581016561592287175185617125932272419
c3=279116358436840580122801369030860797071717129802018282437018488673976577326106718472074964408957326212618048865436045226170032031901019679413199602348078729644581348770787396528963958874221694545619137696961058855467066695666042795471835004925286023187346469299975149390451496495239926629

c=[c1,c2,c3]
n=[n1,n2,n3]
#使用中国余数定理计算m的e次方
x = crt([n1, n2, n3], [c1, c2, c3], check=True)
print(long_to_bytes(iroot(x[0],3)[0]).hex())

第六步

m相关攻击

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
#sage
from Crypto.Util.number import *
import binascii
"""
m1=a1*m+b1
m2=a2*m+b2
"""
n=26847996488880447216096776732070281545074976645749840223230511101684036430699982494901520391374124676936370320908977030678422411113870898677919949108092307560814359856349235904175523637127826401779533321668448534998775648599423127487483632410155870352622828098410769325273126586866498178208776567574352828392125983672996446308065758934722526747310236556876750508203459413705807255650618685650750523570744211286546519649176886249835233519536394639538776259162929144979062059559775101414000670212721128884382352735794626563622728463436421772307972139931705536741059161551098795715075350442339804773649281544806370921391
a1=1
b1=0
c1=24732899138985698048124738358885344459379493315054027124307662756312751844141022376300081819454686750145220818897973180537017198314231472874483596104799907859093488291789788924219598121824323245537546195418486119678702901179691397376775826957705715693979193211784497213599547621382217619658749166534139290785718885852449894739032293904252938440995047190420058143769116751715376151332965862901010949911088033051288770545272582507845444790953964807440668028480049740511795701814222210845363937718599750472068452173181280703803935942166980836867264796046582678020913725095981275231662933966865789526710944092564302745232
a2=1
b2=1
c2=24732899138985698048124738358885344459380038656644856424408162261290252390990430221618386418951988486708762804946769795228623929192434866679235654403422358739678505705164771770043997911978466970263295500889794171343156703395546382916487920614340043903229000609973485677050397022152713772292440520988456316443753468532951303866181082256920212000750824864649908289233351736589192406643159754938503633933659274738581869079639832724262163525528275737821041039669564305836146099495364809454904417807419660442462148929999131337816672689722132290589330769444419576849369335967968005614246785108998860303333448365564289184539
e=7
def franklinReiter(n,e,a1,b1,c1,a2,b2,c2):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (a1*x+b1)^e - c1
    g2 = (a2*x+b2)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,a1,b1,c1,a2,b2,c2)

print(long_to_bytes(int(m)).hex())
#4e53534354467b61323430373434306566643666343139323861323262333463373761303966347d

第七步

我分为了两步

7.1求phin

板子用法：attack(n, e, 512, 2, 0.270,10)

512是n的因数的位数

2是n的因数的个数

0.270是d的那个范围

10可以表示深度，越大越准确但时间越久，一般取4没出就取10，这里取4是可以出的

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
from __future__ import print_function
import time

############################################
# Config
##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(mm//tt * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(mm//tt * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

def attack(N, e, factor_bit_length, factors, delta=0.25, m=1):
    x, y = ZZ["x", "y"].gens()
    A = N + 1
    f = x * (A + y) + 1
    X = int(RR(e) ** delta)
    Y = int(N^((factors-1)/factors))
    t = int((1 - 2 * delta) * m)
    x0, y0 = boneh_durfee(f, e, m, t, X, Y)
    z = int(f(x0, y0))
    if z % e == 0:
        phi = N +int(y0) + 1
        return phi

    return None


n = 11807668285253476335993112649125478311738138284032009521013160232275155591439056104050712447640428132619606976587476242139778581733169915977009541156271158342164308850183882293808973497182420010031579067660977663894542027297739371427053469215030263817360875451422844176774669484378609912250701562139454836788798283646984193408478412076837926365908454580066517380897820350918189254782926664771936070107395821284187885892036352109035393564580351743381904585469190706683218284347728580797326563996730184944085618477815023279614804702457729169640438408479963581615968900059881783129713048355206267321472950141238916990289
e = 5281486869323390978888423235641733430226678655686523392509714694751699050972120246916705000659875362083798615103093121939019773338011435050637066804667485505484551148317473841662442079996914658971301530910391768225029937660420184269526291001532582856000498690281601708552422507554114650938378386138884675333079129219306840932269967053765809850586002685750596186872500960539502358573116582308035530522367769717985694159855985288721479249298872468268929957454831663164937357314947859985362524031645431354657428639172589105754006273997415340441064909574647647141996659760272695449996972251425797398960494913207372272501
print(attack(n, e, 512, 2, 0.270,10))
#11807668285253476335993112649125478311738138284032009521013160232275155591439056104050712447640428132619606976587476242139778581733169915977009541156271158342164308850183882293808973497182420010031579067660977663894542027297739371427053469215030263817360875451422844176774669484378609912250701562139454836788580954283961789345480162099667001543891543639039785702888420923141077344358421051350061532584618771565302075962527648516570054467566143564854760959148274897390714017585220094430947903853829077089810614861107089070658414503772365171320735613805448738756377532942888788137666255740398790486415370724509249593956

7.2 知道phin和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
38
39
40
41
42
43
44
45
46
47
48
49
from random import randrange
from gmpy2 import gcd
from Crypto.Util.number import isPrime
from Crypto.Cipher import AES
import hashlib
def factorize_multi_prime(N, phi):
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2**i) == 0:
            sqrt_1 = pow(w, phi // (2**i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if isPrime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if isPrime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return list(prime_factors)
n= 11807668285253476335993112649125478311738138284032009521013160232275155591439056104050712447640428132619606976587476242139778581733169915977009541156271158342164308850183882293808973497182420010031579067660977663894542027297739371427053469215030263817360875451422844176774669484378609912250701562139454836788798283646984193408478412076837926365908454580066517380897820350918189254782926664771936070107395821284187885892036352109035393564580351743381904585469190706683218284347728580797326563996730184944085618477815023279614804702457729169640438408479963581615968900059881783129713048355206267321472950141238916990289
phi= 11807668285253476335993112649125478311738138284032009521013160232275155591439056104050712447640428132619606976587476242139778581733169915977009541156271158342164308850183882293808973497182420010031579067660977663894542027297739371427053469215030263817360875451422844176774669484378609912250701562139454836788580954283961789345480162099667001543891543639039785702888420923141077344358421051350061532584618771565302075962527648516570054467566143564854760959148274897390714017585220094430947903853829077089810614861107089070658414503772365171320735613805448738756377532942888788137666255740398790486415370724509249593956
     
print(factorize_multi_prime(n,phi))
p=109251812397373321369840755208338684181849016249638331267293943483115497998725084726738929391662966344551120589566300806536096548160787172237706693859608475141219078669813672240834436097740939389436503141021125884696328239129598176499232703067484613497368721713418450511690584287062214763737382684815118290807
q=108077550625030741628409221962586137835061924777093346742105484293996412425780528695135608131114083374334689339942402785929242548853421006289436932461307334151285188092694814125544224045160168464838500475686808324260061959555765821820470091607030229362222645403574544480356208327745262071320196731914549105527
c=7320983754394577422767542259069116006114676957581611253208089569490712064263822719681906219830045070027417890563005314255698660920759511532031914399521431010299257046526287119522646336307583924582732194043891855691431909500109014302908312283511965320377811140085483883126526462467293815637138718444001931483069474449989528839243687527037766658696775697609190493251942630904142633135051494201917324487853767845670807311896759009183844195818162749380637909781931403232226599915889508138332312516115335987268671038564169230604383642551512237979390401177728387916170497777974947392809240193434636218076335466512033333461
e=5281486869323390978888423235641733430226678655686523392509714694751699050972120246916705000659875362083798615103093121939019773338011435050637066804667485505484551148317473841662442079996914658971301530910391768225029937660420184269526291001532582856000498690281601708552422507554114650938378386138884675333079129219306840932269967053765809850586002685750596186872500960539502358573116582308035530522367769717985694159855985288721479249298872468268929957454831663164937357314947859985362524031645431354657428639172589105754006273997415340441064909574647647141996659760272695449996972251425797398960494913207372272501
d=invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)).hex())

[羊城杯 2020]INVITATIONS

题目

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
52
53
54
55
56
57
58
59
60
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
import gmpy2
import random



def pad(s,i):
    return i * pow(3,s.bit_length()) + s**2

def gen_N():
    return getPrime(512) * getPrime(512)


assert len(flag) == 54
invite = bytes_to_long(flag)

e_list = [random.choice([3,5,7]) for i in range(14)]
N_list = [gen_N() for i in range(14)]

with open('./invitations','w') as f:
    for i in range(14):
        invis = pow(pad(invite,i+1),e_list[i],N_list[i])
        f.write('Invitation%d: %d \n'%(i+1,invis))

    f.write('Wait a minute! \n')

    for i in range(14):
        f.write('[e%d,N%d]: [%d,%d]\n'%(i+1,i+1,e_list[i],N_list[i]))
"""
Invitation1: 2726880165485794753015221799903015469859604350960070462389832770775190258204902795671085685627736110579803076064313238826997962227132535666379117171603278182417820587346210511971127809627876548907651538393737303011542136469304569045407566630840981287558726831003180186144633381044057099863505591978316576331 
Invitation2: 52844103418322232725177561034428083147725292376614668718220523666259095447694889972949103379829470432332480992707892007073319952276490981511612735696207090391646476749895265951654074573797235607971038590694835782189124391368712277613425337912212240432011011071881837734857743183367019103096901117395938690572 
Invitation3: 129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823 
Invitation4: 56852637683122735164568970875066131746509133403072354742812890131597805562226047560392266004050592533316793038372256396537829143627478792510526346644756590135871716813976819138793368813440386409129373327577756689416990858633825538766694242123021009535005392002648416127869437948525458000795891155650312894218 
Invitation5: 24933581882539143383805596779774030477763512752520375486982562296903063067503747125713029403793101373585417342942950790457235350083784905974251188305010098928244056980941419687746319300184530161551239060873604405554973757867815783641391659818219177575212360602858057667033472530286856616676363511656764861866 
Invitation6: 7491476722927235473944826192371870577426352529433316210668760004930228302472920679959949471665143237333356259221787618020560963460668303766902416340056446225333025453011937952801159044781738493694911250765543392959285625650198325627539546777165439291150376527665779894748453633305704694635029402487576286720 
Invitation7: 46994515206702516116723205176259615067102717099690856936455392000070823814544052445278146449282379251128163008476565339875497253781717590664182753552262233895322322657625202522815172174432182181682631558679857615390973133346476079858014623412440411395083299226947371458955797627789607079672039131280242758091 
Invitation8: 8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214 
Invitation9: 8385766476371753553977800353128766303065572190592509929058486984964439147256960481698015327599879810752997804957814193113184978479627127131318723231581432235920975812354556190022727375961505764199831794239507708621401077801662954349957627630157786326057704380977697746043041515978455150985893713987598581167 
Invitation10: 25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080 
Invitation11: 9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346 
Invitation12: 42653412322252936189967169320174001935456500265020295381235749570735595316912049949245536609634786767873783560657460914097412643705264107040560389003526999720357122717443215007182355846769697457076620951388839672721527406861414375682603373503445636748304326212654026233985520038237509837611802457243967916967 
Invitation13: 50163996128508874413636370533324079468893191391677157815578286348174669089976633631417431754505804284298354381223186985949160012660340790440711469708712479223582014168361667639570586425626182863344576254691662799762136734638820942002509860333817967414572002225418810272184173820322912928927789061077468994953 
Invitation14: 55181712049788569218094734913693030675622116883683701002270524678292896232044695586872582672159854063365203462010143885417632291300773699604618481578372258936513301821561273604986211363808846581429372811764533701610119228124866223770584249909429743735157839245622925997548481946831963456454939343358587988983 
Wait a minute! 
[e1,N1]: [5,90361246179367799606636863352077187566064794796456461177972505143929614628873639223638940051613378291778175724735519020067052934403115774679961661481160141872257338930620863078688082915958381094674423803586734810828570206667419458295735288184697613296663226516640069281835035704453280781694226293902395215269]
[e2,N2]: [5,83202136479583179143205059354864808364257451670037867814548678142629716115373207061455185843132942837300718212806534861585785041547496145915392175827479376792813058845422044909477892978293495048968520853100992244672416436363272286740068846609018921112995562647093952700070707124842514243806528982910520604851]
[e3,N3]: [3,146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391]
[e4,N4]: [7,145212137982314671207105886550619275956842416412937060552686822638155412950680057688522218990023473104787006548449644240065948769143660097622695125682017688804838701293738298008178105057147539522368965730223561911750657089352591376219016726977232279206451303896573325330139830440927228125810665303608828462177]
[e5,N5]: [5,69335368232766044823545542187513771534967902179150417021053554241638095909666122935053210964003511014870892979205875153115719406287728162111662254890513324436473313860142126335197489227724691042286796058111753972895113145188906829975189506125997319609609974126645475084944238417929532560409919420929255247813]
[e6,N6]: [5,93889543065608951579836429313520485233295158467296710329997599807630401722519056218864031741675898621375735347229494633577571323057785261271373295860331130588582231771193563731092603614818963592931492474988532068227153492022582339704874613690044001529412669510094771064646843676765163737757104643318364446839]
[e7,N7]: [7,66174700839404221060785862467924299511645570336361033287335855493589093141782896451863402373425798838446538369142584932156150350565382116869446083154097803842190010954019565857767923584979615770650706675094209251111816761431713779074557571353022624477001770694207393369796369620048999514683357963227119554487]
[e8,N8]: [3,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029]
[e9,N9]: [5,72454311940971803130612024751128556938725737742029062979349607787083978826668706819793864356790325653817555839762732164812521831864626411495002267399139766907846534945632792910468487287154661692733986224962564621615361536373173705359255153606552352581704159462310354407361311378558150604159961029937052901709]
[e10,N10]: [3,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901]
[e11,N11]: [3,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
[e12,N12]: [7,88063052818271125442049408332053226451497067720511502513828848476569985821115735898897947439175727789641390104005400308936768495751619165683456550165811034670341697022370415202614387373196086237042577737857259724530596416810462125219296930758592032765843338961894697491961439584875235274163072466474940670589]
[e13,N13]: [5,86478932133708863968749977073639049451666195461247968321317885106346907736572028122496476049748246757185316498949163898915427948597498506162230927380667345132742891001640364064647368394822175742973968167028656790729030556005407153405955458636780270673780720333871959638216946584461925553782697695137132507853]
[e14,N14]: [7,137641493263428303662262187582231235637921833879366309318941383348412296182252654397496377642861646991438721153462001357875169325595544056465299787575422581289053630686684843044593163904089201855371863459503176022957832807726507152235818181000484878683030989944063049622694810207054366378176225221479695833371]
"""

分析

加密过程：

从3,5,7中随机选择14次，当作e，然后正常生成14个n。

循环14次，每次先对m进行pad，pad的值跟i和flag长度有关。这里flag长度是固定值。

根据flag头“GWTH{”（比赛时肯定能知道），flag长度，进行计算。

pad的过程可以当作是线性填充，不过对m进行了平方，这不影响。

pad之后就是正常的rsa加密。

解密过程：

我找了xenny师傅的模板（可以直接pip install xenny，然后去site-packages里面找），还有[RSA Coppersmith相关攻击 | NonupleBroken](https://nonuplebroken.com/2019/11/21/RSA Coppersmith相关攻击/#broadcast-attack-with-linear-padding)这里的模板，没有理解原理，我就直接上结论了。

这里先放几篇文章

paper:RSA-survey.pdf (stanford.edu)

Crypton/RSA-encryption/Attack-Hastad-Broadcast/README.md at master · ashutosh1206/Crypton (github.com)

先放一下步骤

Exploit in a Nutshell:

  1. Calculate N = n1n2…
  2. Calculate each element T[j] as per the above conditions using CRT
  3. Assign P. = PolynomialRing(Zmod(N))
  4. g[j] = (i*(2^m) + x)^e - c, where the message is padded using the above conditions
  5. Assign g = Sum_of(T[j] * g[j])
  6. Check if g is a monic polynomial, if not transform it into a monic polynomial
  7. Find small roots of g and check if that is the flag

首先对同一个消息m进行了多次加密，虽然这里对m进行了线性填充，无法直接使用中国剩余定理，但是有多组密文，我们仍然可以求解，这也就是SMUPE问题。在这题中，我们先进行了预处理（参考xenny师傅），然后调用了smupe函数进行求解。

根据 Alexander May and Maike Ritzenhofen 于 2008 年的结论，对于 SMUPE-problem（也就是这题的问题），当 ∑i=1k1ei>1\sum_{i=1}^k \frac{1}{e_i} > 1 时可解。所以我仍然借助了xenny师傅的预处理，利用x_change函数求解满足条件的几组密文。

1、计算N

2、利用CRT计算T[j]，在原理解释说t[i]=1 if i=j, t[i]=0 if i≠j，所以我这里就依葫芦画瓢了。

3、建立在N下的模多项式

4、根据加密使用的线性填充，计算gi，顺便乘上T[j]

5、monic将g的首项转为1

6、最后通过small_roots求解m

exp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
from functools import reduce
import gmpy2

_sage_const_1 = Integer(1);
_sage_const_0 = Integer(0);
_sage_const_1p = RealNumber('1.');
_sage_const_1000 = Integer(1000);
_sage_const_7p = RealNumber('7.');
_sage_const_8 = Integer(8);
_sage_const_2 = Integer(2)
__author__ = 'x3nny'
x_calc = lambda x, n: ((n - x) // x + _sage_const_1, (n - x) % x)
def x_change(e_list):
    e_list = [(i, e_list[i]) for i in range(len(e_list))]
    e_list = sorted(e_list, key=lambda x: x[_sage_const_1])
    sum = max_i = _sage_const_0
    indexs = []
    exponents = []
    for index, exp in e_list:
        sum += _sage_const_1 / exp
        indexs.append(index)
        if exp > max_i:
            max_i = exp
        if sum > _sage_const_1p:
            break
    for i in range(len(indexs)):
        exponents.append(x_calc(e_list[i][_sage_const_1], max_i))
    return indexs, exponents


def modinv(a, m):
    return gmpy2.invert(gmpy2.mpz(a), gmpy2.mpz(m))
def CRT(n, a):
    N = reduce(lambda x, y: x * y, n)
    result = 0
    for n_i, a_i in zip(n, a):
        p = N / n_i
        s = modinv(p, n_i)
        result += a_i * s * p
    return result % N

def smupe(c_list, n_list, a_list, b_list, e_list, bits=_sage_const_1000, beta=_sage_const_7p / _sage_const_8):
    indexs, exponents = x_change(e_list)
    
    N = reduce(lambda x, y: x * y, [n_list[i] for i in indexs])
    
    T=[]
    n=[]
    tj=[]
    for i in range(len(indexs)):
        n.append(n_list[indexs[i]])
        tj.append([0 for i in range(len(indexs))])
        tj[i][i]=1
    for i in range(len(indexs)):
        T.append(CRT(n,tj[i]))
        
    P.<x> = PolynomialRing(Zmod(N))
    g=0
    for i in range(len(indexs)):
        g+=((a_list[indexs[i]] * x + b_list[indexs[i]]) ** e_list[indexs[i]] - c_list[indexs[i]])*T[i]
    g = g.monic()
    m=g.small_roots(X=2**bits, beta=beta)
    if m:
        return m[_sage_const_0]
    return None


Invitation1 = 2726880165485794753015221799903015469859604350960070462389832770775190258204902795671085685627736110579803076064313238826997962227132535666379117171603278182417820587346210511971127809627876548907651538393737303011542136469304569045407566630840981287558726831003180186144633381044057099863505591978316576331 
Invitation2 = 52844103418322232725177561034428083147725292376614668718220523666259095447694889972949103379829470432332480992707892007073319952276490981511612735696207090391646476749895265951654074573797235607971038590694835782189124391368712277613425337912212240432011011071881837734857743183367019103096901117395938690572 
Invitation3 = 129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823 
Invitation4 = 56852637683122735164568970875066131746509133403072354742812890131597805562226047560392266004050592533316793038372256396537829143627478792510526346644756590135871716813976819138793368813440386409129373327577756689416990858633825538766694242123021009535005392002648416127869437948525458000795891155650312894218 
Invitation5 = 24933581882539143383805596779774030477763512752520375486982562296903063067503747125713029403793101373585417342942950790457235350083784905974251188305010098928244056980941419687746319300184530161551239060873604405554973757867815783641391659818219177575212360602858057667033472530286856616676363511656764861866 
Invitation6 = 7491476722927235473944826192371870577426352529433316210668760004930228302472920679959949471665143237333356259221787618020560963460668303766902416340056446225333025453011937952801159044781738493694911250765543392959285625650198325627539546777165439291150376527665779894748453633305704694635029402487576286720 
Invitation7 = 46994515206702516116723205176259615067102717099690856936455392000070823814544052445278146449282379251128163008476565339875497253781717590664182753552262233895322322657625202522815172174432182181682631558679857615390973133346476079858014623412440411395083299226947371458955797627789607079672039131280242758091 
Invitation8 = 8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214 
Invitation9 = 8385766476371753553977800353128766303065572190592509929058486984964439147256960481698015327599879810752997804957814193113184978479627127131318723231581432235920975812354556190022727375961505764199831794239507708621401077801662954349957627630157786326057704380977697746043041515978455150985893713987598581167 
Invitation10 = 25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080 
Invitation11 = 9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346 
Invitation12 = 42653412322252936189967169320174001935456500265020295381235749570735595316912049949245536609634786767873783560657460914097412643705264107040560389003526999720357122717443215007182355846769697457076620951388839672721527406861414375682603373503445636748304326212654026233985520038237509837611802457243967916967 
Invitation13 = 50163996128508874413636370533324079468893191391677157815578286348174669089976633631417431754505804284298354381223186985949160012660340790440711469708712479223582014168361667639570586425626182863344576254691662799762136734638820942002509860333817967414572002225418810272184173820322912928927789061077468994953 
Invitation14 = 55181712049788569218094734913693030675622116883683701002270524678292896232044695586872582672159854063365203462010143885417632291300773699604618481578372258936513301821561273604986211363808846581429372811764533701610119228124866223770584249909429743735157839245622925997548481946831963456454939343358587988983 

e1,N1 = [5,90361246179367799606636863352077187566064794796456461177972505143929614628873639223638940051613378291778175724735519020067052934403115774679961661481160141872257338930620863078688082915958381094674423803586734810828570206667419458295735288184697613296663226516640069281835035704453280781694226293902395215269]
e2,N2 = [5,83202136479583179143205059354864808364257451670037867814548678142629716115373207061455185843132942837300718212806534861585785041547496145915392175827479376792813058845422044909477892978293495048968520853100992244672416436363272286740068846609018921112995562647093952700070707124842514243806528982910520604851]
e3,N3 = [3,146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391]
e4,N4 = [7,145212137982314671207105886550619275956842416412937060552686822638155412950680057688522218990023473104787006548449644240065948769143660097622695125682017688804838701293738298008178105057147539522368965730223561911750657089352591376219016726977232279206451303896573325330139830440927228125810665303608828462177]
e5,N5 = [5,69335368232766044823545542187513771534967902179150417021053554241638095909666122935053210964003511014870892979205875153115719406287728162111662254890513324436473313860142126335197489227724691042286796058111753972895113145188906829975189506125997319609609974126645475084944238417929532560409919420929255247813]
e6,N6 = [5,93889543065608951579836429313520485233295158467296710329997599807630401722519056218864031741675898621375735347229494633577571323057785261271373295860331130588582231771193563731092603614818963592931492474988532068227153492022582339704874613690044001529412669510094771064646843676765163737757104643318364446839]
e7,N7 = [7,66174700839404221060785862467924299511645570336361033287335855493589093141782896451863402373425798838446538369142584932156150350565382116869446083154097803842190010954019565857767923584979615770650706675094209251111816761431713779074557571353022624477001770694207393369796369620048999514683357963227119554487]
e8,N8 = [3,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029]
e9,N9 = [5,72454311940971803130612024751128556938725737742029062979349607787083978826668706819793864356790325653817555839762732164812521831864626411495002267399139766907846534945632792910468487287154661692733986224962564621615361536373173705359255153606552352581704159462310354407361311378558150604159961029937052901709]
e10,N10 = [3,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901]
e11,N11 = [3,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
e12,N12 = [7,88063052818271125442049408332053226451497067720511502513828848476569985821115735898897947439175727789641390104005400308936768495751619165683456550165811034670341697022370415202614387373196086237042577737857259724530596416810462125219296930758592032765843338961894697491961439584875235274163072466474940670589]
e13,N13 = [5,86478932133708863968749977073639049451666195461247968321317885106346907736572028122496476049748246757185316498949163898915427948597498506162230927380667345132742891001640364064647368394822175742973968167028656790729030556005407153405955458636780270673780720333871959638216946584461925553782697695137132507853]
e14,N14 = [7,137641493263428303662262187582231235637921833879366309318941383348412296182252654397496377642861646991438721153462001357875169325595544056465299787575422581289053630686684843044593163904089201855371863459503176022957832807726507152235818181000484878683030989944063049622694810207054366378176225221479695833371]

e = []
n = []
c = []
for i in range(14):
    e.append(eval('e%d' % (i+1)))
    n.append(eval('N%d' % (i+1)))
    c.append(eval('Invitation%d' % (i+1)))
flag=b'GWTH{'+b'x'*49
flag=bytes_to_long(flag)
bits=flag.bit_length()
b = [(i+1)*(3**bits) for i in range(14)]
a = [1 for i in range(14)]
m = smupe(c, n, a, b, e_list=e)
print(long_to_bytes(iroot(int(m), 2)[0]))

#b'GWHT{e959e3f8e7242954b43e1b91de9886e1}Welc0metomyp4rty'
#NSSCTF{e959e3f8e7242954b43e1b91de9886e1}

[鹤城杯 2021]BabyRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
"""
1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
40812438243894343296354573724131194431453023461572200856406939246297219541329623
21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
"""

分析

先放一篇文章，讲得比较好

RSA中coppersmith定理的应用条件_sagemath coppersmith-CSDN博客

我们知道p的高300位，和q的低265位

经过计算

p∗q=nmod(2265)pl∗ql=nmod(2265)pl=n∗ql−1mod(2265)p*q=n\quad mod(2^{265})\\ p_l*q_l=n\quad mod(2^{265})\\ p_l=n*q_l^{-1}\quad mod(2^{265})

我们也可以知道p的低265位，这样我们就知道p的565位，还有459位未知，无法直接用coppersmith求解，只有454未知时我们才可以求解（具体原理可以看上面那篇文章），所以还有5位未知，我们可以爆破一下

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#sage
from Crypto.Util.number import *
from gmpy2 import *
hint1=1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2=40812438243894343296354573724131194431453023461572200856406939246297219541329623
n=21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c=19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e=65537

pl = n*invert(hint2, 2**265) % 2**265
pbar = (hint1 << 724) + pl
PR.<x> = PolynomialRing(Zmod(n))

for i in range(2**5):
    f = pbar + (x*2**265*2**5) + (i<<265)
    f = f.monic()
    pp = f.small_roots(X=2^454, beta=0.4)
    if pp: 
        break

p = int(pbar + (pp[0]*2**265*2**5) + (i<<265))
print(long_to_bytes(int(pow(c, invert(e,p-1), p))))
#b'flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}'
#NSSCTF{ef5e1582-8116-4f61-b458-f793dc03f2ff}

[GWCTF 2019]BabyRSA2

题目

没有题目，nc

分析

又是一个写到疯的题目

而且不能手动输入，只能借助pwntools来传输，所以被迫要去搞了一下wsl的sage环境，这样就方便许多了，下面放几篇教程。

wsl的安装：

(搞到最后一步直接用Microsoft Store安装Ubuntu)

【WSL】在WIN11安装并使用Linux子系统（Ubuntu）_wsl ubuntu-CSDN博客

sagemath环境：

sagemath 入门笔记 | 独奏の小屋 (hasegawaazusa.github.io)

搞完之后你应该能够在vscode里连接上ubuntu了，并且可以执行sage代码

可以先尝试输入sage，进入sage终端，然后pip安装好pwntools和Crypto（这个我是直接从本地复制过去了）

python3报错：ModuleNotFoundError: No module named ‘Crypto‘_modulenotfounderror: no module named 'cryptography-CSDN博客

之后运行的脚本直接在终端中输入 sage [filename].sage

搞完上面之后就可以开始，建议直接照着exp学，反正我好多原理都没搞懂

除了最后一个，其他的m都不用转成字节

第一部分

需要爆破一下hash，一共需要爆破5个字符，我是看wp里才看到字符范围是数字和小写字母，我一开始还以为题目给的+last是十六进制，原理就是字符

第二部分

最简单的共模攻击

第三部分

小e，直接开根

第四部分

p高位攻击，直接上模板了

第五部分

（最后两部分我直接上xenny师傅的exp了，已经写疯了，不想看了）

共享素数，但是逆元不存在，可以求的gcd(ei,ϕ(n)=14)gcd(e_i,\phi(n_)=14)

我们可以求出m14但这个直接无法开根

之后我们发现gcd(7,q1q2)=1gcd(7,q_1q_2)=1这样我们就可以求出m2

d3∗7=1mod((q1−1)(q2−1))m2=m14∗d3mod(q1q2)d_3*7=1\quad mod((q_1-1)(q_2-1))\\ m_2=m^{14*d_3}\quad mod(q_1q_2)

之后对m2开根就行了

第六部分

是m的线性填充攻击，但是不知道填充参数

根据exp看，应该是

M1=mM2=m+rM_1=m\\ M_2=m+r

找了xenny师傅exp的源码

先利用CoppersmithShortPadAttack求出填充的r，然后再利用franklinReiter就可以求解了

exp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from pwn import *
from hashlib import md5
from Crypto.Util.number import *
from gmpy2 import *
from sage.all import *
p = remote("node4.anna.nssctf.cn", 28932)

p.recvuntil(b'md5(str + ')

last = p.recv(4).decode()
p.recvuntil(b'[0:5] == ')
known_md5 = p.recv(5).decode()

temp = "0123456789qwertyuiopasdfghjklzxcvbnm"


def calc_md5():
    for i in temp:
        for j in temp:
            for k in temp:
                for l in temp:
                    for m in temp:
                        a = (i + j + k + l + m + last).encode()
                        if str(md5(a).hexdigest())[0:5] == known_md5:
                            return i + j + k + l + m


all_md5 = calc_md5()
p.sendlineafter(b'Give me xxxxx: ', all_md5.encode())

p.recvuntil(b'n = ')
n = int(p.recvline().decode().strip())
p.recvuntil(b'e1 = ')
e1 = int(p.recvline().decode().strip())
p.recvuntil(b'e2 = ')
e2 = int(p.recvline().decode().strip())
p.recvuntil(b'c1 = ')
c1 = int(p.recvline().decode().strip())
p.recvuntil(b'c2 = ')
c2 = int(p.recvline().decode().strip())

_, s1, s2 = gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n

p.sendlineafter(b'Please input your answer:', str(m).encode())

p.recvuntil(b'n = ')
n = int(p.recvline().decode().strip()[2:-1], 16)
p.recvuntil(b'e = ')
e = int(p.recvline().decode().strip())
p.recvuntil(b'c = ')
c = int(p.recvline().decode().strip()[2:-1], 16)

m = iroot(c, e)[0]
p.sendlineafter(b'Please input your answer:', str(m).encode())

p.recvuntil(b'n = ')
n = int(p.recvline().decode().strip()[2:-1], 16)
p.recvuntil(b'e = ')
e = int(p.recvline().decode().strip()[2:],16)
p.recvuntil(b'p>>448 = ')
high_p = int(p.recvline().decode().strip()[2:-1], 16)
p.recvuntil(b'c = ')
c = int(p.recvline().decode().strip()[2:-1], 16)

unknown_bits=448
high_p=high_p<<unknown_bits
R.<x> = PolynomialRing(Zmod(n))
f = high_p + x
x = f.small_roots(X = 2^unknown_bits,beta = 0.4)
pp=int(high_p+x[0])
m=pow(c,invert(e,(pp-1)*(n//pp-1)),n)
p.sendlineafter(b'Please input your answer:', str(m).encode())

p.recvuntil(b'n1 = ')
n1 = int(p.recvline().decode().strip()[2:-1],16)
p.recvuntil(b'n2 = ')
n2 = int(p.recvline().decode().strip()[2:-1],16)
p.recvuntil(b'e1 = ')
e1 = int(p.recvline().decode().strip()[2:],16)
p.recvuntil(b'e2 = ')
e2 = int(p.recvline().decode().strip()[2:],16)
p.recvuntil(b'c1 = ')
c1 = int(p.recvline().decode().strip()[2:-1],16)
p.recvuntil(b'c2 = ')
c2 = int(p.recvline().decode().strip()[2:-1],16)

pp=gcd(n1,n2)
q = n1 // pp

phi = (pp-1)*(q-1)
phi2 = (pp-1)*(n2 // pp-1)
d1 = invert(e1 // 14, phi)
d2 = invert(e2 // 14, phi2)
m1 = powmod(c1, d1, n1)
m2 = powmod(c2, d2, n2)
m = crt([m1,m2], [n1,n2])
assert m % n1 == m1
assert m % n2 == m2
n = q * (n2 // pp)
d = invert(7, (q-1)*(n2//pp-1))
m = powmod(m, d, n)
m = iroot(m, 2)[0]
p.sendlineafter(b'Please input your answer:', str(m).encode())


p.recvuntil(b'n = ')
n = int(p.recvline().decode().strip())
p.recvuntil(b'e = ')
e = int(p.recvline().decode().strip())
p.recvuntil(b'c1 = ')
c1 = int(p.recvline().decode().strip())
p.recvuntil(b'c2 = ')
c2 = int(p.recvline().decode().strip())

_sage_const_0 = Integer(0); _sage_const_1 = Integer(1); _sage_const_30 = Integer(30); _sage_const_2 = Integer(2); _sage_const_0p5 = RealNumber('0.5'); _sage_const_25 = Integer(25)
def CoppersmithShortPadAttack(e,n,C1,C2,eps=_sage_const_1 /_sage_const_30 ):
    P = PolynomialRing(ZZ, names=('x', 'y',)); (x, y,) = P._first_ngens(2)
    ZmodN = Zmod(n)
    g1 = x**e - C1
    g2 = (x+y)**e - C2
    res = g1.resultant(g2)
    P = PolynomialRing(ZmodN, names=('y',)); (y,) = P._first_ngens(1)
    rres = _sage_const_0 
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y**(res.exponents()[i][_sage_const_1 ]))

    diff = rres.small_roots(epsilon=eps)
    if diff:
        return diff[_sage_const_0 ]
    return None
r=CoppersmithShortPadAttack(e, n, c1, c2)

def franklinReiter(n,e,r,c1,c2):
    R = Zmod(n)['X']; (X,) = R._first_ngens(1)
    f1 = X**e - c1
    f2 = (X + r)**e - c2
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[_sage_const_0 ])
def compositeModulusGCD(a, b):
    if(b == _sage_const_0 ):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)
m=franklinReiter(n,e,r,c1,c2)
m=long_to_bytes(m)
m=m.decode()[16:]
p.sendlineafter(b'Please input the password:', str(m).encode())


p.interactive()

[深育杯 2021]GeGe

题目

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 *
import gmpy2
from flag import flag

def encrypt(plaintext):
    p = getStrongPrime(3072) 
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        c = (r * h + m * f) % p
        return (h, p, c)

h, p, c = encrypt(flag)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")

"""
h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672
"""

分析

一道格的入门题，格的学习我是看这位师傅的，具体原理我也不太懂，纯纯的脚本小子

https://dexterjie.github.io/2023/07/28/初识格

https://dexterjie.github.io/2023/07/29/格密码入门

我们知道：

h=f−1∗gmod(p)c=r∗h+m∗fmod(p)h=f^{-1}*g\quad mod(p)\\ c=r*h+m*f \quad mod(p)

可以求得：

f∗h=k∗p+gg=f∗h−k∗p构造格：L=(1h0p)(f,k)L=(f,g)f*h=k*p+g\\ g=f*h-k*p\\ 构造格： L=(\begin{matrix} 1 & h\\ 0 & p \end{matrix})\\ (f,k)L=(f,g)\\

具体原理我也不会（哭

c=r∗f−1∗g+m∗fmod(p)f∗c=r∗g+m∗f2mod(p)f∗cmod(p)=m∗f2mod(g)m=(f∗cmod(p))∗(f2)−1mod(g)c=r*f^{-1}*g+m*f\quad mod(p)\\ f*c=r*g+m*f^2 \quad mod(p)\\ f*c\quad mod(p)=m*f^2\quad mod(g)\\ m=(f*c\quad mod(p))*(f^2)^{-1}\quad mod(g)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#sage
from Crypto.Util.number import *
from gmpy2 import *
h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

L = matrix(ZZ, [[1, h],[0, p]])
v = L.LLL()[0]
f, g = map(abs, v)
m = ((f*c%p)*invert(f*f,g))%g
print(long_to_bytes(m))
#b'Sangfor{pfa2s1f65ads4fwev1s2d3v1cxxavqes}'
#NSSCTF{pfa2s1f65ads4fwev1s2d3v1cxxavqes}

[MTCTF 2021 final]ezRSA

题目\

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

flag = open('flag.txt', 'rb').read()
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(256)
M = getPrime(5048)
hint = (p - 297498275426) * inverse(s, M) % M
t = open("message.txt", "w")
t.write(f"e = {e}\nc = {c}\nn = {n}\nM = {M}\nhint = {hint}\n")
t.close()
"""e = 65537
c = 11223534598141520071392544441952727165225232358333005778273904279807651365082135278999006409297342081157139972503703772556228315654837441044781410960887536342197257046095815516053582104516752168718754752274252871063410625756822861003235434929734796245933907621657696650609132419469456238860601166224944487116
n = 99499509473364452726944770421623721217675378717234178828554602484867641740497277374806036356486848621495917213623425604565104435195783450029879177770305417469850119739921527698744700219067563802483159458398895082044997907953256062342593605652927874232404778144112740505724215742062859322375891810785229735653
M = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087
"""

分析

我们知道：

hint=(p−a)∗s−1mod(M)hint=(p-a)*s^{-1}\quad mod(M)

将p-a当作一个整体

hint∗s=p+k∗Mp=hint∗s+k∗M构造格L=(1hint0M)(s,k)L=(s,p)hint*s=p+k*M\\ p=hint*s+k*M\\ 构造格L=(\begin{matrix} 1 & hint\\ 0 & M \end{matrix})\\ (s,k)L=(s,p)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from gmpy2 import *
e = 65537
c = 11223534598141520071392544441952727165225232358333005778273904279807651365082135278999006409297342081157139972503703772556228315654837441044781410960887536342197257046095815516053582104516752168718754752274252871063410625756822861003235434929734796245933907621657696650609132419469456238860601166224944487116
n = 99499509473364452726944770421623721217675378717234178828554602484867641740497277374806036356486848621495917213623425604565104435195783450029879177770305417469850119739921527698744700219067563802483159458398895082044997907953256062342593605652927874232404778144112740505724215742062859322375891810785229735653
M = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087

L = matrix(ZZ, [[1, hint],[0, M]])
v = L.LLL()
v = v[0]
s, p = map(abs, v)
p=p+297498275426
print(long_to_bytes(int(pow(c,invert(e,(p-1)*(n//p-1)),n))))
#b'flag{388bb794-ccda-f02e-79c6-8e44659c2481}'
#NSSCTF{388bb794-ccda-f02e-79c6-8e44659c2481}

[羊城杯 2021]Easy_Rsa

题目

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

def gen_prime(nbits, gamma):
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                q = 2 * g * b + 1
            return p, q

def encrypt(nbits, gamma):
    p, q = gen_prime(nbits, gamma)
    n = p * q
    e = getPrime(16)
    while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
        e = getPrime(16)
    m = bytes_to_long(flag)
    c = pow(m, e, n)
    return n, e, c

n, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c

# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

分析

分析了半天，发现还是只会照搬wp

PollardRho 算法：

【快速因数分解】Pollard’s Rho 算法 - RioTian (cnblogs.com)

优化：方法来自Cryptanalysis of RSA and It’s Variants的Section 11.2 Factoring the Modulus

将x2+1x^2+1改成了xn−1+3mod(n)x^{n-1}+3\quad mod(n)

这个优化方法的原理我没找到

exp

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

f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668
e = 58337

p,q = phllard_rho(n)
d = invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
#b'SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}'
#NSSCTF{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}

[TSGCTF 2021]Minimalists_Private

题目

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
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')
"""
#requirements:pycryptodome == 3.9.9

N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

"""

分析

已知

aL=1mod(N)e∗d=1mod(L)a^L=1\quad mod(N)\\ e*d=1\quad mod(L)

根据费马小定理可以知道L=ϕ(N)kL=\frac{\phi(N)}{k}

又有

L2≤10000∗N(ϕ(N)k)2≤10000∗p∗qϕ(N)2≤10000∗p∗q∗k2L^2≤10000*N\\ (\frac{\phi(N)}{k})^2≤10000*p*q\\ \phi(N)^2≤10000*p*q*k^2

因为ϕ(N)≈N\phi(N)≈N

所以：

N2<10000∗p∗q∗k2N<10000∗k2N^2<10000*p*q*k^2\\ N<10000*k^2

可以估计k很大，那么根据前面的推导ϕ(N)=L∗k\phi(N)=L*k就说明了p-1和q-1有一个较大的因子

然后xenny师傅说还是可以用PollardRho，我还是不理解，所以是p-1和q-1有一个较大的因子就可以用这个方法咯？

跟上题exp完全一样

exp

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

N=1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151
e=65537
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1
p,q=phllard_rho(N)
print(long_to_bytes(int(pow(c,invert(e,(p-1)*(q-1)),N))))
#b"TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}"
#NSSCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}
ctf > wp
#Crypto #RSA #Xenny的RSA题单
Xenny的RSA题单
http://example.com/2024/12/05/XennyRSA/
作者
Naby
发布于
2024年12月5日
许可协议