[Break All CTF] Crypto 2023 Writeup

藉這次平台來增強不熟練的RSA，並搭配這次CTF做了一份筆記
➠ https://hackmd.io/@hyu/RSA

Crypto101

ABCTF 2016 : caesar-salad-10

使用線上工具解密：https://cryptii.com/pipes/caesar-cipher

得到flag：abctf{w3_thought_w3_n33d3d_on3_of_th3s3}

AlexCTF2017: Fore1-Hit_the_core

利用strings指令查看檔案的string，照到了一串類似flag的字串：
cvqAeqacLtqazEigwiXobxrCrtuiTzahfFreqc{bnjrKwgk83kgd43j85ePgb_e_rwqr7fvbmHjklo3tews_hmkogooyf0vbnk0ii87Drfgh_n kiwutfb0ghk9ro987k5tfb_hjiouo087ptfcv}

得到flag：ALEXCTF{K33P_7H3_g00D_w0rk_up}

RC3 CTF 2016 : salad-100

根據題意，該題為凱撒密碼，並將數字加入編碼
使用線上工具解密：https://cryptii.com/pipes/caesar-cipher
將字母集(Alphabet)改為abcdefghijklmnopqrstuvwxyz0123456789

得到flag：rc3-2016-romangod

EKOPARTY CTF 2015: SCYTCRYPTO

該題為密碼棒，解法如下：

因題目前面為EKO，應為三個字為一組
得到flag：EKOMYFIRSTCRYPTOCHALL

Pico CTF 2014 : Substitution

使用題目提供網站：http://quipqiup.com/
該網站是利用頻率分析（密文字母出現頻率與常見單字出現頻率比較）進行解密

下方出現的為可能字串，越上面機率越大
而第一串出現字串the authorization code is awholenewworld
表示本題答案為awholenewworld

School CTF 2015: affine-cipher-100

使用線上工具解密：https://cryptii.com/pipes/affine-cipher
根據題意要求，將Slope改為4，Intercept改為15，並於字母集加上'_'
得到密文flag_is_every_haxor_love_math
該題flag為：every_haxor_love_math

angstromCTF 2017: Substitution Cipher

使用頻率分析網站解密 http://quipqiup.com/

原密文中括弧內有16個字
網站不會顯示大括弧，將括弧加上並刪去空格
得到flag：{fewgoodmenjessep}
Δ註記：本題使用頻率分析時，不可只輸入括弧內容

angstromCTF 2017:The Beginning

本題為凱薩密碼，使用線上工具解密：https://cryptii.com/pipes/caesar-cipher

得到flag：actf{back_to_the_future}

angstromCTF 2016 : artifact-20

使用頻率分析網站解密 http://quipqiup.com/

flag：classics_are_always_in_style

EasyCTF-2014:A Simple Cipher

http://quipqiup.com/
flag：CAESAR_IS_HOME

Vigenère cipher

使用線上工具解密：https://www.guballa.de/vigenere-solver

PicoCTF_2018-caesar cipher 2

讀取檔案後得到了密文：e^Xd8I;pX6ZhVGT8^E]:gHT_jHITVG:cITh:XJg:r
根據Ascii表(附圖)觀察規律得知平移了11位

Python程式碼：

s = input()
ss = ''
for i in s:
  ss += chr(ord(i)+11)
print(ss)

picoCTF{cAesaR_CiPhErS_juST_aREnT_sEcUrE}

現代密碼及其破密分析 & Level 1

Hash Try 10

我用了這個網站查出PNG附件的MD5
https://emn178.github.io/online-tools/md5_checksum.html
而得到的MD5值(9b554f33d83c13653059b5b4a669fef8)為壓縮檔的密碼
解壓縮後能得到寫著Flag的另一張圖片

YANG_RSA-1 50

最基本的RSA題，先將n分解成p和q: http://factordb.com/

from Crypto.Util.number import *

