NEEPUCTF-Crypto

Match

Created At : 2023-05-25 09:50

Count:865 Views 👀 :

easymath
Loss
Loud&Loud2

easymath

from Crypto.Util.number import *

flag=bytes_to_long(b'Neepu{xxx}')

N = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
m = 1391372358062724416224243990838035874507346098208831800403257
n = 3583006200974501742604527103814726194237416368238514877166633691321127310414088215607009332255751700661232767709290883038406749484575415867828156201338536386376279995491732514052716934519151026884616917483040
l = 359786222110993880715372696002813612045630045754565831162281874392294886391569010600976425535545860799388851419768061619942493351122730748490893471593987207207967996028533058621192187630928610989765004439777

c = (110 * pow(m, flag, N) +313 * pow(n, flag, N) + 114 * pow(l, flag, N)) % N
print(c)
'''
c = 1895030805615627998889733471639619972225091175824712353587361803906002039112746104833908879918848049981737808710773335455541140252543329151696420250885361493998408542681830779056032193286985350503581777508964
'''

已知：

$c = (110 \cdot m^{flag} \space mod \space N + 313 \cdot n^{flag} \space mod \space N + 114 \cdot l^{flag} \space mod \space N) \space mod \space N$

通过所谓的经验可以得到：

$m \cdot n ≡ 1 (mod N)$
$m^2 \cdot l ≡ 1 (mod N)$

将这两个等式代入原始的等式：

$110 * m^f + 313 * n^f + 114 * l^f ≡ c (mod N) $

$110 * m^{3f} + 313 * m^f + 114 ≡ c * m^{2f} (mod N)$

这里将$m^f$当作整体，然后解同余方程。

接着应该是离散对数问题，观察发现N-1光滑（我观察不出来。。。）

N =
73893134812233842149947626198233005899784230758575407120079813738870188601748462080009
57230283669342186460652521580595183523706412588695116906905718440770776239313669678685
198683933547601793742596023475603667
m = 1391372358062724416224243990838035874507346098208831800403257
n =
35830062009745017426045271038147261942374163682385148771666336913211273104140882156070
09332255751700661232767709290883038406749484575415867828156201338536386376279995491732
514052716934519151026884616917483040
l =
35978622211099388071537269600281361204563004575456583116228187439229488639156901060097
64255355458607993888514197680616199424933511227307484908934715939872072079679960285330
58621192187630928610989765004439777
c =
18950308056156279988897334716396199722250911758247123535873618039060020391127461048339
08879918848049981737808710773335455541140252543329151696420250885361493998408542681830
779056032193286985350503581777508964
print(factor(N-1))
from Crypto.Util.number import *
P.<x> = PolynomialRing(Zmod(N))
f=110*x^3-c*x^2+313*x+114
f=f.monic()
print(f.roots())
a=227512395620376536323376596129750737912423698096760314507923917720826452343855537829
81776025175997085330048053699862460981278634807985282068185768886554275916855344781615
71717613561380234338516607855593046949
fac = [2, 136327, 169937, 313351, 321427, 323377,356887,413783, 519733,792413, 860077, 906289, 976501]
G=Zmod(N)
m1=G(m)
c1=G(a)
oo=[]
for i in fac:
    h=(N-1)//i
    dlp1=discrete_log(c1**h,m1**h)
    oo.append(int(dlp1))
sk=crt(oo,fac)
mod = prod(fac)
for i in range(100):
    print(long_to_bytes(int(sk + i * mod)))

Loss

from cryptography.hazmat.primitives.ciphers.algorithms import AES
from cryptography.hazmat.primitives.ciphers import Cipher, modes
from Crypto.Util.number import *
import random
flag=b""
key=long_to_bytes(random.getrandbits(16*8))
assert len(flag) == 32
def myhex(x):
    return "".join(hex(k)[2:] for k in x)
def encrypt(pt, key):
   aes = Cipher(AES(key), modes.ECB())
   enc = aes.encryptor()
   ct  = enc.update(pt)
   ct += enc.finalize()
   return ct
ct  = myhex(encrypt(flag, key))
key = myhex(key)

print(ct)
print(key)
# ct  = '98691cbec88e449e8bac58e91142269a7da5efa9e7c62848e7135f1150f02a'
# key = '8ee2b28564433679d93b82873fe8a'

myhex函数的写法会导致转换为16进制的时候将0开头部分的0去掉，通过查看key和ct的位数也可以发现是不完整的。我们只需要爆破所以可能就可以还原key和ct。

