CSAW'21 CTF Writeup (Crypto)

はじめに

9/11 - 9/13 で開催された CSAW'21 CTF にソロで参加し、Bits 以外の Crypto 問題を解いたので、その Writeup を書きます。Bits は Rust の問題プログラムが読めなかったため、挑むことすらできませんでした・・・

Gotta Decrypt Them All

問題概要

問題サーバに接続すると、モールス信号が送られてくる。

$ nc crypto.chal.csaw.io 5001
Can you decrypt them all to prove yourself?

What does this mean?
---.. ....- /.---- ----- ..... /-.... ..... /..... --... /--... ...-- /-.... ---.. /.---- ----- ...-- /.---- ..--- .---- /--... --... /.---- ..--- ..--- /.---- ----- --... /.---- ..--- .---- /--... --... /-.... ---.. /-.... ..... /.---- ..--- ----- /--... --... /-.... ---.. /--... ...-- /.---- ..--- ..--- /--... ---.. /.---- ----- -.... /---.. ..... /....- ----. /--... --... /.---- ..--- ..--- /----. ----. /.---- .---- ----. /--... ----. /---.. ....- /---.. .---- /..... ..--- /--... ----. /---.. ....- /---.. ----. /..... ..--- /--... --... /-.... ---.. /-.... ----. /.---- ..--- ----- /--... ----. /-.... ---.. /.---- ----- --... /..... .---- /--... ---.. /---.. ....- /-.... ----. /..... ...-- /--... ---.. /-.... ---.. /---.. ----. /..... ----- /--... ---.. /.---- ..--- ..--- /-.... ..... /.---- ..--- .---- /--... ----. /-.... ---.. /-.... ..... /..... ----- /--... ---.. /---.. ....- /.---- ----- --... /.---- ..--- .---- /--... ---.. /---.. ....- /.---- ----- --... /..... ----- /--... --... /---.. ....- /---.. .---- /.---- .---- ----. /--... --... /-.... ---.. /-.... ----. /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. ..... /.---- .---- ----. /--... ----. /-.... ---.. /--... ...-- /..... ...-- /--... ---.. /-.... ---.. /---.. ..... /.---- ..--- ----- /--... --... /---.. ....- /---.. .---- /.---- .---- ----. /--... --... /.---- ..--- ..--- /---.. ----. /..... ----- /--... ----. /---.. ....- /--... ...-- /....- ---.. /--... ----. /---.. ....- /---.. .---- /..... ..--- /--... ----. /---.. ....- /-.... ----. /..... .---- /--... ---.. /.---- ----- -.... /-.... ..... /.---- .---- ----. /--... ---.. /.---- ----- -.... /.---- ----- --... /..... ...-- /--... ----. /-.... ---.. /.---- ----- ...-- /.---- .---- ----. /--... ---.. /.---- ----- -.... /---.. ..... /..... ----- /--... ---.. /.---- ----- -.... /.---- ----- ...-- /..... ...-- /--... ---.. /---.. ....- /---.. ..... /.---- ..--- .---- /--... ---.. /---.. ....- /--... ...-- /.---- .---- ----. /--... ---.. /-.... ---.. /--... ...-- /..... ..--- /--... ---.. /.---- ----- -.... /--... --... /..... ...-- /--... ---.. /-.... ---.. /-.... ----. /.---- ..--- .---- /--... ---.. /-.... ---.. /---.. ----. /....- ----. /--... ---.. /.---- ..--- ..--- /---.. ----. /.---- ..--- ----- /--... --... /.---- ----- -.... /.---- ----- ...-- /....- ----. /--... ---.. /---.. ....- /--... --... /..... ----- /--... ----. /-.... ---.. /.---- ----- ...-- /..... ----- /--... ---.. /.---- ----- -.... /--... ...-- /....- ----. /--... ----. /---.. ....- /--... --... /.---- ..--- ..--- /--... ----. /---.. ....- /----. ----. /..... ...-- /--... --... /.---- ..--- ..--- /.---- ----- ...-- /....- ---.. /--... ---.. /.---- ..--- ..--- /---.. ----. /.---- .---- ----. /--... ----. /-.... ---.. /--... ...-- /.---- ..--- ----- /--... ---.. /.---- ----- -.... /--... ...-- /.---- ..--- ----- /--... --... /.---- ..--- ..--- /--... ...-- /..... .---- /--... ---.. /.---- ----- -.... /-.... ..... /..... ----- /--... --... /---.. ....- /-.... ..... /..... .---- /--... --... /---.. ....- /-.... ..... /..... ----- /--... ---.. /.---- ----- -.... /--... --... /.---- ..--- ..--- /--... ----. /---.. ....- /---.. ----. /.---- ..--- ----- /--... ---.. /.---- ----- -.... /.---- ----- ...-- /....- ----. /--... --... /.---- ----- -.... /.---- ----- --... /..... ...-- /--... --... /---.. ....- /--... ...-- /....- ----. /--... ---.. /---.. ....- /---.. ..... /..... ..--- /--... ---.. /.---- ..--- ..--- /--... --... /..... ...-- /--... ---.. /---.. ....- /.---- ----- --... /....- ---.. /--... ---.. /.---- ..--- ..--- /--... ...-- /..... ----- /--... ---.. /---.. ....- /---.. .---- /..... ...-- /--... ---.. /.---- ----- -.... /-.... ..... /....- ----. /--... --... /.---- ..--- ..--- /---.. ----. /.---- ..--- .---- /--... ---.. /.---- ----- -.... /-.... ----. /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. ..... /....- ----. /--... ----. /---.. ....- /-.... ..... /....- ----. /--... ---.. /.---- ..--- ..--- /----. ----. /.---- ..--- ..--- /--... --... /-.... ---.. /---.. ..... /....- ----. /--... ---.. /---.. ....- /.---- ----- ...-- /....- ----. /--... ---.. /.---- ----- -.... /.---- ----- ...-- /.---- ..--- .---- /--... ----. /---.. ....- /-.... ..... /.---- .---- ----. /--... --... /---.. ....- /---.. ----. /..... ...-- /--... --... /---.. ....- /.---- ----- --... /.---- .---- ----. /--... ----. /---.. ....- /.---- ----- --... /....- ----. /--... --... /-.... ---.. /--... ...-- /..... ----- /--... ---.. /.---- ----- -.... /---.. .---- /.---- ..--- ..--- /--... --... /-.... ---.. /.---- ----- ...-- /..... ...-- /--... --... /.---- ----- -.... /-.... ----. /.---- .---- ----. /--... ----. /---.. ....- /---.. .---- /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. ----. /.---- ..--- ..--- /--... --... /.---- ..--- ..--- /----. ----. /....- ---.. /--... ---.. /.---- ----- -.... /---.. .---- /....- ----. /--... --... /.---- ..--- ..--- /---.. ..... /.---- ..--- .---- /--... ----. /-.... ---.. /.---- ----- --... /..... .---- /--... ---.. /.---- ----- -.... /---.. ..... /....- ----. /--... ---.. /-.... ---.. /-.... ----. /..... ..--- /--... ---.. /-.... ---.. /---.. ..... /..... ----- /--... --... /-.... ---.. /--... --... /.---- .---- ----. /--... --... /-.... ---.. /---.. ..... /.---- .---- ----. /--... ---.. /-.... ---.. /-.... ..... /..... ...-- /--... ----. /---.. ....- /-.... ..... /..... ..--- /--... --... /.---- ..--- ..--- /--... --... /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /-.... ..... /.---- ..--- ..--- /--... ----. /---.. ....- /.---- ----- --... /..... ...-- /--... ---.. /---.. ....- /.---- ----- --... /....- ----. /--... --... /.---- ..--- ..--- /-.... ----. /..... ----- /--... ----. /-.... ---.. /--... --... /..... ----- /--... ---.. /.---- ----- -.... /--... ...-- /..... ----- /--... --... /-.... ---.. /.---- ----- ...-- /.---- .---- ----. /--... --... /-.... ---.. /-.... ..... /.---- ..--- ----- /--... --... /-.... ---.. /--... ...-- /..... .---- /--... ---.. /-.... ---.. /-.... ----. /..... ...-- /-.... --... /.---- ----- ----. /---.. ..... /.---- ----- ...-- /---.. ----- /---.. ...-- /-.... ..... /.---- ..--- ..--- /-.... --... /.---- ----- ----. /--... --... /.---- ----- ...-- /---.. ----- /---.. ...-- /-.... ..... /.---- ..--- ----- /--... ---.. /---.. ....- /--... ...-- /.---- ..--- ----- /--... ---.. /.---- ----- -.... /----. ----. /....- ---.. /--... --... /.---- ----- -.... /---.. .---- /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /--... --... /..... ...-- /--... ---.. /.---- ..--- ..--- /----. ----. /....- ---.. /--... --... /.---- ..--- ..--- /---.. ----. /..... .---- /--... --... /-.... ---.. /--... ...-- /..... ..--- /--... ----. /---.. ....- /-.... ..... /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /--... --... /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /---.. .---- /....- ----. /--... --... /-.... ---.. /-.... ----. /..... .---- /--... --... /.---- ..--- ..--- /---.. .---- /.---- .---- ----. /--... --... /---.. ....- /--... ...-- /..... .---- /--... ---.. /.---- ----- -.... /---.. ..... /..... ..--- /--... ----. /-.... ---.. /--... ...-- /....- ---.. /--... ----. /-.... ---.. /----. ----. /.---- .---- ----. /--... --... /-.... ---.. /.---- ----- ...-- /.---- ..--- ..--- /--... --... /.---- ..--- ..--- /.---- ----- ...-- /..... ...-- /--... ---.. /.---- ..--- ..--- /--... --... /.---- ..--- .---- /--... --... /.---- ..--- ..--- /--... ...-- /....- ----. /--... --... /-.... ---.. /--... ...-- /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /-.... ..... /.---- ..--- ..--- /--... ---.. /---.. ....- /---.. ----. /.---- ..--- ..--- /--... ---.. /.---- ..--- ..--- /---.. ..... /.---- ..--- ----- /--... ---.. /-.... ---.. /.---- ----- ...-- /..... ..--- /--... --... /---.. ....- /.---- ----- ...-- /..... ----- /--... --... /-.... ---.. /.---- ----- --... /..... ----- /--... --... /.---- ----- -.... /-.... ----. /..... ..--- /--... ---.. /.---- ----- -.... /--... --... /..... ...-- /--... ---.. /.---- ..--- ..--- /---.. ..... /.---- ..--- .---- /--... ---.. /---.. ....- /---.. ----. /-.... .----
>>