e = 11
p = 2262150367
q = 3006300461
r = 12218233223644524650141958853163065112163255395621655741865064529020634406575730714768264558014607893896434523845321502371618344594488810317052606914954669
c = 32392151763267291269610586564983347951891395196084251182633225594245167922176424232164117237142038355860036871811244158149537196288428230971760474130300660929743492107190512
n = p * q * r

phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi) 
m = long_to_bytes(pow(c, d, n)).decode()
print(m)

YANG_RSA-2 50

把c開e次方根

import gmpy2
from Crypto.Util.number import *

e = 7
n = 1005098784594165848821832590501628403524802902674053382968470498538675288024873128424879364961488454145355936225677709124632789481770148984368708158164916266844271786072406765898627538801884748356080826075494258116818573097428235536790636847100997446916017821607591551722483794674940379793999230206353715117589898489861301662334780242666620337676110221421426102941068711974618344098371538140671153829377393837740293830337243493085160451872753422509384072905634851957789103689582476286664749588114456827960476870164048784404280351460249562996906271414272625881748849175309114734205368513000888013065441040602267654552015590863773059574256085653649422840863428324602357578340644446996674941825103598620438972286389472676382307637357209115141975325946791432841852827828407465818721747161090664009799105129953728589693126992849713556841586265400095017954688319716059398240941350468461830314384384626840855999556176928576367255322330539451380078690665639135509274932616776447492100759094249811584415361859939091438557866035439570864472528889723274777281738473905899882030941410513275852891694991922437995200537246398155615904052214367857177598437501143127042446835618109714924845047124233631838729882640996639575165133299706184551662489093
c = 44163895521220531459057055795752057167876718238617963549906371036055586914199267109947281359325715489398261335563468559859879340774499726524035061903919328383390193234339356811666801858858748990899697833645511123626735258871404048116302274347058468791179874933001105300534600581977271895856972533976629641765182868484553104584590829347999386472615066779248550781718812068424236647225425670871554757459074630360567280382876137651283102473254886990887517217176132596555364994651622062720390486911698802074418697530462711619997107804919499320409084297665919116751543056038865957808455949742740596859550586982302492545205898434968509344729243293414190715139959127090472661918871372070659935437431160846169010492251366727698703670348564864343164944932175842131148853297549424891479394079434940030257530096990169847176293150870765433888895069248560702669885642923421945661068042034911026426121363007026093515922333722778955975053692081279596854554640425470049534192255739670036469

flag = iroot(c,e)[0]

m = long_to_bytes(flag).decode()
print(m)

babyRSA 50

公鑰 pub.pem 和密文 flag.enc 以檔案形式出現，先求出題目e、n、c值
n、e

from Crypto.Util.number import *

rsa = RSA.importKey(open('pub.pem').read())
print(rsa.n)
print(rsa.e)

c

from Crypto.Util.number import *

c = bytes_to_long(open('flag.enc','rb').read())
print(c)

輸出

n:86044608266042558038553786299703811809507347936888618532703612396944160396661
e:65537
c:17683423645350108865861669667533929275271021363505775532390605606130471893777

