seccon beginners ctf前の最後の勉強会. 今回はアルゴリズムに関する問題が多かった.

Math I

RSAの公開鍵暗号に関する問題. ちなみに、

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。

c(暗号文)とm(平文)は以下のようにして求める.

c = m^e mod n
m = c^d mod n

よってdさえ求まれば復号できる. dを求める式は以下の通り.

d = e^(-1)(mod(p-1)(q-1))

dを求めるには,

  1. n = pqを求める
  2. p-1とq-1の最大公倍数lcm(p-1, q-1) = (p-1)(q-1)/gcd(p-1)(q-1)を求める
  3. ed≡1(mod L)となるようなedの組みを求める

拡張ユークリッドの互除法が使われている.

このサイトを参考にして実装した.

import math
e = 65537
n = 1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029
c = 225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163
p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223
# step1
L = (p-1)*(q-1)//math.gcd(p-1, q-1)
# step2
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
    return a0
d = ex_euclid(e, L)
# step3
m = pow(c,d,n)
print ("%0512x"%m).decode("hex")

Math II

モジュロ演算という割り算の余りを求める計算と関わっている. xの101乗根を普通に求めようとしてもオーバーフローが起きてしまうので, 二分探索を実装する. このサイトを参考にした.

# python3
import math
x = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273
y_min = 0
y_max = 10 ** 300 #ここは適当
y_jou = 101
for num in range(0,2000): # 2000も適当
  mid = ( y_min + y_max ) // 2
  dy = pow (mid , y_jou)
  if dy == x:
    print (mid)
    break
  elif dy > x:
    y_max = mid
    print ("大きすぎ")
  elif dy < x:
    y_min = mid
    print ("小さすぎ")
  keta = int(math.log10(mid)+1)
  print (str(num) + ": " + str(keta) + "桁")

解答の範囲の上限と下限を適当に決めて, 中間値の101乗を計算して, 結果がxより大きいか小さいかを判断する.

USB flash drive

Forensicsの問題. 使えるツールはここにまとまっている.

問題のdrive.zipをダウンロードして解凍してもなかをみることができない. そこでThe Sleuth Kitをインストールしてflsやicatを使えるようにする.

brew install sleuthkit

ちなみに,

  • fls
    • ディスクイメージ内のファイルとディレクトリの名前を列挙してくれる
  • icat
    • inode番号を指定するとそのファイルを出力してくれる.
      である. fls drive.imgでフォルダの中身をみて, icat drive.img 36-128-4などで中身を表示する.

ZIP de kure

zipファイルをダウンロードしてunzipしようとするとパスワードを要求されて解凍できない. しかし, flag.htmlとは別にStandard-lock-key.jpgが入っていることがわかる. Standard-lock-key.jpgはググったら出てくる鍵の写真で, 平文の一部がわかっていると復号ができる. PkCrackとうツールを使って以下のコマンドを実行する.

pkcrack -c Standard-lock-key.jpg -p ./Standard-lock-key.jpg -C flag.zip -d ans.zip

G00913

グーグルの求人のURLがこの問題だったらしい. 円周率を10桁ずつ見ていったときに最初に素数である数が答えである.

import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
#円周率 とりあえず100桁
pi = "31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
x = 0
while(x < 90):
    num = int(pi[x:x+10])   #10桁の円周率を抽出
    if(is_prime(num)):
        print(num)
        break
    x += 1

感想

ZIP de kureの平文の一部だけで復号できてしまうことに驚いた. 普通にフォルダにファイル適当に仕込んだらうまく使えそう.