picoCTF 2022 Crypto Write-ups
source link: https://blog.lxdlam.com/post/1f7260ad/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
被拉来打的，只做了 Crypto。做啥写啥。
100 Points
要么照着题目随便搞搞，要么搜索一下，大部分就是古典密码或者轮换替换，批量一键过题。
- basic-mod*：照着题目说法写一个
f然后''.join(map(lambda x: chr(f(int(x))), input.strip().split()))。 - credstuff：
grep -in cultiris usernames.txt | awk -F ':' '{print $1}' | xargs head passwords.txt -n，然后 ROT13。 - morse-code：https://morsecode.world/international/decoder/audio-decoder-adaptive.html。
- rail-fence：https://gchq.github.io/CyberChef/#recipe=Rail_Fence_Cipher_Decode(4,0)。
- substitution*：https://www.quipqiup.com/。
- transposition-trial：
''.join((input[i+2] + input[i:i+2]) for i in range(0, len(input), 3))。 - Vigenere：https://gchq.github.io/CyberChef/#recipe=Vigen%C3%A8re_Decode('')。
Very Smooth
审计 get_smooth_prime，发现 p−1p-1p−1 是光滑质数，所以用 Pollard’s p-1 算法分解质因子：
from gmpy2 import powmod, gcd
def factor_smooth_p(N: int) -> (int, int):
a = 2
n = 2
for n in range(2, N)
a = powmod(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
然后直接跑就行了。
from gmpy2 import powmod, gcd, lcm
def factor_smooth_p(N):
a = 2
n = 2
for n in range(2, N):
a = powmod(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
if __name__ == "__main__":
e = 0x10001
# copy from file
n = int('', 16)
c = int('', 16)
p, q = factor_smooth_p(n)
m = lcm(p - 1, q - 1)
d = powmod(e, -1, m)
print(bytes.fromhex(hex(powmod(c, d, n))[2:]))
Sequences
直接审计 m_func：
# snippets...
ITERS = int(2e7)
# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
return 55692 * m_func(i - 4) - 9549 * m_func(i - 3) + 301 * m_func(
i - 2) + 21 * m_func(i - 1)
# snippets...
if __name__ == "__main__":
sol = m_func(ITERS)
decrypt_flag(sol)
f(x)={x+1,1≤x≤321f(x−1)+301f(x−2)−9549f(x−3)+55692f(x−4),3<x,x∈N+ f(x) = \begin{cases}x+1, &1\le x\le 3\\21f(x-1)+301f(x-2)-9549f(x-3)+55692f(x-4),&3<x\end{cases}, x\in\N^+ f(x)={x+1,21f(x−1)+301f(x−2)−9549f(x−3)+55692f(x−4),1≤x≤33<x,x∈N+
一个非常经典的线性递推。因为 iter 数量有 2×1072\times10^72×107 次，直接递推也是不太方便的，考虑矩阵快速幂优化线性递推。
[f(x+3)f(x+2)f(x+1)f(x)]=[21301−954955692100001000010]x⋅[f(3)f(2)f(1)f(0)] \begin{bmatrix}f(x+3)\\f(x+2)\\f(x+1)\\f(x)\end{bmatrix}=\begin{bmatrix}21&301&-9549&55692\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{bmatrix}^x\cdot\begin{bmatrix}f(3)\\f(2)\\f(1)\\f(0)\end{bmatrix} ⎣⎢⎢⎢⎡f(x+3)f(x+2)f(x+1)f(x)⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎡21100301010−954900155692000⎦⎥⎥⎥⎤x⋅⎣⎢⎢⎢⎡f(3)f(2)f(1)f(0)⎦⎥⎥⎥⎤
对这个方法不太了解的可以参考 https://oi-wiki.org/math/fibonacci/#_5。
注意 numpy 默认的数据类型会爆精度，需要手动指定 dtype='object'。同时该取模的地方要取上。
import numpy as np
MOD = 10**10000
def bin_pow(base, exp):
ans = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]],
dtype='object')
while exp:
if (exp & 1) > 0:
ans = ans.dot(base) % MOD
base = base.dot(base) % MOD
exp >>= 1
return ans
def fast_m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
arr = np.array([[4], [3], [2], [1]], dtype='object')
coef = np.array(
[[21, 301, -9549, 55692], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]],
dtype='object')
return bin_pow(coef, i - 3).dot(arr)[0][0]
Sum-O-Primes
不知道为什么这个题要给 400 points。
from sympy import symbols, solve
import math
if __name__ == "__main__":
e = 65537
# copy from file
x = int('', 16)
n = int('', 16)
c = int('', 16)
P, Q = symbols('p,q')
# x = p + q
# n = p * q
ret = solve([P + Q - x, P * Q - n], [P, Q], dict=True)
p = ret[0][P]
q = ret[0][Q]
m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)
print(bytes.fromhex(hex(pow(c, d, n))[2:]))
NSA Backdoor
首先 p−1p-1p−1 和 q−1q-1q−1 都是光滑的，直接用 Pollard’s p-1 算法搞出来。
搞出来后注意到我们要求解的式子，是一个离散对数问题： c=3FLAG(modn) c= 3^{\text{FLAG}} \pmod n c=3FLAG(modn) 朴素的 BSGS 复杂度太高，直接算算不了。由于 n=p×qn=p\times qn=p×q，而 ppp，qqq 都是光滑质数，而且根据生成方式，ppp 和 qqq 的质因子不大，数量也不多，提示我们可以用 Pohlig-Hellman 算法求离散对数。
具体的算法可以参考 https://ctf-wiki.org/crypto/asymmetric/discrete-log/discrete-log/#pohlig-hellman-algorithm。我直接用 sage 算了。
from sage.all import gcd, GF
def factor_smooth_p(N):
a = 2
n = 2
for n in range(2, N):
a = pow(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
if __name__ == "__main__":
# copy from file
n = int('', 16)
c = int('', 16)
p, q = factor_smooth_p(n)
R = GF(p)
x = R(c).log(3)
assert R(3)**x == c
print(bytes.fromhex(hex(x)[2:]))
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK