2023技能兴鲁

山东省技能兴鲁网络安全大赛——Crypto

babyRSA

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

flag = 'flag{I\'m not gonna tell you the FLAG}' # 这个肯定不是FLAG了,不要交这个咯

p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))


e1 = 3247473589
e2 = 3698409173

n = p*q

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


# flag1= 295658788074157816670393593671184451782123605135184996662528766686642109492132533952160456440919197939935742027629210419312032730004032666912404179229952394343569590488768472800784830058534578639706805456277578757250365834591813481786084959844340418320620440636997732915872346619679993987903742079972676425404864295283955565746004124045155664762158516005326368384488346997494926539295740248007606864906884407198601326915643000764477435205579583836917598642053869541648731754384026407310786288997756775232852732033054591953078116290088267188296560877481534143707414153749140670404213262630122369941889862912426176115220410931992046973925991075473656781794097329513119548617920256625579072719981729556158392454956362838720993254919638177786730004086883044525967823454986241038123671907279715773848673713008902432841449556980494600938989397567019338970200872333713986608537678650318511128703055185979834233315117153115613952940778789222515375743186066883492596068186378372611075958909412662251913621375996518671118244409393829141365207153662416265238312206577474940661548038715230313608405518108581922154335405303862701783678336161505643508831482409054761542959278392940037561736468155509922530420964726953308604138731805543997557197893
# flag2= 219454357017359138238563345020257296433275019950745269658921329153689267055871241202626317639487122341365759606018366576305678949982408366815977617307888894995289951707241009621444691307275542686770303994110416384086739599181934011812163156338859395115724413628620575935425221522079154607411877822646179457455118804970038865452163833416447505142114976758532806787419762250921421272492466133659234602794242531776209324085944417173098820895755851386042954303555790085402616519592065446023510096773546730662074307900123349548340507067971393642039476326402523930789953483843698593104578179169624886357604650615249286150367204109726460230037005175927865466199600272190112483494387929732049738312695796015009178606906549093365261114132002222704510637261038978031857378729856467918978246977163353146981239215886053379980533235786905270211605457443266127512667882149285155542735532327780898540341696557860555884277608448996773250847560675650046440569736010800155992053362696097992699863059686881689842065077997427372972290872427656847223849769329713841670853267584161386494525686204330028142217737052411422895042170169703550774908415280261731967511925122636118468176645781785352430657090024109246103061415446942211482659025722233229083093876
# n= 549785700554963543393222974982211136067042846536450239199968863551137077564447156832697813202963334596948298760762991663065504535035143397250208506445202607659676332816610122258862787906629525548439909792727593939957178783466989816894454522630301104349317697612174888605090061231211194974337772507249418567229560145454791075929946332668360553910328900103264562348881791004831033587660163923517440406942993348972589262051083908075790422096042338651001937740085414301019827335549437397656318095919875053213333008551761167437683250592542156348138055482054331330609375930693247365749085041596578748797801601289693449629548744535914348450016287545136436964138806081283470239420969311905998245715160353982174880912315601876305613349276824998688275587308133069178764001924866079232824850209407236694426779262951463035278887804883917516580169051530590466082511045503107508117656821592538792566264160105940730326929474477787053681516844548383814388361089499629312831727731267796167205124844987064389097138747938870221504684958713047985374714612321540288239995935347905120710583169131356970267386562665138437631517802641426575996558648777831102462652517305151412695166331935115971277205305816897886952646432233312318756155702046584205507027737

很常规的共模攻击

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

c1=
c2=
n=
e1 = 3247473589
e2 = 3698409173

t = gmpy2.gcd(e1,e2)
if t == 1:
s,x,y = gmpy2.gcdext(e1,e2)
m = (pow(c1,x,n)*pow(c2,y,n))%n
print(long_to_bytes(m))
else:
s,x,y = gmpy2.gcdext(e1,e2)
k = 0
while 1:
m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n)+k*n)%n,t)
if m[1]:
print(long_to_bytes(m[0]))
break
else:
k += 1

# flag{baby_r3a_sierting_2023}

EasyRSA

感觉是为了赞助商出的一道题

关注公众号,然后获得公钥pem的数据,密文,然后回答一个问题之后获得提示(私钥pem的数据)

public.pem:

1
2
3
-----BEGIN RSA PUBLIC KEY-----
MIGJAoGBAKOSX8AR8/CsqasPfC7VL5aJzic8W9KFI1920SHhEhmcWd7yp5Dl9UfXgzLHIIZJExd7D1CwIxAMHANHV6qF/7FEedwEMHusBxbAWsjXQUGFeEMmzo+SUVbbRnDSw/jZwCNoofQfukVO7+5CBzV5S/N5WDTk+8bvwfrDDA9AHdW5AgMBAAE=
-----END RSA PUBLIC KEY-----

private.pem

1
2
3
-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCjkl/AEfPwrKmrD3wu1S+Wic4nPFvShSNfdtEh4RIZnFne8qeQ5fVH14MyxyCGSRMXew9QsCMQDBwDR1eqhf+xRHncBDB7rAcWwFrI10FBhXhDJs6PklFW20Zw0sP42cAjaKH0H7pFTu/uQgc1eUvzeVg05PvG78H6wwwPQB3VuQIDAQABAoGADZ61jFeyWTr3UcATVg74TG+jE89J0gi1/k/1b/2+tRU4woCwBTewqc+/I+5Cvgu9pDnh95UDBmYLuxYorZFEzgrSa3rZ5y7OFQZl9nXapt2LttBXoQaWf3jtyslsGmfNi/VuNgKaiiVwINhVG8NeIFzzAB3AqNDitHlKDalkKZECQQDN1lZKV8bximZNDVL9CajmdE6f3DobYgGNvOXsOS4Qkzx+/3LvAbqSiiiel5V08pBIG18DRIpxBRN57z8fbJxlAkEAy28zeeMeb3ZFL7/iyosQ8RWrz3/BxlUtREh9GSplRa7EJtjm852IQCk98lg2HR++tuugmdtVAS0lxd/UVDXMxQJAFaVwtai9dzFCyN+Z1pppdLLOgek7Ax4vY6R12X255mxVdFWQ1Kmt4TM+Sk9OnFnV6n9WYpWWqYQLJEuQq9FUMQJAe6Vt+yJhCEwxRxFw7bxSosWSNL8o7rwslDke1+HdxdmwXRAuZ1mTS7QFc7vLwC3gQ9u5NGqMIvfm4nrl2f0NJQJAJrOQDrZX/KpYAnFmW8IGXxkcJrtdB2Xi9VN1WdC9r4QGz28X5ScH0o9mcYVxaDxzNU7A9DPiRL28fAltiGdJLg==
-----END RSA PRIVATE KEY-----

读取即可获得n,然后求解

密文:

1
QhS9n7TkavmU8E4CFa872ZzqIq/NG/agtCkxQBzB0/E1PDZRv6otOYxBLsxwd/7h0fPkYYMCpPt4nXqYBGQ/n8/F3q3spV94+IFs7+CjyybUvAQg8MXLgSTzVt+ua0Ub0/et5/7Q1xAcgzT3/jWHwjklEAykdpSYMAqv5PQrhT4=

exp:

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

c = "QhS9n7TkavmU8E4CFa872ZzqIq/NG/agtCkxQBzB0/E1PDZRv6otOYxBLsxwd/7h0fPkYYMCpPt4nXqYBGQ/n8/F3q3spV94+IFs7+CjyybUvAQg8MXLgSTzVt+ua0Ub0/et5/7Q1xAcgzT3/jWHwjklEAykdpSYMAqv5PQrhT4="
c = bytes_to_long(base64.b64decode(c))

public_key = import_key(open("public.pem",'r').read())
private_key = import_key(open("private.pem",'r').read())

n = public_key.n
d = private_key.d

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

# flag{c2915ff0a0ca8ffd50af20cd27682ff2}

ezPython

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import time
from tqdm import tqdm
from qsnctf import *

flag = "flag{}"
flag = caesar_encrypt(flag, 8)
for i in tqdm(range(21)):
flag = string_reverse(flag)
flag = atbash_cipher(flag)
for i in tqdm(range(20)):
flag = base64_encode(flag)
flag = base100_encode(flag)
print(flag)

# flag = "emoji emoji"

利用qsnctf这个库,安装方法:pip install qsnctf

唯一需要注意的是,解题的时候注意把密文的空格删除

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from qsnctf import *
from tqdm import tqdm

c = "emoji emoji "
c = c.replace(" ","")

c = base100_decode(c)

for i in tqdm(range(20)):
c = base64_decode(c)

c = atbash_cipher(c)

for i in tqdm(range(21)):
c = string_reverse(c)
flag = caesar_decrypt(c, 8)
print(flag)