一定の時間内に回答しないと、タイムアウトするようになっている。

Oof! Not fast enough!

Looks like things didn't work out for you! Wah, wah, wah!

解法

まずはモールス信号を / 区切りでデコードしてみた。

84 105 65 57 73 68 103 121 77 122 107 121 77 68 65 120 77 68 73 122 78 106 85 49 77 122 99 119 79 84 81 52 79 84 89 52 77 68 69 120 79 68 107 51 78 84 69 53 78 68 89 50 78 122 65 121 79 68 65 50 78 84 107 121 78 84 107 50 77 84 81 119 77 68 69 120 78 122 85 119 79 68 73 53 78 68 85 120 77 84 81 119 77 122 89 50 79 84 73 48 79 84 81 52 79 84 69 51 78 106 65 119 78 106 107 53 79 68 103 119 78 106 85 50 78 106 103 53 78 84 85 121 78 84 73 119 78 68 73 52 78 106 77 53 78 68 69 121 78 68 89 49 78 122 89 120 77 106 103 49 78 84 77 50 79 68 103 50 78 106 73 49 79 84 77 122 79 84 99 53 77 122 103 48 78 122 89 119 79 68 73 120 78 106 73 120 77 122 73 51 78 106 65 50 77 84 65 51 77 84 65 50 78 106 77 122 79 84 89 120 78 106 103 49 77 106 107 53 77 84 73 49 78 84 85 52 78 122 77 53 78 84 107 48 78 122 73 50 78 84 81 53 78 106 65 49 77 122 89 121 78 106 69 120 78 122 85 49 79 84 65 49 78 122 99 122 77 68 85 49 78 84 103 49 78 106 103 121 79 84 65 119 77 84 89 53 77 84 107 119 79 84 107 49 77 68 73 50 78 106 81 122 77 68 103 53 77 106 69 119 79 84 81 120 78 122 89 122 77 122 99 48 78 106 81 49 77 122 85 121 79 68 107 51 78 106 85 49 78 68 69 52 78 68 85 50 77 68 77 119 77 68 85 119 78 68 65 53 79 84 65 52 77 122 77 120 78 122 65 122 79 84 107 53 78 84 107 49 77 122 69 50 79 68 77 50 78 106 73 50 77 68 103 119 77 68 65 120 77 68 73 51 78 68 69 53 67 109 85 103 80 83 65 122 67 109 77 103 80 83 65 120 78 84 73 120 78 106 99 48 77 106 81 121 78 122 77 53 78 122 99 48 77 122 89 51 77 68 73 52 79 84 65 121 78 122 77 121 78 122 81 49 77 68 69 51 77 122 81 119 77 84 73 51 78 106 85 52 79 68 73 48 79 68 99 119 77 68 103 122 77 122 103 53 78 122 77 121 77 122 73 49 77 68 73 120 78 122 65 122 78 84 89 122 78 122 85 120 78 68 103 52 77 84 103 50 77 68 107 50 77 106 69 52 78 106 77 53 78 122 85 121 78 84 89 61

これらを文字列に変換してみると、Base64 らしきものが出てきた。

TiA9IDgyMzkyMDAxMDIzNjU1MzcwOTQ4OTY4MDExODk3NTE5NDY2NzAyODA2NTkyNTk2MTQwMDExNzUwODI5NDUxMTQwMzY2OTI0OTQ4OTE3NjAwNjk5ODgwNjU2Njg5NTUyNTIwNDI4NjM5NDEyNDY1NzYxMjg1NTM2ODg2NjI1OTMzOTc5Mzg0NzYwODIxNjIxMzI3NjA2MTA3MTA2NjMzOTYxNjg1Mjk5MTI1NTU4NzM5NTk0NzI2NTQ5NjA1MzYyNjExNzU1OTA1NzczMDU1NTg1NjgyOTAwMTY5MTkwOTk1MDI2NjQzMDg5MjEwOTQxNzYzMzc0NjQ1MzUyODk3NjU1NDE4NDU2MDMwMDUwNDA5OTA4MzMxNzAzOTk5NTk1MzE2ODM2NjI2MDgwMDAxMDI3NDE5CmUgPSAzCmMgPSAxNTIxNjc0MjQyNzM5Nzc0MzY3MDI4OTAyNzMyNzQ1MDE3MzQwMTI3NjU4ODI0ODcwMDgzMzg5NzMyMzI1MDIxNzAzNTYzNzUxNDg4MTg2MDk2MjE4NjM5NzUyNTY=

