20211221-PWHHUB12月赛-CryptoSecWriteUp
ecRNG
考点
- ecRNG
用椭圆曲线来生成的PRNG伪随机数发生器，但是该曲线是不安全的，可以用smartAttack把私钥r给算出来
十几分钟
1 | #!/usr/bin/env python3 |
1 | flag{so__Cooool__about__the_backdoor!~} |
easy login
考点
- AES.CBC模式整活
- MT19937伪随机数的恢复，
getrandbits中的潜规则
至于AES的脑洞，出题人还是很严谨的，代码中特意体现出来的东西都用到了，但我对此几乎无感，两步都是尚师傅提示的。全部围绕下面这个东西展开的战斗
1 | {name}##{identity}##{sever_certificate}##{hash} |
大致绕过方法如下：第二步登录之后需要先使得identity变成admin（默认是guest），这个在token前面加一段$iv\ \oplus\ \ guest\ \oplus admin$就可以成功通过，之后需要恢复死循环外面的一个512位的随机数secret_key从而获得flag；第一步每次注册加密的时候会生成一个256位的随机数sever_certificate，而登录解密的时候，如果identity位置的{}='admin'会输出name位置的{}，借用第一步的方法我们可以把前面两个{name}##{identity}##给解成乱码（乱码对.split(b"##")没有任何影响），这样就使得{sever_certificate}位置提前，之后再在密文中{sever_certificate}部分之后，加入类似xor(xor(iv, b'{' + b'A' * 15), b'{admin}##{xxx}##') + token[:16]的一段，就可以把{admin}##{xxx}##给添到{sever_certificate}之后，成功获得sever_certificate。凑足了78个256位（$32\times 624=78\times 256$）的sever_certificate就可以通过recover_MT19937恢复secret_key了。
之前的题目是getrandbits(32)，经过尚师傅的手工测验后，getrandbits(256)就是32个前者比特串连起来
1 | def token_decrypt(Cipher: bytes, iv: bytes, key: bytes): |
完整的exp
1 | #!/usr/bin/env python3 |
sign_in_rsa
考点
RSA泄露$d$分解$N$
算法
- 计算$k=ed-1$，并分解成$2^tr$（$r$是奇数）
- 随机选取$g$，$g\in\mathbb{Z}_N^*$
- 令$i$遍历$[0,\ t)$，如果$(g^{2^i\times r}-1, N)>1$，则$p=(g^{2^i\times r}-1, N)$，$q=\frac{N}{p}$，返回$p,\ q$
- 否则回到第二步重新选取随机数
原理
设$k=ed-1=\Delta_1\varphi(N)$，随机数$g\in\mathbb{Z}_N$，则$g^k\equiv g^{\Delta_1\varphi(N)}\equiv g^{\varphi(N)}\equiv1\ (mod\ N)$，即$g^k-1\equiv0(mod\ N)$，即
$$
g^k-1=N\Delta_2=pq\Delta_2
$$
我们想分解$N$，但是直接从$pq$下手会遇到大整数分解难题，而转换成$g^k-1$上则会有一些突破口；一般来说$(g^k-1,\ N)=N$由于$k=ed-1$是偶数可以分解成$2^tr$的形式，其中$r$是奇数，所以$(1)$可以被分解成
$$
g^k-1=(g^{\frac{k}{2}}+1)(g^{\frac{k}{2}}-1)=pq\Delta_2\notag
$$
同理$(g^{\frac{k}{2}}-1)$能够被继续分解直到$(g^{\frac{k}{2^t}}+1)(g^{\frac{k}{2^t}}-1)$结合CRT在QR和square roots中的应用
$(g^{\frac{k}{2^i}})^2\equiv g^{\frac{k}{2^{i-1}}}\equiv\dots\equiv g^{k}\equiv1\ (mod\ N)$，则
$\begin{align}g^{\frac{k}{2^i}}&=CRT(<1,\ 1>)\leftrightarrow x_1\notag\\&=CRT(<1,\ -1>)\leftrightarrow x_2\notag\\&=CRT(<-1,\ 1>)\leftrightarrow x_3\notag\\&=CRT(<-1,\ -1>)\leftrightarrow x_4\notag\end{align}$
只有在$x_2$或$x_3$的情况下，$g^{\frac{k}{2^i}}$才满足（$x_3$同理）
$$
\begin{cases}
g^{\frac{k}{2^i}}\equiv 1\ (mod\ p)\\
g^{\frac{k}{2^i}}\equiv -1\ (mod\ q)
\end{cases}\notag
$$
也就说$p$是$g^{\frac{k}{2^i}}-1$的因子，而$q$不是，这个时候求$(g^{2^i\times r}-1, N)$就是等于$p$（当然你换成$g^{\frac{k}{2^i}}+1$也可以最后就是概率的问题，因为每求得一个$g^{\frac{k}{2^i}}$，其实它只对应一个$x_i$，而其是$x_2$或$x_3$的概率正好是$\frac{1}{2}$
而论文中说在${g\ |\ g\in \mathbb{Z}_N^*}$中，找到符合条件的$g$的概率是$\frac{1}{2}$（没想到为什么，统计出来的就罢了
![image-20220103161009555]()
脚本
1
2
3
4
5
6
7
8
9
10
11
12
13
14def divide_pq(e, d, n):
k = e * d - 1
t, _k = 0, k
while _k % 2 == 0:
t += 1
_k = _k // 2
r = k // (2 ** t)
while 1:
g = getrandbits(100)
for i in range(t):
p = gcd(pow(g, 2 ** i * r, n) - 1, n)
if p > 1 and p != n:
q = n // p
return p, q
最后有点像hash链的加密
1 | from Crypto.Util.number import * |
1 | flag{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y} |
疑问（或者说方法）
泄漏$d$攻击的步骤一定是像上面这样吗？
由$ed-1=k\varphi(n)$可知其实$e$和$k$是同一数量级的，而$e$一般都取65537，所以直接爆破就可以算出$\varphi(n)$岂不美哉
1
2
3
4
5
6
7
8
9
10
11
12def get_flag(phi):
for _, ei in friend_keys[::-1]:
di = inverse(ei, phi)
cipher = pow(cipher, di, n)
return bytes.fromhex(hex(cipher)[2:])
for k in range(1, e):
t = (e * d - 1) // k
if get_flag(t).startswith(b'flag'):
print(get_flag(t))
break但至于适用性还值得考量
luukaka
考点
- CopperSimth求小根
- Paillier同态加密的一般形式
第二个类似祥云杯2021-Guess
1 | #!/usr/bin/env sage |
1 | flag{P4ll13r&C0pP3r5m17h_m4y_b3_g00d_Fr13nds~} |
Reference
- Coinc1dens-RSA 基础知识及攻击方法-d 泄露攻击
- ctf wik-d 泄露攻击
- Dan Boneh-Twenty Years of Attacks on the RSA Cryptosystem
- Why Smart’s attack doesn’t work on this ECDLP?
something else