# flag{dea8a56c1dcf73ae7fa75c52af41bb70}

emoji代替了密文的表情

N and n

part1(推导没写完,先套个脚本)


$$
e_1d_1 \equiv 1 \mod \lambda(n)
$$

$$
e_2d_2 \equiv 1 \mod \lambda(n)
$$

其中$\lambda(n) = \frac{\phi(n)}{g}$,$\phi(n) = (p-1)(q-1)$

参考【精选】密码学硬核笔记——扩展维纳攻击_维纳攻击定理-CSDN博客

构造格

part2

用连分数解

参考Generalized_attack_on_RSA_schemesfinal.pdf (cnrs.fr)

$\because ed \equiv 1 \mod (p^2-1)(q^2-1)$

$\therefore ed = k\times (p^2-1)(q^2-1) + 1$

同除$d \times (p^2-1)(q^2-1)$得

$\frac{e}{(p^2-1)(q^2-1)} = \frac{k}{d} + \frac{1}{e(p^2-1)(q^2-1)}$

用$n^2 - \frac{9n}{4} + 1$代替$(p^2-1)(q^2-1)$

于是有$\frac{e}{n^2 - \frac{9n}{4} + 1} \approx \frac{k}{d}$

连分数展开即可

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

def solve1(e1,e2,n,c):
M1 = n^(0.5)
alpha = 0.356 # 729 / 2048
M2 = n^(1 + alpha)
D = diagonal_matrix(ZZ,[N,M1,M2,1])
M = matrix(ZZ,[[1,-N,0,N**2],[0,e1,-e1,-e1*N],[0,0,e2,-e2*N],[0,0,0,e1*e2]])*D
L = M.LLL()
t = vector(ZZ,L[0])
x = t * M^(-1)
phi = int(x[1]/x[0]*e1)
d = gmpy2.invert(65537,phi)
m = pow(c,d,n)
flag = bytes.fromhex(hex(m)[2:])
return flag

def solve2(n,e,c):
cf = continued_fraction(ZZ(e) / ZZ(int(n^2 -9/4*n +1)))

i = 1
while 1:
k = int(cf.numerator(i)) #取连分数的分子
d = int(cf.denominator(i)) #取连分数的分母
#计算kphi
if (e * d - 1) % k == 0 and int(d).bit_length() == 2048:
m = pow(c,d,n)
flag = bytes.fromhex(hex(m)[2:])
return flag
else:
i += 1

e1 = 6782830682230611892084175893995043755623450171130631139250814602452836410932481493209925839414493072446570097572921721560056963314211148834567825979410196067533609339954325440284367117897127238641398908902696308109917225523901632458380925510517775783868643648356134858145600669382521666362737188742144325523512588157232342293570634035652649445253400156551025152962072745747445128287133526360740783991628418816716755623721512647940638074583741576763841775870753051303810250872868143593623277717239627310768357298460604761267661552551655957927428276127907943998267780474909778188402303623762690857740249960456774790057
e2 = 2103214336317997856589077219522416472126303166911734317206694246467268219995764970161228565888078478437417364428737223600541742231616538055544730871259451853602822824030730446037149215814151937007759784461240091013861699020393748068407644808847481103765151973619978574286131278626194949671002389644717742113710424421427515044238228547483630350104322094022063329900043953074144455813752895850411680204776639620697612634932069006593739621658746752068562661835048227282976669707149561909183948452229624114003615085530216638127958237779537381755038387944189598715581703073251023985468629411284347709891083474234876217463
C = 29989464921369023556682797868010016761018920329572945071155900694105273355964587007056986267712321773704235790532528354216923933793097271606770062213705165659395515866861504389622774632727796989109881498337975935953211195543145705126576701050921790651344138412223208506167505671199878150807990122800243557999848684393902248880601469831139694292727905631653021260642914026110749040895120735190773734221354234102719240917477878117340342682396785253367077886829396722805689079044627803038192815819268299096723702651032328877700961625008336392915779555073331746659247259680693531225729446517842360145219661338579799576558
N = 30344300732028581232055573105267124359676188143150900167627553124815567866404397432618233963414140210742264633672189858251955823399837706447362136668421589160230997509307799044768633993451916070777658566053448924598053107182517067411689272508341060006607406671139418906121846321917188581384347220115835524818729646138538805397174148412625308825976478229354595231559952075478573137303317127264083147914620219710706789060326244876382524823370726774783578934340406201760636614424268881611139037722190200706902280712973313045676140513487706619995064309929439932176799828094975671497855556312196872661906398504926989682483

