CTF 密碼學工具與腳本整理大全

前言

從兩個月之前(2021 年 10 月) 開始接觸 CTF 密碼學，開始慢慢對 Cryptography 一些題目裡常見的套路有了觸覺(雖然有時還是會一臉懵)，所以干脆寫一篇只有腳本的整理。

借一張知乎@醉清風的圖來說明這一篇文的正確用法

v2-4f7bb5ea2f5c6fca24d45ae96d020132_720w

這裡有 :

常用解密的線上網站
常見的 RSA python 腳本
其它可利用的加/解密腳本

這裡沒有 :

~~教你如何安裝這些工具~~
~~教你如何使用這些工具~~
~~解題思路~~

總結來說，這裡是我的密碼學筆記精華，如何對你有幫助就拿去用吧。

Caesar Cipher (凱撒密碼)

網站: —> Caesar Cipher <—

最喜歡是把 26 種組合都列出來，並按權重排列

Vigenère Cipher (維吉尼亞密碼)

網站: —> Vigenère Cipher Decoder and Solver <—

我最喜歡它有 Auto Solve(without key)，但要注意調整 Max Key Length

Morse code (摩斯密碼)

網站: —> Morse decoder <—

字頻分析線上網站 quipqiup

網站: —> quipqiup <—

RSA (非對稱加密)

公鑰與私鑰的產生：

隨機選擇兩個不同大質數 $p$ 和 $q$ ，計算 $N = p × q$
根據歐拉函數, 求得 $r=φ(N)=φ(p)φ(q)=(p−1)(q−1)$
選擇一個小於 $r$ 的整數 $e$ , 使 $e$ 和 $r$ 互質。並求得 $e$ 關於 $r$ 的模反元素, 命名為 $d (ed≡1(modr))$
將 $p$ 和 $q$ 的記錄銷毀。

此時(N, e)為公鑰, (N, d)為私鑰。

RSA 加密與解密：

加密: $C = M^e (Mod N)$

解密: $M = C^d (Mod N)$

分解因數

網站: —> factordb <—

已知 p, q, e, c 解 d, m

這是最基本腳本

#!coding:utf-8
import libnum

p = 16785538806603229546831014867806945109174660684369252526571837177530020871776186503540363533465363436174429883763287316563818908234704635026805208486158808815204607414064752499457590165922796827640257996628461578646367976289553053679994614392008975330957576095066582897319511781376559616923510156908689506249476205882440567232723613726676265000210162626070990882901701638639329709168419553908493633695967170810506043830544025025868627495339109609570196487756662527058313568351636167996254403290525990940877945979650689490916970989273615045213903412532460018605565074702280990810882484707265130962429078075196987306823
q = 16785538806603229546831014867806945109174660684369252526571837177530020871776186503540363533465363436174429883763287316563818908234704635026805208486158808815204607414064752499457590165922796827640257996628461578646367976289553053679994614392008975330957576095066582897319511781376559616923510156908689506249476205882440567232723613726676265000210162626070990882901701638639329709168419553908493633695967170810506043830544025025868627495339109609570196487756662527058313568351636167996254403290525990940877945979650689490916970989273615045213903412532460018605565074702280990810882484707265130962429078075196987310173
n = p * q
e = 65537
c = 269844405061794408881325419068561434485918688756051876642746375053141507717597929239825337577579209690816428513931525234036734301387574498261290078881044479415744014820256909105714495529730629663658937178159412731786389961698282168259920902233310707944063223479503448187557768961081851712485146366548760263966245778212016948978527798277704632093115069928072483024285945733444356730940369756065506406633833767904027043643430662336549748635722383646959378992875277740185048950670626105822924157897674315671293920327582374631250965788561361655881854955542053089903302229673705337653184163330865800003873020538616404245132158526695981794705668869949289304505930692263324309476091304524253205836627565978339970916413587242299449345741887246431160569558890339312469194580183192572697658795725506098343583961185323328585347462691697809168365959166845470549054286300104327087547588837152920745317074385583980574691863675380358400449205876594680258453351033464040969208972777013806493485998564483884597732352399514265770300017498599635859458768753030321735697937089458748104376271070036461140010690454117843525729200228018391681972735344212666250731100957752185781052102382617863235173016936453322118156390709789254433748018918655915860480150
phi = (p - 1) * (q - 1)
d = libnum.modular.invmod(e, phi)
m = libnum.n2s(pow(c, d, n))
print(m) 

e = 3 (小公鑰/低加密指數攻擊)

import gmpy2,binascii,libnum,time
n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146956044568639690002921620304969196755223769438221859424275683828638207433071955615349052424040706261639770492033970498727183446507482899334169592311953247661557664109356372049286283480939368007035616954029177541731719684026988849403756133033533171081378815289443019437298879607294287249591634702823432448559878065453908423094452047188125358790554039587941488937855941604809869090304206028751113018999782990033393577325766685647733181521675994939066814158759362046052998582186178682593597175186539419118605277037256659707217066953121398700583644564201414551200278389319378027058801216150663695102005048597466358061508725332471930736629781191567057009302022382219283560795941554288119544255055962
res = 0

for k in range(200000000):
	if gmpy2.iroot(c+n*k,3)[1]==1:
		res=gmpy2.iroot(c+n*k,3)[0]
		print(k,res)
		print(libnum.n2s(int(res)))
		break

e 太大 (高加密指數攻擊) / d 太小 (低解密指數攻擊)

透過數值很大的 c 和 n，去求出數值較小的 d。

import libnum
import owiener

