羊城杯2023-Crypto

Easy_3L

题目是一个NTRU+LCG。但是其实这个NTRU用模板跑出来的q不是素数，但是不知道为啥答案也是对的...然后我构造了个四维格子，其实三维也可以的。

我的解答

p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

A=matrix(QQ,4,4)
A[0,0]=1
A[1,1]=1/2**512
A[2,2]=1/2**512
A[0,3]=c
A[1,3]=1
A[2,3]=h
A[3,3]=p
S3=A.LLL()[1]*2**512

p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
s=8578228700306461635801143672885395197607212415337569546083986946223337693304964812887877332223090265726227310801792059554804373996008349086523997356351191
S3=5350347583048047497687986160432985584479948718649671034062080769451257000345517118379144518832137661817523764823766100346655854673992063035026005785632303*2
S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736

x=(S3-S2)*(S3-S1)-(S4-S2)*(S2-S1)
y=(S3-S2)*(S4-S1)-(S5-S2)*(S2-S1)
print(x)
print(y)
from gmpy2 import *
from Crypto.Util.number import *
n=12433235385460084327215142269091752668477278692416805859007828624838647815241707248797912107322868748847211061641608674422095027981318008221949510129177787
a=int(invert(S2-S1,n))*(S3-S2)%n
b=(S2-a*S1)%n
m=(S1-b)*int(invert(a,n))%n
print(long_to_bytes(m))

Danger_RSA

其实是个CryptoCTF2023的一道题目，这边就不写了。

SigninCrypto

随机数预测+copper，反正就套了好多

我的解答

from extend_mt19937_predictor import ExtendMT19937Predictor
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from random import *
import hashlib
f=open('task.txt','r')
ls1=[]
ls2=[]
for i in range(624):
    ls1.append(f.readline()[2:-1])

for i in range(312):
    ls2.append(f.readline()[2:-1])
ran=[]
k=0
for num in ls2:
    tmp=int(num,16)
    s=bin(tmp)[2:].zfill(32)
    s1=bin(int(ls1[k+1],16))[2:].zfill(16)
    s2=s[:16]
    s3=bin(int(ls1[k],16))[2:].zfill(16)
    s4=s[16:]
    ran.append(int(s1+s2+s3+s4,2))
    k+=2
rc=ExtendMT19937Predictor()
for i in range(len(ran)):
    rc.setrandbits(ran[i],64)
K2=rc.predict_getrandbits(64)

dig=0x62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833
h2=22078953819177294945130027344
dig=long_to_bytes(dig)
print(dig)
os_l=bin(h2)[-32:]
iv_h=bin(h2)[2:33]
iv=long_to_bytes(int(iv_h,2))
x=334648638865560142973669981316964458403
print(long_to_bytes(x))
h1=b'\xfb\xc2'*8
K1=long_to_bytes(bytes_to_long(h1)^x)
print(K1)
c=int('a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1',16)
K2=long_to_bytes(K2)

for cc in range(256):
    K3 = b'DASCTF{'
    K3 += long_to_bytes(cc)
    KEY = K1 + K2 + K3
    print(len(KEY))
    mode = DES3.MODE_CBC
    des3 = DES3.new(KEY, mode, iv)
    print(des3.decrypt(long_to_bytes(c)))

MCeorpkpleer

pubkey第一个就是w，然后找到第几个超过m，第一个超过m的数会modm所以以此可以求出m。后面就是一个背包密码。

我的解答

from Crypto.Util.number import *

e_bin=64
w=18143710780782459577
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
for i in range(len(pubkey)):
    if pubkey[i]%w==0:
        print('no')
    else:
        print(i)
        break
print(3**24*w)
print(3**24*w-pubkey[24])
m=4522492601441914729446821257037

import binascii
pubKey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
encoded=31087054322877663244023458448558
nbit=len(pubKey)
# create a large matrix of 0's (dimensions are public key length +1)
A = Matrix(ZZ, nbit + 1, nbit + 1)
# fill in the identity matrix
for i in range(nbit):
    A[i, i] = 1
# replace the bottom row with your public key
for i in range(nbit):
    A[i, nbit] = pubKey[i]
# last element is the encoded message
A[nbit, nbit] = -int(encoded)

res = A.LLL()
for i in range(0, nbit + 1):
    # print solution
    M = res.row(i).list()
    flag = True
    for m in M:
        if m != 0 and m != 1:
            flag = False
            break
    if flag:
        print(i, M)
        M = ''.join(str(j) for j in M)
        # remove the last bit
        M = M[:-1]
        M = hex(int(M, 2))[2:-1]
        print(M)

p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
p0=p>>435
R.<x>=Zmod(n)[]
f=p0*2**435+x
print(f.small_roots(X=2^435,beta=0.4))
p=22279478575805637289061098350801418725939755105414714905065078232409620860952900304322034404385073099026861643396875749287858710167+p0*2**435
print(p)

e=15960663600754919507
print(isPrime(e))
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
p=139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179677630589032444985150800881889090713797496239571291907818169058929859395965304623825442220206712660451198754072531986630133689525911
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

XOR贯穿始终

就一个私钥文件然后分解n再异或一下就行

我的解答

from base64 import *
from Crypto.Util.number import *
c='MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbILSuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYEN4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuWeZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESvIgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbnjxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaAUETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25uGz3++w=='
print(b64decode(c).hex())
d=0x00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
enc= 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
n=0x00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
p=0x00ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9
print(n%p)
q=n//p
m=pow(enc,d,n)
print(long_to_bytes(bytes_to_long(b'C0ngr4tulati0n5_y0u_fou^d_m3')^m))

esyRSA

这题赛后出，emmm怎么说呢这附件数据还错的，自己也没去关心那个n是重复的...无语了。数据正确后直接连分数求解就行。

我的解答

from Crypto.Util.number import *
from hashlib import *

n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913


c = continued_fraction(Integer(d) / Integer(n))

for i in range(1, len(c)):
    e = c.denominator(i)
    k = c.numerator(i)
    if (e*d-1)%k==0:
        phi=(e*d-1)//k
        if n>phi:
            p,q=var('p q')
            eq1=p*q==n
            eq2=(p-1)*(q-1)==phi
            ans=solve([eq1,eq2],[p,q])
            print(ans)
p=10181341212828413853336916619161138854377885230386496425058202154486415709366161346816273366144505351043947477469664133317598479763451392984403646602585037
q=7920625690369490250766357750388349704260128405941822835255851274284409978206593795103040446837018619894098452542488850045009467407103749792461438242280929
print(md5(str(p+q).encode()).hexdigest())