picoCTF 2022 Crypto Write Up - MtSakaのブログ

これは何？

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が与えられるのでテキトーな波形表示ソフトで読み込むと、長音と短音と空白がわかりやすくなるので、それをテキトーなモールス信号復号ツールに投げる。

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 10¹⁰⁰⁰なので愚直じゃ普通に間に合わない。だから行列累乗とかすると高速に求まる。他にも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を適用すればいい。これで解けました！コードは消えたので残っていません。