e不大且n=65537，用因式分解即可 (http://factordb.com)

from Crypto.Util.number import *

e = 65537
p = 270613060120468613971049355250995010949
q = 317961772531370599800029965079161987889
c = 17683423645350108865861669667533929275271021363505775532390605606130471893777
n = p * q

phi = (p-1)*(q-1)
d = inverse(e, phi) 
m = long_to_bytes(pow(c, d, n)).decode()
print(m)

噴出了錯誤

UnicodeDecodeError: 'utf-8' codec can't decode byte 0x93 in position 6: invalid start byte

不過把.decode()刪掉也是可以拿到flag，只是會噴出很多東西～

Low exponent 10

e、n、c都給了，明顯是RSA，不過c很小(=3)，推論m^e=k*n+m。

import gmpy2
from Crypto.Util.number import *

n = 2497300189753895574756199389081351115673483547267761473369603807977358087750230416071218221042109470426599606659561528032219753516648965581561236096422435760230691537241046527847722030268619203209258954709
e = 3
c = 58168203689615197168203652676518356795151350198697707463169957788618822006314762468543987338364185026829499143907623179340114258988599090808706581369621068080488465881560266707967151040686138163812089103
for k in range(100000000):    
  if gmpy2.iroot(c+n*k,e)[1]==1:    
    flag = gmpy2.iroot(c+n*k,e)[0]       
    m = long_to_bytes(flag).decode()
    print(m)
    break 

雖然只有10分，但這題難度其實比YANG_RSA-1、YANG_RSA-2都高

YANG_RSA-3 50

有兩個n，且n1 = p * q n2 = (p+2) * (q+2)

import gmpy2
from Crypto.Util.number import *

c = 139042738526108915518382315590614161559545672874231013930043771888153330995636895021496690157019719891495421789891311751114070162820109898550748729125606711558619118645191771802867431417997808791808947663873157450381886576198018116644175503419727838166069179286320364053606871929319609609717883881827703531071294250903725115590903885439257993122448450155592341119519506480784700882637629148100289455951870378287065580019819787172666799064867472787388018501312484677758639630205985303521919625967928777576894714176370710514866851261857421113481579194403231201302648732458813285636116381750742800141620920665296851274731594398742733371863332481364651903565612256089078337832051794479664232703579382433662773172010772985745670472577141377427032667489413571147659184721008370862939384402765999758594739567633919697832750413509665699046792692953501205991502771826582951017086701333243949551066796272454956773817169423364362577405931516463850167131352119912514527378117187253789191465090914208628886222374130328836743075062815304664169005843065539134914179702827261596407513474449624318873499341773097243
e = 10000001
n1 = 3627444771006641937670374103598493492277170277116493920932885955435916968318288577415856168749785331840818803112714250474056975340846972000039130600885450836486139285287969449202825040685732379632326635633418300048983634209556964867175030252399986593427857865008518171239775643235488954015082260035235036283487660366488550474516338472679222048717177747614210739606052154819639691004286246240020230188651006378959767398084324322008453152063183987372973164598066860174889163715767177543295634165129243441461597670797375484554640164983017774064835500981051070425037996029762438322599385986157913795423953648261358937185717844177379683832237044491180000482549114763268386632780913610754235834240512650659409215396821697752992594864370658750560426230664402293637048067412815299294991452283113777309961811323532557633057727900060941499142193907009891170468728522049291402072655778336976688416252463974783689158463516778651386914053541081481476612718983711795850458476656130316790582555711188904501523691656768916238612527464448411081019203952981305496349455714491843585609791073272252568166553125529140639
n2 = 3627444771006641937670374103598493492277170277116493920932885955435916968318288577415856168749785331840818803112714250474056975340846972000039130600885450836486139285287969449202825040685732379632326635633418300048983634209556964867175030252399986593427857865008518171239775643235488954015082260035235036283487660366488550474516338472679222048717177747614210739606052154819639691004286246240020230188651006378959767398084324322008453152063183987372973164598066860174889163715767177543295634165129419489479581992906703549293578307256488898187992353900184420118800322552534062759653705575925115281872928967944090554962523467896972290709767538721152187005614513210255277428624583175610744256739492598420738558920178579717917167080004296928204063086948663685116578675918309866385297630728361719704990361341156140881005762465007490782078136991995257037173077806031411193484423581964394970840431076138212137582851077173111409746242976470913498571389253297470379823689833891657511115618469031966199517813387433692841129826086480794218247482240815273496487448622735466819104529863148460012391153385059278883


pq = (n2-n1-4)//2
n1_phi = n1-pq+1
n2_phi = n1+pq+1
d1 = int(gmpy2.invert(e, n1_phi))
d2 = int(gmpy2.invert(e, n2_phi))

m = long_to_bytes(pow(pow(c,d2,n2),d1,n1)).decode()
print(m)

Level 2

AIS3_Pre_exam_2015-Crypto2 100

tgz是一個壓縮檔，使用linux指令解壓縮：

tar zxvf crypto2.tgz

裡面有兩個檔案：flag.enc 和 rsa.py
這題一樣是RSA，rsa.py有n和e，flag.enc能利用上面babyRSA的方法拿到c
然後其實這題不難，一樣是因式分解 (http://factordb.com)

import gmpy2
from Crypto.Util.number import inverse, long_to_bytes

p = 800644567978575682363895000391634967
q = 83024947846700869393771322159348359271173
e = 65537
c = 40862099549212311776166843530964346935858219354460333674195486984708439315653

n = p * q

phi = (p-1)*(q-1)
d = inverse(e, phi) 
m = long_to_bytes(pow(c, d, n))
print(m)

YANG_RSA-4 100

共模攻擊，可依參考這個程式碼

import gmpy2
from Crypto.Util.number import inverse, long_to_bytes

def common_modulus_attack(c1, c2, e1, e2, n):
  _, s1, s2 = gmpy2.gcdext(e1, e2)
  if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)
  elif s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)
  c1s1 = pow(c1, s1 ,n)
  c2s2 = pow(c2, s2, n)
  m = (c1s1 * c2s2) % n
  return m

