好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

picoCTF2022 [Cryptography] writeup

picoCTF CTF

2022年3月15日~3月29日に開催された中高生向けのCTF大会、picoCTFの[Cryptography]分野のwriteupです。 その他のジャンルについてはこちらを参照。

tech.kusuwada.com

basic-mod1

We found this weird message being passed around on the servers, we think we have a working decrpytion scheme.

Take each number mod 37 and map it to the following character set: 0-25 is the alphabet (uppercase), 26-35 are the decimal digits, and 36 is an underscore.

Wrap your decrypted message in the picoCTF flag format (i.e. picoCTF{decrypted_message})

以下のmessage.txtが配布されます。

91 322 57 124 40 406 272 147 239 285 353 272 77 110 296 262 299 323 255 337 150 102

問題文のとおりに変換するスクリプトを実装します。

import string

candidate = string.ascii_uppercase + string.digits + '_'
arr = [91, 322, 57, 124, 40, 406, 272, 147, 239, 285, 353, 272, 77, 110, 296, 262, 299, 323, 255, 337, 150, 102]

for a in arr:
     print(candidate[a%37], end='')

実行結果

$ python solve.py 
R0UND_N_R0UND_ADD17EC2

これをflagフォーマットに入れれば答え。

basic-mod2

A new modular challenge!

Download the message here.

Take each number mod 41 and find the modular inverse for the result. Then map to the following character set: 1-26 are the alphabet, 27-36 are the decimal digits, and 37 is an underscore.

Wrap your decrypted message in the picoCTF flag format (i.e. picoCTF{decrypted_message})

先程の問題と似ています。今回はmodular inverseを計算する必要があり、pythonではpow(a, -1, m)で出来ます。
indexが先程の問題と1ずれていることに注意。

import string

candidate = string.ascii_uppercase + string.digits + '_'
arr = [104, 290, 356, 313, 262, 337, 354, 229, 146, 297, 118, 373, 221, 359, 338, 321, 288, 79, 214, 277, 131, 190, 377]

for a in arr:
    print(candidate[pow(a, -1, 41)-1], end='')

実行結果

$ python solve.py 
1NV3R53LY_H4RD_8A05D939

credstuff

We found a leak of a blackmarket website's login credentials. Can you find the password of the user cultiris and successfully decrypt it?

Download the leak here.

The first user in usernames.txt corresponds to the first password in passwords.txt. The second user corresponds to the second password, and so on.

passwords.txt,usernames.txtが配布されます。どちらも505行。
usernames.txtの方に、cultirisという名前が378行目にあったので、passwords.txtの同じ行を確認してみるとcvpbPGS{P7e1S_54I35_71Z3}。これは換字暗号で解けそう。

...と思ったけど、CyberChefに突っ込んでROT13したらフラグになりました👍

morse-code

Morse code is well known. Can you decrypt this?

Download the file here.

Wrap your answer with picoCTF{}, put underscores in place of pauses, and use all lowercase.

morse_chal.wavが配布されます。音声のモールス信号問題かな？

Morse Code Adaptive Audio Decoder | Morse Code World

こちらのサイトで音声のモールス信号をdecodeしてくれるので、ここにファイルをアップして試してみます。ちょっと安定しなかったので何度か試してみます。

  • WH47 H47H 80D W20U9H7
  • WH47H47H 9ŠD W20U9H7
  • WH47 H47H 90S W20U9H7
  • WH47H47H90DW20U9H7

leet codeで読めるようにワードを選びつつ、空白をアンスコに、uppercaseをlowercaseに置き換えると

wh47_h47h_90d_w20u9h7 -> what hath god wrought
これ、聖書に出てくる言葉らしいです。Samuel Morse demonstrates the telegraph with the message, “What hath God wrought?” - HISTORYを読むと、このメッセージはモールスがモールス信号の実演で使ったワードであることがわかります。ということでこれをflag formatに入れたやつが答え。

rail-fence

A type of transposition cipher is the rail fence cipher, which is described here. Here is one such cipher encrypted using the rail fence with 4 rails. Can you decrypt it?

Download the message here.

Put the decoded message in the picoCTF flag format, picoCTF{decoded_message}.

これはタイトルから rail-fence 暗号に違いない！まえにどっかのCTFで使った記憶。CyberChefに用意されているので、配布されたmessageを貼り付けてみます。

key=4 にするとflagが出てきました。

f:id:kusuwada:20220402152220p:plain

substitution0

A message has come in but it seems to be all scrambled. Luckily it seems to have the key at the beginning. Can you crack this substitution cipher?

Download the message here.

下記のような長いメッセージが配布されます。

VOUHMJLTESZCDKWIXNQYFAPGBR 