n = 103070577929726253631344410352692529019028899492417679170030712588726916233260956307828281366719578148149337963676063478754302654908868697186141139935785807607477859007299550759696360710761593462350508280204189428161004900112381330220076890145703597040417081075805402174962296795435711459649783056881789490351
e = 81229431932405069076115541286401461443494262822135658283742292897410925764495502689451059315212238547938663797948023035990811381899591212921183487360416649701773568973719409413970364821014306572579550625402194135767284307689116463076867207148137667749321676903262731528419046683614746969287791511567819422311
d = owiener.attack(e, n)
print("d = ", d)

c = 91695657020488911546514984124491767203636048945190356702572340308491541333231892208913410842759055058532538326429698845388689133318492812505642888037888994704290866466325628211196801570268671101701776860750050743516334024242682186605601842248508533894710903871285318149826578248317551453724632008257499100559
m = libnum.n2s(pow(c, d, n))
print("flag = ", m)

已知 n, e1, e2, c1, c2 (共模攻擊)

已知 n ,e1 ,e2 ,c1 ,c2，就可以在不知道 d1, d2 情況下，解出 m

from gmpy2 import *
import libnum

n = 21861849068488503326777564160482917768295313612622098844005843941150416001449415831637974753612296634178937206635448545759776608072919261837704109903460487852321593647461325194355863907156869648747188133965073402040821653255878590888415203522221544646026084652799982648089185458004128592803363049028863875147302298032914963095395238481777617108444373792690712586751618914946813447656100899378283397273293143842550921101844777123910587444282360703980995288785551256271451760332791447461673193550567714926450717517656392539447836755985235708569019532947491148812339977048504141761177263545250566883133462383528417086483

e1 = 17603549263186425341767929511665789959105944330977732610916014873119252282802636800619943218173617441888097241786330044467390706899621342311537780960325827434196373002926945337049116646768167280435578161313136166984912128140809491969353494782750474301810262688555936515237213157072589888855009082917459841124317212785314003914313234917639294833196462895550624990993855672424098551845194332818039618333455201098641549770441114401683833649029496333471721218422923953911572405255917219368996940141028493863221349007615701640977231767979869511746450459020309485973427107977390630775364092661966159756765434661573566462163
e2 = 15344508209087520408904622039612403292778077018374460918944647544769165640337137582186403919710159968904923421386737007919512784139878000070417785469235072760767520470631932153936681007172335035560603688152851363757551810390163356371161738851859293395985292893266642634947470905628261585873301406883399307465584080339646976686630070325570603080476048485894627862169328144852580941394727582550746753409269261023938462291893093488806622999431476759128322955553737212823603838438441286632412590780859732560765318694595239577819399088507513384628815021733400052028849608900698718593489414974683054465037065557915104359925
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743

s = gcdext(e1, e2)
s1 = s[1]
s2 = -s[2]

c2 = invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
flag = libnum.n2s(int(m))
print(flag)

已知 n, e, dp, c

原理參見 RSA之拒绝套路(1)

import gmpy2
import libnum
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1,65538):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            phi = (p - 1) * (q - 1)
            d = int(gmpy2.invert(e,phi)%phi)
            print(libnum.n2s(pow(c,d,n)))

已知 dp, dq, p, q, c

原理參見 RSA之拒绝套路(2)

import gmpy2
import libnum

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = int((((mp - mq) * InvQ) % p) * q + mq)
    print(libnum.n2s(m))

dp= 24417628139330679432551095868116968814142396193102639509841676574931690513464588523684381397207121003439385360929299071710433231196678202942915347185802024747158497456267595000613289619481116892073493417896024118597833611923086327107489774162727006791982668721110819684552525393969199138125692085053266311867
dq= 39019112110614280252241495036646034807151213716557526376274345944263453299622818575225245299195523420254672088668617876062998490653404750105272510633841394184860866942704080992475543547501372565259180366123356119418623253283732615682878021900318153700726522250094020806743598752556541454865233668070931534349
p= 114461439704891616590422134857421869878753559940962522699708885701308630438427731936479777010552391068812199529467348873013239528376604282404207321401876195560830474695517139918118078685078197948576662138382523308600480733574419071424466292785993331731881271557573094521160051353184489095799816579282742140953
q= 173407999660109485520889209734134041910836523881475540116955713891631837403964097088089751678165465931150331234455699896350201315926126639981461748491240790317968076899655657331112140939100897570439934688992874242416328330344836429844042122956843979375681077968897817612357468397424082494911472122421034561779
c= 13156088528156801357013836665002509320288819562687150049688430847488062217199478847649128772442129783962344653461951822569890099822350753026372449754819799394899656016487248023042927376134885257136511477879900672582593964626335310995748816166750941755394630154620318544805488209700324391789948495807096701620546557726907853315159542234979480907794659188799145765761654813882682456135251746607111274015475601810166327843158879230660349983897375641623569327757258851636029354634714133778666281729500815659100876558161468140039778498553902396380237570072543395294246750182054410091138654202418836971487515663618000662737
decrypt(dp,dq,p,q,c)

MD5 訊息摘要演算法

#!/usr/bin/env python
import hashlib
import re

prefix = 'hkcert_ank'

def breakit():
    iters = 0
    while 1:
        s = prefix + str(iters)
        s = s.encode('utf-8')
        hashed_s = hashlib.md5(s).hexdigest()
        iters = iters + 1
        # MD5 total len = 32
        r = re.match('^0e[0-9]{30}', hashed_s)
        if r:
            print("[+] found! md5( {} ) ---> {}".format(s, hashed_s))
            print("[+] in {} iterations".format(iters))
            exit(0)

        if iters % 1000000 == 0:
            print("[+] current value: {}       {} iterations, continue...".format(s, iters))

breakit()