Base64 でデコードしてみると、RSA らしき暗号が出てきた。

N = 82392001023655370948968011897519466702806592596140011750829451140366924948917600699880656689552520428639412465761285536886625933979384760821621327606107106633961685299125558739594726549605362611755905773055585682900169190995026643089210941763374645352897655418456030050409908331703999595316836626080001027419
e = 3
c = 152167424273977436702890273274501734012765882487008338973232502170356375148818609621863975256

e が明らかに小さいので c の e 乗根を計算してみると、謎の文字列が出てきた。

Cbxrzba Anzrf

ROT13 を試してみると、答えらしき文字列が出てきた。

Pokemon Names

これを入力してみると、次の問題が表示された。

>> Pokemon Names
You are correct!

What does this mean?
---.. ....- /.---- ----- ..... /-.... ..... /..... --... /--... ...-- /-.... ---.. /-.... ----. /....- ---.. /--... ---.. /-.... ---.. /----. ----. /..... ----- /--... --... /-.... ---.. /--... ...-- /....- ---.. /--... ----. /-.... ---.. /-.... ----. /..... .---- /--... ----. /-.... ---.. /---.. ..... /....- ----. /--... ---.. /-.... ---.. /-.... ..... /....- ---.. /--... --... /-.... ---.. /---.. ..... /.---- ..--- ----- /--... --... /---.. ....- /--... --... /.---- ..--- .---- /--... ---.. /-.... ---.. /-.... ..... /..... ...-- /--... ---.. /.---- ..--- ..--- /.---- ----- ...-- /..... .---- /--... ---.. /.---- ..--- ..--- /-.... ..... /..... ..--- /--... ---.. /-.... ---.. /.---- ----- --... /.---- ..--- ..--- /--... ---.. /---.. ....- /----. ----. /.---- .---- ----. /--... --... /.---- ----- -.... /--... ...-- /....- ----. /--... ---.. /.---- ----- -.... /---.. .---- /..... ----- /--... --... /-.... ---.. /----. ----. /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. .---- /.---- ..--- ----- /--... ----. /---.. ....- /---.. ----. /.---- ..--- ..--- /--... ---.. /.---- ..--- ..--- /-.... ----. /..... ...-- /--... --... /-.... ---.. /---.. ----. /.---- ..--- ----- /--... ----. /---.. ....- /-.... ..... /.---- ..--- .---- /--... ---.. /.---- ----- -.... /--... ...-- /.---- ..--- ----- /--... ---.. /-.... ---.. /---.. ..... /.---- .---- ----. /--... --... /.---- ..--- ..--- /---.. .---- /.---- ..--- ----- /--... --... /.---- ..--- ..--- /.---- ----- --... /..... ...-- /--... ---.. /-.... ---.. /----. ----. /..... ...-- /--... --... /---.. ....- /--... ...-- /.---- ..--- .---- /--... ----. /---.. ....- /.---- ----- --... /.---- .---- ----. /--... --... /-.... ---.. /---.. .---- /.---- ..--- .---- /--... --... /---.. ....- /-.... ----. /.---- ..--- .---- /--... --... /.---- ----- -.... /---.. ..... /..... ..--- /--... ---.. /.---- ..--- ..--- /----. ----. /.---- .---- ----. /--... ---.. /.---- ..--- ..--- /---.. ----. /..... .---- /--... --... /.---- ----- -.... /-.... ----. /..... ----- /--... --... /-.... ---.. /-.... ..... /..... ----- /--... --... /-.... ---.. /.---- ----- --... /.---- ..--- ----- /--... ---.. /.---- ----- -.... /-.... ----. /.---- .---- ----. /--... ---.. /---.. ....- /---.. ----. /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. ..... /..... ...-- /--... ---.. /---.. ....- /.---- ----- --... /..... ..--- /--... --... /.---- ----- -.... /---.. ..... /..... ..--- /--... ---.. /---.. ....- /-.... ----. /..... .---- /--... ---.. /-.... ---.. /--... --... /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /---.. ----. /.---- .---- ----. /--... ---.. /---.. ....- /--... --... /....- ----. /--... --... /.---- ----- -.... /--... ...-- /.---- ..--- .---- /--... ----. /-.... ---.. /-.... ----. /.---- ..--- ..--- /--... ---.. /---.. ....- /--... ...-- /.---- ..--- .---- /--... ----. /-.... ---.. /--... ...-- /..... ...-- /--... --... /-.... ---.. /.---- ----- --... /....- ----. /--... ---.. /-.... ---.. /----. ----. /..... ----- /--... ---.. /.---- ----- -.... /----. ----. /..... ...-- /--... ---.. /-.... ---.. /---.. ..... /..... ----- /--... ---.. /.---- ----- -.... /.---- ----- ...-- /.---- ..--- .---- /--... --... /-.... ---.. /--... --... /.---- ..--- .---- /--... --... /-.... ---.. /---.. ..... /..... .---- /--... ---.. /---.. ....- /--... --... /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /--... --... /..... ...-- /--... ---.. /---.. ....- /---.. ----. /.---- ..--- .---- /--... --... /.---- ----- -.... /---.. .---- /..... ...-- /--... ---.. /.---- ----- -.... /----. ----. /....- ---.. /--... ---.. /.---- ..--- ..--- /.---- ----- ...-- /.---- ..--- ..--- /--... --... /.---- ----- -.... /.---- ----- --... /.---- ..--- .---- /--... ---.. /.---- ..--- ..--- /---.. ----. /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /---.. ..... /.---- .---- ----. /--... ----. /-.... ---.. /-.... ..... /..... ----- /--... --... /-.... ---.. /--... --... /.---- ..--- ..--- /--... --... /---.. ....- /---.. ..... /.---- ..--- .---- /--... ---.. /---.. ....- /-.... ..... /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /-.... ..... /....- ----. /--... --... /---.. ....- /--... --... /....- ----. /--... --... /-.... ---.. /--... --... /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /.---- ----- --... /.---- ..--- ..--- /--... ---.. /.---- ..--- ..--- /----. ----. /.---- ..--- ----- /--... --... /.---- ----- -.... /.---- ----- --... /.---- ..--- .---- /--... ----. /---.. ....- /-.... ..... /....- ----. /--... ---.. /-.... ---.. /.---- ----- ...-- /..... ...-- /--... ----. /---.. ....- /-.... ..... /..... ..--- /--... ----. /-.... ---.. /----. ----. /..... .---- /--... --... /-.... ---.. /--... --... /.---- ..--- ..--- /--... ---.. /---.. ....- /---.. .---- /....- ---.. /--... --... /.---- ----- -.... /--... ...-- /..... ...-- /--... ----. /-.... ---.. /--... ...-- /..... ..--- /--... ----. /-.... ---.. /.---- ----- --... /..... ..--- /--... --... /---.. ....- /-.... ----. /.---- ..--- ----- /--... --... /---.. ....- /--... --... /..... ----- /--... ---.. /-.... ---.. /---.. ..... /..... ..--- /--... ---.. /---.. ....- /----. ----. /..... ...-- /--... ----. /---.. ....- /---.. ..... /..... ..--- /--... ----. /---.. ....- /---.. ----. /.---- ..--- ..--- /--... --... /.---- ..--- ..--- /-.... ----. /..... ...-- /--... --... /.---- ----- -.... /--... ...-- /....- ----. /--... --... /-.... ---.. /-.... ----. /.---- ..--- ----- /--... ---.. /---.. ....- /--... --... /..... .---- /--... --... /-.... ---.. /-.... ----. /.---- ..--- .---- /--... ----. /-.... ---.. /---.. ..... /.---- .---- ----. /--... ---.. /---.. ....- /.---- ----- --... /..... ----- /--... --... /.---- ----- -.... /---.. .---- /.---- ..--- ----- /--... ---.. /---.. ....- /-.... ----. /.---- ..--- ----- /--... --... /-.... ---.. /.---- ----- --... /.---- ..--- ----- /--... ---.. /.---- ..--- ..--- /--... ...-- /.---- ..--- .---- /--... --... /.---- ----- -.... /.---- ----- ...-- /.---- ..--- ..--- /--... --... /.---- ----- -.... /-.... ----. /....- ---.. /--... ---.. /.---- .---- ----. /.---- .---- ..--- /.---- ----- ---.. /--... ...-- /-.... ---.. /....- ---.. /.---- ----- ...-- /--... --... /.---- .---- ----. /.---- .---- ..--- /.---- ----- -.... /--... ...-- /-.... ---.. /....- ---.. /.---- ----- ...-- /--... --... /---.. ....- /-.... ..... /..... ...-- /--... ---.. /---.. ....- /-.... ----. /.---- ..--- ..--- /--... ----. /---.. ....- /-.... ..... /.---- ..--- ----- /--... --... /-.... ---.. /----. ----. /..... .---- /--... --... /---.. ....- /---.. .---- /..... ...-- /--... ----. /-.... ---.. /-.... ..... /.---- ..--- ..--- /--... ---.. /-.... ---.. /----. ----. /....- ----. /--... ----. /---.. ....- /-.... ----. /..... ..--- /--... ---.. /---.. ....- /-.... ----. /.---- ..--- ..--- /--... --... /---.. ....- /---.. ----. /..... ..--- /--... --... /.---- ..--- ..--- /-.... ----. /..... ----- /--... ----. /-.... ---.. /---.. ----. /.---- .---- ----. /--... ----. /-.... ---.. /--... ...-- /.---- ..--- ..--- /--... --... /---.. ....- /-.... ----. /.---- ..--- ----- /--... ---.. /-.... ---.. /---.. ----. /.---- .---- ----. /--... --... /.---- ----- -.... /--... --... /..... ..--- /--... ---.. /.---- ----- -.... /.---- ----- ...-- /..... .---- /--... ---.. /.---- ----- -.... /---.. ----. /.---- .---- ----. /--... ---.. /---.. ....- /---.. .---- /....- ---..
>>