Tmnmfiwk Cmlnvkh vnwqm, peyt v lnvam vkh qyvymcb ven, vkh onwflty dm ytm ommycm
jnwd v lcvqq uvqm ek pteut ey pvq mkucwqmh. Ey pvq v omvfyejfc quvnvovmfq, vkh, vy
ytvy yedm, fkzkwpk yw kvyfnvceqyq—wj uwfnqm v lnmvy inerm ek v quemkyejeu iweky
wj aemp. Ytmnm pmnm ypw nwfkh ocvuz qiwyq kmvn wkm mgynmdeyb wj ytm ovuz, vkh v
cwkl wkm kmvn ytm wytmn. Ytm quvcmq pmnm mgummheklcb tvnh vkh lcwqqb, peyt vcc ytm
viimvnvkum wj ofnkeqtmh lwch. Ytm pmelty wj ytm ekqmuy pvq amnb nmdvnzvocm, vkh,
yvzekl vcc yteklq ekyw uwkqehmnvyewk, E uwfch tvnhcb ocvdm Sfieymn jwn teq wiekewk
nmqimuyekl ey.

Ytm jcvl eq: ieuwUYJ{5FO5717F710K_3A0CF710K_357OJ9JJ}

ヒントから、頻度解析が役に立ちそうということで、単一換字暗号みたい。ツールを使うことを推奨されていますが、手で解くのが好きなので手で解きました。頻度の高い文字は e, 一文字の単語は a, 頻出の3語は the みたいな感じで。というかflag format部分で半分くらいの文字変換が判明。
更に少し読み進めると、最初の行がアルファベット順に並んでいることがわかるのですべての文字の対応表が完成する。

a -> V
b -> Y
c -> L
d -> M
e -> I
f -> U
g -> X
h -> D
i -> P
j -> F
k -> N
l -> G
m -> E
n -> R
o -> B
p -> W
q -> S
r -> Z
s -> J
t -> H
u -> C
v -> A
w -> O
x -> Q
y -> T
z -> K

最後の行にflagが出てくる。

substitution1

A second message has come in the mail, and it seems almost identical to the first one. Maybe the same thing will work again.

Download the message here.

今度はこんなメッセージ

WYHg (gzray hra wimybas yzs hvij) ias i yums rh wrombysa gswbakyu wromsykykrl. Wrlysgyilyg ias masgslysn dkyz i gsy rh wzivvsljsg dzkwz ysgy yzska wasiykxkyu, yswzlkwiv (iln jrrjvklj) gckvvg, iln marqvso-grvxklj iqkvkyu. Wzivvsljsg bgbivvu wrxsa i lboqsa rh wiysjraksg, iln dzsl grvxsn, siwz uksvng i gyaklj (wivvsn i hvij) dzkwz kg gbqokyysn yr il rlvkls gwraklj gsaxkws. WYHg ias i jasiy diu yr vsial i dkns iaaiu rh wrombysa gswbakyu gckvvg kl i gihs, vsjiv slxkarlosly, iln ias zrgysn iln mviusn qu oilu gswbakyu jarbmg iarbln yzs dravn hra hbl iln maiwykws. Hra yzkg marqvso, yzs hvij kg: mkwrWYH{HA3FB3LWU_4774WC5_4A3_W001_7II384QW}

さっきと同じ手法で解きます。

a -> R
b -> U
c -> K
d -> W
e -> 
f -> Q
g -> S
h -> F
i -> A
j -> G
k -> I
l -> N
m -> P
n -> D
o -> M
p -> 
q -> B
r -> O
s -> E
t -> 
u -> Y
v -> L
w -> C
x -> V
y -> T
z -> H

今回は通常文のみだったので埋まらない対応も出てきましたが、上記の変換を施すとflag部分は全部変換できました👍

substitution2

It seems that another encrypted message has been intercepted. The encryptor seems to have learned their lesson though and now there isn't any punctuation! Can you still crack the cipher?

Download the message here.

今度はスペースのない文章が配布されます。

xidcddhsgxgdqdcjvwxidczdvvdgxjyvsgidrisoigtiwwvtwufbxdcgdtbcsxltwufdxsxswpgsptvbrspotlydcfjxcswxjprbgtlydctijvvdpodxidgdtwufdxsxswpgawtbgfcsujcsvlwpglgxdugjruspsgxcjxswpabprjudpxjvgzistijcdqdclbgdabvjprujcmdxjyvdgmsvvgiwzdqdczdydvsdqdxidfcwfdcfbcfwgdwajisoigtiwwvtwufbxdcgdtbcsxltwufdxsxswpsgpwxwpvlxwxdjtiqjvbjyvdgmsvvgybxjvgwxwodxgxbrdpxgspxdcdgxdrspjprdhtsxdrjywbxtwufbxdcgtsdptdrdadpgsqdtwufdxsxswpgjcdwaxdpvjywcswbgjaajscgjprtwudrwzpxwcbppspotidtmvsgxgjprdhdtbxspotwpasogtcsfxgwaadpgdwpxidwxidcijprsgidjqsvlawtbgdrwpdhfvwcjxswpjprsufcwqsgjxswpjprwaxdpijgdvdudpxgwafvjlzdydvsdqdjtwufdxsxswpxwbtispowpxidwaadpgsqddvdudpxgwatwufbxdcgdtbcsxlsgxidcdawcdjydxxdcqdistvdawcxdtidqjpodvsguxwgxbrdpxgspjudcstjpisoigtiwwvgabcxidczdydvsdqdxijxjpbprdcgxjprspowawaadpgsqdxdtipsnbdgsgdggdpxsjvawcuwbpxspojpdaadtxsqdrdadpgdjprxijxxidxwwvgjprtwpasobcjxswpawtbgdptwbpxdcdrsprdadpgsqdtwufdxsxswpgrwdgpwxvdjrgxbrdpxgxwmpwzxidscdpduljgdaadtxsqdvljgxdjtispoxiduxwjtxsqdvlxispmvsmdjpjxxjtmdcfstwtxasgjpwaadpgsqdvlwcsdpxdrisoigtiwwvtwufbxdcgdtbcsxltwufdxsxswpxijxgddmgxwodpdcjxdspxdcdgxsptwufbxdcgtsdptdjuwpoisoigtiwwvdcgxdjtispoxidudpwboijywbxtwufbxdcgdtbcsxlxwfsnbdxidsctbcswgsxluwxsqjxspoxiduxwdhfvwcdwpxidscwzpjprdpjyvspoxiduxwydxxdcrdadprxidscujtispdgxidavjosgfstwTXA{P6C4U_4P41L515_15_73R10B5_702A03AT}

