N1CTF 2022 Writeups
這次在隊伍 隨便啦
解了些 Crypto 方面的題目,因為蠻有趣的所以簡單紀錄一下做法。
Crypto
ezdlp
from Crypto.Util.number import *
from math import prod
from secret import flag
def keygen(pbits,kbits,k):
p = getPrime(pbits)
x = [getPrime(kbits + 1) for i in range(k)]
y = prod(x)
while 1:
r = getPrime(pbits - kbits * k)
q = 2 * y * r + 1
if isPrime(q):
return p*q, (p, q, r, x)
def encrypt(key, message):
return pow(0x10001, message, key)
key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]
print(messages[:-1])
print(enc)
這題會先用 ,其中 是個 smooth number,然後隨便生成些 之後給你 的值,然後它並沒給你 的值。
首先是要還原 ,這部分對我來說其實很簡單,因為我不久前才給 ImaginaryCTF 出了個 No modulus,裡面用的概念完全相同,都是用 LLL + gcd 去得到 XDD。
之後得到 之後就是分解 ,第一眼會覺得 是 smooth 的,但實際上因為 ,所以還會多出一個 bits 的 factor。而就是這個多出來的 factor 讓我原本寫好的 pollard p-1 跑不出來,變得要去找所有的 bits prime 才行,但這個在我用 Python 寫的腳本要花上十個小時左右…。(我這邊的方法類似 wiki 上說的 Two-stage variant,取 )
後來查了些資料才知道說有個叫 gmp-ecm 的神奇 command line 工具有實作 p-1, p+1, ecm,並且支援許多自訂的設定,所以稍微研究了一下之後可以生出這條指令:
echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296
然後他很神奇的就在大概 15 秒內就吐出了 prime factor,所以之後只要在 下解 DLP 就能得到 flag 了。
from Crypto.Util.number import *
import ast
with open('output.txt') as f:
msgs = ast.literal_eval(f.readline())
enc = ast.literal_eval(f.readline())
M = matrix(ZZ, msgs).T.augment(matrix.identity(len(msgs)))
M[:,0] *= 2^1024
M = M.LLL()
print(M[0])
print(M[1])
aa = product([ZZ(x)^y for x,y in zip(enc, M[0][1:])])
bb = product([ZZ(x)^y for x,y in zip(enc, M[1][1:])])
n = gcd(aa.numer() - aa.denom(), bb.numer() - bb.denom())
print(n)
# echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296
n = 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
q = 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
p = n // q
m = GF(q)(enc[-1]).log(0x10001)
flag = long_to_bytes(int(m))
print(flag)
brand_new_checkin
from Crypto.Util.number import *
from random import getrandbits
from secret import flag
def keygen():
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
while True:
a = getrandbits(1024)
b = phi + 1 - a
s = getrandbits(1024)
t = -s*a * inverse(b, phi) % phi
if GCD(b, phi) == 1:
break
return (s, t, n), (a, b, n)
def enc(m, k):
s, t, n = k
r = getrandbits(1024)
return m * pow(r, s, n) % n, m * pow(r, t, n) % n
pubkey, privkey = keygen()
flag = pow(bytes_to_long(flag), 0x10001, pubkey[2])
c = []
for m in long_to_bytes(flag):
c1, c2 = enc(m, pubkey)
c.append((c1, c2))
print(pubkey)
print(c)
這題是基於 CakeCTF 2022 - brand_new_crypto 改的,主要差異在於它在 byte by byte 加密前會先用一般的 RSA 先把 flag 加密過一遍,再來是它取 random 的地方改為使用 Python random
的 getrandbits
,且固定使用 1024 bits。
前面的部分就直接用元題的解法來做就好,主要的難點還是在怎麼解 RSA 的部分。因為它 random 的改動所以可以很明顯的看出是要想辦法去回推 MT19937 得到 。
首先是可以假想有 的情況我們可以做什麼,所以先從 keygen
列出兩條等式:
把第一條改寫可以得到:
這裡面我們唯一不知道的是 ,所以自然會想把 拿掉,所以第一式乘上 之後和第二式相減可得:
所以可知 是 的倍數,RSA 其實也只需要知道 就能算出一個能用的 private key 了,所以只要有 我們就能解決這題。
再來是要恢復 random,從 enc
的部分可以知道當 已知時可得 和 ,而這題因為 所以用 common modulus attack 就能獲得 。因為每個 是 1024 bits,而且這題又提供的大量的 sample 所以直接隨便找個 MT19937 的破解工具來用應該就行了。
…我最初確實是這麼想的,但是實際上在獲得 之後遇到的許多困難,才發現說 並不是一定成立的,而前面的 common modulus attack 得到的其實是 ,而做些實驗可以方法 可能是 三者之一。
因為破解 MT19937 需要 624 個 32 bits 的輸出,而 ,所以至少要 20 個 才夠 (),但是每個 都有三種可能,所以一共需要 的 brute force,計算量以 CTF 來說有點太大因此不太可行。
我後來寫了個函數 (solve script 的 try_xx
) 會嘗試還原 MT19937 後生成一些輸出,然後和真正的 比較看看有多少的 bits 是相同的,然後經過一些實驗發現有些 xx (猜測的輸入)可以得出較高的正確率,所以有機會能利用一些比較好的爆破方法把原本的 3^20 的搜尋空間壓縮。
而我這邊具體使用的方法是一個類似基因演算法 (Genetic Algorithm) 的方法,詳情請見 code,不過這個方法確實是有效幫我破解 MT19937 的,所以後來就隨便將它 reverse 回去之後直接暴力找 ,然後用前面的方法算出 private key 之後就有 flag 了。
from Crypto.Util.number import *
import ast
from sage.all import xgcd, gcd, matrix, ZZ
import gmpy2
def pow(a, b, c):
return int(gmpy2.powmod(a, b, c))
with open("output.txt") as f:
s, t, n = ast.literal_eval(f.readline())
c = ast.literal_eval(f.readline())
def inverse(x, y):
return pow(x, -1, y)
# decrypt
flagct = []
for (c1, c2) in c:
for m in range(1, 256):
if c1 == c2 == 0:
flagct.append(0)
break
rs = c1 * inverse(m, n) % n
rt = c2 * inverse(m, n) % n
if pow(rs, t, n) == pow(rt, s, n):
flagct.append(m)
break
else:
raise ValueError("???")
print(bytes(flagct))
# flagct = list(
# b'\x08EZg\xbf\xa0\xeb\x9d\x81\x01\xa8\x96m\x97\x08I(\xed\xb5iQE\xdb\xf5\x8c\xbdcr!\xe6\xc9\xac\x0c\x16K\xa0\x0fr\xecM\x04\xe6\x87\x0f}9\x94\xcfa\x16\x87\x8f4\xcd\xcb\xa4\x0eq\xc3Q\x16\x928&\xe2\x18C\xafN\x87\xcc\x18\xc2D\x9d\x06\xbd"\xe7\xe8\xb7\x12\xb0\xb8CC\x9aM\xff\x12\x00\x05,\xeeopYC)mI\xb7\x81\xb6\x13\x0e\x8a\xc0\xd7\xd3\xd2\xa9\xe5vg.\xa4\xf3\xaa\x10f\x9c\xa4nS=O\xe9'
# )
# recover r
g, x, y = xgcd(s, t)
assert g == 1
assert x * s + y * t == 1
rrr = []
for m, (c1, c2) in zip(flagct, c):
try:
im = inverse(m, n)
rs = im * c1 % n
rt = im * c2 % n
r = pow(rs, x, n) * pow(rt, y, n) % n
rrr.append(r)
except:
break
print(len(rrr))
import sys
sys.path.append("./MT19937-Symbolic-Execution-and-Solver/source")
from MT19937 import MT19937, MT19937_symbolic
from XorSolver import XorSolver
import random
from functools import lru_cache
@lru_cache(maxsize=None)
def split1024(r):
x = []
for _ in range(1024 // 32):
x.append(r & 0xFFFFFFFF)
r >>= 32
return x
def clone(rng):
return MT19937(state=rng.state[:])
def grb1024(rng):
ss = 0
for i in range(1024 // 32):
ss |= rng() << (i * 32)
return ss
def randgen(n, prob=0.3, prob2=0.05):
ar = []
for _ in range(n):
r = random.random()
if r < prob2:
ar.append(2)
elif r < prob:
ar.append(1)
else:
ar.append(0)
return ar
def compare(x, y):
cnt = 0
for a, b in zip(f"{x:01024b}", f"{y:01024b}"):
cnt += a == b
return cnt
def try_xx(xx, n_cmp, return_rng=False):
# xx: a list of 0, 1, 2
rtmp = [r + x * n for r, x in zip(rr, xx)]
data = []
for r in rtmp:
data += split1024(r)
try:
rng_clone = MT19937(state_from_data=(data, 32))
# print("gj", xx)
cr = clone(rng_clone)
tot = 0
for j in range(n_cmp):
lhs = grb1024(cr) % n
rhs = rrr[baseidx + j]
cond = lhs == rhs
cp = compare(lhs, rhs)
tot += cp
# print(j, cond, cp)
# print(tot)
if return_rng:
return rng_clone
return tot
except Exception as ex:
# import traceback
# traceback.print_exc()
pass
def mutate(xx):
xx = list(xx)
v = random.randint(0, 2)
xx[random.randrange(len(xx))] = v
return xx
baseidx = 0 # choose a starting index to start searching
rr = rrr[baseidx : baseidx + 20]
xx = [0] * 20
tot = 0
n_cmp = 40
# a shitty searching algorithm inspired by genetic algorithm
# try_xx is some sort of a fitness function
while tot < n_cmp * 1024:
mut = [mutate(xx) for _ in range(10)] + [randgen(len(xx)) for _ in range(10)]
res = [(ret, mx) for mx in mut if (ret := try_xx(mx, n_cmp)) is not None]
res.sort(key=lambda x: x[0], reverse=True)
# for r, mx in res:
# print(r, mx)
if len(res) >= 1:
tot, mx = res[0]
print(tot, mx)
xx = mx
rng_clone = try_xx(xx, n_cmp, return_rng=True)
# do some santiy check
cr = clone(rng_clone)
print(grb1024(cr) % n, rrr[baseidx])
cr = clone(rng_clone)
print([cr() for _ in range(1024 // 32)], split1024(rrr[baseidx] + xx[0] * n))
rng = clone(rng_clone)
rng.reverse_states(512 * (1024 // 32))
for i in range(512):
ss = grb1024(rng)
if s == ss:
print("good")
print(hex(s))
print(hex(ss))
a = prv
print(hex(a))
phik = s * a - t * a + t
d = inverse(0x10001, phik)
cc = bytes_to_long(bytes(flagct))
m = pow(cc, d, n)
print(long_to_bytes(m))
prv = ss
# n1ctf{5255840f-9140-4479-950f-a3c03fe7f4cd}
babyecc
from Crypto.Util.number import *
from secret import flag
m = Integer(int.from_bytes(flag, 'big'))
for _ in range(7):
p = getPrime(512)
q = getPrime(512)
n = p * q
while 1:
try:
a = randint(0,n)
b = randint(0,n)
Ep = EllipticCurve(GF(p), [a,b])
Gp = Ep.lift_x(m) * 2
Eq = EllipticCurve(GF(q), [a,b])
Gq = Eq.lift_x(m) * 2
y = crt([int(Gp[1]),int(Gq[1])],[p,q])
break
except Exception as err:
pass
print(n, a, b, y)
這題會隨機生成 和 得到一條橢圓曲線 ,之後取上面一點 之後給你 的 y 座標。其中的 固定是 flag,一共會重複七次所以有七組 。
方法也很簡單,就對每組設 的座標為未知數,然後用橢圓曲線的定義可以得到第一條等式,再來用 doubling formula 和它給的 又能得到另一條等式,然後用 resultant 把未知的 的 y 座標給消除後能得到一個 12 次的多項式 以 為根。
因為有七個,所以可以拿到七組 和 ,之後利用 CRT 可以得到另一個 在 的情況下以 為根,所以用 coppersmith 就能得到 flag。 ()
CRT 部分可以參考 CakeCTF 2021 - Party Ticket,這題和那題的概念很接近,可以當作是擴展是 hastad broadcast attack
from Crypto.Util.number import *
with open("output.txt") as f:
ar = []
for line in f:
n, a, b, y = map(ZZ, line.strip().split(" "))
ar.append((n, a, b, y))
def double(x, y, a, b):
s = (3 * x ^ 2 + a) / (2 * y)
xr = s ^ 2 - 2 * x
yr = y + s * (xr - x)
return xr, yr
P.<mx, my> = QQ[]
eqs = []
for n, a, b, y in ar:
eq1 = my ^ 2 - (mx ^ 3 + a * mx + b)
_, yy = double(mx, my, a, b)
eq2 = (yy - y).numerator()
f = eq1.sylvester_matrix(eq2, my).det().univariate_polynomial()
eqs.append(f)
ns = [n for n, a, b, y in ar]
Ti = [crt([1 if nn == n else 0 for nn in ns], ns) for n in ns]
N = product(ns)
ff = sum([f * ti for f, ti in zip(eqs, Ti)])
ff = ff.change_ring(Zmod(N)).monic()
set_verbose(1)
rs = ff.small_roots(epsilon=0.03)
print(rs)
m = int(rs[0])
print(long_to_bytes(m))
# n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}