e = 299742004862647001956313120212789574846580220823019898357792625504178411714797094742432220851214080697312929100795881061754804067011066316407767459562109544884325934987539239861070418621447111093384013351477684377198341027898504996993593283522838272857329217507275894840277894087904595190160194511978382517367710210686608995602714780005450539330715470056742064042206153672425362533446859048923068749681843218896929215564488280011450180418975217192154388297131854037285601204641315928728064065304223386593308998171792136113396426653699567707675838292526904189649118232094386995015436190372800414449432499422121184507296113393960935243786261895033570509606345209363596478499929774934469773180406690091187100398142619942900506959798908476235527337658505697642546150130061396487901956233214920407126566742159502020936536102917887602433208819189094143202883705424044449702123000696909084455782204447010924860970874738632469322937536658587288795299893333604630770500062873462999648761323377136099352157869839874240047601711751117191788451204663149112399751636505123892586635002009146630554168009325095964088948381302377160571209753641851547586086873112029280568971051001188617418651169235174090191703598083547611960978741863850616433263009976666609668535251515828817752896001889209178886059547569894616006038953764625172390993903264458258177870227410638829192618453676849376407446542593464461363622931772907815255954081688800997429274829215857042728871715036568727537618708814278187475175445085765782432533976143942716189575103855683395694832855726053336953735763741373335952612979908944501059234949083627802270461031980382156408726205210854884917749230264947939710324129260944905762085727485969049441097952735976295710871516976985865549318708942751416482271454250791949807080875692537392184605862254771134466225346692451821722506385446147370548767344376192640024822285511915833028610576811425847988096411847042081445063639035379481001149253846725342523772332728219803605916063700830046907196875382999881830571672177374985624241574089434376468760007094988366233326668044929011742179533386718697976595104507037505540811648287104846603486989691127711050916093950525301636944418121491192837338728578578330392782556349149954539883490468195279215271284541239787166817777355721489582824730761639598958998623312024938112967900492630170624380269694407585239618920757230271109189336570404961491906293460873344066516775823246298215432838113623662329545676928716855813667142568884689
c = 126695602720287888676696559539723856104067880497647910249667466893383255209045508458853397118652154927531942978073740450713169724992849585395980530995616033417536181504956346153802206636341529342379554700812003676995067291620365422490729240182771628157839856497982161939850099419818846168892124000934230938596843008515097940267452003035829575993632190810983916075770086955915299960458326215544353491716475416507979327966205005560687748553292934357925494272906793366830635665955254360832729599330402509893842443992566513483714382646025195961137009000018753983651046339079082240599803110561923185022718826369932953293392042843316783280269536972413964168113045731922548355553310815705462142367484991077862467325614074446691792390594414839402047022568848720013674657754350468599049824440676054373139693146540866117364152197587588957272239652412704757261350214302868926397274366692066128442089847092896219437033747372413635564005759528955854210845606433051956506324333881982679048116436237358902439216062577682934439187221817783476381404025207390125422670463968924533866239220945599943424853960721952593755424063509284740828904466959593982825341965617094231864134504669071102977784540127151904413578177761848793566690223185451889990820402
n = 859565655364744504691128999173163629390646814643060535547080894876016015739755448061478525059968284125179725990710325321893406147631932546407240817403077573269303336968136350915335129516055615375854960217610941327794523495841406247731161064324407758961532167363890807327195033732279449216861117755979815380858624730326007741056071800878183909447988835586091073740707308565512311924433072879024119766899755012553349626636468493851062542303298661624120541942178182347374045947609043216734445638877776294108043514178865246029735264509336247861885730840387655988039742469139971460741869400259399992998520698159168380993790528772660805213735331660411376032794407414712321416964946987284847501890015182686215583876281440889392100599628100990699849428461136706052752442644724202914118196513060602262180109347482361752489574671269844731950856639343609901971646601035980653387918471588092168412636621698349007474550692258931250093394500150330222620648922922629823659927849987286747846800518750174996915977804476772593787465161038218032247260333768345962898351749721089493153901951125423616164946743757205492717572128978767398876091279363699959624457451368185973411191832200498560071743826896179527897577648387335153453732357692561765479438357

flag1 = solve1(e1,e2,N,C)
flag2 = solve2(n,e,c)
flag = flag1 + flag2
print(flag)
# flag{238a162f235967c4e64d3aa155ac788c}
-------------已经到底啦!-------------