とはいえ、flagフォーマットは見えているので、焦らず対応を探していきます。最後のflagフォーマットと周辺の文字から、THEFLAGISPICOCTF{ の対応が取れたので、これをきっかけに解読していきます。スペースは自分で良いところに入れていくタイプっぽい。大変。

a -> F
b -> U
c -> R
d -> E
e -> 
f -> P
g -> S
h -> X
i -> H
j -> A
k -> 
l -> Y
m -> K
n -> Q
o -> G
p -> N
q -> V
r -> D
s -> I
t -> C
u -> M
v -> L
w -> O
x -> T
y -> B
z -> W

ちょっと難しい単語や長い単語が多くて大変でしたが、何となくこんな感じに復号できた。句読点は気分で付けてみた。

THERE EXIST SEVERAL OTHER WELL ESTABLISHED HIGHSCHOOL COMPUTER SECURITY COMPETITIONS INCLUDING CYBER PATRIOT AND US CYBER CHALLENGE. THESE COMPETITIONS FOCUS PRIMARILY ON SYSTEMS ADMINISTRATION FUNDAMENTALS WHICH ARE VERY USEFUL AND MARKETABLE SKILLS.

HOWEVER WE BELIEVE THE PROPER PURPOSE OF A HIGHSCHOOL COMPUTER SECURITY COMPETITION IS NOT ONLY TO TEACH VALUABLE SKILLS BUT ALSO TO GET STUDENTS INTERESTED IN AND EXCITED ABOUT COMPUTER SCIENCE DEFENSIVE.

COMPETITIONS ARE OFTEN LABORIOUS AFFAIRS AND COME DOWN TO RUNNING CHECK LISTS AND EXECUTING CONFIG SCRIPTS OFFENSE. ON THE OTHER HAND IS HEAVILY FOCUSED ON EXPLORATION AND IMPROVISATION AND OFTEN HAS ELEMENTS OF PLAY WEBELIEVE A COMPETITION TOUCHING ON. THE OFFENSIVE ELEMENTS OF COMPUTER SECURITY IS THEREFORE ABETTER VEHICLE FOR TECH EVANGELISM TO STUDENTS IN AME RICAN HIGH SCHOOLS FURTHER WEBELIEVE THAT AN UNDERSTANDING OF OFFENSIVE TECHNIQUES IS ESSENTIAL FOR MOUNTING AN EFFECTIVE DEFENSE AND THAT THE TOOL SAND CONFIGURATION FOCUSEN COUNTERED IN DEFENSIVE COMPETITIONS DOES NOT LEAD STUDENTS TO KNOW THEIR ENEMY AS EFFECTIVELY AS TEACHING THEM TO ACTIVELY THINK LIKE AN ATTACKER PICOCTF IS AN OFFENSIVELY ORIENTED HIGHSCHOOL COMPUTER SECURITY COMPETITION.

THAT SEEKS TO GENERATE INTEREST IN COMPUTER SCIENCE AMONG HIGHSCHOOLERS TEACHING THEME NOUGH ABOUT COMPUTER SECURITY TO PIQUE THEIR CURIOSITY MOTIVATING THEM TO EXPLORE ON THEIR OWN AND ENABLING THE MTOBETTER DEFEND THE IR MACHINES

THE FLAG IS PICOCTF{N6R4M_4N41Y515_15_73D10U5_702F****}

transposition-trial

Our data got corrupted on the way here. Luckily, nothing got replaced, but every block of 3 got scrambled around! The first word seems to be three letters long, maybe you can use that to recover the rest of the message.

Download the corrupted message here.

配布されたメッセージは

heTfl g as iicpCTo{7F4NRP051N5_16_35P3X51N3_V091B0AE}2

ただの並び替えのように見えるけど、どういう順番で並び替えればよいのだろうか。

The flag is picoCTF{***} になると思われるので、並び替えの規則を探せば良さそう。

"heT" => "The"
"fl " => " fl"
"g a" => "ag "
"s i" => "is "
"icp" => "pic"
"CTo" => "oCT"

3文字ずつ切って並べ替え。

message = "heTfl g as iicpCTo{7F4NRP051N5_16_35P3X51N3_V091B0AE}2"

for i in range(len(message)//3 + 1):
    m = message[i*3:i*3+3]
    print(m[2] + m[0] + m[1], end="")

実行結果

$ python solve.py 
The flag is picoCTF{7R4N5P051N6_15_3XP3N51V3_109AB02E}

※適当スクリプトによりindex out of rangeになるけど解答に影響はないので気にしない…。

Vigenere

Can you decrypt this message?

Decrypt this message using this key "CYLAB".

Vigenere暗号、keyまで教えてもらっているので、CyberCheefにそのまま突っ込みます。

f:id:kusuwada:20220402152417p:plain

diffie-hellman

Alice and Bob wanted to exchange information secretly. The two of them agreed to use the Diffie-Hellman key exchange algorithm, using p = 13 and g = 5. They both chose numbers secretly where Alice chose 7 and Bob chose 3. Then, Alice sent Bob some encoded text (with both letters and digits) using the generated key as the shift amount for a Caesar cipher over the alphabet and the decimal digits. Can you figure out the contents of the message?

Download the message here.

Wrap your decrypted message in the picoCTF flag format like: picoCTF{decrypted_message}

Diffie-Hellman鍵交換アルゴリズムの問題。人の名前まで一緒の説明ありがたい。必要なパラメータは問題文中にあるので、あとは公式に当てはめて計算するだけ。

g = 5
p = 13
A = pow(g, 7, p)
B = pow(g, 3, p)
KA = pow(B, 7, p)
print(KA)

実行結果

$ python solve.py 
5

次にシーザー暗号を復号します。オンラインで復号してくれるところがあるので、ここに鍵の5とアルファベットを[A-Z0-9]にカスタマイズして投げます。

以下2つの結果が得られました。

MEDFE1_MBZRD1_BF_E_IBH_A4HNEHDN_FODMCOOC
C4354R_C1PH3R_15_4_817_0U7D473D_5E3C2EE2

下のやつがleetとして読めるので、これが答え。

Very Smooth

Forget safe primes... Here, we like to live life dangerously... >:) * gen.py * output.txt

なんか見たことあるタイトルだ。SECCON 2017 online CTF Very smooth、これだ！
この時使った ポラードのp-1因数分解法 のスクリプトをそのまま使いまわしたところ、なんと n が因数分解できました。やったね。(スクリプトと解説は上記リンク参考)

$ python solve.py 
M=10000
M=20000
M=30000
M=40000
M=50000
M=60000
factor is 159652342260602436611264882107764540496206777532515381978886917602247902747922672308128228056532167311635408138845484288179466203049041882723045592330122232567342518194630068422135188545880928509542459095514667379085548962076958641693004621121073173222707331672786582779407036356311260724097659870075337003627, M = 64373
p: 159652342260602436611264882107764540496206777532515381978886917602247902747922672308128228056532167311635408138845484288179466203049041882723045592330122232567342518194630068422135188545880928509542459095514667379085548962076958641693004621121073173222707331672786582779407036356311260724097659870075337003627
q: 155886972960664534013041814351782927840465950022742711153704061512767231252254923859358385447688708709761645561788434482490726299524712681978677060822069411804436435368518028882769406676617745559724738774782701625211779174370759988895228070938831967483401953816901269670197361506466713077188578114638897325343

これをもとに、cipher text(c)を復号します。

from Crypto.Util.number import inverse
import binascii

n = 0xc5261293c8f9c420bc5291ac0c14e103944b6621bb2595089f1641d85c4dae589f101e0962fe2b25fcf4186fb259cbd88154b75f327d990a76351a03ac0185af4e1a127b708348db59cd4625b40d4e161d17b8ead6944148e9582985bbc6a7eaf9916cb138706ce293232378ebd8f95c3f4db6c8a77a597974848d695d774efae5bd3b32c64c72bcf19d3b181c2046e194212696ec41f0671314f506c27a2ecfd48313e371b0ae731026d6951f6e39dc6592ebd1e60b845253f8cd6b0497f0139e8a16d9e5c446e4a33811f3e8a918c6cd917ca83408b323ce299d1ea9f7e7e1408e724679725688c92ca96b84b0c94ce717a54c470d035764bc0b92f404f1f5
c = 0x1f511af6dd19a480eb16415a54c122d7485de4d933e0aeee6e9b5598a8e338c2b29583aee80c241116bc949980e1310649216c4afa97c212fb3eba87d2b3a428c4cc145136eff7b902c508cb871dcd326332d75b6176a5a551840ba3c76cf4ad6e3fdbba0d031159ef60b59a1c6f4d87d90623e5fe140b9f56a2ebc4c87ee7b708f188742732ff2c09b175f4703960f2c29abccf428b3326d0bd3d737343e699a788398e1a623a8bd13828ef5483c82e19f31dca2a7effe5b1f8dc8a81a5ce873a082016b1f510f712ae2fa58ecdd49ab3a489c8a86e2bb088a85262d791af313b0383a56f14ddbb85cb89fb31f863923377771d3e73788560c9ced7b188ba97
E = 65537
p = 159652342260602436611264882107764540496206777532515381978886917602247902747922672308128228056532167311635408138845484288179466203049041882723045592330122232567342518194630068422135188545880928509542459095514667379085548962076958641693004621121073173222707331672786582779407036356311260724097659870075337003627
q = 155886972960664534013041814351782927840465950022742711153704061512767231252254923859358385447688708709761645561788434482490726299524712681978677060822069411804436435368518028882769406676617745559724738774782701625211779174370759988895228070938831967483401953816901269670197361506466713077188578114638897325343
d = inverse(E, (p-1)*(q-1))

m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:]).decode('ascii')
print(flag)

