こんにちは。公式writeupっぽいやつは早く出しすぎると参加者が「じゃあ自分はwriteup書かなくてもよいか……」と思ってしまうのでしばらく経ってから出したほうが良いと思っているので寝かせていました。まだ書いていない人でこれを読んでいる人はぜひ運営へのねぎらいだと思ってwriteup書いてください。
你好。 如果你过早地把官方写的东西放出来，参与者会想，“好吧，我不必写写……”，所以我觉得过一会儿再写出来会更好，所以我把它放在床上。 如果您还没有写过并且正在阅读本文，请写下来作为对管理层的感谢。
以下は解説というよりは感想です。出題した問題はGitHubで公開してます。solverも入っているので詳しい解き方を知りたい人はそちらを見てください（あと解いた人のwriteupを読んだりしてください）。
以下更多的是印象而不是解释。 这些问题可在 GitHub 上找到。 它还包括一个求解器，所以如果你想知道如何详细解决它，请看一下那里（并阅读解决它的人的文章）。
- [crypto/warmup] simple signature (88 solves)
[加密/预热] 简单签名（88 解决） - [rev] Cake Puzzle (56 solves)
[修订版] 蛋糕拼图 （56 solves） - [crypto] janken vs yoshiking 2(43 solves)
[加密] Janken vs Yoshiking 2（43 解决） - [crypto/pwn] decryptyou (13 solves)
[crypto/pwn] 解密你 （13 solves） - [crypto] Iron Door (8 solves)
[加密] 铁门 （8 solves） - 感想
[crypto/warmup] simple signature (88 solves)
[加密/预热] 简单签名（88 解决）
なんか昔つくった問題なのでよく憶えていません……。昔なんかいい問題を作ろうと思ってがちゃがちゃやっていたときにできた何やっても解ける問題を拾い上げてきました。
我不太记得了，因为这是我很久以前编造的问题。 过去，当我试图提出一个好问题时，我捡到了一个无论我做什么都可以解决的问题。
kanonさんがwriteupにいいことを書いてくれてるんですが、”基本的に、公開鍵と秘密鍵は何か数学的な関連性が必要であるから解けないわけで、今回はx,u�,�が公開鍵にしか使われていないため、なんでもおｋ”です。適当に値を決め打ちしてそれで辻褄が合うようにすると解ける。
Kanon在writeup上写了一些不错的话，“基本上，公钥和私钥是无法解决的，因为它们需要某种数学关系，在这种情况下，只用于公钥， x,u�,� 所以它就是一切。 可以通过随机设置一个值并键入它以使其匹配来解决。
一見難しそうに見えて普通に数学やると解けるのでwarmupです。
乍一看，这看起来很困难，但可以通过做正常的数学来解决，所以它是热身。
[rev] Cake Puzzle (56 solves)
[修订版] 蛋糕拼图 （56 solves）
これは非常にシンプルな15パズルで、さくっとreversingしてさくっとソルバ拾ってきて解くだけです。
这是一个非常简单的 15 个谜题，您只需要快速反转，拿起求解器并解决它。
reversing何もわからないのに無理やり何か作ろうとして結局このあたりに落ち着きました。特に面白いことはないので、出したことは多少以上に後悔してます。
逆转：我什么都不知道，但我试图强迫自己做点什么，我最终在这个领域安顿下来。 它没有什么特别有趣的地方，所以我后悔把它放出来。
[crypto] janken vs yoshiking 2(43 solves)
[加密] Janken vs Yoshiking 2（43 解决）
janken vsシリーズ、または vs yoshiking シリーズです。これまでの作品はzer0pts CTF 2021に出題したjanken vs yoshiking, SECCON CTF 2022 Qualsに出題したjanken vs kurenaifです。jankenは本当に便利な題材で、手の種類が3通りしかないのでweakなパターンを作りやすいですよね。
Janken VS 系列，或 VS Yoshiking 系列。 之前的作品是 zer0pts CTF 2021 中的 janken vs yoshiking 和 SECCON CTF 2022 Quals 中的 janken vs kurenaif。 Janken 是一个非常有用的主题，由于只有三种类型的动作，因此很容易创建弱模式。
さて、今回はyoshikingはFp��上の5×5のランダムな行列M�に対しMr��を計算してくれてrmod3�mod3がyoshikingの手です。p�はsmoothですが一般線形群GL5(Fp)��5(��)では特に嬉しくないです*1。どうにかして離散対数問題を解いてr�を求めたいですね。
好吧，这一次 Yoshiking rmod3�mod3 计算 Mr�� Fp�� 了上面的 5×5 随机矩阵 M� 。 p� 很平滑，但我对一般线性群 *1 不是特别满意 GL5(Fp)��5(��) 。 我想以某种方式解决 r� 离散对数问题。
そこで一般にdet(Ar)=det(A)rdet(��)=det(�)�だねということを思い出してdet(M),det(Mr)=det(M)rdet(�),det(��)=det(�)�を取るとdeterminantはFp��上の計算ですから、このdiscrete logはPohlig-Hellmanで楽に解けるのでじゃんけん勝ち放題という問題でした。
所以，一般来说 det(Ar)=det(A)rdet(��)=det(�)� ，如果你 det(M),det(Mr)=det(M)rdet(�),det(��)=det(�)� 采用行列式计算 Fp�� ，这个离散的对数可以很容易地被 Pohlig-Hellman 求解，所以这是一个你可以在石头剪刀布中随心所欲地赢得的问题。
行列の冪乗が出てきたときに行列式を考えたりジョルダン標準形を考えるのは典型だと思っているのでもうひと工夫しても良かったなと思います。あと、janken vs yoshikingを作問したときもp-1が3を位数に持っているとか持っていないとかで非想定の解法を作ったのに今回もそういう解き方のことを失念してたのも良くないですね*2。憶えてたらp�はランダムに生成してたと思います。まあでもpがsmoothなことでmod pで考えたくなるという誘導にはなったので別に良いか。良いような気もします
我认为当矩阵的幂出来时，通常会考虑行列式或乔丹标准形式，所以我认为如果能多一点独创性就好了。 另外，当我提出 Janken vs Yoshiking 问题时，我根据 P-1 的订单号中是否有 3 提出了一个不起眼的解决方案，但这次我也忘记了这样的解决方案并不好*2。 如果我 p� 没记错的话，我认为它是随机生成的。 好吧，没关系，因为 P 是流畅的这一事实让我想用 mod P 来思考。 我觉得很好
[crypto/pwn] decryptyou (13 solves)
[crypto/pwn] 解密你 （13 solves）
zer0pts CTF 2022に(ptr-yudaiが)出題したsignmeという問題は crypto + pwnの問題で、RSA-CRTによる署名時に一時変数を破壊できるので素因数分解できて……という問題でした。今回出題したdecryptyouはcrypto + pwnの問題でRSA-CRTによる復号をしてくれるのですが、pwn要素によって復号時に一時変数u=pmodq�=�mod�を破壊できます。
zer0pts CTF 2022 中的 signme 问题（由 ptr-yudai 解决）是一个加密 + pwn 问题，可以分解，因为在使用 RSA-CRT 签名时可以销毁临时变量。 这就是问题所在。 这次出现的 decryptyou 是一个 crypto + pwn 问题，使用 RSA-CRT 解密，但 pwn 元素在解密过程中会破坏 u=pmodq�=�mod� 临时变量。
RSA-CRTにおける復号ではmp=cdpmodp=mmodp,mq=cdqmodq=mmodq��=���mod�=�mod�,��=���mod�=�mod�としたあとgarnerのアルゴリズムでm=((mp−mq)umodp)+mqmodn�=((��−��)�mod�)+��mod�としてm�を復元します。このときu�が壊れているとして
在 RSA-CRT 中，解码完成， mp=cdpmodp=mmodp,mq=cdqmodq=mmodq��=���mod�=�mod�,��=���mod�=�mod� 然后 m� 按照 garner 算法进行重建 m=((mp−mq)umodp)+mqmodn�=((��−��)�mod�)+��mod� 。 u� 假设此时已损坏
- m≤p�≤�であればmp��とmq��は同じ値になるのでmp−mq=0��−��=0となり、garnerのアルゴリズムの(mp−mq)umodp(��−��)�mod�の部分は0なのでu�が壊れていてもu�の影響はm�に届かないので復号に成功します
m≤p�≤� mp�� 如果 的值 mq�� 与 相同，则为 ，并且 Garner 算法的部分为 0，因此即使 u� 被破解 mp−mq=0��−��=0 ， (mp−mq)umodp(��−��)�mod� 效果 m� 也达不到 ， u� 所以解密成功 - m>p�>�であればu�が壊れているので復号に失敗します
m>p�>� 如果 u� 已损坏，解密将失败
というオラクルが手に入るので、復号に成功するかをみつつ二分探索するとp�がわかるという解法を想定していました。しかしこんな解き方をしている人は誰もいなくて、u�が壊れているときその復号結果はmodpmod�ではm�かつmodqmod�では非m�となるような値m′�′なので、m−m′�−�′がn�でないp�の倍数になり得る*3ということを利用して解かれているようでした。
既然你可以得到预言机，我假设解决方案是找出你是否搜索了两分钟，同时查看 p� 解密是否成功。 但是，没有人以这种方式解决它，并且当被破坏时，解码结果是一个值，例如 is 和 modqmod� u� non modpmod� m� ，因此 m−m′�−�′ 可以是 * n� m� m′�′ 的倍数 p� 它似乎通过使用数字 3 来解决。
……これはsignmeの解法とほとんど一緒です。自分たちの過去問と同じ問題を出してしまった……が、ばれてないのでセーフ！！！！！*4
…… 这与 signme 解决方案几乎相同。 我们给了他们和过去一样的问题…… 但它是安全的，因为它没有暴露!!! *4
違う問題！（同じ問題だった……） 不同的问题！ （同样的问题…
[crypto] Iron Door (8 solves)
[加密] 铁门 （8 solves）
今回のボス問題です。唯一lunaticタグがついていたpwnのbofwowは22 solvesあることを考えるとこの問題にlunaticがついてないのはおかしい。
这是这次的老板问题。 考虑到唯一带有疯子标签的 PWN bofwow 有 22 个解决方案，这个问题没有疯子是很奇怪的。
この問題については簡単に説明するのが難しいのですがCakeCTF 2022に出題したRock Doorの改題で、以前はDSAのr,k�,�が小さいのでLLLで解ける……という問題でした。今回はr�は小さく、k�は大きい、ただしk−1modq�−1mod�は小さいという問題設定になっています。
这个问题很难简单解释，但随着 CakeCTF 2022 中出现的 Rock Door 的更名，它曾经是 DSA，因为它很小，所以 r,k�,� 可以用 LLL 解决…… 这就是问题所在。 r� 在这种情况下，很小，很大， k� 但 k−1modq�−1mod� 很小。
とりあえずsjrik−1i−sirjk−1j������−1−������−1を考えると、両方の項にxrik−1irjk−1j�����−1����−1が登場するのでx�を消去でき、剰余の方に比べて小さい値になることが期待できるので、係数rik−1i,rjk−1j����−1,����−1をLLLで求めることができます。
目前，我们可以 sjrik−1i−sirjk−1j������−1−������−1 消除 x� 因为两个项的 xrik−1irjk−1j�����−1����−1 出现，我们可以预期该值将小于余数，因此 rik−1i,rjk−1j����−1,����−1 我们可以用 LLL 找到系数。
続いて、si≡zik−1i+xrik−1imodq��≡����−1+�����−1mod�という式はsi,zi,rik−1i��,��,����−1既知でx�は未知だがすべての式で共通、k−1i��−1が式ごとに異なる比較的小さな未知数なのでこれは典型的なHidden Number Problemのインスタンスです。
随后，是隐藏数问题的典型实例，因为隐藏数是一个相对较小的未知数，它是已知的，但对所有表达式都是通用的， k−1i��−1 但 si≡zik−1i+xrik−1imodq��≡����−1+�����−1mod� si,zi,rik−1i��,��,����−1 x� 因表达式而异。
したがってこれを解けばx�が求められる、という問題でした。2段階のLLLが登場してこれは難しいぞと思いましたが、実際にはただLLLなので難しいだけで、解かれた方は大体二段階目のLLLはやらずにrik−1i����−1を素因数分解するという方針で解かれていたようでした
因此，这是一个问题，如果你解决了这个问题， x� 你将被要求。 我以为当两阶段LLL出现时，这会很困难，但实际上它只是因为它只是LLL，而解决它的人似乎是用分解的策略来解决的， rik−1i����−1 而不做第二阶段LLL
感想
毎年「このCTFで持ちネタ全部尽きたぁ。終わりだぁ……」と思っているけど、実際にやってみると簡単な問題もそこそこ難しい問題も作れているような気がします。……が、これは罠で、よく見るとjanken vs yoshiking 2もdecryptyouもIron Doorも過去の問題の焼き直しです。もう本当にだめ
每年，我都会想，“这个 CTF 的材料已经用完了，结束了……”，但当我真正尝试它时，我觉得我能够创建简单和中等难度的问题。 …… 但这是一个陷阱，如果你仔细观察，janken vs yoshiking 2、decryptyou 和 Iron Door 都是过去问题的重演。 我真的做不到了
インプットを怠った結果アウトプットが枯渇している状態だと思うので、来年のCakeCTF開催のためにもいろいろなCTFに参加していきたいですね（口だけオバケ）。
我认为由于忽视了投入，产出正在耗尽，所以我想参加明年 CakeCTF 的各种 CTF（只是一口）。
あとReversingとWebは本当に作れないので協力してくれる人を募集しています
另外，我无法真正创建 Reversing 和 Web，所以我正在寻找帮助我的人
それではさようなら 再见
原文始发于Hatena Blog：CakeCTF 2023 作問感想
相关文章
