某校网安综合实践（三）-crypto
24
|
|
0
|
学校课程

1482 字
|
22 分钟

1.格密码

通过构建特定矩阵并应用LLL 算法，恢复密文c的明文，从而获取最终的标志字符串。

解题脚本

# 建议使用SageMath在线运行
# https://cocalc.com/features/sage
from Crypto.Util.number import *
from gmpy2 import invert
h = 311970364425799366998489758816351964614898164597015962390522858760089331210269507769408330245745888541705059882396722340774681935443615888403494901415226651295201132556613291289590900246992553502513664561058230713840616052310750850144077552701142563872837663789636304968423919464707545482008647087312063949024744195318160335652074407874634742273493108112212110123691909346846612115479023950119286716243604630664235633831784083300431161225131883065150778501178458601885263943907964612851841356128492283759401129349655263360496418606534637831065564054627124545266130146585012568948018083420026867791483624987951876329968315410612748989452628410331813540143425873481351220499681815979569479285905651270208308396719282247586008816711527598915797885618862654168623002012746684102245733757428828517277952675441290263051618987121956646671901357370585784409633697165339182406341764320293630983680416055584947772382282259966044517683538433409836256995980804901093405108581243143413703339657071622279140236369465154220363993923085583049720512383384577159975134910449465903227555419552492606439149153015674603047695345700309870206034743317361786333732070962362572427411597266252707397451423195512449103367120235737550650354427690243524900449675
p = 958396606448120961344481821891302529131234571519205540072533929007120447482644938027839069855225984909598017115601687321093037138370623689366302399472755221666720998204960391688686871213784218139146955110040572010513513710257471193690475085340782434134757767894370195789546551282060123540167285748706110004061656181247087025993389812671658906912145384679566372037915179523706023309666826191629634851598509448675340758156737530185937223948687001934035933966720541257653562031308634592003639145311246147664928094381997264652669457904886666262851691565920076364034433600062253014377522558972668765617631467665085324790312091927917199333642804731490452686230714946707520153374983386856748968281865500447110447064499127304576389450231449458997253721401398074788997192735673939296531420329207264490272774186484762804708405995307032141715953080254098506768585899454119852852002578252291310329200959476618660765556861112558404254680356703540148703891793429589128285327230398620737214653509556883409293525132433655639546382948760666188308135216174434756100646981938900940757869329579150360836505992616459066632938605335205569767007863591747811468281490752448411521431430302168214014717351186242150709061058943921599462022604009950194741903607
c = 767158168672362136291238223905378538545444315829681403660668665037917788547250510431680762324989504337886911129872811283399423182492713085621340850466620775416712732614020830060267436728824312319343522189998875569791210615658554329492772575522352284894778864900683043087475949382767603528807809596004213194946687583749277851731545121301799909443549367647188538291294493900118514585149301404415365107375148502163345229200555520367376148986792681776613941685900525114359918025093194374564154918465789098039688273260831196880453048787881692220588699313824407443049610470566611891830120455606865304514498141918370250200060333776115471607369861567714061571248634366226901360555240991881037749649258353302128601187117945261098036478588953880956746052307508140721683848770369771427200654010686745459084737649483182116223928908511586372587312845173805333061611628627699056444060210866689908925857413693914088384801590539118419817748706914585535977225375257595014121709225398146804929559026288825337416874187757876993164395155899845807880799091660701491902131855351054079661782867046531376623992742661604584530403794933640735943298254524984623808363772872836875750554022138997087590785362832339405833456398277842368920260448389099114876068641
mat = [[0, p], [1, h]]
M = Matrix(ZZ, mat)
a, g = M.LLL()[0]
m = (a*c % p*invert(a, g)*invert(a, g)) % g
flag = long_to_bytes(int(m))
print(flag)
# b'vmc{L4ttice_I5_pretty_easy_F0r_U!!!}'

2.DSA签名

本题考查共享k攻击。本题实际上是给我们多组签名+消息，让我们进行共享k攻击，以此计算出密钥。

解题脚本

import socket  # 导入 socket 模块用于网络通信
import time  # 导入 time 模块用于时间控制
import math  # 导入 math 模块用于数学运算
from gmpy2 import invert  # 从 gmpy2 导入 invert 函数，用于求逆元
import hashlib  # 导入 hashlib 模块用于哈希计算
# 定义服务器的 IP 地址和端口
HOST = '10.12.153.8'
PORT = 31961
loop_times = 7  # 定义请求次数
def get_signatures():
    # 初始化签名和哈希值列表
    sign_s, hash_m = [], []
    for i in range(loop_times):
        print(f"\r获取到第{i + 1}组签名与消息", end='', flush=True)
        time.sleep(1.1 if i > 0 else 0)  # 等待一下，让服务端哈希值更新
        with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:  # 使用 with 语句管理 socket 连接
            try:
                s.connect((HOST, PORT))  # 连接到指定的主机和端口
                s.recv(1024)  # 接收初始响应
                s.send(b"1\n")  # 发送请求以获取签名和哈希值
                response = s.recv(1024).decode().split(",")  # 接收响应并解析
                sign_r = int(response[0])  # 提取签名 r 值
                sign_s.append(int(response[1]))  # 保存签名 s 值
                hash_m.append(int(response[2]))  # 保存消息哈希值
            except Exception as e:
                print("发生错误:", e)  # 捕获并打印异常
    return sign_r, sign_s, hash_m  # 返回最后一个 r 值和所有签名、哈希值
