文章 - 2024源鲁杯round1-crypto题解

break

题目只有e不知道，从55555到66666爆破就好，加上限制条件
GCD(e,fn) == 1很快就能出flag。

from Crypto.Util.number import *
c = 2924474039245207571198784141495689937992753969132480503242933533024162740004938423057237165017818906240932582715571015311615140080805023083962661783117059081563515779040295926885648843373271315827557447038547354198633841318619550200065416569879422309228789074212184023902170629973366868476512892731022218074481334467704848598178703915477912059538625730030159772883926139645914921352787315268142917830673283253131667111029720811149494108036204927030497411599878456477044315081343437693246136153310194047948564341148092314660072088671342677689405603317615027453036593857501070187347664725660962477605859064071664385456
p = 112201812592436732390795120344111949417282805598314874949132199714697698933980025001138515893011073823715376332558632580563147885418631793000008453933543935617128269371275964779672888059389120797503550397834151733721290859419396400302434404551112484195071653351729447294368676427327217463094723449293599543541
q = 177020901129489152716203177604566447047904210970788458377477238771801463954823395388149502481778049515384638107090852884561335334330598757905074879935774091890632735202395688784335456371467073899458492800214225585277983419966028073512968573622161412555169766112847647015717557828009246475428909355149575012613
n=p*q
fn = (p - 1) * (q - 1)
for e in range(55555,66666):
    if (GCD(e,fn) == 1):
        d = inverse(e, fn)
        flag = long_to_bytes(pow(c, d, n))
        if b'YLCTF' in flag:
            print(flag)

signrsa

很明显n1和n2有共同的最大公因数作为p，两个q用n//p得到
解两次rsa即可

n1 = 18674375108313094928585156581138941368570022222190945461284402673204018075354069827186085851309806592398721628845336840532779579197302984987661547245423180760958022898546496524249201679543421158842103496452861932183144343315925106154322066796612415616342291023962127055311307613898583850177922930685155351380500587263611591893137588708003711296496548004793832636078992866149115453883484010146248683416979269684197112659302912316105354447631916609587360103908746719586185593386794532066034112164661723748874045470225129298518385683561122623859924435600673501186244422907402943929464694448652074412105888867178867357727
n2 = 20071978783607427283823783012022286910630968751671103864055982304683197064862908267206049336732205051588820325894943126769930029619538705149178241710069113634567118672515743206769333625177879492557703359178528342489585156713623530654319500738508146831223487732824835005697932704427046675392714922683584376449203594641540794557871881581407228096642417744611261557101573050163285919971711214856243031354845945564837109657494523902296444463748723639109612438012590084771865377795409000586992732971594598355272609789079147061852664472115395344504822644651957496307894998467309347038349470471900776050769578152203349128951
e = 65537
c=4721377072175102613361137337163270450983076870461012080652608649067859481206971060161155816649247160878434395152796321210268422584637234140631039330300115975083038369927011916570817249992214651092542295887930374819488816544925258808164890759410896254628719868063693625803589151901799807559532759251092179113590052601425294005027367189756893720938355257150254856426634214439058866943243968243210693711236433896995405047967164622961318487818253199727332452840163640265957657180502710903570963921577923474192175101410987367896287822681214695583798834702458747901971075175776553409411361220635933669443816934461204801558

from Crypto.Util.number import *
p=GCD(n1,n2)
q1=n1//p
q2=n2//p
fn1=(p-1)*(q1-1)
fn2=(p-1)*(q2-1)
d1=inverse(e,fn1)
d2=inverse(e,fn2)
m=pow(c,d2,n2)
m=pow(m,d1,n1)
print(long_to_bytes(m))

ezrsa

Franklin-Reiter相关攻击

from Crypto.Util.number import *
import gmpy2

hint= 8513094072436201400532864370157676676545398490099575039293889946871592540619086942171017488477916941330206032020101866149404863654515492087521705481184611012186664065661881426891736868171939650078776106500757490558941201372084603283072887906689184934992490469570921415262541722869372961583027319511969431982
n= 99265672434049729756038132217517962479159068695713358764022806908380704629309937843011822230834173854816630846356283854873674672302130954663075935989773077837558092780359518937957684933158876630810528487658883868442907986813706233106199440715777688304232279102800295205858600652918642637100422852642668108939
c= 47693028107878116729337684111637335262261219649406290292357286028647330700400229668877227829507027834915567863282062578224103957335584429706888295095670890399935061114803981984906527493344204242920164598247018882772395053872248846442631644556517388251879777172570391340349408526540924413701242380906168219678
e=65537
b=20240918

p = gmpy2.gcd(pow(b,e,n)-hint,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

r(A)=3

用z3解方程，与靶机交互300次

from pwn import *
from z3 import *

context.log_level = 'debug'
io = remote('challenge.yuanloo.com', 42966)

for _ in range(300):
    io.recvuntil(b'function')
    io.recvuntil(b':\n')
    s = Solver()
    x, y, z = Ints('x y z')
    for _ in range(3):
        ex = io.recvline().replace(b'=', b'==')
        s.add(eval(ex))

    if s.check() == sat:
        io.sendlineafter(b'x=\n', str(s.model()[x]))
        io.sendlineafter(b'y=\n', str(s.model()[y]))
        io.sendlineafter(b'z=\n', str(s.model()[z]))

io.interactive()

threecry

1.后半段flag，近似值求pq，解rsa，e和phi不互质

2.快速幂解，把n1当e解rsa

from Crypto.Util.number import *
import gmpy2

number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947

c1 = 1576739897938895686293637078217512046577154849061724326950216224306081604858347053226002846364721773684982628886957169294142909589627850854333323116659362258165953937985356771185111322771941354725306369601659261870311430935576680284981931459550337190721159545918284515511156207400714178048751308246012397994399
c2 = 10812291346741962967287214576601993388517230010258906889102882335883352410743265563481891270979873590186662733213213298890648307295479089640334422507921659917994206393918233008291490882886718236723251040221739393929459543909965568461829273810112020445742091170502904217369226447865067177089532409565402247817574

e = 0xe18e

a_near = gmpy2.iroot(number2 // 325, 2)[0]
while number2 % gmpy2.next_prime(13 * a_near) != 0:
    a_near = gmpy2.next_prime(a_near)

p = gmpy2.next_prime(13 * a_near)
q = number2 // p
phi = (p - 1) * (q - 1)

t = gmpy2.gcd(e, phi)
d = gmpy2.invert(e // t, phi)

m2 = gmpy2.iroot(pow(c2, d, number2), t)[0]
flag2 = long_to_bytes(m2)

d1 = gmpy2.invert(number1, phi)
m1 = pow(c1, d1, number2)
flag1 = long_to_bytes(m1)

print(flag1 + flag2)