Zenn
🐷

kurenaif_2000_subscribers_challenge writeup

2021/10/04に公開
CTF
crypto
tech

まえがき

2000人本当にありがとうございます 😆😆😆😆
最近は暗号以外にも様々な知識に触れる機会が増えてとても楽しい日々を送らせていただいております！
今後は暗号系の動画はちょっと少なくして、いろんな人と知識を共有しながらいろんな知識の習得過程を動画の形で残していければと思っています。そのためにはたくさん友だちが欲しいので、もっとチャンネル登録者数を増やして色んな人と技術交流をしてみたいです！
今後もよろしくおねがいします！

問題

フラグの長さは383bitです。（サンプルの文字列と同じ）
この問題には以下の特徴があります。

  • pとqが20bit(とてもちいさい)
  • n = p*q にはフラグに入り切らない
  • e が 20000 (2の倍数)
from Crypto.Util.number import *

flag = bytes_to_long(b"kurenaifCTF{DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMY}")
print("# bit_length = ", flag.bit_length())
e = 20000

ns = []
cs = []

for i in range(2*200):
    p = getPrime(20)
    q = getPrime(20)
    n = p * q
    ns.append(n)
    cs.append(pow(flag, e, n))

print("e=", e)
print("ns=", ns)
print("cs=", cs)

解答

n が小さすぎるので容易に素因数分解可能

p,q \leq 2^{21} \approx 10^6

程度です。10^6 くらいまでループを回して総当りをすれば、 n を割り切るような p や q を見つけることができるため、容易に素因数分解をすることができます。

\begin{aligned} \phi &= (p-1)(q-1) \\ d &= e^{-1} \mod \phi \end{aligned}

e と \phi が互いに素ではない

残念ながら、この問題は e と \phi が確実に互いに素ではありません。
p と q が奇数で、

\phi = (p-1)(q-1)

であるから、 \mathrm{gcd(e, \phi)} は最低でも4の倍数になります。（lcmで求める場合は2の倍数で収まるケースも作れます。）

ここで、 以下の式を考え、ユークリッドの互除法で a, b を求めると、

ed + \phi b = \mathrm{gcd(e, \phi)}

より、

(m^e)^d = m^{ed} = m^{\mathrm{gcd(e, \phi)} + b \phi} = m^{\mathrm{gcd(e, \phi)} } m^{b \phi} = m^{\mathrm{gcd(e, \phi)} }

となります。もし、 \mathrm{gcd(e, \phi)} が 4であれば、 c^d \equiv m^4\ \mod n が導出できます。

m^4 の情報が足りない

m^4 をたくさん取得することができますが、n = pq が小さすぎるので、 m の復元には至りません。が、今回は p, q がたくさんあるので \mathrm{gcd(e,\phi)} が 4 となるものをたくさん集めて、cを復元することが可能です。
ここで、4となるものの個数によって復元できるかどうかが異なります。筆者手元の環境では10回連続では成功してくれたので、概ね問題なしと思い問題にしました。

\mathrm{gcd(e,\phi)} を 4で保証するかどうかはかなり悩みましたが、あまりに与えるヒントが多すぎるため今回はそこは guess/お祈り して貰う形にしました。少しでもguessを減らそうとbit_lengthの情報は書くことにしました。

https://twitter.com/fwarashi/status/1443948992799260678?s=20

m^4 から m へ

nが十分に大きい場合、 m^4 \mod n は \mod n を外しても問題なくなるのであとは4乗根を求めるだけです。 自分で書く場合は二部探索、ライブラリを使う場合はgmpy2などがあります。

あとがき

1問で典型的なRSA暗号問をいくつか重ね合わせてみました。が、ぶっちゃけ e と \phi が 互いに素 + 4乗根だけでも良かったなとリリースしたあとに思いました。もともとCRTベースの問題だったのですが、非想定解放とか考えていくとこの形になりました。

ソースコード

sagemathでときました

from Crypto.Util.number import *
import gmpy2
from params import *

ms = []
cnt = 0

ans_ns = []
ans_ms = []
nn = 1

memo = {}

for i in range(len(ns)):
	n = ns[i]
	c = cs[i]
	p = factor(n)[0][0]
	q = factor(n)[1][0]
	phi = (p-1) * (q-1)
	g, d, _ = xgcd(e, phi)
	if g not in memo:
		memo[g] = 0
	memo[g] += 1
	print(g)
	if g == 4:
		cnt += 1
		ans_ms.append(int(pow(c,d,n)))
		ans_ns.append(n)
		nn *= n

print(memo)
print(int(cnt))
print(int(nn).bit_length())
print(long_to_bytes(crt(ans_ms, ans_ns).nth_root(4)))

Discussion