def compute_keys(sign_r, sign_s, hash_m):
    # 计算签名差值和哈希差值
    delta_s = [sign_s[i + 1] - sign_s[i] for i in range(len(sign_s) - 1)]
    delta_h = [hash_m[i + 1] - hash_m[i] for i in range(len(hash_m) - 1)]
    q = 0  # 初始化 q 值
    for i in range(2, len(delta_s)):
        # 计算 kq1 和 kq2，用于求解 q
        kq1 = abs(delta_s[i - 2] * delta_h[i - 1] -
                  delta_s[i - 1] * delta_h[i - 2])
        kq2 = abs(delta_s[i - 1] * delta_h[i] - delta_s[i] * delta_h[i - 1])
        kq = math.gcd(kq1, kq2)  # 计算 kq 的最大公约数
        q = math.gcd(q, kq) if q > 0 else kq  # 更新 q 值
    # 计算临时密钥 k 和密钥 x
    k = delta_h[0] * invert(delta_s[0], q) % q
    x = (k * sign_s[0] - hash_m[0]) * invert(sign_r, q) % q
    return q, k, x  # 返回计算出的 q, k, x
def send_final_signature(sign_r, sign_s):
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:  
# 使用 with 语句管理 socket 连接
        try:
            s.connect((HOST, PORT))  # 连接到指定的主机和端口
            s.recv(1024)  # 接收初始响应
            s.send(b"2\n")  # 发送请求以验证签名
            response = s.recv(1024)  # 接收响应
            signature_part = response.decode().split('"')[1]  # 提取签名部分
            to_check = int(hashlib.md5(signature_part.encode()
                                       ).hexdigest(), 16)  # 计算待检查的哈希值
            sign_s = (to_check + x * sign_r) * invert(k, q) % q  # 计算最终签名
            s.send(f"{sign_r}, {sign_s}\n".encode())  # 发送签名和 r 值
            final_response = s.recv(1024).decode()  # 接收最终响应
            final_response = s.recv(1024).decode().strip()  # 再次接收并去除空格
            print('\n\n', final_response, '\n\n')  # 打印最终响应
        except Exception as e:
            print("发生错误:", e)  # 捕获并打印异常
# 主程序
sign_r, sign_s, hash_m = get_signatures()  # 获取签名和哈希值
q, k, x = compute_keys(sign_r, sign_s, hash_m)  # 计算公钥和临时密钥
send_final_signature(sign_r, x)  # 发送最终签名
# flag是动态生成的，每个人flag不一样
# flag案例：vmc{x8Xr9WQdXWyT08k91DwVHXOf8UTeuxh8}

3.简单RSA_signin

本题考查 低加密指数广播攻击 的基本原理。由于 RSA 加密的模数 ( n ) 只能分解为两个质数 ( p ) 和 ( q )，当存在大量的不同模数 ( n ) 时，有较高概率会出现某些模数中的 ( p ) 或 ( q ) 是相同的。

因此，不同的 ( n ) 之间可能存在相同的质因数 ( p ) 或 ( q )。通过计算不同 ( n ) 之间的最大公约数 gcd()，我们可以确定是否存在相同的质因数：若最大公约数大于 1，说明存在共享质因数，可以用来计算私钥。

解题脚本