Pokemon Names 以降はランダムになっているようなので、スクリプトを書く必要がある。

solve.py

from pwn import *
from gmpy2 import iroot
from base64 import b64decode
from Crypto.Util.number import long_to_bytes


MORSE_CODE_DICT = {"A": ".-", "B": "-...",
                   "C": "-.-.", "D": "-..", "E": ".",
                   "F": "..-.", "G": "--.", "H": "....",
                   "I": "..", "J": ".---", "K": "-.-",
                   "L": ".-..", "M": "--", "N": "-.",
                   "O": "---", "P": ".--.", "Q": "--.-",
                   "R": ".-.", "S": "...", "T": "-",
                   "U": "..-", "V": "...-", "W": ".--",
                   "X": "-..-", "Y": "-.--", "Z": "--..",
                   "1": ".----", "2": "..---", "3": "...--",
                   "4": "....-", "5": ".....", "6": "-....",
                   "7": "--...", "8": "---..", "9": "----.",
                   "0": "-----", ", ": "--..--", ".": ".-.-.-",
                   "?": "..--..", "/": "-..-.", "-": "-....-",
                   "(": "-.--.", ")": "-.--.-"}

MORSE_CODE_DICT_INV = {}
for key, value in MORSE_CODE_DICT.items():
    MORSE_CODE_DICT_INV[value] = key


def morse_decrypt(enc):
    enc = enc.strip().split()
    dec = ""
    for c in enc:
        dec += MORSE_CODE_DICT_INV[c]
    return dec


def rot13(enc):
    dec = ""
    for s in enc:
        if "a" <= s <= "z":
            dec += chr((ord(s) - ord("a") + 13) % 26 + ord("a"))
        elif "A" <= s <= "Z":
            dec += chr((ord(s) - ord("A") + 13) % 26 + ord("A"))
        else:
            dec += s
    return dec


io = remote("crypto.chal.csaw.io", 5001)


for i in range(6):
    io.recvuntil(b"What does this mean?\r\n")

    morse_enc = io.recvline().strip().decode()
    morse_enc = morse_enc.split("/")
    morse_dec = []

    for enc in morse_enc:
        morse_dec.append(int(morse_decrypt(enc)))

    char_dec = "".join([chr(x) for x in morse_dec])
    b64_dec = b64decode(char_dec).decode().split("\n")

    N = int(b64_dec[0].split("=")[1])
    e = int(b64_dec[1].split("=")[1])
    c = int(b64_dec[2].split("=")[1])
    rsa_dec = long_to_bytes(iroot(c, e)[0]).decode()

    m = rot(rsa_dec)
    print(m)

    io.recvuntil(b">> ")
    io.sendline(str(m).encode())

print(io.recvall().replace(b"\r\n", b"\n").decode())

$ python3 solve.py
[+] Opening connection to crypto.chal.csaw.io on port 5001: Done
Pokemon Names
Thundurus
Runerigus
Bergmite
Toxapex
Forretress
[+] Receiving all data: Done (151B)
[*] Closed connection to crypto.chal.csaw.io port 5001
You are correct!

Congrats! The GPS is activated and here's a message from your friends: flag{We're_ALrEadY_0N_0uR_waY_7HE_j0UrnEY_57aR75_70day!}