from cryptography.hazmat.primitives.ciphers.algorithms import AES
from cryptography.hazmat.primitives.ciphers import Cipher, modes
from itertools import combinations
from tqdm import tqdm
def decrypt(ct, key):
    aes = Cipher(AES(key), modes.ECB())
    dec = aes.decryptor()
    pt = dec.update(ct)
    pt += dec.finalize()
    return pt
def add_zeros(ct, p):
    test_ct = list(ct)
    for i in p:
        test_ct.insert(i, '0')
    return ''.join(test_ct)
ct = '98691cbec88e449e8bac58e91142269a7da5efa9e7c62848e7135f1150f02a'
key = '8ee2b28564433679d93b82873fe8a'
missing_ct = -len(ct) % 32
missing_key = -len(key) % 16
for mc in tqdm([*combinations(range(len(ct)), missing_ct)]):
    for mk in combinations(range(len(key)), missing_key):
        test_ct = bytes.fromhex(add_zeros(ct, mc))
        test_key = bytes.fromhex(add_zeros(key, mk))
        flag = decrypt(test_ct, test_key)
        if flag.startswith(b'Neepu{'):
            print('Found!', flag)
            print(key)
#Neepu{R41ders_0f_th3_l0st_byt3s}

Loud&Loud2

from Crypto.Util.number import *
import random
flag = randint(1, 2^4096)
print(flag)
p = [getPrime(256) for _ in range(20)]
c = [[randint(0, p[i] - 1) for __ in range(3)] + [int(flag % p[i])] for i in range(20)]
for c0 in c:
    random.shuffle(c0)