n = 601079890037987604431299524604731926071028289714726325853160560822671656672435372422576831180720643755002522349232818450429861500646197062814617330443684235014072184166957803892385199122293587039674209300946383069422025584266381942233078984155793427549685573859988475888412265342970813238059596786787726537911926819530604506451125553192260570386165641188535428166442552194316166923180962521164985215427597102736331300655293153400150333265029368210022213821641355315765165160575924342098863168232177127592546541673292314097366431474533263402112899677852636579661059026081681362887721283820517246291325501590627370903464556352593996466395596703609515756817330200509325258443030773008998508183500802902995673573898878264148773130870857827804095652545116545220268517058077827666474665032138823605624731794285434772957308460566796728714912951423416600299440344847642523901665983827164682786888788009473126538180992204754454924702201128344623836080923997277509247815993
e1 = 9405172090867429167522098902370749942248783790897104683679576493285386831759923838256124796722772712748691601513080032494804780492783260329501965883487449
c1 = 314564217302500200163759194260307839612780113900510659153559994404616233480977901081457219754701436603071046288000515552874294832582078073029908088537206127804857317570661216485480824510676318602134918119497217616722217174492657585743425124324907518649050736733207674535351855501078377195724227557781044380284792016437708580643509685246825169537653244291413420860826461482786045694551841250154752831892803997686933358830881165202213705675567254258355536168864546096585003491156446528289098171464737969907311920151343401576297553073358616531239922292236598022573879617946865136850496267767392774321261208975997120995221104766187122831500354603374561481266350294614422561126906570941980870039995358850974794393980407489204820700624300046702300701395126669428361520630043416955672898292369148908985504063716178629319516455430033390711455943419623574412135759361201047051736309026022515055418451530574539575536836664360617505814472330359018776028176730183083132708449
e2 = 7095565993271201701012700380853978907656102167234011354220093122363055999144351553656782816939748882018682837387651451192207734678816900790888793405286989
c2 = 231454535634498981606804851249268972673565707091933518210376565934116042099763364768783318579394065863001071012758012388779888046220585794303803977781363299140700033882412332072165508546466694644149936737091441176316685512052479450517620932425763542699912556932121122254624930817149270005252865287721155021484087246788171305870704141493508455874364528923527573135942464626727511007260700119374884220390067900433849409633808845764301976479013370962776101364599847645005622330078930265786460112041493284689945296841349882069189318814764669930730356315943075593805608591847059144964078117070976633698053027833770233512967762552688778510572408743102454627944221473329378344576994239421959385787556811017060321709056461254892708398556778100555192544461572784992678053844380781805360413711742586700791882806136633296551922581431775955348872645753475792127252625290521427755906342341946264099004311435719226771725446922256895733539634456628491176695552090922403849365718

m = long_to_bytes(common_modulus_attack(c1, c2, e1, e2, n)).decode()

print(m)

Homework

Hash Encrypt 100

題目的程式碼如下：

from hashlib import sha384
from secret import FLAG