flag{We're_ALrEadY_0N_0uR_waY_7HE_j0UrnEY_57aR75_70day!}

Forgery

問題概要

forgery.py

from Crypto.Util.number import getPrime
from random import randint
from math import gcd

with open("flag.txt", 'r') as f:
    flag = f.read()

p = getPrime(1024)
g = 3
MASK = 2**1024 - 1


def gen_keys():
    x = randint(1, p-2)
    y = pow(g, x, p)
    return (x, y)


def sign(answer: str, x: int):
    while True:
        m = int(answer, 16) & MASK
        k = randint(2, p-2)
        if gcd(k, p - 1) != 1:
            continue
        r = pow(g, k, p)
        s = (m - x*r) * pow(k, -1, p-1) % (p - 1)
        if s == 0:
            continue
        return (r, s)


def verify(answer: str, r: int, s: int, y: int):
    m = int(answer, 16) & MASK
    if any([x <= 0 or x >= p-1 for x in [m, r, s]]):
        return False
    return pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p


def main():
    x, y = gen_keys()
    print(f"Server's public key (p,g,y): {p} {g} {y}")
    print("Who do you think is the tech wizard: Felicity or Cisco or both? Please answer it with your signnature (r,s)")
    print('Answer: ')
    answer = input()
    print('r: ')
    r = int(input())
    print('s: ')
    s = int(input())
    answer_bytes = bytes.fromhex(answer)

    if b'Felicity' not in answer_bytes and b'Cisco' not in answer_bytes and b'both' not in answer_bytes:
        print("Error: the answer is not valid!")
    elif verify(answer, r, s, y):
        if b'Felicity' in answer_bytes:
            print("I see you are a fan of Arrow!")
        elif b'Cisco' in answer_bytes:
            print("I see you are a fan of Flash!")
        else:
            print("Brown noser!")
        print(flag)
    else:
        print("Error: message does not match given signature")


if __name__ == "__main__":
    main()

ElGamal 署名の問題。Felicity, Cisco, both のいずれかが含まれるメッセージと、そのメッセージの署名 $(r, s)$ を送信し、verify を通過するとフラグが出力される。

$ nc crypto.chal.csaw.io 5006
Server's public key (p,g,y): 155567046227783080760824335059692257933250738797728074883857998859093724086419083128851711860984824904960884191372813513148114092354674087570472809956674063572227709119035731248561912442395071042885271015857476453918368181670559874103683910300538540879732140402124856275680409393813289718093219760823852798141 3 147618814733221126174816102582462712463977061437661641500573980890622265927857292706377333627076685226508321670026485025416575400826375935056342459092265285204165859732548358915630203228928718666305148739621152844963915681222749795138650492634566411700407615138855821199361307956734551838013998647351105215050
Who do you think is the tech wizard: Felicity or Cisco or both? Please answer it with your signnature (r,s)
Answer:

ElGamal 署名

鍵生成

• 素数 $p$ と、$1 < g < p$ を満たす原始元 $g$ を選ぶ。
• $0 < x < p-1$ となる整数の乱数 $x$ を選ぶ。
• $y \equiv g^{x} \pmod{p}$ を計算する。
• $(p, g, y)$ を公開鍵、$x$ を秘密鍵とする。

署名

• $0 < k < p-1$ かつ $p-1$ と互いに素である整数の乱数 $k$ を選ぶ。
• $r \equiv g^{k} \pmod{p}$ を計算する。
• 署名するメッセージを $m$ として、$s \equiv (m - xr) k^{-1} \pmod{p-1}$ を計算する。
• $m$ に対する署名を $(r, s)$ とする。

署名の検証

• $0 < r < p$ かつ $0 < s < p - 1$ かどうか。
• $g^m \equiv y^r r^s \pmod{p}$ が成立するかどうか。

署名の偽造

$m$ の部分をハッシュ関数を通した値ではなく、直接メッセージの値を使用している場合は存在的偽造が可能であることが知られている。存在的偽造とは、ある特定のメッセージに対して正しい署名を作成できることである。

• $1 < e, v < p - 1$ かつ $\gcd (v, p-1) = 1$ を満たす $e, v$ を選ぶ。
• $(r, s, m)$ を次のように定める。

$$\begin{align*} r &\equiv g^e y^v \pmod{p} \\ s &\equiv -r v^{-1} \pmod{p-1} \\ m &\equiv es \pmod{p-1} \end{align*}$$

解法

上記の方法を用いると、verify を通過する $(r, s, m)$ を偽造できる。しかし、これだとメッセージ中に Felicity, Cisco, both のいずれも含まれていないため、メッセージの確認を突破できない。ここで、verify の実装を見てみると、署名の検証時には $m$ の下位 1024 ビットだけが用いられていることがわかる。

def verify(answer: str, r: int, s: int, y: int):
    m = int(answer, 16) & MASK
    if any([x <= 0 or x >= p-1 for x in [m, r, s]]):
        return False
    return pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p

つまり、$m$ の下位 1024 ビットより上位のビットに何を付けたとしても verify の結果は変化しないということだ。よって、$m$ の上位ビットに条件の文字を付けて送信するとフラグが得られる。

solve.py

from random import randint
from math import gcd
from pwn import *


io = remote("crypto.chal.csaw.io", 5006)

io.recvuntil(b"Server's public key (p,g,y): ")
p, g, y = [int(c) for c in io.recvline().split()]

while True:
    e = randint(2, p-2)
    v = randint(2, p-2)
    if gcd(v, p-1) != 1:
        continue
    r = pow(g, e, p) * pow(y, v, p) % p
    s = -r * pow(v, -1, p-1) % (p-1)
    m = e * s % (p-1)
    break

ans = b"both".hex() + "{:0256x}".format(m)

io.recvuntil(b"Answer: ")
io.sendline(ans.encode())
io.recvuntil(b"r: ")
io.sendline(str(r).encode())
io.recvuntil(b"s: ")
io.sendline(str(s).encode())

print(io.recvall().replace(b"\r\n", b"\n").decode())

Brown noser!
flag{7h3_4rr0wv3r53_15_4w350M3!}

Thanks to Cyber Apocalypse 2021 for the inspiration for this challenge!

flag{7h3_4rr0wv3r53_15_4w350M3!}

RSA Pop Quiz

問題概要

RSA 暗号の問題が 4 つ出題される。

Part 1 --> This is one of the most common RSA attacks in CTFs!

N = 67173213558540492073641543527765890966555587224753677466291098492870777331723184003060460065962888786626686393121962106533892310859501206169101528002991628850003252730932214844271832631860116702935124563917050543127630878410950546641669779387162603277032730661410688220186433142718133143018333416467867431641
e = 60393570372987439508629085406063536612468805423177322998938656727023523963986927944736002128743732337579872612479590453688095513759712788930389231149640773063669658131938605394149288462759008055030939705819337138625250189795607359055198440216950405846742611042156511643169152800909501146807499261384986132629
c = 57135730441379083618128007992980086193051857549532757002346781406564809946248915530316887427675156654082699592391836332943480247333638479485700254596143145282089429425188325714486522563035311570914821876570293916313760109107083427993799739168127066045151103161794595618262264723826545244456505538802018602740

Part 2 --> Sexy primes were used to make the modulus!

N = 45591594543939036820581386282432430634955511505150874457884359540572791976098908634789254370635340951180420426249770205038465453036549929252077499917223028597156933864766645758057971022945137582325989558087380734338603952458808958686437329653639491787734717063675333378655914214268579152057338140895926822491
e = 65537
c = 1708819600505262662539757775443954762683877936532473290727105020006945400857696115070453339081578199050469415470540794379293606139546129994163640808382612444667923489770883470272982436648490695992903391654824793932805394803400703739482023640385634279438253184886814712191392363709244699867909525156210059364

Part 3 --> Looks like there is a oracle which is telling the LSB of the plaintext. That will not help you, right?

N = 119967010283289788495307928622884560975019659399617588748758613702865895940176342396585544852010431284888684089351311911419768213106289925329379924001561062330290004928506816062845538037533681770367357014153786162044286474168874314253601262348720302613087949506580594474971096294459190921576707577135134451971
e = 65537
c = 113430202071360145253554866665690043228536147966363500290641851841561705147909617166676852087110453496292493709911088618723290290006238675189405847313274109464950497883381586236898876663235623893789692557209370568811763235622588549710679387357910676079666800893215731542859285518232292029077845502730413679506

What would you like to decrypt? (please respond with an integer)

Part 4 --> Oops, looks like I leaked part of the private key. Hope that doesn't come back to bite me!

N = 86648014540331487681062642023243371195442397576482982120882252993132815842542042456131590629716083804653155119009096504462874610325649987572099281772061886319221091074978000497306553610184658100375978768225971354065242171171459592235657459007110209320918278619357219126080722322890456059981805116671726244113
e = 17
d0 = 8398206162947662953564884699232587425437200618125776050913162979594234668931984756609605679934816896267380868050359772603353343034508020706645380909686449
c = 29685418022901513184004769440274756563309256984437039284220168954702073660775312444275225912934259530974098938120626042264586306095856308975928502679555616685512501853969275469449279011014708226209093032983104323589709325566551359222175518862166073360005883508506355407217553715535515323715073542538482337801
d0bits = 512
nBits = 1024

1 問目 － Wiener's Attack

$e$ が明らかに大きいので Wiener's Attack で $d$ を求めることができる。

2 問目 － フェルマー法

問題文から素因数分解ができる $N$ だと考えられる。様々なアルゴリズムを試してみると、フェルマー法を用いて素因数分解ができた^[1]。フェルマー法は 2 つの素数の差が小さいときに有効なアルゴリズムである。

3 問目 － LSB Decryption Oracle Attack

復号結果の LSB を教えてくれるので、LSB Decryption Oracle Attack を用いて $m$ を求めることができる。

4 問目 － d の下位ビットが判明している場合

$e$ が小さく、$d$ の下位ビットがある程度判明しているときは、$p$ の問題に落とし込んで解くことができる。Recovering cryptographic keys from partial information, by example にこの手の話がよくまとまっている。

スクリプト

拝借元はソースコード中に記載している。4 問目だけは Sage で解いたので、スクリプトが別になっている。

solve.py

from fractions import Fraction
from math import ceil
import gmpy2
from Crypto.Util.number import long_to_bytes
from pwn import *
from sympy import sqrt
from sympy.ntheory.primetest import is_square


io = remote("crypto.chal.csaw.io", 5008)

# ===========================================================
# Wiener's Attack
# https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/
# ===========================================================

io.info("Part 1 --> This is one of the most common RSA attacks in CTFs!")
io.recvuntil(b"Part 1 --> This is one of the most common RSA attacks in CTFs!\r\n\r\n")
N = int(io.recvline().split(b"=")[1])
e = int(io.recvline().split(b"=")[1])
c = int(io.recvline().split(b"=")[1])


def rational_to_quotients(x, y):
    a = x // y
    quotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        quotients.append(a)
    return quotients


def convergents_from_quotients(quotients):
    convergents = [(quotients[0], 1)]
    for i in range(2, len(quotients) + 1):
        quotients_partion = quotients[0:i]
        denom = quotients_partion[-1]  # 分母
        num = 1
        for _ in range(-2, -len(quotients_partion), -1):
            num, denom = denom, quotients_partion[_] * denom + num
        num += denom * quotients_partion[0]
        convergents.append((num, denom))
    return convergents


def WienerAttack(e, n):
    quotients = rational_to_quotients(e, n)
    convergents = convergents_from_quotients(quotients)
    for (k, d) in convergents:
        if k and not (e * d - 1) % k:
            phi = (e * d - 1) // k
            # check if (x^2 - coef * x + n = 0) has integer roots
            coef = n - phi + 1
            delta = coef * coef - 4 * n
            if delta > 0 and gmpy2.iroot(delta, 2)[1] == True:
                return d


d = WienerAttack(e, N)
m = pow(c, d, N)
print(long_to_bytes(m).decode())
# -> Wiener wiener chicken dinner

io.recvuntil(b"What is the plaintext?")
io.sendline(long_to_bytes(m))


# ===========================================================
# Fermat's factorization method
# ===========================================================

io.info("Part 2 --> Sexy primes were used to make the modulus!")
io.recvuntil(b"Part 2 --> Sexy primes were used to make the modulus!\r\n\r\n")

N = int(io.recvline().split(b"=")[1])
e = int(io.recvline().split(b"=")[1])
c = int(io.recvline().split(b"=")[1])


def fermat(n):
    a = int(sqrt(n))
    b = (a*a) - n
    while not is_square(b):
        a += 1
        b = (a*a) - n
    else:
        p = int(a - sqrt(b))
        q = n//p
        if p * q == n:
            return p, q
        else:
            return


p, q = fermat(N)
phi = (p-1) * (q-1)
d = pow(e, -1, phi)

m = pow(c, d, N)
print(long_to_bytes(m).decode())
# -> Who came up with this math term anyway?

io.recvuntil(b"What is the plaintext?")
io.sendline(long_to_bytes(m))


# ===========================================================
# LSB decryption oracle attack
# https://kimiyuki.net/blog/2017/06/24/lsb-leak-attack/
# ===========================================================

io.info("Part 3 --> Looks like there is a oracle which is telling the LSB of the plaintext. That will not help you, right?")
io.recvuntil(b"Part 3 --> Looks like there is a oracle which is telling the LSB of the plaintext. That will not help you, right?\r\n\r\n")

N = int(io.recvline().split(b"=")[1])
e = int(io.recvline().split(b"=")[1])
c = int(io.recvline().split(b"=")[1])


def oracle(c):
    io.recvuntil(b"What would you like to decrypt? (please respond with an integer)")
    io.sendline(str(c).encode())
    io.recvuntil(b"The oracle responds with: ")
    ret = int(io.recvline())
    io.recvuntil(b"Would you like to continue? (yes/no)")
    return ret


def lsb_decryption_oracle(e, n, c, oracle):
    l, r = 0, n  # [l, r)
    i = 1
    while r - l >= 1:
        m = Fraction(l + r, 2)
        if oracle(gmpy2.powmod(2, i * e, n) * c % n):
            l = m
        else:
            r = m
        i += 1
        io.sendline(b"yes")
    # to finish decryption
    oracle(1)
    io.sendline(b"no")
    return ceil(l)


m = lsb_decryption_oracle(e, N, c, oracle)
print(long_to_bytes(m).decode())
# -> Totally did not mean to put an oracle there

io.recvuntil(b"What is the plaintext?")
io.sendline(long_to_bytes(m))

io.info("Part 4 --> Oops, looks like I leaked part of the private key. Hope that doesn't come back to bite me!")
io.recvuntil(b"Part 4 --> Oops, looks like I leaked part of the private key. Hope that doesn't come back to bite me!\r\n\r\n")

N = int(io.recvline().split(b"=")[1])
e = int(io.recvline().split(b"=")[1])
d0 = int(io.recvline().split(b"=")[1])
c = int(io.recvline().split(b"=")[1])
d0bits = int(io.recvline().split(b"=")[1])
nBits = int(io.recvline().split(b"=")[1])

"""
print("N =", N)
print("e =", e)
print("d0 =", d0)
print("c =", c)
print("d0bits =", d0bits)
print("nBits =", nBits)
"""

io.recvuntil(b"What is the plaintext?")
# partial_d.sage -> I'll be careful next time to not leak the key
print("I'll be careful next time to not leak the key")
io.sendline(b"I'll be careful next time to not leak the key")

io.recvuntil(b"Success!\r\n\r\n")
print(io.recvall().strip().decode())

solve.sage

from Crypto.Util.number import long_to_bytes


# ===========================================================
# Partial d
# https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/
# ===========================================================


def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4)  # find root < 2^(nbits//2-kbits) with factor >= n^0.4
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

    
def find_p(d0, kbits, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p and p != 1:
                return p


N = 97802602465609710269360509577250323967413078636576277283356400011622378655632524440511750115247957084976946315273475106389586743972724298300689067400489393006339862181652879572603027259740469746663485770153776740480820177104233853864401135460677627349064494792014476103399954879269740254569328523354700527161
e = 17
d0 = 6749627555111846422092675693162811007324834663839898987947435659477797142432110928896521813961861689410987088930670136225426242905277488664811752831843313
c = 44515767849211788946216923955345749543647146672602555225100861878255327267298561458459170190998486656427772887173137729767189845180628137258970180810470865698409682728251961735860692310811583042689402004495917566353285583348618344617845452736572787119661933444445211929503623093565937313629615812757292205720
d0bits = 512
nBits = 1024

p = int(find_p(d0, d0bits, e, N))
q = N // int(p)
d = inverse_mod(e, (p-1)*(q-1))
m = pow(c, d, N)
print(long_to_bytes(m).decode())

$ python3 solve.py
[+] Opening connection to crypto.chal.csaw.io on port 5008: Done
[*] Part 1 --> This is one of the most common RSA attacks in CTFs!
Wiener wiener chicken dinner
[*] Part 2 --> Sexy primes were used to make the modulus!
Who came up with this math term anyway?
[*] Part 3 --> Looks like there is a oracle which is telling the LSB of the plaintext. That will not help you, right?
Totally did not mean to put an oracle there
[*] Part 4 --> Oops, looks like I leaked part of the private key. Hope that doesn't come back to bite me!
I'll be careful next time to not leak the key
[+] Receiving all data: Done (139B)
[*] Closed connection to crypto.chal.csaw.io port 5008
Congrats on passing the RSA Pop Quiz! Here is your flag: flag{l00K5_L1K3_y0u_H4v3_p4223D_7h3_D1ff1Cul7_r54_p0p_Kw12_w17H_fLy1N9_C0L0r2}

flag{l00K5_L1K3_y0u_H4v3_p4223D_7h3_D1ff1Cul7_r54_p0p_Kw12_w17H_fLy1N9_C0L0r2}

ECC Pop Quiz

問題概要

楕円曲線上の離散対数問題に関する問題が 3 つ出題される。

The answer will be a randomly generated solution and hence not an obvious message.
Part 1 --> Are you smart enough to crack this?

The curve parameters are:
p = 69812813449090964632854434431592687676803646800140499125988724233950507730669
a = 19492474903458155432161241956021442384134985636083028865114387784647597974452
b = 55065051885403189012801817415302478564611972563301878306020072247714162567230

P1: (8913210855978695923905831752997460819335024750977269030595185060384384998755 : 12670627014117685378303416856894379655905998792024382405118602497267353713983 : 1)
P2: (6656544267819097743104603652275547560999318388571696573656623904722601924046 : 13274819657587383902233182446100764606246906159997848626736156998762719420336 : 1)
P2 = secret * P1

What is the value of 'secret'?:

Part 2 --> Can you move on to the next question?

The curve parameters are:
p = 995455106847514457951754472432481563515512443
a = 995455106847514457951754472432481563515512442
b = 0

P1: (192646668546558808617097502092298744210223834 : 945936498176072947849258136389032024217379062 : 1)
P2: (168324312587559674706416429926065260825395210 : 774248784228652251562280158513886296849620364 : 1)
P2 = secret * P1

What is the value of 'secret'?:

Part 3 --> This singular question remains between you and completion!

The curve parameters are:
p = 81853705587553705622255255664324085964421034795784318079919027041530181693803
a = ???
b = ???

P1: (24630478192914099519996075763075273919228470641984309873963519120161936808678, 50427872460241832873455988124650033148315493240909138872340959270475472423590)
P2: (48727315299486076618045377577667798668922075379008824010489945675103538924107, 8848164321800547365769773095376033150344078535319827490917385365595155188334)
P2 = secret * P1

What is the value of 'secret'?:

1 問目 － Smart's Attack

有限体 $\mathbb{F}_p$ での楕円曲線 $E$ の位数 $\# E(\mathbb{F}_p)$ が $p$ であるような曲線を Anomalous 楕円曲線という。この場合、Smart's Attack で離散対数問題を解くことができる。

• Smart, N. The Discrete Logarithm Problem on Elliptic Curves of Trace One. J. Cryptology 12, 193–196 (1999). https://doi.org/10.1007/s001459900052

from pwn import *


io = remote("crypto.chal.csaw.io", 5002)


# ============================================================================================
# Smart's Attack
# https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp
# ============================================================================================

def SmartAttack(P, Q, p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p)*p for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)


