これは何？
picoCTF 2022にGhoSaka!というチームで参加して、11800ptで266位でした。
そんな中Cryptoを全完しました。せっかくなので備忘録兼Write Upを書くことにしました。
basic-mod1
message.txtが与えられて問題文の指示通りにする。はい、やるだけ問題。
a=list(map(int,input().split())) ans='' for i in a: i%=37 if i<26: ans+=chr(i+ord('a')) elif i!=36: ans+=chr(i-26+ord('0')) else: ans+='_' print('picoCTF{'+ans+'}')
basic-mod2
またmessage.txtが与えられて問題文通りにやる。
a=list(map(int,input().split())) ans='' for i in a: i=pow(i,-1,41)-1 if i<26: ans+=chr(i+ord('a')) elif i!=36: ans+=chr(i-26+ord('0')) else: ans+='_' print('picoCTF{'+ans+'}')
credstuff
usernames.txtとpasswords.txtが与えられるので、該当ユーザーがusernames.txtの何行目にあるか見て、同じ行をpasswords.txtで見てROT13を取ると答えがでる。
morse-code
morse_chal.wavが与えられるのでテキトーな波形表示ソフトで読み込むと、長音と短音と空白がわかりやすくなるので、それをテキトーなモールス信号復号ツールに投げる。
substitution0
quipqiup - cryptoquip and cryptogram solverに、つっこむ！w
substitution1
quipqiup - cryptoquip and cryptogram solverに、つっこむ！w
substitution2
quipqiup - cryptoquip and cryptogram solverに、つっこむ！w
transposition-trial
最初の三文字がpicになるような置換を3文字ごとに手動で適用すると出る
Vigenere
Vigenère Cipher (automatic solver) | Boxentriqに、つっこむ！ｗ
Very Smooth
ここからが本番です。
gen .pyとoutput.txtが与えられる。gen.pyを見ると、nは二つの素数p,qの積らしい。pは16bitの素数たくさんの積+1(pは1024bit)でqは17bitの素数たくさんの積+1(qは1024bit)っていうのがわかる。これはPollard's p − 1 algorithmが適用できる！！
Pollard's p − 1 algorithm - Wikipedia
テキトーに早そうなコードをググり、nを素因数分解しました。あとはいつも通りのRSAを解くだけ。
def factor(n): a=2 j=2 while True: a=pow(a,j,n) d=math.gcd(a-1,n) if d>1 and d<n: return d j+=1 n=hoge c=fuga p=factor(n) assert(n%p==0) q=n//p phi=(p-1)*(q-1) e=65537 d=pow(e,-1,phi) print(long_to_bytes(pow(c,d,n)))
Sequences
First Blood(FA)だった。sequences.pyが与えられるので見てみると、これは数列があるので第20000000項目を求めるというものだった。mod 101000なので愚直じゃ普通に間に合わない。だから行列累乗とかすると高速に求まる。他にもWolfram Alphaに突っ込むなどするとうまくいく。行列累乗とか、競プロの知識が役立ってうれしい。(コードは残ってない)
あとは数がもとまったら。うまくコード変えてflagを吐かせればよい。
Sum-O-Primes
gen.pyとoutput.txtが与えられる。gen.pyを見るとnが二つの素数p,qの積でxがp+qらしい。よくよく考えると、φ(n)=n-p-q+1だからn-x+1になる。これでもう求まりますね！
x = hoge n = fuga c = hogefuga phi=n-x+1 e=65537 d=pow(e,-1,phi) print(long_to_bytes(pow(c,d,n)))
これで フラグが出てくる。
NSA Backdoor
まず、素数の生成がVery Smoothと同じだとわかるから、素因数分解ができることは確実。そこからどうするかを考えると、pとqにおいて離散対数問題をそれぞれ解いて中国剰余定理を適用すればいい。それぞれのp,qについてはPohlig–Hellman algorithmを適用すればいい。これで解けました！コードは消えたので残っていません。