import gmpy2
from Crypto.Util.number import long_to_bytes
n1 = 14311136148050672419989799427104593072360126727996357997737771323416025835284720893491268771893217645541031293941317348923695393578822127064753705575709943898954014710923499190306307017818318390870426431494240684558802605958320106573913876164986666561830970380943541512973969654875418388029963883263795540100294000652035421721153033158606886225047717035380694266340621241058788836739065168640629195395653804561942826938109892199374995491378415156147693480678475024810828139951747950220497130345509778576687918051304112321531099375758183212756982987812354817112831489097289915234500393466864136375176292077417921687591
c1 = 8202852785876270157863052002756570090495393573671910005596893574711032740799397936438752152316778125546684561981338463208326745896180102802370978316384870311169503381907548755600240181944292293100404896959898321176621546360167190501335724257238240403713094884305633523048639214129394823985010999561391781743707553324793755021757051461973597832982432346639642869313748849063526909019855981543807729556420488050052723152244834336120282794593657490451161292428134031108007189435605884011355136767968584350123097381476633363636607162409220915871083047432673676511990516075293548074046637736562426611866570077500698539680
n2 = 22460630266363520029013021830190111925329835544313855662313212281658578787408425121746654947555625278077070857950491561854244184358831593693401721178255080011283483166990848792925382062687461708064297371852747026491916479626204475066556067461737173240576845698707955971525234482303159455512217128800846697492645909822799706189901143541218109536441677917374991428785622511895854755385017003577998048914326930260299548055902668955263923329699864691566463108030209336765460544710136857719832988428394394769888465359508988507140048564837670939119403564949331948498516419572732361620147189572260923459583795866987431472081
c2 = 19432526669205632933281999861455073126026491878458861462621671904525045303797730344504664894989121738349412826500038805214988364882422697810525702555846266927049056573550455809225019296662813696615576976775557379322353977631701219576737211986654717188414587448855563253088294339676132929423451927193840172170831630957970119245046884198116729677995682724993252964058262130466937449364313778985085600422455117132498006037055650635335969965552319287195500774665911108494949571438011160394509085343201107394718958934368493483937533921994429464995605815197936150743857875518252748373785745134894438095024730301450741282453
n3 = 19992746611686250573671647760828360992790652451036608485720507826226043955859605408699699451019411863153770186932187717361941241622231255580260254382190262367584016091552087834953099478841911684756435739887399597301184520835065407680478222756923581533037301452594035962041816064218938028684243323353238297033311148235732893085634080009149876298111208271705744330460176345343233021475649651633865523828218112224430515495332970126197819600137819495585334361803576994675776334845387976082014911523417917110951173363569720887345722135810314736716071201425604128184784721804187807248872096097020325662816762510615645436571
c3 = 16761239931080052583119467254883044613843428027350731469077889755297092262423557561780949894774738153466792131508164424611538795049564635236315525530198686623671728115367282884740168549689217686122288333094825644587937316520469662154889810617075602455599097628405412912960405528988078488648702010584562028792787672783864514722323122218797620445952080240913471402410015623219514189511849780521859190708136293642508967973582651262544468081041064272940196809701633056064725146113742596400325295624752267310145921728201937132472951530120140732967263171552147743333230746840533608857664162331567733570997571556980494505239
n4 = 14921019826845713229726484877726270689241984653233268169688581852222590026842979172232582201402351497096998635751451613780807919110829778250462314819294132840793361485689131884323905476990345344800354500999858720835604109955299649188824263262669855070670628208634166768950607071709626319152810191066883413750048659163843436449669170112757598763514534870597389082424678999448930303733468731977925649728447952296168606875381663955587878344578094143259273354224725300090671948728897863727697421927341322881916785053396241076618270994707195235790442124786541590007807595576441777573453034209389536619042112736318910325443
c4 = 12104686397227931738546574591380357622718178963781492437624997870522237479459381810675815758685789724824313573784023039145284572968062809536304287761460797042217424459047221638130036481992030911937893114466061516306456345748133768987953527429987096596623215114426732278065630014608792807941320949416675074089844010060080921581229069604896558377581847155615744077237097571536222960051367929483415114503862879052522687638568271435493496076230228746863486426062385692270549241536559384169613474232448181941652396294943544455326954005366751933697950468829610423401267530652463253552042799027022764104040446616376787931262
n5 = 15272117973129901152469934169722584048788617147757632365791658800750926957768612286888655116918215974078040294515078885318068654960150527447692598365088831811318995117764230964044314038653716203717859969703738041008028610260162032852230191129230669874776941136044240565959807731829332386524847728126521323260017315161990238212645767574135949869496033390177430205791394909637449063992173085079787248905055073067988314706720450392314407632759345179381055339164316392960259203496045265143504969702593896637060523554936600159946787412996100488023723444073375164457093841750815749630727650631728835961802439288652334603699
c5 = 532297764293374431345319135535171240943045095118219366603669734014040206220242931909329515668555766603866714403157308728341132357911855102211146534373024920996222861666636331003591302316949272206703801068406427074138926340739839088705439896695034187068266797961518069038409308780210449954657401069006825070712684945411758748948053987788727397125874879525408625499123038021849139152296839592866703874403912296503961242361567822221589253466316231297080976876879308748352796893535008780461957623716084138624526943379136680045925661302308904677210858883806926960136050804664180676876621068489103165553870202604910995376
n6 = 18127445565190266841827299756408077665043095777650452035033831588763995250624530226449665578869899110759577972695623880503477133385907626279488761885382985633639158084738586514921778278865555245046914680629518749458804403715569886973918541812080562181172650152502537375812891519048771588558082901204334158435252420515643904211799472847301722784898572678150897515798405098712379089818245129648803474141927125771800505244427082093944945185718686900289000905220781484367689812209400844758941386387687906381241190162863125419104564432734478849541810862091617652273228009230499783892890115058385198859611734403581802226249
c6 = 2625551961520404822614319606750443223876109845986978449151552936165052835749320005616623196600993458605095692554096855097708637686395841605169785299974081565211071562756383216779434333914364702548682103868142599355338105838477768408407890186681959208882692900392416470186936290224911113828252994437329629224782258411200582637781334626739579364350628562723437287922536352184401820922080861455065326765600711933303305357435210407951675455959745201471975055113425613549118728398786287459590835602915250133309913998661270053053432537991582471485775363429365803053660902542066262325929134649526894392488264686353472291858
n7 = 25237660992000441783172540924847901949806255476314654124494383045994148743356940942874440881134542667025560951339481569248423701914672738098714921038919656013069298866778354991939846296089547559885794448902624003971729162137167779783831440124242627534249857061025395057022758192195177674589080120150420376436821217724603838445185443572474812746620205786353221045209307079281670355293602682023415982568245346832251186821302831580750259178166736133209805179750561812054051649147603891176221687183017285450487422460530968797430297529765912950971240264980005481524829778501446609450861098784049198495969035740974313640899
c7 = 9758510052958978102948228334244869415165545109949510690189969202323542658592737853436921895896043005877526302279472466168422359921314039734929206526881778897067215647448266071512675649702774441944204282736857844920408229618077379117600268298609365142116955969115516459293315364107943215961013155993930752669360414805051578461860895483051303295323035671380094695239371154702653128168720030747483907996025437103350598863926938687075304844605508496789347812093047555407980728165302731410858261186919424953215143824645606262477453433776500347616509302859390460838136875303489356615422369128295995697637647427439868512713
n8 = 19955533170458662985761804452932449390593987518346562969898631299352201545989831893281460148412578517369526658720919482088707995320166109420916639891241308064221944701870005800204762179119680918106851022692518283361744328592294747241881314329848700511911793997624474016287850999414088344863968543717229037324417972590306738893549445237225520016321591983071408545934897016157332798449236458315361699529350506615556348312839445922025118648372865971639732379049406524589404975922736703232700351701473395236257592011553525644430624257716575279594923098275250572920192237624282328232519490104798953285753444652595899325957
c8 = 5022433753545584574117143031265627519908700017841852901138347971391945531323938738554352208060507403852953111947660248378367376641166912935132106560475177447748171664309944096414351572774023692450018139372858073849291842984156603507644503465873113426624118216783446696139091851402504511649519500241874169560056201292888688576629583893408839693395504785358607277756283059836657157634021296323632131586516047266988531300889762998547827434860640455346645237261137583933232042892176045160395713238138369323003278436265032180107440685789185485462210316833781034956658234384694961710079505566144177559766383151016855335339
n9 = 20608859199634918194130601032088539577415284572777850653607410127132207005192265019309019164896422332029145172996783380959321298059319995774401880466279250204140649254796534391070043342181336200002503879904615736004828008926607372732441420607420584367190978626924020480151314284284271853775842020380995071916692220803063585709257634315562577825188623291317610474409190581346471579851384173607854992048115105358643136393989630879508396409064130776969846093322028735610922546423654322949611587521946393195118630449197252203349181158400840617839925338111062535072205440412314897070869886866764427944393070693426107294061
c9 = 10050192344410608998068935375429239665670771519187387860605372443607032600329268146513824254947276553686922523385845186737194846802836526138869569581385508315470455867035385142239183398889710456190235351535042176553076510518297665588409475479055316588612397841445501393454840325279804411511615924369341032269701298276225067067804199514896732689438177467900600611801904132486240038071882239572810172242699299213898596749424528782386605914162076213853512549652177688327788657065676937153434280062393407135432363197473014592849343623564548612342563086319095383330615202341497407758655556539832050197369002526050470369599
n10 = 20805806285184049632494903182037898656796626777130488655004407970221271788165331882237257708603925314800420354895662217494864226959645625070075239215473861715722541741630553384259977713513434100926736696035584681939841921802247690220451066139553223351054942828702790914990631163295186943011164531235577767867026158764389595894194881442438953294426783321898101463208326465639358833221243860132035703135961314186234724441766419253351861465289474724009012132776673656968918735723071233452819815473094463291660853832477326891639373777507662161915777525496490832324659772926373787182948210159495450928991214205652815330869
c10 = 9015884859671622552932005389012646083555572003693004412203185009302291900722481874063759253219711489647937724537174211736617547805446849940178318477773239764757765227817207167959108716372580334865271965514294712352538984676415148679080318564492200186995778605026902573402392252129229000029591988698410733858036585245384330203994610513481342765008508698708246744811783368314010882533900522609878773176859749919592970286877545921479814172431906082707504673496510271590855659018837819464864298105570193152298748220192028719030743533832435738266779004010636016620678768943552808013803769508977675662405020601347549475802
n = [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10]
c = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10]
for i in range(len(n)):
    for j in range(i + 1, len(n)):
        gcd = gmpy2.gcd(n[i], n[j])
        if gcd != 1:
            p = gcd
            q = n[i] // p
            phi = (p - 1) * (q - 1)
            d = gmpy2.invert(65537, phi)
            m = gmpy2.powmod(c[i], d, n[i])
            flag = long_to_bytes(int(m))
            print(flag)
            break