io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())
a = int(io.recvline().split(b"=")[1].strip())
b = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b":").split()[0])
p1y = int(io.recvuntil(b":").split()[0])
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b":").split()[0])
p2y = int(io.recvuntil(b":").split()[0])

E = EllipticCurve(GF(p), [a, b])
P1 = E(p1x, p1y)
P2 = E(p2x, p2y)

assert E.order() == p

secret = SmartAttack(P1, P2, p)
print(secret)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(secret).encode())

2 問目 － MOV Attack (or discrete_log)

埋め込み次数と呼ばれる、$p^k - 1$ が $\# E(\mathbb{F}_p)$ で割り切れる最小の $k$ が非常に小さいとき、MOV Attack で離散対数問題を解くことができる。この問題では $k=2$ となっているようだ。

そもそも $\# E(\mathbb{F}_p)$ が小さいので Sage の discrete_log で一撃ではあるが、問題文の内容と $E$ が supersingular であることから、 MOV Attack を想定していそうな気がした。

# ============================================================================================
# MOV Attack
# https://sectt.github.io/writeups/Volga20/crypto_keygreed/sol.sage
# ============================================================================================

def mov_attack(E, P, xP, a, b, p):
    order = E.order()
    k = 1
    while (p^k - 1) % order:
        k += 1

    Fy = GF(p^k, 'y')
    Ee = EllipticCurve(Fy, [a, b])

    Pe = Ee(P)
    xPe = Ee(xP)

    R = Ee.random_point()
    m = R.order()
    d = gcd(m, P.order())
    Q = (m//d)*R

    assert P.order()/Q.order() in ZZ
    assert P.order() == Q.order()

    n = P.order()
    alpha = Pe.weil_pairing(Q, n)
    beta = xPe.weil_pairing(Q, n)

    dd = beta.log(alpha)
    return dd


io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())
a = int(io.recvline().split(b"=")[1].strip())
b = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b":").split()[0])
p1y = int(io.recvuntil(b":").split()[0])
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b":").split()[0])
p2y = int(io.recvuntil(b":").split()[0])