実行結果

$ python solve2.py 
picoCTF{7c8625a1}

Sum-O-Primes

We have so much faith in RSA we give you not just the product of the primes, but their sum as well! * gen.py * output.txt

今回は掛け算じゃなくて足し算を使ったRSAみたいです。配布されたスクリプトをじっくり読んでみます。

p + q = x
p * q = n

これを満たす p,q を見つければ良いようです。

public key - Breaking RSA with Factor in Range of $\sqrt{N}$ - Cryptography Stack Exchange にも良い説明がありました。

N = p*q = ((p+q)/2)**2 - ((p-q)/2)**2

という性質を利用すると、p + q = x なので、解けそう！

x = 0x193a4f9d511dfa628e25a42de2e16123a4503c2ba1983dab3402b0f84d2b145116c3d45c4ece5c2ef62e425df830c9cf9b324edd729fdf75f8cb89cfad0d217cc83890c37e1caa39c41588deb59b0aae82291ee407dcb51c80be787ad7f61802c6811830faf12be64a8764e95471c645c5dddc686d7068126f5777c731b125198
n = 0x9b38de276b7e997c07bca5117230f669642491b540741badeb3cb8f096f3820149b31154bd674f3e3d7df12c96896bebfb0245d330309af05fc58d3fcfb06523c680334ef7eb9fb1bf2934ebac715b56326de577a2a45b953b6f6e22387be9fc89908a43a65a9133db084c39b18096338cd574614d4bcb5f03827a86f161370aaebdcdc1736289c4f59ab28e9eed74161c3cd9ff7de7c8c2d2845e0c9ebce843a88a3a93a7450bd4b9ab9a123569602f707489f18c3efc63f305de4d2942414c8c76d6ca18b4a8f38227c9b786857612e6fb45daee4db30a94b4cb9328e068fcabd40c0b705b944209e6c866505b1e06cb461da0858eaf7b26a043822c2a93a7
c = 0x93a10ce3b158c94ff48ef51204562d0ab3ce9ce73d494d059d21449e2cb1259ab7d3bd14126661d13bb4739282c2bf5995a7fa28f82f989f9f77afd28efc1a53d7729970bf7460dfb26f23286ba2e7f10917aed99fe27859c96a4e16c101d1e585f623f761dd28b1eca9be34e49ea851f5a649123283cc7d6c85c83b5a7447f1d910bbe0c5541136ce0370621d6e86e5769c160c5574d814bf2a0153de84e391cd1b538ae17c69f8c175a12bd433fd381f3e1617dfe25604e8f83e5a5fe271082e7315bbb70f992bb9a03cb1f39eac31a379620bb31a7bd22abc0f82baf7250dfdfc8f2533cf1f955e67cba94574a1dc968ba02e2fe995797815784c3d8ab74f