# b'vmc{This_is_really_easy_rsa_HAHAAAA}'

4.分组密码工作模式

本题涉及到 CBC 字节翻转攻击 的应用。只需对 user_key 进行合适的位修改，再用修改后的 user_key 解密，即可让明文变成我们想要的AdminAdmin!_____。

import socket
HOST = '10.12.153.8'  # 服务器地址
PORT = 32014          # 端口号
# 创建 socket 连接
with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
    try:
        s.connect((HOST, PORT))  # 连接到服务器
        s.recv(1024)  # 接收初始消息
        s.send(b"1\n")  # 发送创建账户请求
        s.recv(1024)  # 接收中间响应
        # 接收token
        response = s.recv(1024).decode()
        start_index = response.find("token:") + len("token: ")
        end_index = response.find("\n", start_index)
        token = response[start_index:end_index].strip()
        # 计算用户密钥
        user_key = bytes.fromhex(token[:32])  # 前32个字节为user_key
        cur = b'HUSTCTFer!______'
        tar = b'AdminAdmin!_____'
        user_key = bytes([user_key[i] ^ cur[i] ^ tar[i]
                         for i in range(len(cur))])
        s.send(b"3\n")  # 发送登录请求
        s.recv(1024)  # 接收中间响应
        # 发送计算后的用户密钥和密文
        s.send(f'{user_key.hex() + token[32:]} \n'.encode())
        s.recv(1024)  # 接收中间响应
        # 输出最终响应
        print("\n\n", s.recv(1024).decode(), "\n")
        s.send(b"4\n")  # 发送退出请求
    except Exception as e:
        print("发生错误:", e)