print(p)
print(c)
#p=[66467878562792562224887473415011035371976498729276781135103070806273826602147, 87779827664444719705378632508432527366151596527264599732383282214161710342059, 106478845076259796180788022071614290976203859464583466743581048528447954519879, 96059795988661207615203630115134173796188205316583242342092930969746956840537, 76648433583138097341785050433545276046328401071616329410459071963649387342037, 75363807436621723536569872393312030066473340867618075065014040776064056013377, 84549506983821330145587582824091845683589581353932033068622843538281197238321, 111370876180722361599897961586244954018438484624454058266043059162224754345369, 64482965162169334114246637526347201196498007629645251181883638859700004974179, 115737745133463165088409210929201564518908251675851193212090312153202710950611, 65430568356698229457733164116539029669340192339524852345167889932007830803713, 83005759669335703543538842561745612525242745913149020160169673469294684269349, 86695300569990829413494539259312051326564517598709183416846805385774886176327, 87649503475806433108642579024197030978459906709386640769733298397489631575119, 67546279258240068058305769281370224151667980031696762855998467222703960646549, 109277222890519331704406685175081474974918071159722270158398833428598261621993, 94947541482876422720663520475916415155713415168744242709306335577278248129671, 72169704519430039945520319412623531417839608722431394881643470024106954771823, 67960163975784724339119270210646072354375119081204577840800359343098463410911, 99600976311231076437603674530239237427983536499904250636338541144596856152681]
#c=[[36006797306819385066479875554093947690583427970449583820207929310836800884907, 42421831928852572111305575764455253114855197661030346257979092292334693704638, 12802758082612276306666301210467012086210333405770973816248015272325645518737, 35891119003347284519077367147618128608424314149438118637710340094202006973607], [69221811235046204007409195125183399115207721139473251108686359647136964539528, 68728546052531932227774742525240050245981893208569278338806756195046394386320, 77378932313251132635143406501260917558950175409375255430759788116685665756853, 52610629088183684552705334542273079173241031671071904128690224212767984326814], [84632180774187758644772651231005808936754972376616591239738706882585325508504, 22245885241129428291065279034982203110690225047634487933389806520943556010139, 65058154300579433325392929157176043693547112910255708084394089838078169979653, 26450521689799343844879689401496427283279097300795496218417820952255310453381], [31743210200723432871171527300926464156713378567872351797727553809801223755669, 13585899089974057026763852048073375117825112528263695778864069316682632842469, 61718974141826995988697061776372539645461814294568567001726256109104825647174, 51180314603392071189287058511013567287870020999513958065031674007822278281592], [54972437884087220348657249916515696089000557932808046438758622081654015388431, 60595394189514447466338506137494568375465810079275014516953880523799578017650, 48290106501584587524538351792623115913538457076946109833703750186838567097829, 75809640108047877199495621711957016420204838905577105767711805228492185803198], [2043782039074334576524460230918369530353673853539675192552828729137718721899, 49835004172676327317136633790276532689791891581739516605994211773520862094089, 74150446127124215081973853925119891529594162176613983713739514646864857274598, 3870903633214309884568064156029910145031131868082685800718700340446754642668], [58530922734504496400650172153260509666806593206632885245359170202099163777029, 24679955301703325026039585637067957593890919790442322117013190013849632870045, 47461847478301275711387089619360312020232490159064156700718722079533108310495, 78436661760605062831488783213279281637896003485976271847409520316669048162591], [3960169205004685923298734670827529710258905436583484891133449600679523626998, 56971763036590510871648632641525055519742294555040115044720432874482626152527, 7500941845513450196840656641552395008944195976110947855355515297144549893577, 104364444158131675753431216431697712763613996035708348677723420914206545999308], [21090310989423433113256120275297260716078136824734467530250689161392790805917, 59095240674034520085214866457855433129352762312493710903594522366480317145097, 25950268632849909273587896220763105221984980662119437334003683923010964181793, 22214910913289817220594820237750728594412035322558117144502181839908519483813], [6516207309607110723013310828779534786605721487724433166085213573594060054191, 62491095915002854769743893168840271080994195414466604510886959458801333994425, 43298696119722427147738220942971604096101207270771677319478440633957185506012, 95999300849358990419162309412086189707629278626118528491801630061635930409174], [21901937371736027133484836626793049950863305103635439434565692334061323247459, 22177707944556298482781825594816606678702151909926553218938857302296851101061, 37265517992688571580384548897674161792052985496826940853296718063969030761085, 45803015810935362104176472501216732994877801735307247883040947086374864784522], [22887302429552282917137975404437379689230279867683032429064655381687354309967, 63687512791087585071097169701758075850922324857489524802811455099431146712006, 43241233600118761031756067392063544631958472413548145463886944168747993611755, 78540416079875697330277927812643707908744419489483603613867805715379418188382], [83274701456245595041914535781657541250722792681868330743604458671030342631093, 29265221035131869074958665850197081103720257562467498607821734305785454256445, 19656036104607964818483236621454584533830854692521644548949580232419092579485, 36685991496747026794589417986750583003976651961717444764360736602328859939203], [7197271849934394038490337096465830651019854061628854994110403632096530818658, 13199583400545916173897024693988359528617080325104182927755868559199746329580, 76705903744610047925943025263768006533642196751938988456317343613219129386367, 8284847848213860404087592474405055922947517109038702885136704630947806019241], [40192513898904947184731216279798716826510915071804534174239538082671192078053, 756883344718645808681598066443462390307116757281839378450937721653214302485, 46319296839244788373603804279624137323125709215284595152627739510983625831713, 38066834404440733412548216101182968084184940639461830700714702917736840764910], [52459924240743004858678271074727889512634425322058383892565820049302166247484, 1124830903052334805081369416754962375712146318972731973481260141314675294280, 7048586820754100983732909765398789018269542052380424872274364753361851089050, 46261533803791211860667474793341333491934930635468558951890405299902112599717], [23712997405587065505471765580307890926020635436932008780552027395793174460196, 67696894015776789806885369424535665938702806354704500197616129889160343225036, 22335907790107175161378264382954791596027764567679319454957440806458200559861, 76817272441881586284817699756225532359147752598882508352406898668675942956599], [48442733699161048528383543478196401606393182356208996862954079146924798030016, 33988046942702399144226829264100378601075005547176282333019034404108127701223, 3878811651113775226499837109875057444157158981192358109242560352485567236840, 48096508435450140842190594378561970076075899550630622502080370324305787016204], [4661700708549906139665791533582485338344505441635713456342199101346895847315, 57085434497175712126874334119472545667616658739402471396702109228089918012639, 43291903057149273908186130451801222008858189682043034712173498638683726314620, 43681777323686685006867808938443372833327865869793588659920726812432020143637], [34817244237217626483621974571192315048341502556634007719371004295715069335162, 10855671893795758052388714204250213675262352053079039688785650172729770783108, 55808546957704772545340135312880985328286637622927964296444521648705445287337, 57996505385421171401445757882512186395065784033051493647151141293523405436642]]

参考论文：

https://link.springer.com/content/pdf/10.1007/3-540-45539-6_4.pdf

参考：

NEEPU Sec 2023 公开赛 Crypto wp 全解_无趣的浅的博客-CSDN博客

[NEEPU Sec 2023 公开赛 writeup_是Mumuzi的博客-CSDN博客](https://blog.csdn.net/qq_42880719/article/details/130798835?ops_request_misc=%7B%22request%5Fid%22%3A%22168629897516800197022880%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168629897516800197022880&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-130798835-null-null.142^v88^koosearch_v1,239^v2^insert_chatgpt&utm_term=NEEPU Sec 2023 公开赛&spm=1018.2226.3001.4187)

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com