buuctf newstar 2023 公开赛-crypto-week2-writeup

admin

102523
文章

87
评论

2023年10月16日18:58:19评论21 views字数 19655阅读65分31秒阅读模式

声明：该公众号大部分文章来自作者日常学习笔记，也有部分文章是经过作者授权和其他公众号白名单转载，未经授权，严禁转载，如需转载，联系开白。请勿利用文章内的相关技术从事非法测试，如因此产生的一切不良后果与文章作者和本公众号无关。

week2的题目比上周稍微难了一点，需要大家对rsa多熟悉下才行

滴啤

题目：

from Crypto.Util.number import *
import gmpy2
from flag import flag
def gen_prime(number):
    p = getPrime(number//2)
    q = getPrime(number//2)
    return p,q

m = bytes_to_long(flag.encode())
p,q = gen_prime(1024)
print(p*q)
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
print(d%(p-1))
print(pow(m,e,p*q))
# 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
# 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
# 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089

经典的rsa dp泄露题目，具体这篇博文有讲解https://blog.csdn.net/qq_52193383/article/details/119760806

wp:

import libnum
import gmpy2

e = 65537
n = 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
dp = 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
c = 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089

for i in range(1, 65538):
    p = (dp * e - 1) // i + 1
    if n % p == 0:
        q = n // p
        break

phi_n = (p - 1) * (q - 1)

d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c,d,n)

flag = libnum.n2s(int(m)).decode()

print(m)
print(flag)

buuctf newstar 2023 公开赛-crypto-week2-writeup

不止一个pi

题目：

from flag import flag
from Crypto.Util.number import *
import gmpy2
p = getPrime(1024)
q = getPrime(1024)
n = p**3*q**2
print("q = ",q)
print("p = ",p)
m = bytes_to_long(flag.encode())
c = pow(m,65537,n)
print("c = ",c)

# q =  115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
# p =  171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
# c =  4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337

题目给出n = p3*q2，那么根据欧拉定理φ(n) = （p-1)(q-1)p^2q。这题主要就是考察大家对欧拉定理的熟系程度。拓展一下，如果n是多个互素的数组成，如p，q，r互素，那么φ(n)=（p-1）（q-1）*（r-1）

wp：

from Crypto.Util.number import *
import gmpy2


e = 65537
q =  115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
p =  171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
c =  4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337

n = p**3*q**2
phi=(p-1)*(q-1) * p**2*q
d = gmpy2.invert(e, phi)

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

halfcandecode

题目：

from Crypto.Util.number import *
import gmpy2
from flag import flag
import os
from hashlib import md5