# flag是动态生成的，每个人flag不一样
# flag案例：vmc{U7pSxq1bodyGydI6gpc1amTCkYvkBnvF}

5.古典密码破译-Hill密码

三阶Hill密码需要通过三组密文和明文来解出加密矩阵。根据题目提供的信息，我们已经知道了两组明文和一个字符，可以通过枚举未知的两个明文字符来填充明文矩阵。接着，利用这两组明文和密文，可以解出加密矩阵。然后，使用该加密矩阵对密文进行解密，得到解密后的明文。如果解密出来的明文都是可打印字符，则输出解密结果。

# 建议使用SageMath在线运行
# https://cocalc.com/features/sage
from Crypto.Util.number import *
raw = b'>u\x10l9\npI,0\x04^J\x00ib\x03\x0c\x158d\x1f\x08Ixk\nF\x19fz\x14PT\x04\x03>R~'
rawi = [int(x) for x in raw]
p = matrix(Zmod(127), 3, 3, [118, 109, 99, 123, 0, 0, 125, 32, 32])
c = matrix(Zmod(127), 3, 3, [62, 117, 16, 108, 57, 10, 62, 82, 126])
for i in range(0, 127):
    for j in range(0, 127):
        p[1, 1] = j
        p[1, 2] = i
        flag = True
        if p.is_invertible():
            K = p.solve_right(c)
            decode = ''
            for k in range(13):
                tmp = matrix(Zmod(127), 1, 3, rawi[k*3:(k+1)*3])
                A = K.solve_left(tmp)
                for l in range(3):
                    char = chr(A[0, l])
                    if not char == ' ' and not char.isprintable():
                        flag = False
                        break
                    decode += char
                if flag is False:
                    break
            if flag is True:
                print(f"{i},{j}|{decode}")
'''
56,60|vmc{<8e3EDJua&47mUIDe3ouIzWeR01_dK9D}  
56,78|vmc{N8eDEDhua^47nUI[e3(uI=WeL01mdKhD}  
56,94|vmc{^8eEED.ua-47}UI7e3vuI#Weq01AdK/D}  
56,100|vmc{d8euED8uaj47SUIie34uI9Weo01pdKiD}  
56,112|vmc{p8eVEDLuae47~UINe3/uIeWek01OdK^D}  
56,117|vmc{u8e~ED*ua.47[UI#e3wuIMWe?01adKdD}  
69,60|vmc{<Ee3.DJ6a&$7myID(3oeIz2eRV1_`K9m}  
69,78|vmc{NEeD.Dh6a^$7nyI[(3(eI=2eLV1m`Khm}  
69,94|vmc{^EeE.D.6a-$7}yI7(3veI#2eqV1A`K/m}  
69,100|vmc{dEeu.D86aj$7SyIi(34eI92eoV1p`Kim}  
69,112|vmc{pEeV.DL6ae$7~yIN(3/eIe2ekV1O`K^m}  
69,117|vmc{uEe~.D*6a.$7[yI#(3weIM2e?V1a`Kdm}  
108,60|vmc{<le3hDJwa&s7mfIDo3o5IzBeRI1_TK9i}  
108,78|vmc{NleDhDhwa^s7nfI[o3(5I=BeLI1mTKhi}  
108,94|vmc{^leEhD.wa-s7}fI7o3v5I#BeqI1ATK/i}  
108,100|vmc{dleuhD8wajs7SfIio345I9BeoI1pTKii}  
108,112|vmc{pleVhDLwaes7~fINo3/5IeBekI1OTK^i}  
108,117|vmc{ule~hD*wa.s7[fI#o3w5IMBe?I1aTKdi} 
'''
# 经测试flag是vmc{d8euED8uaj47SUIie34uI9Weo01pdKiD}