# N = p*q = ((p+q)/2)**2 - ((p-q)/2)**2

a = (x//2)**2 - n
print(a)

このあと、math.sqrt(a) をすると、数が大きすぎてエラーになってしまったので、【Python】巨大な数の整数平方根のプログラム【改良版】 - 流れる空の中で数学を。 こちらのプログラムをお借りしてaの平方根を計算。結果を sq として上記プログラムの続きです。

sq = 22154469208447724337645605498105541244045940508206582138619491297742548708528348073438559350773059843630670647316651373227707404301742437996121773370743392191293715942636636207512443558849172807144098364052302896334658043475260234764933068154832506032305953302163703204903611040380967815654013878302033608275

diff = sq * 2

p = (x - diff)//2
q = x - p
nN = p * q
print("p: " + str(p))
print("q: " + str(q))
assert(nN == n)

from Crypto.Util.number import inverse
import binascii

e = 65537
d = inverse(e, (p-1)*(q-1))

m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:]).decode('ascii')
print(flag)

実行結果

$ python solve.py 
a: 490820505908058337368283981531109627807402127531142542427947862130574350091918036940295424425701199047266993366295249043439314888765047453867815218478947622150504908410575020261521736500949284556518433231910929569012328071036882940565560782245458314227342273506207004531712531541640161962748539915109560112137910617892409916894158080630686835299162644215620406858295781560432853097848632157895135083981210544568971256902003255222439754015534345160107916958726128221372125498786920907450534844616825044404163114480838141130040536436144152321474749837253804174879508938655573797188172613852565209755581427616148475625
p: 119569912348019973808690648749233130234147905846600013235049261329629970511527761524945847616965313961538713539339797361044473682137188967689436399275622598823807683697187768076793066267578400065793399498609464820787702834758072187460388248841109767616650659184902691855492090063216897253934411433653188209273
q: 163878850764915422483981859745444212722239786863013177512288243925115067928584457671822966318511433648800054833973100107499888490740673843681679946017109383206395115582461040491817953385276745680081596226714070613457018921708592656990254385150774779681262565789230098265299312143978832885242439190257255425823
picoCTF{24929c45}