E = EllipticCurve(GF(p), [a, b])

P1 = E(p1x, p1y)
P2 = E(p2x, p2y)

secret = mov_attack(E, P1, P2, a, b, p)
print(secret)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(secret).encode())

3 問目 － Singular Curve (node)

まず、P1 と P2 から曲線のパラメータ $a$, $b$ を求める。

$$\left\{ \, \begin{align*} y_1^2 &\equiv x_1^3 + a x_1 + b \pmod{p}\\ y_2^2 &\equiv x_2^3 + a x_2 + b \pmod{p}\\ \end{align*} \right.$$

$$\begin{bmatrix*} x_1 & 1 \\ x_2 & 1 \end{bmatrix*} \begin{bmatrix*} a \\ b \end{bmatrix*} \equiv \begin{bmatrix*} y_1^2 - x_1 ^ 3 \\ y_2^2 - x_2 ^ 3 \end{bmatrix*}$$

とすると、Sage の solve_right で $a$, $b$ を計算できる。

そして、$4a^3 + 27 b^2 \equiv 0 \pmod{p}$ であることから、特異点を持つ Singular 曲線だということが分かる。特異点には cusp と node の 2 種類があり、この問題では node となっている。

• cusp : $y^2 = (x - \alpha)^3$
• node : $y^2 = (x - \alpha)^2 (x - \beta)$

$(\alpha, 0)$ を特異点に持つとき、$(x, y) \mapsto (x - \alpha, y)$ とすると $(0, 0)$ が特異点となり、その曲線は次の形で表される。

$$y^2 = x^2 (x - s)$$

この形になると、$s$ の square root を計算し、次のように移すと簡単に離散対数問題が解けるようになる。

$$(x, y) \mapsto \frac{y + x \sqrt{s}}{y - x \sqrt{s}}$$

# ============================================================================================
# Singular Curve (node)
# https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp
# ============================================================================================

set_verbose(-1)

io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b",").replace(b",", b""))
p1y = int(io.recvuntil(b")").replace(b")", b""))
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b",").replace(b",", b""))
p2y = int(io.recvuntil(b")").replace(b")", b""))

