picoCTF 2022 writeup[crypto]

問題ファイルや私がかいたソルバは()にあります。

basic-mod1 (100pts)

言われた通りに数値を文字に変換していくだけ。
picoCTF{r0und_n_r0und_8c863ee7}

basic-mod2 (100pts)

言われた通りに数値を文字に変換していくだけ2。modular inverseを求めるのにはCrypto.Util.number.inverse()を使いました。
picoCTF{1nv3r53ly_h4rd_f6747912}

credstuff (100pts)

passwords.txtの中にcvpbPGS{P7e1S_54I35_71Z3}とかいう文字列があります。caesar cipherなので元に戻してやるとflagになります。
picoCTF{C7r1F_54V35_71M3}

morse-code (100pts)

渡されたwavファイルは明らかにモールス信号なので頑張って復元します。モールス信号の音声を自動で文字列に変換するツールってあるのかな。

.-- .... ....- --...
.... ....- --... ....
----. ----- -..
.-- ..--- ----- ..- ----. .... --...

picoCTF{wh47_h47h_90d_w20u9h7}

rail-fence (100pts)

Rail fence cipherという暗号らしいです。がんばって復号します。

T.....a..... ....._.....7.....N.....6.....D.....5.....4
.h...l.g...:.W...3.D..._.H...3.C...3.1...N._..._.5...1.0
..e.f... .s...H.R...0.5...3.F...3.8...N.4...3.D...2.8
... .....i.....3.....3....._....._....._.....N.....2

"The flag is: WH3R3_D035_7H3_F3NC3_8361N_4ND_3ND_5528140"と書いてありました。
picoCTF{WH3R3_D035_7H3_F3NC3_8361N_4ND_3ND_55228140}

substitution0 (100pts)

単一換字式暗号らしいのでがんばって復号します。一行目の文字列がABC...XYZということがわかったところで終了です。

ABCDEFGHIJKLMNOPQRSTUVWXYZ 

Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
that time, unknown to naturalists#of course a great prize in a scientific point
of view. There were two round black spots near one extremity of the back, and a
long one near the other. The scales were exceedingly hard and glossy, with all the
appearance of burnished gold. The weight of the insect was very remarkable, and,
taking all things into consideration, I could hardly blame Jupiter for his opinion
respecting it.

The flag is: picoCTF{5UB5717U710N_3V0LU710N_AA1CC2B7}

substitution1 (100pts)

単一換字式暗号らしいのでがんばって復号します2。なぜかflagにしか登場しない文字Qがありguess要素が発生しています。

CTFs (short for capture the flag) are a type of computer security competition. Contestants are presented with a set of challenges which test their creativity, technical (and googling) skills, and problem-solving ability. Challenges usually cover a number of categories, and when solved, each yields a string (called a flag) which is submitted to an online scoring service. CTFs are a great way to learn a wide array of computer security skills in a safe, legal environment, and are hosted and played by many security groups around the world for fun and practice. For this problem, the flag is: picoCTF{FR3#U3NCY_4774CK5_4R3_C001_B810DD84}

picoCTF{FR3QU3NCY_4774CK5_4R3_C001_B810DD84}

substitution2 (100pts)

単一換字式暗号らしいのでがんばって復号します3。頻度分析とかするとよいです。

thereexistseveralotherwellestablishedhighschoolcomputersecuritycompetitionsincludingcyberpatriotanduscyberchallengethesecompetitionsfocusprimarilyonsystemsadministrationfundamentalswhichareveryusefulandmarketableskillshoweverwebelievetheproperpurposeofahighschoolcomputersecuritycompetitionisnotonlytoteachvaluableskillsbutalsotogetstudentsinterestedinandexcitedaboutcomputersciencedefensivecompetitionsareoftenlaboriousaffairsandcomedowntorunningchecklistsandexecutingconfigscriptsoffenseontheotherhandisheavilyfocusedonexplorationandimprovisationandoftenhaselementsofplaywebelieveacompetitiontouchingontheoffensiveelementsofcomputersecurityisthereforeabettervehiclefortechevangelismtostudentsinamericanhighschoolsfurtherwebelievethatanunderstandingofoffensivetechniquesisessentialformountinganeffectivedefenseandthatthetoolsandconfigurationfocusencounteredindefensivecompetitionsdoesnotleadstudentstoknowtheirenemyaseffectivelyasteachingthemtoactivelythinklikeanattackerpicoctfisanoffensivelyorientedhighschoolcomputersecuritycompetitionthatseekstogenerateinterestincomputerscienceamonghighschoolersteachingthemenoughaboutcomputersecuritytopiquetheircuriositymotivatingthemtoexploreontheirownandenablingthemtobetterdefendtheirmachinestheflagispicoCTF{N6R4M_4N41Y515_15_73D10U5_F302F3B6}

transposition-trial (100pts)

先頭18文字heTfl g as iicpCToがもとはThe flag is picoCTだったと推測できるので、ブロックごとの置換規則をがんばって求めます。
The flag is picoCTF{7R4N5P051N6_15_3XP3N51V3_ECDE4C74}

Vigenere (100pts)

Vigenere暗号なのでインターネットに転がってる復号ツールに投げます。
picoCTF{D0NT_US3_V1G3N3R3_C1PH3R_c481du5f}

diffie-hellman (200pts)

共有される鍵は$5^{21} \mod 13\equiv 5$です。よって、ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789を56789ABCDEFGHIJKLMNOPQRSTUVWXYZ01234に移すようなcaesar cipherのdecodeをすればよいです。
picoCTF{C4354R_C1PH3R_15_4_817_0U7D473D_E657DA5D}

Very Smooth (300pts)

$p,q$は素数ですが、$p-1,q-1$はそれぞれ$2^{16}, 2^{17}$未満の素数の積になっています。(こういう素数$p,q$のことをsmooth-primeというらしいです)このような$p,q$の積$n=pq$を素因数分解するアルゴリズムにPollard's $p-1$ algorithmというものがあるので、これを使えばよいです。
picoCTF{95d15b05}

Sequences (400pts)

配布されたプログラムをいじって$O(N)$で走るようにします。実行するのに50分くらいかかりました。
picoCTF{b1g_numb3rs_1e4c686b}

Sum-O-Primes (400pts)

$m=(p-1)(q-1)=pq-p-q+1=n-x+1$なので$n,x$から$m$を計算可能です。あとはRSAを復号するだけ。
picoCTF{f5eab190}

NSA Backdoor (500pts)

ヒントに書いてあるMr.Wongのpaperというのはたぶんコレのことです。このpaperの5章が今回の問題通りなので、この通りにします。
この問題では$p,q$がsmooth-primeなので、$\varphi(n)=(p-1)(q-1)$は小さめな素因数の積で表すことができます。よって、Pohlig–Hellman algorithmと同様に各素因数でmodをとったときの離散対数$x$の値を集めることができ、中国剰余定理によりもとの$x$を計算できます。
picoCTF{49ed5f06}