6.RSA加密算法攻击

对于这一题，我们有以下表达式：

[ \frac{N1}{N2} = \left(\frac{P1}{P2}\right)^2 \cdot \frac{Q1}{Q2} ]

显然可以推导出：

[ \frac{N1}{N2} < \frac{Q1}{Q2} ]

因此，我们可以确定 (\frac{Q1}{Q2}) 的范围为：

[ \frac{Q1}{Q2} \in \left(\frac{N1}{N2}, 1\right) ]

这是解题的关键。

接下来我们对 (\displaystyle \frac{N1}{N2}) 进行 连分数展开，并求出其各项的渐近分数。在这些渐近分数中，某个连分数的分母可能就是 (Q1)。我们可以通过验证条件 (N \% Q == 0) 来确认这个猜测。

解题脚本

from Crypto.Util.number import *
import gmpy2
n1 = 27682578737141139764880192910976946263355689816882797515059917479242862799083599745594956880258244112867559722435850732812023189662581052511287867553308318268020022386306820424829898858029986193412922645944359409248568131057377380697236238480724883073062491532254626363468032145049953168789073328812076794158602028961853986034378144749656228541552641207393473830715156452473432130040360471566096165146087202836036783304640579183082301858529818598032339821237841219774124710789761912675044056265735587753304064079484844965820681168729776560497921764083742448045654891113500035063474318442078036531813957551086231747079155691690001433127187382636049871228279519466735719768798574776353687049667125384146566107739705553580693984918816215940308884007192621418304753551998125658993859095063641090798574130161651257890916914325076137436869018454577522833
c1 = 14360977893873474578201937159000122429359790977572665232657843468076201963407780015131857192621550737338805880514393357390576423731328871867241029260294051045710144482989801857054158816998897546124709802730198690244128545073634486145786763294634081834588146373913232490890078533918320777534358739106486350300547206365723045306767038214923412032633833255742963954701475401704385045019069883734625251436409851588044241336835452728962860280865504000103361559688861149086469939940113748174610019620309023214292662384279070127090992947332945432141695583191136521301940116585610033790348125114471980285332011918355578839128892075058698885319243593345096734776497817461251643381989958326810478500026684389358920342021836572511688796450072700142033952403561408907486022094802237175920044147084170050294965826258250618675638343726352907476393474128674488943
e1 = 138906518221471521524404330039616633297752765534176570868900039237133419857485415639423196636068397237296224442083213768630488100717977884415342104239280950424735129147986053115335928783190377695248250926374734988108972136349625965753649992146322810352768246041575396721661142246729747572832017510241749082431
n2 = 27682578737141139764880192910976946263355689816882797515059917479242862799083599745594956880258244112867559722435850732812023189662581052511287867553308576254232706953290519059976159239205559295965110148734449650209977235953163255494808056707188551192674128213090005439928085856216617642935948961573449294338310127166077195263402939848861686214485115686799032901147314759348481062418109120418661302585413868782602282463165171129063197961455779193665041902822948963032580054067050227612838335828201043413949164885293325493829570131849345344856137656453666135670724974184749115550720826497558763320127218251970576144750319782121194483563545371157323166968983176013145267856898865437101799958588342741257457472036311490402279982286349929050116350394664561659857216725849236910894778018502118673902399095646487808462155207034764432342699549109080808769
c2 = 11293777290569693972360166961981727494638218221438571150393361751316389824613571820229370915191500766619410597117671232443452691634734112652285521806824284959073558010661204730954928847260946403867297932862687770449632506087883187920107766050673462588812979708792790888354008526054467620780053118019643408427959406056087370960170992834047890080269663747877143270683069575318397144844481262382463469080755423097527007161449411933936669451476467352049264455203632729909164666006688294056405955940041007137719228484035343153943155100892867641033645111253109951972003798413524003505574000784399458705347262353155363413513341797868942085136977548116650815336000627353933708913237438841909324920070013498153627767891674969586034872104569344923832761239959420543717354211689339868787331074579605476477152218068810732089913023456240425720821047030224659918
e2 = 138906518221471521524404330039616633297752765534176570868900039237133419857485415639423196636068397237296224442083213768630488100717977884415342104239280950424735129147986053115335928783190377695248250926374734988108972136349625965753649992146322810352768246041575396721661142246729747572832017510241749082619
def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF
def Simplify(ctnf):
    numerator = 1
    denominator = 0
    for x in ctnf[::-1]:
        numerator, denominator = x * numerator + denominator, numerator
    return (numerator, denominator)
def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf
def wienerAttack(e, n):
    cf = continuedFra(e, n)
    for (Q1, Q2) in getit(cf):
        if Q1 == 0:
            continue
        if n1 % Q1 == 0 and Q1 != 1:
            return (Q1, Q2)
    print('Not Found')