Sequences（★要復習）

I wrote this linear recurrence function, can you figure out how to make it run fast enough and get the flag?

Download the code here sequences.py

Note that even an efficient solution might take several seconds to run. If your solution is taking several minutes, then you may need to reconsider your approach.

sequences.pyが配布されます。

import math
import hashlib
import sys
from tqdm import tqdm
import functools

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")

# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
    if i == 0: return 1
    if i == 1: return 2
    if i == 2: return 3
    if i == 3: return 4

    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)


# Decrypt the flag
def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

if __name__ == "__main__":
    sol = m_func(ITERS)
    decrypt_flag(sol)

ヒントは

Google "matrix diagonalization". Can you figure out how to apply it to this function?

単純にスクリプトを実行してみます。

$ python3 sequences.py 
Traceback (most recent call last):
  File "/home/kali/ctf/pico2022/sequences.py", line 38, in <module>
    sol = m_func(ITERS)
  File "/home/kali/ctf/pico2022/sequences.py", line 19, in m_func
    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
  File "/home/kali/ctf/pico2022/sequences.py", line 19, in m_func
    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
  File "/home/kali/ctf/pico2022/sequences.py", line 19, in m_func
    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
  [Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded

再帰が深すぎて駄目っぽい。
今回の数式は、こんな感じの漸化式で表せます。

a_n=21a_{n-1} + 301a_{n-2} - 9549a_{n-3} + 55692a_{n-4} \\ {\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} a_{3} = 4 \\ a_{2} = 3 \\ a_{1} = 2 \\ a_{0} = 1 \end{array} \right. \end{eqnarray} } , n>4

とりあえず非再帰化 (stack, memorize)

再帰が深すぎるときは、とりあえず全部平にするよう書き直してみる！ということで、ヒントを無視してやってみました。
漸化式を再帰を使わないようにする書き直しについては、Python(17)再帰関数の例を非再帰にする:まとめ編-p--qを参考にしました。

import math
import hashlib
import sys

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")


def my_func(i):
    if i == 0: return 1
    if i == 1: return 2
    if i == 2: return 3
    if i == 3: return 4
    
    a = 4
    b = 3
    c = 2
    d = 1
    while i > 3:
        i -=1
        newa = 21*a + 301*b - 9549*c + 55692*d
        d = c
        c = b
        b = a
        a = newa
        if i % 10000 == 0:
            print(i)
    return a

# Decrypt the flag
def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    
    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

if __name__ == "__main__":
    sol = my_func(ITERS)
    print(sol)
    decrypt_flag(sol)

nが4,5,6など小さいときは問題なく動いたので、問題の 20000000 を入れて動かして見ます。が、debug printを出して速度を確認したところ、とても終わりそうにない。他の解法も並行して考えます。

対角化行列 (matrix diagonalization)

ヒントをちゃんと見て、"matrix diagonalization", 対角行列について調べました。
条件はあるものの、漸化式を線形代数で解く方法です。
この解き方については、pythonライブラリ sympy の使い方も合わせて載っている、線形代数で漸化式を解くやつ - くろのて を参考にしました。

import numpy as np
import sympy as sy
import math
import hashlib
import sys

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")

def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

sy.init_printing()
n = sy.Symbol('n')
A = sy.Matrix([[21, 301, -9549, 55692], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]])
evs = A.eigenvects()
P = sy.Matrix([ev[-1][0].values() for ev in evs]).T
D = P ** (-1) * A * P
sol = (P) * (D ** (ITERS)) * (P ** -1) * sy.Matrix([4, 3, 2, 1])
print(sol)
decrypt_flag(sol[-1])

この方法で試しに10000などを入れて計算させてみたところ、先程の非再帰化よりも格段に早く解けそう。なんたってヒント使ってるし、これがきっと想定解…！と思って動かしてみます。…が、寝て起きて6時間経っても終わってない…。flag取っていた気でいたので、「あれ？まだ想定解じゃない？」と並行して見直してみます。

更に工夫が必要そう

ところで、上記の対角行列で計算したときに導出した一般項は、上記のスクリプトを

sol = (P) * (D ** (n)) * (P ** -1) * sy.Matrix([4, 3, 2, 1])