print(''.join([sha384(c.encode()).hexdigest()[:5] for c in FLAG ]))

# 8a5e675d378d18254a5981deaad14a1ad0e1ad0e95ed472df8bcf6e5335f72df8586b017580a87d840f985f9158ac1075823758237582375823000f40b759a4eb0bcf6ec2b14000f41d0ec17580a87d8f99c575d37883c5049e7e7cdc1d0ec000f41f366

我推測程式碼的意思是把flag中每個字元轉為SHA-384雜湊值，並取雜湊值的前五個字元組成一個字串。因為字串有200個字元，flag應該由40個字組成。

為了證實我的推測，CTF的Flag第一個字都是大寫B，而B的SHA-384值為8a5e6d9081b08ada24918c6a8697952bc7c7c92f74a3341eb4a31be93dd425c8781f88c2f2fe40d5f81018ba81a54b48，與我的推測相符。

於是我便利用該推測寫了以下的程式碼，成功拿到了flag：

import string
import hashlib
s = "8a5e675d378d18254a5981deaad14a1ad0e1ad0e95ed472df8bcf6e5335f72df8586b017580a87d840f985f9158ac1075823758237582375823000f40b759a4eb0bcf6ec2b14000f41d0ec17580a87d8f99c575d37883c5049e7e7cdc1d0ec000f41f366"
for i in range(0,len(s),5):
  for c in string.ascii_letters + string.digits + string.punctuation:
    n = (hashlib.sha384(c.encode())).hexdigest()[:5]
    if s[i]+s[i+1]+s[i+2]+s[i+3]+s[i+4] == n:
      print(c, end='')

Level 4

RSA 後門 (1)