def gen_prime(number):
    p = getPrime(number // 2)
    q = gmpy2.next_prime(p)
    return p * q

def md5_hash(m):
    return md5(m.encode()).hexdigest()
e = 65537
n = gen_prime(1024)
m1 = bytes_to_long(flag[:len(flag) // 2].encode() + os.urandom(8))
c1 = pow(m1, e, n)
m2 = flag[len(flag) // 2:]
with open("out.txt","w") as f:
    f.write(str(n) + 'n')
    f.write(str(c1) + 'n')
    for t in m2:
        f.write(str(md5_hash(t))+'n')

output：113021375625152132650190712599981988437204747209058903684387817901743950240396649608148052382567758817980625681440722581705541952712770770893410244646286485083142929097056891857721084849003860977390188797648441292666187101736281034814846427200984062294497391471725496839508139522313741138689378936638290593969430547662355311113725288593525679959779486251573406737956190751381836839290019861008338662276880815638038629779366808224079248973574912013564134936455159624588545707311761930552597795640519912770929413793927000651502869366077840737074486301504058980830001571749277332601983556906206394870495233453803649486494a8a08f09d37b73795649038408b5f3303c7c0ace395d80182db07ae2c30f034e1671797c52e15f763380b45e841ec32b14a7b8059d9c055954c92674ce60032e358efa489f58062f10dd7316b65649ecfcd208495d565ef66e7dff9f98764dab14a7b8059d9c055954c92674ce600328fa14cdd754f91cc6554c9e71929cce70cc175b9c0f1b6a831c399e2697726614a8a08f09d37b73795649038408b5f33e358efa489f58062f10dd7316b65649ecfcd208495d565ef66e7dff9f98764da4b43b0aee35624cd95b910189b3dc231cbb184dd8e05c9709e5dcaedaa0495cf

这道题其实是考了两个部分，flag分成两个部分来加密，一半是rsa加密，其中q是p的下一个素数，这种情况其实是板子题，我们直接对n进行开发得到一个近似数，然后这个数的下一个素数，就一定是q。flag的另外一半是挨个读取字母去hash加密，那么我们去一个一个hash加密枚举就行

wp：

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



def md5_hash(m):
    return md5(m.encode()).hexdigest()

n = 113021375625152132650190712599981988437204747209058903684387817901743950240396649608148052382567758817980625681440722581705541952712770770893410244646286485083142929097056891857721084849003860977390188797648441292666187101736281034814846427200984062294497391471725496839508139522313741138689378936638290593969
temp=gmpy2.iroot(n,2)[0]
p=gmpy2.next_prime(temp)
q=n//p
print(p)
print(q)

e = 65537
c1 = 43054766235531111372528859352567995977948625157340673795619075138183683929001986100833866227688081563803862977936680822407924897357491201356413493645515962458854570731176193055259779564051991277092941379392700065150286936607784073707448630150405898083000157174927733260198355690620639487049523345380364948649
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m1 = pow(c1,d,n)
print(long_to_bytes(m1)[:-8])

data = []
c2 =['4a8a08f09d37b73795649038408b5f33','03c7c0ace395d80182db07ae2c30f034','e1671797c52e15f763380b45e841ec32','b14a7b8059d9c055954c92674ce60032','e358efa489f58062f10dd7316b65649e','cfcd208495d565ef66e7dff9f98764da','b14a7b8059d9c055954c92674ce60032','8fa14cdd754f91cc6554c9e71929cce7','0cc175b9c0f1b6a831c399e269772661','4a8a08f09d37b73795649038408b5f33','e358efa489f58062f10dd7316b65649e','cfcd208495d565ef66e7dff9f98764da','4b43b0aee35624cd95b910189b3dc231','cbb184dd8e05c9709e5dcaedaa0495cf']
for t in c2:
    for i in range(40,180):
        i = chr(i)
        # print(i)
        # print(str(md5_hash(i)))
        if str(md5_hash(i)) == t:
            # print(i)
            data.append(i)
            continue

m2 = ''.join(data)
print(m2)

buuctf newstar 2023 公开赛-crypto-week2-writeup

Rotate Xor

题目：

# from secret import flag
from os import urandom
from pwn import xor
from Cryptodome.Util.number import *
k1 = getPrime(64)
k2 = getPrime(64)
ROUND = 12
# ciphertext = xor(flag, long_to_bytes(k1))
def round_rotate_left(num, step):
    return ((num) << step | num >> (64-step)) & 0xffffffffffffffff
def encrypt_key(key):
    
    for _ in range(ROUND):
        key = round_rotate_left(key, 3) ^ k2
    
    return key
# print('ciphertext =', ciphertext)
print('enc_k1 =', encrypt_key(k1))

print('enc_test =', encrypt_key(16012422788958079932))

print('k2 =', k2)

# ciphertext = b'x8dSyyxd2xcexe2xd2x98x0fthx9axc6x8exbcxde`zlxc0x85xe0xe4xdfQlc'
# enc_k1 = 7318833940520128665
# k2 = 9982833494309156947

异或题，关键在于这一步((num) << step | num >> (64-step)) & 0xffffffffffffffff这一步的意思其实是，64位key，的最左边三位移动到最末尾去。然后通过循环后，一共进行了12次变化 key = round_rotate_left(key, 3) ^ k2注意其中是每次变化后会异或k2，如果我们要还原，就应该每次先异或k2，然后进行一次还原变化，连续12次

wp：

from os import urandom
from pwn import xor
from Cryptodome.Util.number import *


enc_k1 = 7318833940520128665
k2 = 9982833494309156947
ciphertext = b'x8dSyyxd2xcexe2xd2x98x0fthx9axc6x8exbcxde`zlxc0x85xe0xe4xdfQlc'
ROUND = 12
def round_rotate_left(num, step):
    return ((num) >> step | (num & 0b111) << (64 - step) )
def decrypt_key(key):
    for _ in range(ROUND):
        key = round_rotate_left(key ^ k2, 3)

    return key

k1 = decrypt_key(enc_k1)
print(k1)

flag = xor(ciphertext, long_to_bytes(k1))

print(flag)

buuctf newstar 2023 公开赛-crypto-week2-writeup

broadcast

题目：

from secret import flag
from Cryptodome.Util.number import *

menu = '''
Welcome to RSA Broadcasting system

please select your option:

1. brocast the flag
2. exit
'''
e = 17
def broadcast_the_flag():
    p = getPrime(256)
    q = getPrime(256)
    n=p*q
    m = bytes_to_long(flag)
    c = pow(m,e,n)
    print('n =', n)
    print('c =', c)
    print('e =', e)
while True:
    print(menu)
    opt = input('> ')
    try:
        opt = int(opt)
        if opt == 1:
            broadcast_the_flag()
        elif opt == 2:
            break
        else:
            print('invalid option')
    except:
        print('oh no, something wrong!')

这道题是一道交互题，需要使用pwntools库交互，具体用法这里不细讲，可以自行去搜索pwntools库分析这道题，给出了e=17，然后p，q是每次随机生成的256位素数。e和明文m不变，那么我们可以用广播攻击，要求满足至少有e组n c，所以我们获取了17组nc，然后使用广播攻击就能解题

wp：获取n c

from Crypto.Util.number import *
import gmpy2
from pwn import *

e = 17


n=[]
c=[]
for i in range(17):
    p=remote('node4.buuoj.cn',29843)
    p.recv()
    p.sendline(b'1')
    n.append(int(p.recvline().replace(b'n',b'').replace(b'n =',b'').decode()))
    c.append(int(p.recvline().replace(b'n',b'').replace(b'c =',b'').decode()))
print('c=',c)
print('n=',n)

sage脚本广播攻击，这里的nc是我自己获取的，做密码学的各位，如果没有接触过sagemath，可以借这个机会去了解下，安装一个。当然有在线网站，一般情况下也可以应对，不过在线网站不能使用第三方库，不是很方便https://sagecell.sagemath.org/

import binascii,gmpy2
from functools import reduce

import libnum


def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e= 17
c= [9661153434759574379859903358663343622115531388701604052995340150260853589246372752491099007658897885335490417713735107563683243839972106377994034746231363, 5649357067972851281371476364935221372345238585881395796853021705876082549018031327619841849742608813732046417170149333192658632564482414207137825618236949, 2870136367158393954777380227448574241132700139965726625395795918739451149651127582649734290845514407225348948881631201010176854245485956305159952540299865, 1077343637020076467875373838668351982733502457227980977681612026711314641456278986820826079925535350573567802447219526038332304137147574444792061861411657, 2644007428829364736575965706130007518555415995344647493850405107761311909834970410125314361929476550018523108206103346098085367102300667662237423411940330, 3685600296638753638911486065481998915480717775949339071242312512627602416521557012319509093841014765888308004752619778878345420125875740214724880954836661, 4289031075190044368672104184549677485963903105650162710559479617893194060339546956837239153676835388402650834971135815956999923663055818514231760876914444, 7182820438534579221577754531800338702317779428267789791103567388178877803905246758991064030815016635067683555385545333553096562636224010441200856554749314, 3868309491951396619125162772265326209450308917902039608678645258592150638450071707743860516128358593847043436618895603396565227099538879691505636282340270, 3448672011077247555118129413707751254132323829618360402913715215602349881292514221309528263154524416883314415100645100348515649147439293782133864544861315, 1768431448665131065599913149460310423617930725056178517816201535032320556501355090805019992669125872155157073605477851729690475224103034087049150738843688, 3800655926189698312104635622983253077542496025487227316707557511881868423949582124349963725345101385638040453540725463439214219522609412080217230011119459, 9255810867709427440794808257974524923389243018805473264779455021765726787156058316324711896470846035602112357236681997024995207622593206270680729764491587, 8724666261507069491127903582588621352024524445971165023841334519288437447460939020344635646300534561087573439349545314692717879340104536076578148390110753, 2372264582610272864033652351533394761233611977781708919610693085475375694580496007662266491294499851916486833378325677099403209580878264782795025813990645, 3720135138713856523912898072662622264971758963742284609983934826367080068499447141481777129389135907350706769428262872806513617223503571383503797756308093, 2309160130620138900158004840101420646442009873296364009711163572202165227280005420280052153875421806680191608588021183349216324479141063477605592796438213]
n= [9694009759270807262304892497645624437501393776840536704238491549401760095238182336719767338516887608930942672440188834921726821436718342677957655857935171, 7142432521669231627125417275279562014790583935960930810739121600120364298074233409907461590706841638288744647349619694391873662157523041625885386309170389, 4647611667221444013505950955093166037760586464181218485165796819132906673485822432223626993292775520294832372975899465711162685559251996818808655818875139, 9076283357460119334203511754548173137687661920327866438853030449056541757281299644719415746196360952570526449377577770186916579331227100365104581354596879, 4735279519524545554833202977641921463494452005215544282703919149198239783297607398701393500340428131838471244661032380061362445673825337200471783877599449, 8751810958579207066769763997280869225635065734751798803529665365667266223828646185170470142547722337173179001238251823517148105536029111404008098930151627, 6386794886831274493386978629178515966773094314740305687967070237380483986262380179569697400297867680379046124262569238635712436005436867789055458302554469, 10672335220065772405991371054950539310778791527956821112376458772506483468987268031471817151044287384713097111752212960673682967653542980880875798358495183, 10988583920339227969097003373379956655139164861399079222725917204787728338812158589930349268040671090863322416874185718164410881315174806267425906062543377, 4489755996809009896519566429531114457661304950160897022006286417505122781363840277099572616510699193731920546981953585292976451141575742851797695032790987, 6440317313368359409617275842601857685425793450537565032567294032676910455483514810127913601622942964213566944524722884682718104649309444505966735229495919, 8069348974613041745759878335821602509010127429294819327574050273327493514908056604355580532908670119223132096320323404358443680152188671895185696276156461, 9384031116327730200220309741346474934004566316132600236082052290201856420645167283201366922551613151111359193781728049635891070355366833714604846635906153, 9305511014379834765523508857699321376884369461257410725918518536143636418307930641751864277752463968029984382328623093590497156120770241073590956870609239, 5329245227985380147196376531352627705918891452495224955734897170503133531501385748336525339351111304859785356446379817599324760555111353332705045433692647, 3910763663503869215151842855780834249880410525915677135356977205861778286074933187021387585217435713650545063148447655108086896588009238367217856901812061, 8195541539987855247528967573809918896864360294180865229414740813347279399034952256301781910933210506501884670119164221761958852153015291272411670305688543]

#CRT(n,c)
m=gmpy2.iroot(crt(c,n), e)[0]
print(m)
print(libnum.n2s(int(m)))

partial decrypt

题目：

from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(512)

n = p*q 

c = pow(m,e,n)

dp = inverse(e, (p-1))
dq = inverse(e, (q-1))
m1 = pow(c,dp, p)
m2 = pow(c,dq, q)
q_inv = inverse(q, p)
h = (q_inv*(m1-m2)) % p
print('m2 =', m2)
print('h =', h)
print('q =', q)

# m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
# h = 4180720137090447835816240697100630525624574275
# q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931

这题上周看了一眼，应该是要进行数学变化，找出规律，后面工作没时间做了。后面学习了一个大佬的解法，这里放出源连接：https://blog.csdn.net/qq_73643549/article/details/133775673 这道题是一道魔改题，但是不是很难。好好分析还是挺简单的，因为只需要搞清楚h是什么就可以了。（需要先理解前面的dp泄露） dp=1+k{1}(p-1),dq=1+k{2}(q-1),m1=m (mod p),m2=m (mod q)因为h=(q_inv(m1-m2))。所以h=(q_inv(k{3}p-k{4}q))(mod p)=-k_{4}(modp),但是k4大小我们未知，其的正负都有可能。但是看到题目只解一半，也就说m > q,即k4 < 0, 所以h就是我们要求取的系数。

wp：

from Crypto.Util.number import *



m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
h = 4180720137090447835816240697100630525624574275
q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931


m = m2 + h* q
print(long_to_bytes(m))

原文始发于微信公众号（夜安团队SEC）：buuctf newstar 2023 公开赛-crypto-week2-writeup

左青龙
微信扫一扫

右白虎
微信扫一扫

buuctf newstar 2023 公开赛-crypto-week2-writeup

滴啤

不止一个pi

halfcandecode

Rotate Xor

broadcast

partial decrypt

2023某省电子取证比武wp

看雪2023 KCTF年度赛 | 第11题·步步逼近-设计思路及解析

一文掌握简单Native分析：以攻防世界#Android2.0为例

第十五届蓝桥杯大赛网络安全赛项个人赛Writeup

数信杯一个题目窥看内存取证

高JDK的JNDI绕过之复现某比赛0解题

ctf工控流量题

AVSS 2024 Writeup Polaris战队

2024警察大学第七届精武杯电子数据取证技能比武暨信息安全协会社团邀请赛参考wp

国科ctf python脚本 ctf常用python库

发表评论

在线咨询

微信