と書き換えると出てきて

\dfrac{403(-21)^{n}}{10659} + \dfrac{760(12)^{n}}{33} - \dfrac{1727(13)^{n}}{68} + \dfrac{253(17)^{n}}{76}

これで n \to \infty にすると収束、とかしてくれる項があればよかったんだけど、無さそう。
なんとか計算量を減らせないかと思って、再度配布されたスクリプトを見ていると sol をdecrypt時に

sol = sol % (10**10000)

して使っている。上の桁の情報はだいぶ落ちてしまうようだ。
solの演算中に剰余を挟んで計算を軽く出来ないかな？

[数学] n乗の計算 | maspyのHP この辺の知識（中国剰余定理・Fermatの小定理・Eulerの定理）を使えば計算がだいぶ楽になりそうだと思って、ノートを使って考え始めたのだけど…

結局、上の対角行列で計算するやつが更に数時間後に答えを出してくれていたのでflagゲット。

$ solve.py
...(omit)...too long sol
picoCTF{b1g_numb3rs_689693c6}

とりあえずflag入れて考えるのを後回しにしてしまったので、要復習。

NSA Backdoor（★要復習）

I heard someone has been sneakily installing backdoors in open-source implementations of Diffie-Hellman... I wonder who it could be... ;) * gen.py * output.txt

この問題、解けたけど理論をちゃんと理解していないので要復習。
最後の問題なので、まずヒントを見てみます。

Look for Mr. Wong's whitepaper... His work has helped so many cats!

なんか論文がヒントになりそうらしい。
配布されたgen.pyを見てみると、p,qの選出に get_smooth_prime という関数を使っています。smooth、さっき見たな。

とりあえず、Very Smoothと同じように、p-1法で p,q を割り出してみます。

#!/usr/bin/env python3

from math import gcd

N = 0x8d9424ddbf9fff7636d98abc25af7fde87e719dc3ceee86ca441b079e167cc22ff283f1a8671263c2e5ebd383ca3255e903b37ebca9961fd8a657cb987ef1e709866acc457995bfc7a6d4be7e88b9ee03a9872329e05cb7eb849d61e4bb44a25be8bd42f19f13a9417bfab73ba616b7c05865640682dc685890bbce8c20c65175f322b5b27788fede4f6704c6cb7b2d2d9439fad50f8b79ffab0b790591ae7f43bd0316565b097b9361d3beb88b6ef569d05af75d655b5133dc59a24c86d147a5eb5311344a66791f03a3da797effd600aa61564ce4ffd81f70bfedf12ca7857b9ac781a4823f6c1a08f1e86f8fe0e1eb3eb6ac71b63e4b03ba841c8588f6df1
seed = 2  # seedは通常2か3, うまく分解できなかったときに動かす
B = 100000 # B-smoothと仮定する 通常100000まで

a = seed
G = 1
cnt = 0
M = 1
while(G<=1):
    M = M + 1
    if M >= B:
        break
    if M % 10000 == 0:
        print("M=" + str(M))
    a = pow(a, M, N)
    G = gcd(a-1, N)
if G > 1 and G < N:
    print("factor is " + str(G) + ", M = " + str(M))
else:
    print("try new seed")