import gmpy2
from Crypto.Util.number import inverse, long_to_bytes
n = 760070912350840319011516178942471824408271276603018122766107466458905659805366910876741133101064132968975290327141913870064382857896676965896339499301686289349478192042225387715815300890772726396671069777379993317290403468858998199888875329375096856205675179863574081470688602128633185902300536380591686253782626310388376732381905094112550405708724116437892957067685087277238106233348311268725082471734753857194847838970086800848099069387690801700501505622593836970903856921989336476413802534078525413311063453348054161408156303570666333425678334142525184422436235677229592264286240481233065103525594733333609350428196011268071126676023443256564227488106063073893805882904030218186925942692848016877882566240601003792167543787342287123520711449083265386813671510310650585456131441220450039511889734856795425972738718472877437781909089006687000385532764327586589650518853864825005505232375529254511923368560433385960598232647516144607822711918385784586608803888123523660880157194471094579495414720939362559417376095025821133997982361566429601158965282863289774835745836514384219847770664031196660782737380240398358478721495348483958183701077510621561366810555045657804658889409015678773329196458757404769771384361180527520601391357800258141800488661477548160080188323687255844523623758493111371703516522245476661361074371234254770474249888532163823739762576169486427817071850060196906194007205553628806031759720577392913205266258974893510396850982203198212807648844222854214722691172053026220943259272390113639543712309874760232956983371190047789729422160337209334177864706118802632248174293863932718038360834909893547570166552708085714105225222230703430768672212375445000147155804641468351838745755024401386395525712050470895155325019568159034388240484857157405320152956355210692650494136549140160597175749
e = 65537
c = 23043402590987555987470005871777877151151322716060092459929038792187374705968922913981882558830225470321029330756473052187571435747992606303872345391192250986189523554344860876217195521571582376245238947762932906008745950998260974696231231824601028638289006875327541511759557000571143570848503096379667666967042396170909355179367747237803420662010299628257013342744836612954085028392265365961440279234959713291284949713775237855329413455655772310421877970592292542102538256515263604910522531928228880078584842456141579974665432527149970116608055188948668252221996589209114900583773037478077453666787948360947075322921408423852746262833539233406967548960178792506005300931929791663889585748150722426246846945324183653314928671217591271109921760823893150502841856609499818424934712192715672939108605032696495577793313699830025230983849952517890751090570666447986086847837086779757192278809702226557559967552406759613743288491173421943288898163371672471990115969010871440555604481217266874916781598035536414979414464006324273200204670733327544831907946399527743271591693219872979511671485433003231621892498425559325421320388096593342519672705301186660848415575840192111782413754304841694673552200242842522814616994132736554544962232150040663460968513256281961794248016394841074724067661800839577955360386734635675931880822030409894997770620409228346807030968725967258287589342081617955999751395789800908644912870435347895906209405598557569815132825199794518175327458521867303551685164794679068776727276119468526737538107724423172989004606420592240046923867223729763034260869375338820559888057264343970350523466971697923158383084508306076913151571967057252009643027901618887695230860718585529467899380034905236786873876780870273574985011685074373247696219994297416533789436191368362809767858885056459978807647
'd^2*e + 7phi' = 1620126254178307107805925347409210109079418631271539038205383853825500296811505131321875475715376307920981259462614357533466941753203754184389902040317390296735523174111832078921071210983364802271706444506677317213375748433529142733682590086434843883159602424571840661084006789837565204356906806127384353403137070496607341705255529168928432860284811151663733497947457852894849483010205070190430044884550533111192278310167522337536246523319753834614895078829866621645079609537944800585691132921447071067406128053795992296555789860705164267117376403341249194265381912880381122911987670787720090648797468392804379581428828927625443096354958698305106425356304804759341769351628590201355981787898026961417197010017978586896498369566391766916389949150734429923140437868014851873995161973857943326484813660496439427382145248573160747328757222766985442936636962614338471082462176542018466676085655454126951355550126361556257104662075266568603316336712255778109160502274520531194415105288138253088913783390737905518421815608069570180353522268625980073518750189827406619294497755771287793106258255192904299584048308228213978894683176026406779635394795370495734518744326300256193256380087951019044375347232461900888446065009489097640645391262386569608187845289178411183302612154855933859365795959462296302969045375802007650006363182447142282246172159815897175833698776663254485330016779371149328376513575569112760942981544834502925172841196048299545002337578813030918604554192291352785887470669511311646710910107563532165621630764987769666815016543655079038651842299906822911300266765706794298700862048041414816161796925300877951583684498109038799176817515156155043226336378501966674335980213598353300400499799267983331829293506615875633931684214060079961057050811529994328542272465237370490978257671901267949207368118469813482528549191337691272398251984525988911374674261415802154066814829811852235633680796855638371608427840349392807069113908188523610318541628405008514061483659101476049254558271853247155909822423178322733169352572052726772582248896209811295644754652929887794307253538519583308522548764807171997390978930362807674618922673784345674399280165757903254849166255862761505958877746491695638693225723742471994074977722764774396977099203362493734497024157950664679560033045482790511829641981266050781145047063439829017411287025152601657710843117158464125963489235207735032378012469116305985018154124770869140988608396527280659847552980183759392006298043098302142036369831264210519529460144456046718107048666133409389414971293612254496187041396109788710182456978219643383191376104152139390281682725843970462663476429188678725076567909771351453134707771292457507252653887820906120220438288603368324527890395568883849113861497960739320824870111660002336940925676213182090142135460146471543405919951993709743278922880730501901447471415221734066265696076586382009664274086330323532584722108261464690626012127056796760247870942832409248150162628837118556643673490483508340076601494462894830031383023978791318416731750735151837937806847488275195597134674111405788736045846451812924630643394346576798523225002203801819682823374228410113250193049149956290221614268899002507311843085666803688279048710674142634342181537227528937600806325860076859203781668984084015772848021783541825345156247897291696817517617346614862474694333096308102196024040585991378871897997839002740030027319532462250477445464847537717734353083321981680750712108267543263803466885591366936121859171083424502493973267513173320411368750946440514079437531574281488938077212799745537360636372874039590628648466074136236105865275970476148518382544665640833

m = long_to_bytes(pow(c, 'd^2*e + 7phi', n)).decode()

print(m)

我把'd^2*e + 7phi'當d就過了，至為甚麼我不清楚。
這題算矇到(?)

tags: 資安