M = matrix(GF(p), [[p1x, 1], [p2x, 1]])
a, b = M.solve_right(vector([p1y^2 - p1x^3, p2y^2 - p2x^3]))
# check a, b
assert (p1x ** 3 + a * p1x + b) % p == p1y ** 2 % p
assert (p2x ** 3 + a * p2x + b) % p == p2y ** 2 % p
# check singular
assert 4*a^3 + 27*b^2 == 0

# define singular curve
F = GF(p)
K.<x,y> = F[]
f = x^3 + a*x + b
C = Curve(f - y^2)
singular_point = C.singular_points()[0]

# (0, 0) -> singular
f_ = f.subs(x=x+singular_point[0])

# (x - s) x^2 -> node
print(f_.factor())

# shift P1, P2
P1 = (p1x - singular_point[0], p1y)
P2 = (p2x - singular_point[0], p2y)

s = f_.factor()[0][0] - x
t = F(s).square_root()

# mapping point
u = (P1[1] + t*P1[0]) / (P1[1] - t*P1[0])
v = (P2[1] + t*P2[0]) / (P2[1] - t*P2[0])

n = discrete_log(v, u)
print(n)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(n).encode())

io.recvuntil(b"Success!\r\n\r\n")
print(io.recvall().strip().decode())

スクリプト

最終的なスクリプトは以下の通りである。

solve.sage

from pwn import *


io = remote("crypto.chal.csaw.io", 5002)


# ============================================================================================
# SmartAttack
# https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp
# ============================================================================================

def SmartAttack(P, Q, p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p)*p for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)


io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())
a = int(io.recvline().split(b"=")[1].strip())
b = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b":").split()[0])
p1y = int(io.recvuntil(b":").split()[0])
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b":").split()[0])
p2y = int(io.recvuntil(b":").split()[0])

E = EllipticCurve(GF(p), [a, b])
P1 = E(p1x, p1y)
P2 = E(p2x, p2y)

assert E.order() == p

secret = SmartAttack(P1, P2, p)
print(secret)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(secret).encode())


# ============================================================================================
# MOV Attack
# https://sectt.github.io/writeups/Volga20/crypto_keygreed/sol.sage
# ============================================================================================

def mov_attack(E, P, xP, a, b, p):
    order = E.order()
    k = 1
    while (p^k - 1) % order:
        k += 1

    Fy = GF(p^k, 'y')
    Ee = EllipticCurve(Fy, [a, b])

    Pe = Ee(P)
    xPe = Ee(xP)

    R = Ee.random_point()
    m = R.order()
    d = gcd(m, P.order())
    Q = (m//d)*R

    assert P.order()/Q.order() in ZZ
    assert P.order() == Q.order()

    n = P.order()
    alpha = Pe.weil_pairing(Q, n)
    beta = xPe.weil_pairing(Q, n)

    dd = beta.log(alpha)
    return dd


io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())
a = int(io.recvline().split(b"=")[1].strip())
b = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b":").split()[0])
p1y = int(io.recvuntil(b":").split()[0])
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b":").split()[0])
p2y = int(io.recvuntil(b":").split()[0])

E = EllipticCurve(GF(p), [a, b])

P1 = E(p1x, p1y)
P2 = E(p2x, p2y)

secret = mov_attack(E, P1, P2, a, b, p)
print(secret)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(secret).encode())

# ============================================================================================
# Singular Curve (node)
# https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp
# ============================================================================================

set_verbose(-1)

io.recvuntil(b"The curve parameters are:\r\n")
p = int(io.recvline().split(b"=")[1].strip())

io.recvuntil(b"P1: (")
p1x = int(io.recvuntil(b",").replace(b",", b""))
p1y = int(io.recvuntil(b")").replace(b")", b""))
io.recvuntil(b"P2: (")
p2x = int(io.recvuntil(b",").replace(b",", b""))
p2y = int(io.recvuntil(b")").replace(b")", b""))

M = matrix(GF(p), [[p1x, 1], [p2x, 1]])
a, b = M.solve_right(vector([p1y^2 - p1x^3, p2y^2 - p2x^3]))
# check a, b
assert (p1x ** 3 + a * p1x + b) % p == p1y ** 2 % p
assert (p2x ** 3 + a * p2x + b) % p == p2y ** 2 % p
# check singular
assert 4*a^3 + 27*b^2 == 0

# define singular curve
F = GF(p)
K.<x,y> = F[]
f = x^3 + a*x + b
C = Curve(f - y^2)
singular_point = C.singular_points()[0]

# (0, 0) -> singular
f_ = f.subs(x=x+singular_point[0])

# (x - s) x^2 -> node
print(f_.factor())

# shift P1, P2
P1 = (p1x - singular_point[0], p1y)
P2 = (p2x - singular_point[0], p2y)

s = f_.factor()[0][0] - x
t = F(s).square_root()

# mapping point
u = (P1[1] + t*P1[0]) / (P1[1] - t*P1[0])
v = (P2[1] + t*P2[0]) / (P2[1] - t*P2[0])

n = discrete_log(v, u)
print(n)

io.recvuntil(b"What is the value of 'secret'?:")
io.sendline(str(n).encode())

io.recvuntil(b"Success!\r\n\r\n")
print(io.recvall().strip().decode())

[+] Opening connection to crypto.chal.csaw.io on port 5002: Done
39265935355144641964000542481876729479308592441223572137686882358743051916992
781409392
(x + 3) * x^2
904175
[+] Receiving all data: Done (132B)
[*] Closed connection to crypto.chal.csaw.io port 5002
Congrats on passing the ECC Pop Quiz! Here is your flag: flag{4Ll_0f_tH353_4tT4cK5_R3lY_0N_51mPl1FY1n9_th3_D15cr3t3_l09_pr08l3m}

flag{4Ll_0f_tH353_4tT4cK5_R3lY_0N_51mPl1FY1n9_th3_D15cr3t3_l09_pr08l3m}

脚注

1. sexy prime は差が 6 の素数の組なので、当たり前ではある。