InterKosenCTF 2020 ciphertexts writeup
皆さん、こんにちは！ Ken.Sです！
丁度本日9/6の22時に終わったInterKosenCTFの問題の一つのciphertextsのwriteupを書いていきます！
InterKosenCTF
問題概要
問題名：ciphertexts
分野：crypto warmup
得点：201pt (33 solves)
問題文
Since there are two ciphertexts, it is easy to solve, isn't it?
問題ファイル
- main.py
- output.txt
(writeupも掲載しています。)
解法
本番ではtar.gzファイルで渡されて、解凍してみると上の二つのファイルが手に入ります。
main.pyを実行したものがoutput.txtに出力されています。
main.pyについて、512bitの素数p,q,rの内、n1はp,qの積、n2はp,q,rの積となっています。次に、20bitの素数e1とそのe1の次に小さい素数e2を格納し、それらを公開鍵としてbytes_to_longしたflagを基に暗号文c1,c2を形成します。最後にn,e,cを出力します。(某企業名みたい)
n2がq,rの積だったら、n1とn2の最小公倍数からqを求めて、そのqでn1,n2を割ればp,rは得られるなぁと思いつつ、p,qを求める方法を探しましたが見つからず断念。同じ平文を暗号化しているのでここになにかヒントがあるのだろうと、いつものslideshareを閲覧。
その8にあるcommon modulus attackがそれっぽい！(最初はその次のページの方法かなとも思ったけど、e個も暗号文を与えられてないので諦め)
けど、同一のnを用いて暗号文が形成されている必要があるので、ここを上手くやらないといけません。つまり、
c'1 = m^e1 mod n2 or c'2 = m^e2 mod n1
を求める必要があります。
n2 = r * n1 なので、なんか行けそうな気がするなぁと考えてたらやはりいけました。
c2 = m^e2 mod n2より
m^e2 = k*n2 + c2 (kは整数) = k*r*n1 + c2 = c2 mod n1
∴ c'2 = c2 mod n1 と簡単に求まりました。
では、この求めたc'2やc1,e1,e2,n1を使ってcommon modulus attackを行っていきます。
common modulus attackはこのサイトが分かりやすかったですが、ここでも噛み砕いて説明します。
拡張ユークリッドの互除法を用います。簡単に言うと、
a*x + b*y = c (a,b,c : 既知)
となる、x,yの解の一つを求めるやつです。
このサイトの「一次不定方程式への応用」ってところを読むと分かるはずです。
e1*s1 + e2*s2 = 1 となるs1,s2を求めます。そのs1,s2を使うと、
c1^s1*c'2^s2
= (m^e1)^s1*(m^e2)*s2 mod n1 = m^(e1*s1+e2*s2) mod n1 = m^1 = m
と平文mが求まります！
では、s1,s2を拡張ユークリッドの互除法でどうプログラムしていくかというと、このサイトを活用(丸パクリ)します。
こんな感じで平文mを求めてlong_to_bytesするとflagが出ました。
KosenCTF{HALDYN_D0M3}
solverも先のgithubに掲載しています。
このInterKosenCTFは昨日10時から始まったのですが、気付かず今日の夕方にやり始めてなんとかこの問題は解けたけど結局他の問題は解けなかったです。多分時間かけても変わらない結果だったと思います(笑)
それでは！
See you next time!
