[CTF秀] CTFshow 第二届月饼杯 Crypto部分 个人writeup
本文使用 Zhihu On VSCode 创作并发布
这次现代密码学部分是我出（tou）的题，所以我就没做，结果比赛结束时每题都个位数的解，可能是大佬都去过中秋节团圆去了……
两道古典密码学不难，不能说送分，但是也是古典密码里面比较基础的东西了……
ctfshow_login
题目描述
这道题基于DSA： y=g^x \bmod p 。我们知道 (g, p, y) 但是不知道 x 。
题目给了签名和验签的代码。
需要消息中包含特定字符串，并且验签通过，才能得到flag。
我的解答
正如题目所说的，只要用任意一个名字成功登录就能拿到flag，也就是说消息 m 需要有对应子串。但是tricky的地方在于：他并没有对消息的大小直接进行判断，而是直接取消息的末1024位 u 进行计算，并且也没有用哈希函数对消息进行哈希。
所以我们就可以让消息的高位为对应子串，然后去构造消息的末1024位 u 使验签通过。
那么问题来了：如何构造在不知道 x 的情况下构造 (u, r, s) 使得验签通过，也就是
g^u \equiv y^r r^s \ (\bmod p)
解法一
我们可以让 r 有 g 和 y 的因子：也就是令
r=g^i y^j
这样我们就可以把问题化归到 g 和 y 上。代入到验签式中：
g^u \equiv y^r g^{si} y^{sj} \ (\bmod p)
也就是我们想要让
\left\{ \begin{aligned} u \equiv si \ (\bmod (p-1)) \\ y \equiv sj \ (\bmod (p-1)) \end{aligned} \right.
那么我们的构造根据这些变量式的约数也就变得清晰了：
-
随机生成 (i, j) ；
-
计算 r=g^i y^j ；
-
计算 s=y^{-1} j \bmod (p-1) ；
-
计算 u=si \bmod (p-1) 。
这就可以构造出满足要求的 (u, r, s)
解法二
利用二次剩余（勒让德符号）的性质：我们知道由费马小定理，
g^{p-1} \equiv 1 \ (\bmod p)
既然题目让我们构造的数都要在 2 \sim p-2 范围内，所以我们肯定不能直接用 p-1 。但是我们可以用 (p-1)/2 来构造：
g^{(p-1)/2} \equiv \left\{ \begin{aligned} & 1 & g\textrm{是模}p\textrm{的二次剩余} \\ & -1 & g\textrm{是模}p\textrm{的非二次剩余} \end{aligned} \right.
所以我们可以在验签式中令 u=r=s=(p-1)/2 ，然后验签式的三部分都变成1或-1。多拼几次人品使得验签式成立即可。
解法一代码如下：
from Crypto.Util.number import *
from random import randint
g = 7
while (True):
i, j = randint(2, p-2), randint(2, p-2)
if GCD(j, p-1) != 1:
continue
r = pow(g, i, p) * pow(y, j, p) % p
s = -r * inverse(j, p-1) % (p-1)
m = s * i % (p-1)
m = b'Daniu@CTFshow'.hex() + f'{m:0260x}'
print(m)
print(f'{r:x}')
print(f'{s:x}')
break
解法二类似
切记务必一定要简单
题目描述
RSA中 N=pq ，其中 p 为1127位素数， q=13/17 \cdot p + \Delta ，其中 \Delta 为573位数， q 为素数，试求得 N=pq 的分解。
我的解答
其实之后 提示 里面就已经有解法了：费马分解
费马分解的思想：利用恒等式
pq=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2
并且注意到正整数 t 和 t+1 各自平方之间的间隔：
(t+1)^2-t^2=2t+1=O(t)
也就是说，当 |p-q| 小的时候，我们有
pq \approx \left(\frac{p+q}{2}\right)^2
而且注意到由于 p 和 q 是奇数所以 (p+q)/2 和 (p-q)/2 是整数。
所以说我们可以枚举 (p+q)/2 ，这个数必定不小于 \sqrt{pq}=\sqrt{N} 。如果 ((p-q)/2)^2 大概是 (p+q)/2 这个量级，也就是 p-q 的量级大概是 p+q 的平方根量级的话，我们就能在很少次数中的枚举中枚举到。
那么实操也就是让 s=(p+q)/2 从 \sqrt{N} 开始枚举，然后计算 s^2-N 是否为完全平方数：若是，则开根号求得 |p-q|/2 ，并且解线性方程组得到 (p, q) ；若否，则继续枚举。
回到这题，在这题中并不是 |p-q| 小，而是 |17q-13p| 小。
那么我们也可以利用类似的恒等式：
17 \cdot 13 N = \left(\frac{17q+13p}{2}\right)^2 - \left(\frac{17q-13p}{2}\right)^2
以及类似思路来做。
粗略估算下， (17q+13p)/2 这个数大概是1131位。在枚举的过程中，平方的增长是1131位的增长，而 |17q-13p|/2 是576位，其平方大概是1152位。所以期望枚举21位整数（也就是最多尝试 2^{21} 次）即可完成分解。解题代码如下：
from Crypto.Util.number import *
import gmpy2
e = 65537
N = gmpy2.mpz(N)
h1, ok = gmpy2.iroot(17 * 13 * N, 2)
while True:
h1 += 1
h2 = h1 ** 2 - 17 * 13 * N
h2, ok = gmpy2.iroot(h2, 2)
if (ok):
break
print(h1)
q = (h1 + h2) // 17
p = N // q
if (p * q != N):
q = (h1 + h2) // 13
p = N // q
print(p * q - N)
d = gmpy2.invert(e, (p-1)*(q-1))
m = gmpy2.powmod(c, d, N)
print(long_to_bytes(m))
张八炫CTFshow三结义
题目描述
RSA中给了 N ， e 未知但是是91以内的素数。
明文 m 被拆分成了 m_1, m_2, m_3 三部分，密文 c_i=m_i^e \bmod N 对 i=1, 2, 3 。
另外给出明文三部分之和 s=m_1+m_2+m_3 。
试求明文。
我的解答
由 e 的限制知道 e 的取值有限。
这题其实就是考察Grobner基的应用：Grobner基求的是多元多项式的“最大公约数”。特别地，如果这些多元多项式都有共同的根的话，就可以利用Grobner基来求出这些根。
所以这题的本质就是枚举 e ，对理想 (x^e-c_1, y^e-c_2, z^e-c_3, x+y+z-s) 求Grobner基，其结果即为明文。
这里值得注意一下就是题目的生成代码是随机生成的 e ，但是实验在 e 比较大的时候求Grobner基可能会耗时较久。我建议如果十分钟后还没有求出结果的话，把容器destroy一下重新刷新一个 e 就好。求解代码如下：
from tqdm import tqdm
from Crypto.Util.number import *
cs =
P.<x, y, z> = PolynomialRing(Zmod(N))
e_list = [i for i in range(1, 91) if isPrime(i)]
for e in tqdm(e_list):
G = [x+y+z-s, x^e-cs[0], y^e-cs[1], z^e-cs[2]]
B = Ideal(G).groebner_basis()
if (len(B) != 1):
print(B)
沐沐子倒拔垂杨柳
题目描述
AES-CBC中， IV=key ，并且给了加密和解密的Oracle。
试求key。
我的解答
首先我们看看CBC的加密式和解密式。加密式：
c_1 = \mathrm{Enc}(m_1 \oplus IV)
c_2 = \mathrm{Enc}(m_2 \oplus c_1)
解密式：
m'_1 = \mathrm{Dec}(c'_1) \oplus IV
我们要求的也就是 IV ，肯定是利用解密式所暴露的这个异或的 IV 来求。
在加密式中，我们除了 IV ，其他的值都是知道的。所以我们可以利用第二个式子来构造：假设我们在解密式中令 c'_1=c_2 ，便有：
\begin{align} m'_1 &= \mathrm{Dec}(\mathrm{Enc}(m_2 \oplus c_1)) \\ &=m_2 \oplus c_1 \oplus IV \end{align}
所以我们就可以算出 IV=m'_1 \oplus m_2 \oplus c_1 。求解代码如下：
import binascii
m = '0' * 64
print(m)
m = bytes.fromhex(m)
c = ''
c = bytes.fromhex(c)
def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))
c1 = c[:16]
c2 = c[16:32]
m2 = m[16:32]
print(c2.hex())
c_ = ''
c_ = bytes.fromhex(c_)
c_1 = c_[:16]
mm = xor(xor(c1, m2), c_1)
print(mm)
我的木头啊！！！
题目描述
古典密码，只给了一串密文。
我的解答
题目给的密文中，
ctfshow
这些字母出现的位置似乎有规律。
联想到题目描述中所提到的栅栏，怀疑是栅栏加密。
但是用 枚举工具 试了一下，发现并没有东西。
所以想到可能是W型栅栏。
直接去网上搜现成的代码，解得
ctfshow{626173653136_MJQXGZJTGI_YmFzZTY0_qzTiEHgB_@UX=h}
发现flag格式归位了，但是flag内容似乎都是编码，看上去第一个是hex（base16）编码，第二个是base32编码……
所以解到这里还没完，要把这些base编码都给解开才算完。这里推荐 解码工具 ，会发现下划线分隔的每部分依次是base16、base32、base64、base58、base85编码，都解开就能得到最后的flag。
解W型栅栏代码如下：
def generate_w(string, n):
'''将字符排列成w型'''
array = [['.']*len(string) for i in range(n)] #生成初始矩阵
row = 0
upflag = False
for col in range(len(string)): #在矩阵上按w型画出string
array[row][col] = string[col]
if row == n-1:
upflag = True
if row == 0:
upflag = False
if upflag:
row -= 1
else:
row += 1
return array
def encode(string, n):
'''加密'''
array = generate_w(string, n)
msg = []
for row in range(n): #将每行的字符连起来
for col in range(len(string)):
if array[row][col] != '.':
msg.append(array[row][col])
return array, msg
def decode(string, n):
'''解密'''
array = generate_w(string, n)
sub = 0
for row in range(n): #将w型字符按行的顺序依次替换为string
for col in range(len(string)):
if array[row][col] != '.':
array[row][col] = string[sub]
sub += 1
msg = []
for col in range(len(string)): #以列的顺序依次连接各字符
for row in range(n):
if array[row][col] != '.':
msg.append(array[row][col])
return array, msg
def crack_cipher(string):
'''破解密码'''
for n in range(2,len(string)): #遍历所有可能的栏数
print(str(n)+'栏：'+''.join(decode(string, n)[1]))
if __name__ == "__main__":
string = "c6_I_@t216MG_0q_Uf673JTYYzBXs{31QJmTTg=hw63XZFZiHho5GzE}"
n = 5 #栏数
#若不知道栏数，则遍历所有可能
crack_cipher(string)
# #若知道栏数
# array,msg = decode(string, n)