Q1, Q2 = wienerAttack(n1, n2)
P1 = gmpy2.iroot(n1//Q1, 2)[0]
P2 = gmpy2.next_prime(P1)
phi1 = P1*(P1-1)*(Q1-1)
phi2 = P2*(P2-1)*(Q2-1)
d1 = gmpy2.invert(e1, phi1)
d2 = gmpy2.invert(e2, phi2)
m1 = long_to_bytes(gmpy2.powmod(c1, d1, n1))
m2 = long_to_bytes(gmpy2.powmod(c2, d2, n2))
print((m1+m2))
# b'vmc{Y0u_Ar3_real11ly_sm4rt_in_rrssaa}

7.LFSR-MyFSR

该LFSR的反馈函数表达如下：

$$a{i+n}=\sum{j=1}^{n}c{j}a{i+n-j}(其中 c{j}\in\mathbb{F}{2})$$

不妨设 $$ l =\begin{pmatrix} a{1} & a{2} & \cdots & a{n-1} & a{n}\ a{2} & a{3} & \cdots & a{n} & a{n+1}\ a{3} & a{4} & \cdots & a{n+1} & a{n+2}\ \vdots & \vdots & \ddots & \vdots & \vdots\ a{n} & a{n+1} & \cdots & a{2n-2} & a{2n-1} \ \end{pmatrix} \quad r= \begin{pmatrix} a{n+1} \ a{n+2} \ a{n+3} \ \vdots \ a{2n} \end{pmatrix}$$

显然有$$ l \cdot \begin{pmatrix} c{1} \ c{2} \ c{3} \ \vdots \ c{n} \end{pmatrix} = r $$

这里可以用SageMath的solve_right函数求解

解出cn的值后，构造递推矩阵m

$$ m =\begin{pmatrix} 0 & 0 & \cdots & 0 & c{n}\ 1 & 0 & \cdots & 0 & c{n-1}\ 0 & 1 & \cdots & 0 & c{n-2}\ \vdots & \vdots & \ddots & \vdots & \vdots\ 0 & 0 & \cdots & 1 & c{1}\ \end{pmatrix}$$

根据题意 $$ flag =\begin{pmatrix} f{1} & f{2} & \cdots & f{399} & f{400} \end{pmatrix} $$ 而 $flag$ 先进行了2024轮递推，再开始输出，即 $$ flag \cdot m^{2024} = output $$

所以用已知的输出与 $m^{2024}$ 解出 $flag$

解题脚本

# 建议使用SageMath在线运行
# https://cocalc.com/features/sage
ct = '10000100001110000110010001010111011110010100101011100100100001111010011001010101100101010011101010000011010011001100111110000100101011011101001111100010101001111011111111001010110111010000110011110010101001000111111000011110101010100010101111010111010001101100110111110001101000100100011000010010100011010111110101100100111010101011011100111001001110010101110011101010110011101101010010010101111110100011011111110001110000001000111111000011101010001100110000001010001000010001010001101010110100101001011111100101100001000010000011000110011110110111011111000101100100111101111011000000010111100010010010100101011110110010001100101111001101100000100010011101110000100111010100110111110110001100001000100001011010010111100011001110001011011110001101010110111000101110110110101101110101100010111010001000'
n = 400
c = list(map(int, list(ct)))
l = matrix(GF(2), [c[i:i+n] for i in range(n)])
r = matrix(GF(2), [c[i+n:i+n+1] for i in range(n)])
k = l.solve_right(r)
m = matrix(GF(2),n)
for i in range(n-1):
    m[i+1,i]=1
for i in range(n):
    m[i,-1]=k[i][0]
v = (m^2024).solve_left(matrix(GF(2), c[:n]))
sv = ''.join([str(i) for i in v[0]])
''.join([chr(int(sv[i:i+8],2)) for i in range(0,len(sv),8)])
# \x00mc{Brut!e_@r_so1^e_A_sy3teM_0f_eq&&aT10n3??}mQUMY
# 这个flag感觉有问题感觉
# flag应该是 vmc{Brut!e_@r_so1^e_A_sy3teM_0f_eq&&aT10n3??}

8.DH密钥交换算法

这道题表面上考察 DH 密钥交换，实则核心在于 离散对数问题 的解法。题目给出 ( A = 7^a \pmod{p} )，我们需要计算私钥 ( a ) 来解出 flag。由于题目要求给出素数 ( p )，可以选择构造一个 ( p ) 使得 ( p – 1 ) 拥有较多小质因数，这样便于使用 Pohlig-Hellman 算法 来求解公钥 ( A ) 对应的私钥 ( a )。幸运的是，在 SageMath 中有现成的函数可以直接使用，因此无需手动实现该算法。

解题脚本

第一步、构造一个至少1024位的素数p

from Crypto.Util.number import isPrime
import random
def generate_prime_with_factors_of_2_3_5(bits=1024):
    count = 0
    while True:
        count += 1
        print(f'[{count}]', end='\r')
        # 随机选择a, b, c的值来生成p-1，使得p有足够的位数
        a = random.randint(100, 1000)  # 控制2的指数
        b = random.randint(100, 700)   # 控制3的指数
        c = random.randint(100, 500)   # 控制5的指数
        p_minus_1 = (2 ** a) * (3 ** b) * (5**c)
        p = p_minus_1 + 1
        if p.bit_length() >= bits and isPrime(p):
            print(f"tried {count} times")
            return p, a, b, c
# 生成一个至少1024位的素数p，满足p-1的质因数仅为2, 3, 5
p, a, b, c = generate_prime_with_factors_of_2_3_5()
print(f"p = {p}")
print(f"p-1 = 2^{a} * 3^{b} * 5^{c}")
print(f"p.bit_length() = {p.bit_length()}")
'''
tried 241 times
p = 1255652507375424180771153661593175450240095099309617997830398479481251473806248999027009487987474628937865240529484483880639448709701174539063275550960844784506422070337433308527616053480228338110351562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
p-1 = 2^230 * 3^406 * 5^242
p.bit_length() = 1436
'''

第二步、接收公钥A、B和密文m

import socket
from Crypto.Util.number import *
import gmpy2
# 这里设置你申请的环境的IP和端口号
HOST = '10.12.153.8'
PORT = 10615
p = 1255652507375424180771153661593175450240095099309617997830398479481251473806248999027009487987474628937865240529484483880639448709701174539063275550960844784506422070337433308527616053480228338110351562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
    s.connect((HOST, PORT))
    msg = s.recv(1024).decode()
    s.send((str(p)+'\n').encode())
    msg = s.recv(1024).decode()
    A = gmpy2.mpz(msg.split(": ")[1].strip())
    msg = s.recv(1024).decode()
    B = gmpy2.mpz(msg.split("Bob公钥: ")[1].split("\n")[0].strip())
    m = gmpy2.mpz(msg.split("密文: ")[1].strip())
    print(f"A = {A}")
    print(f"B = {B}")
    print(f"m = {m}")
    print(f"p = {p}")
'''
A = 355669952921034267831168541396567338166363947361450219963530670142687154164278499711963689789931667207960303928644101973338721608009019378529002236001354163677946386844933203453073205489158777257835345405122620355189693067109336813677425279853274540753847346090117570519936576319829093516256630287227380835834438884042941842672591004254247265449059753546783624217188034293412170221475955127046619991959632722679225589581470575106694
B = 4992551235074421871387972107968363771487136233276180239286246353689116359919410725041440739723408220491150036255059188021684456127922797856578063653007508543762038252915287314177885710762029828656129272330513550260038681775995929558879880649055420782855871380114208676073334623012899162425011870026150202171063960907783143952078876819868496068228454956523392683249724797267889518106109240459463770234197103729380352444944674569942
m = 529905113648101891970936246144584619026712228170489544108250303351975726498967447469928715993635197350465528008213412604954544642112322932091016935939664407327069321404497425823323811343729108388418224967949337788356272012533097878402642053780546701312232145530937593063913656091383846555658677949338255392032614254214581291911487366810137132348740515477804813556580096985377993909891228820887237253011458755426767833584560979924277
p = 1255652507375424180771153661593175450240095099309617997830398479481251473806248999027009487987474628937865240529484483880639448709701174539063275550960844784506422070337433308527616053480228338110351562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
'''

第三步、用SageMath计算私钥a和flag

# 建议使用SageMath在线运行
# https://cocalc.com/features/sage
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
A = 355669952921034267831168541396567338166363947361450219963530670142687154164278499711963689789931667207960303928644101973338721608009019378529002236001354163677946386844933203453073205489158777257835345405122620355189693067109336813677425279853274540753847346090117570519936576319829093516256630287227380835834438884042941842672591004254247265449059753546783624217188034293412170221475955127046619991959632722679225589581470575106694
B = 4992551235074421871387972107968363771487136233276180239286246353689116359919410725041440739723408220491150036255059188021684456127922797856578063653007508543762038252915287314177885710762029828656129272330513550260038681775995929558879880649055420782855871380114208676073334623012899162425011870026150202171063960907783143952078876819868496068228454956523392683249724797267889518106109240459463770234197103729380352444944674569942
m = 529905113648101891970936246144584619026712228170489544108250303351975726498967447469928715993635197350465528008213412604954544642112322932091016935939664407327069321404497425823323811343729108388418224967949337788356272012533097878402642053780546701312232145530937593063913656091383846555658677949338255392032614254214581291911487366810137132348740515477804813556580096985377993909891228820887237253011458755426767833584560979924277
p = 1255652507375424180771153661593175450240095099309617997830398479481251473806248999027009487987474628937865240529484483880639448709701174539063275550960844784506422070337433308527616053480228338110351562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
R = GF(p)
a = R(A).log(7)
superkey = pow(B, a, p)
flag = m*invert(superkey, p) % p
print(long_to_bytes(flag))
# flag是动态生成的，每个人flag不一样
# flag案例：vmc{ccWkmguSPf2FN6XdChbSqByJEneFdsQr}
其他CTF方向
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