print("p: " + str(G))
print("q: " + str(N//G))

実行結果

$ python solve.py 
M=10000
M=20000
M=30000
M=40000
M=50000
M=60000
factor is 120759530765440164788393584815198181785453365216058011221242572474857701934543658420625103273619411412685939059091676362260202826471982447213813057019415223578402663988113530890287786672842686395844059610821738383797601768012556360596829980884906822859047976972535357205380764775443960532258052851032850088083, M = 65011
p: 120759530765440164788393584815198181785453365216058011221242572474857701934543658420625103273619411412685939059091676362260202826471982447213813057019415223578402663988113530890287786672842686395844059610821738383797601768012556360596829980884906822859047976972535357205380764775443960532258052851032850088083
q: 148002012100249225211662649106891900338687449066163723028254833265186276357822984503291431005022345537114605526401000578931094547354527644098114527189618934427749093865493885104212273645033334829221879070432779709963099329606891524353790656906054627628242281301321807207140508428052078410188358267430195699179

p,qが求まりました！
Very Smoothと違うところは、cの算出方法。

n = p * q

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

だったのが

n = p * q
c = pow(3, FLAG, n)

になっています。なんだこれは。
cの計算にp,q使ってないじゃん。cを暗号文と仮定すると、平文が3って事になってsecretがeってことになる。
この式、FLAGをsecretと見立てると、どちらかというと鍵交換のほうがしっくりくる。最近全然やってなかったので、Diffie-Hellmanについて以下で基本をおさらい。

今回の課題をRSA公開鍵暗号方式ではなくてDiffie-Hellman鍵共有の話だと思って紛らわしい変数を読み替えると、

RSA -> DH
n   -> p
c   -> A
3   -> g
FLAG-> a

となってそう。gがとても小さいのが今回の問題の鍵っぽい。

Diffie-Hellman Wong type:pdfでググると、下記の論文がヒット。

これがヒントのwhitepaperそのものかはわかりませんが、Backdoorというワードも入ってるので怪しい。ざーっと流し読んでみます。
ここで紹介されている攻撃ツール、GitHub - mimoo/Diffie-Hellman_Backdoor: How to backdoor Diffie-Hellmanに飛んで、こっちもざっと流し読み。更にこのツールを使って解いているCTFのwriteupを探してみると

UIUCTF 2021 CTF Writeup > Dhke-adventure

このwriteupが引っかかりました。
このときの g は 2 で、やはりとても小さい。なんか同じ手が使えそう…。

先程のp-1法によりpは求まっているので、

b = discrete_log(jotaro, Mod(g, p))

の部分だけ拝借します。先ほどのwikipediaの記事と変数の対応を合わせると、

a = discrete_log(A, Mod(g, q))

これを sage に解いてもらいます。

$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.4, Release Date: 2021-08-22                     │
│ Using Python 3.9.8. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
sage: modgq = Mod(3,148002012100249225211662649106891900338687449066163723028254833265186276357822984503291431005022345537114605526401000578931094547354527644098114527189618934427749093865493885104212273645033334829221879070432779709963099329606891524353790656906054627628242281301321807207140508428052078410188358267430195699179)
sage: discrete_log(0x4679331be9883c4518d4870352281710777bcd74e6c9e9abb886254cf42c2f7adf5b58af8c8c00a51a72ee1ffaa8af3e9877a11d8ee8702446f1814a0255013a1e1b50a1c795218130a0dade9a5eb6b2c74a726c689ea9a5fe8391d7963d0a648c7ed79f3571d28252fd109f071a3f4ed6cb1de203c24e1cb5517983a8946a4b69cb39844c9f1c6975ad3f9ff7075b1c3a28a8eb25e28d7ecab781686412ca81f0c646094782c8cbacce9a58609c8041b82f9052ff0afd7c9953fa191ed548cf756e7f713341b434b6cc84ac62ff14740c213c60985fc71a6d23ffec7c2e145af0a4217af5f3263083030bc803c0e591a18760c4ea957f72017dcebe7b130e08,modgq)
38251710328773353863818251834343663286141

一瞬で求まりました。

f:id:kusuwada:20220404142614p:plain

後はこれをlong_to_bytesしたらflagが出ました。ほとんどスクリプト使ってないけど、流れを掴むためだけの雰囲気スクリプト

from Crypto.Util.number import *

p = 120759530765440164788393584815198181785453365216058011221242572474857701934543658420625103273619411412685939059091676362260202826471982447213813057019415223578402663988113530890287786672842686395844059610821738383797601768012556360596829980884906822859047976972535357205380764775443960532258052851032850088083
q = 148002012100249225211662649106891900338687449066163723028254833265186276357822984503291431005022345537114605526401000578931094547354527644098114527189618934427749093865493885104212273645033334829221879070432779709963099329606891524353790656906054627628242281301321807207140508428052078410188358267430195699179
n = 0x8d9424ddbf9fff7636d98abc25af7fde87e719dc3ceee86ca441b079e167cc22ff283f1a8671263c2e5ebd383ca3255e903b37ebca9961fd8a657cb987ef1e709866acc457995bfc7a6d4be7e88b9ee03a9872329e05cb7eb849d61e4bb44a25be8bd42f19f13a9417bfab73ba616b7c05865640682dc685890bbce8c20c65175f322b5b27788fede4f6704c6cb7b2d2d9439fad50f8b79ffab0b790591ae7f43bd0316565b097b9361d3beb88b6ef569d05af75d655b5133dc59a24c86d147a5eb5311344a66791f03a3da797effd600aa61564ce4ffd81f70bfedf12ca7857b9ac781a4823f6c1a08f1e86f8fe0e1eb3eb6ac71b63e4b03ba841c8588f6df1
c = 0x4679331be9883c4518d4870352281710777bcd74e6c9e9abb886254cf42c2f7adf5b58af8c8c00a51a72ee1ffaa8af3e9877a11d8ee8702446f1814a0255013a1e1b50a1c795218130a0dade9a5eb6b2c74a726c689ea9a5fe8391d7963d0a648c7ed79f3571d28252fd109f071a3f4ed6cb1de203c24e1cb5517983a8946a4b69cb39844c9f1c6975ad3f9ff7075b1c3a28a8eb25e28d7ecab781686412ca81f0c646094782c8cbacce9a58609c8041b82f9052ff0afd7c9953fa191ed548cf756e7f713341b434b6cc84ac62ff14740c213c60985fc71a6d23ffec7c2e145af0a4217af5f3263083030bc803c0e591a18760c4ea957f72017dcebe7b130e08

g = 3
#a = discrete_log(c, Mod(g, p))  // calc by sage
a = 38251710328773353863818251834343663286141
flag = long_to_bytes(a)
print(flag)

これは要復習。偶然似た問題と解法があって助かった。ちゃんと数学的に理解できたら追記予定。