CryptoCTF Wp 1

WriteUp
CTFSeason3
发布日期:   2021-08-03

CryptoCTF WriteUp 1 By huangx607087

0.About

8月的第一篇文章，之前瞄了一眼，发现7月并没有形成一个更博客的高峰期—— 因为自己摸鱼太多了实际上是因为自己太废了，这几天有个CryptoCTF，做了几题，剩下的内容还在研究中，准备再写一篇Wp，也是5道题。

进入八月事情莫名其妙地开始多了起来，一是八月份还有很多CTF要打，二是我还要准备一篇2000字实习报告，三是之前在院科协搞了个什么项目，到时候要启动集群做项目

一开始感觉有些题目似乎确实还是比较难的，不过最终感觉可能还是因为自己太菜了所以导致没做出来。

哦对还有一个AES没学，这玩意最近似乎出现频率越来越高，果然huangx607087==fw

1. Farm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env sage 
from sage.all import *
import string, base64, math
from flag import flag
ALPHABET = string.printable[:62] + '\\='
F = list(GF(64))
def keygen(l):
	key = [F[randint(1, 63)] for _ in range(l)] 
	key = math.prod(key) # Optimization the key length :D
	return key
def maptofarm(c):
	assert c in ALPHABET
	return F[ALPHABET.index(c)]
def encrypt(msg, key):
	m64 = base64.b64encode(msg)
	enc, pkey = '', key**5 + key**3 + key**2 + 1
	for m in m64:
		enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
	return enc
# KEEP IT SECRET 
key = keygen(14) # I think 64**14 > 2**64 is not brute-forcible :P
enc = encrypt(flag, key)
print(f'enc = {enc}')
#805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj

一开始拿到这个题目，似乎没什么头绪——感觉好像是一个有限域多项式的玩意，不过细一看——原来是先对明文$m$进行了base64操作，然后对base64后的内容进行了一个相当于多项式的位移——并且这个位移是一定的。再加上我们知道了已知明文的开头式CCTF，因此就可以根据最前面几位的内容判断一下位移量即可——这里的位移量是$44$。

不过这边还有一些细节需要注意：上面代码中：F=list(GF(64))是$GF_{64}$上的一个多项式环，里面记录了$x$的多少次方的内容，sagemath中貌似用的是不可约多项式$x^{6}+x^4+x^3+x+1$。（注：这实际上是本源多项式），因为测试中发现$x^5·x=x^4+x^3+x+1$。而更好玩的是：题目中出现的多项式$x^5+x^3+x^2+1$恰好是$x^{62}$的值——也可以认为是$x^{-1}$的值。但这里有个问题就是F[0]=0,F[63]=1。所以有些地方需要简单操作一下：一是由于字符0在题目给出的字典中下标是$0$，因此遇到0要保持不变。二是当下标超过$64$，对$64$进行取模后，下标值要继续加上$1$，这样是为了跳过ALPHABET[0]中的那个'0'

解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from base64 import *
cipher='805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj'
alphabet='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ\='
message=''
for i in cipher:
    C=alphabet.index(i)
    if(C==0):
        message+='0'
    elif(C+44>=64):
        message+=alphabet[(C+44)%64+1]
    else:
        message+=alphabet[C+44]
print(b64decode(message))
#CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}

2.hyper_normal

写在前面的内容：作为一个Crypto打了快一年的人应该有基本的数学素养——比如在解题过程中看到多重数组就要想到矩阵，看到二元组之间的运算就要想到椭圆曲线，而不是像huangx607087一样什么也不懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/env python3
import random
from flag import FLAG
p = 8443
def transpose(x):
	result = [[x[j][i] for j in range(len(x))] for i in range(len(x[0]))]
	return result
def vsum(u, v):
	assert len(u) == len(v)
	l, w = len(u), []
	for i in range(l):
		w += [(u[i] + v[i]) % p]
	return w
def sprod(a, u):
	w = []
	for i in range(len(u)):
		w += [a*u[i] % p]
	return w
def encrypt(msg):
	l = len(msg)
	hyper = [ord(m)*(i+1) for (m, i) in zip(list(msg), range(l))]
	V, W = [], []
	for i in range(l):
		v = [0]*i + [hyper[i]] + [0]*(l - i - 1)
		V.append(v)
	random.shuffle(V)
	for _ in range(l):
		R, v = [random.randint(0, 126) for _ in range(l)], [0]*l
		for j in range(l):
			v = vsum(v, sprod(R[j], V[j]))
		W.append(v)
	random.shuffle(transpose(W))
	return W
enc = encrypt(FLAG)
print('W=',enc)
#输出文件保存在given.py内

打开given.py看了一下，W是一个$55×55$的矩阵——初步读完代码后，可以判断flag有$55$位。本地测试了一下transpose,vsum,sprod三个函数：其中transpose函数是将一个矩阵转置，vsum是两个行向量相加，sprod是对一个行向量进行数乘操作。当然这一切都是在$GF(8443)$上进行的。

继续阅读代码，可以发现$V$实际上可以认为是矩阵$\mathrm{diag}(m_1,m_2,…,m_{55})$与矩阵$\mathrm{diag}(1,2,…,55)$的乘积，其中$m_i$表示flag第$i$位的ASCII码值。计算过后，将$V$每一行都打乱了。而关于加密中出现的$R$，我们可以认为$R$是一个随机矩阵，最后的加密结果$W$为$RV$的值。

这道题的一个突破口就是$R$是一个随机矩阵，根据以前的做题经验——遇到了随机数，就要想办法消除随机数带来的影响。由于那天下午刚好为了星盟晚上的分享，对椭圆曲线上的几种最简单的加密算法进行了研究，搞了一下椭圆曲线上的多项式，注意到了有限域内两个高次多项式是可以通过欧几里得辗转相除法，将其化简成一个一次多项式的。——然后就感觉这会不会也是有限域内求所谓的”公约式”。

然后发现这个方法似乎并不那么可行——因为经过很简单的分析就知道这个方法一定是无法成功的（。然后我注意到这个数据规模似乎并不大——也就是可以一位一位的爆破。

试爆了三个：CCT，但试爆第$4$个的时候，发生了多解的情况——但内部竟然存在F，并且F对应的乘数恰好是$4$。我又试爆了几个，确实，这个貌似都是按顺序来的。然后就可以写出下面的解题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from given import W
from Crypto.Util.number import *
from string import printable
p=8443
arr=[]
S=""
for _t in range(55):
    print(_t)
    print(S)
    arr=[]
    for __r in range(55):
        arr.append(W[__r][_t])
    #print(arr)
    for i in printable:
        #for j in range(1,56):
        for j in [_t+1]
            T,fail=[],0
            for k in range(127):
                checker=(ord(i)*j*k)%8443
                T.append(checker)
            for k in arr:
                if k not in T:
                    fail=1
            if(fail==0):
                S+=i     
print(S)
#CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}

为什么他最后还是可以解出来正确的顺序呢——通过简单的理论分析一下就知道：由于$R$是随机数组，而为了保证与$R$无关，我们就可以随意变换$R$。而对于$n$阶的一个矩阵$E=\mathrm {diag}(1,1,1,…,1,1)$，将$E$行打乱，得到矩阵$M$，那么$M^{-1}$一定是$E$的另一种行打乱方法。因此，我们可以从理论上推出：$RV=RV’M$，其中$V’$是打乱之前的矩阵。但由于$R$是随机矩阵，因此我们可以把$R$视为$M^{-1}R’$。由于$MNM^{-1}$是一定可以交换的，因此我们就把无序的矩阵$RV$化成有序的矩阵$R’V’$，这样仍然可以得到原来的结果了。

当然据说可以不进行对字符的爆破，13行代码就能解决问题——这个还有待考证。但刚才的理论分析确实把for j in range(1,56):的一重循环去掉了。至于再去一重循环，可能真的不是特别好想到。

3.Rima

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/env python
from Crypto.Util.number import *
from flag import FLAG
def nextPrime(n):
    while True:
        n += (n % 2) + 1
        if isPrime(n):
            return n
f = [int(x) for x in bin(int(FLAG.hex(), 16))[2:]]
f.insert(0, 0)
for i in range(len(f)-1): f[i] += f[i+1]
a = nextPrime(len(f))
b = nextPrime(a)
g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]
c = nextPrime(len(f) >> 2)
for _ in [g, h]:
    for __ in range(c): _.insert(0, 0)
    for i in range(len(_) -  c): _[i] += _[i+c]
g, h = [int(''.join([str(_) for _ in __]), 5) for __ in [g, h]]
for _ in [g, h]:
    if _ == g:
        fname = 'g'
    else:
        fname = 'h'
    of = open(f'{fname}.enc', 'wb')
    of.write(long_to_bytes(_))
    of.close()
#输出文件g.enc 19115字节
#输出文件f.enc 19561字节

拿到题目的第一感觉就是要把里面的参数$a,b,c$全给求出来——虽然一开始并没有看懂代码，但有两个基本事实是可以确定的：一是flag一定是CCTF{xxxxxxxx}的格式，二是flag越长，那么输出的g.enc和h.enc文件也越长。因此这里我们可以再开一个相同的加密脚本，设flag为CCTF{000...000}，通过不断加长里面$0$字符加密后输出的文件长度对比，最后确定flag的总长度为$32$，$(a,b,c)=(257,263,67)$。

确定了里面的内容之后，这个时候就直接一步一步地求逆就行了，就是一位一位的减而已，难度不是很大，并且整个过程就用了g.enc一个文件。

当然，个人认为题目给了你两个文件，可能是存在通过不爆破flag的长度，而是真正通过文件g,h来计算flag的长度，进而计算粗话三个参数的值的。待考证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
Cg=open("g.enc","rb").read()
Cg=bytes_to_long(Cg)
Garr=[]
while Cg:
    Garr.append(Cg%5)
    Cg//=5
for i in range(67,len(Garr)):
    Garr[i]=Garr[i]-Garr[i-67]
Garr=Garr[::-1][67:]
for i in range(256*256):
    assert Garr[i]==Garr[i+256]
Garr=Garr[:256]
for i in range(254,-1,-1):
    Garr[i]-=Garr[i+1]    
assert Garr.count(2)==0
m=0
for i in Garr:
    m<<=1
    m|=i
print(long_to_bytes(m))
#CCTF{_how_finD_7h1s_1z_s3cr3T?!}

4.hamul

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from flag import flag
nbit = 64
while True:
	p, q = getPrime(nbit), getPrime(nbit)
	P = int(str(p) + str(q))
	Q = int(str(q) + str(p))
	PP = int(str(P) + str(Q))
	QQ = int(str(Q) + str(P))
	if isPrime(PP) and isPrime(QQ):
		print(PP,QQ)
		break
n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
	c = pow(m, 65537, n)
	print('n =', n)
	print('c =', c)

这里又是一个很有意思的RSA的题目——在生成$p,q$的时候，先生成两个$64$比特的较小素数，然后基于这两个小素数直接连接式组合，得到了大素数，最后乘起来得到了最后的$n$。

由于这种直接组合他是受到了十进制位数的影响的，但$2^{63}=9223372036854775808$，$2^{64}=18446744073709551616$，也就是说，生成的素数有是$20$位十进制数的可能，也有可能是$19$位十进制数的可能。这样根据排列组合就有三种情况：两个$20$位十进制数的素数、一个$19$位，一个$20$位十进制数的素数，也有可能是两个$19$位十进制数的素数。由于直接连接，因此乘数会不一样，因此必须先定性。

首先设$p,q$均为$10^{19}$，发现组合后数值比$n$大，然后设$p,q$均为$10^{19}-1$，发现组合后数值比$n$小了。因此最终定性——$p,q$的十进制位数，一个是$20$，一个是$19$。不妨设$\dfrac{\ln p}{\ln 10}=20,\dfrac{\ln q}{\ln 10}=19$。记int(str(p)+str(q))为$[pq]$，那么我们可以得到下面$4$个式子：
$$
[pq]=10^{19}p+q
$$

$$
[qp]=10^{20}q+p
$$

$$
[pqqp]=10^{58}p+10^{39}q+10^{20}q+p
$$

$$
[qppq]=10^{59}q+10^{39}p+10^{19}p+q
$$

与此同时，我们还可以得到：$\dfrac{\ln pq}{\ln10}=\dfrac{\ln q^2}{\ln10}=38$，$\dfrac{\ln p^2}{\ln10}=39$。也就是，所有的已知量可以直接用下面这个图来表示

1

因此，$n=[pqqp]×[qppq]=((10^{58}+1)p+(10^{39}+10^{20})q)×((10^{39}+10^{19})p+(10^{59}+1)q)$。

化简一下，可以得到： $p^2$的系数是$(10^{58}+1)(10^{39}+10^{19})=10^{97}+10^{77}+10^{39}+10^{19}$
$q^2$的系数是$(10^{39}+10^{20})(10^{59}+1)=10^{98}+10^{79}+10^{39}+10^{20}$
$pq$的系数是$(10^{58}+1)(10^{59}+1)+(10^{39}+10^{20})(10^{39}+10^{19})$，该结果化简为$10^{117}+10^{78}+2×10^{59}+2×10^{58}+10^{39}+1$

那么我们就可以得到下面这个图了

2

很显然，我们可以看出在$10^{137}$往上和$10^{18}$往下都是只有$pq$的高位和低位的，但这样一组合后，$pq$的值的中间一位是不知道的。因此考虑到$n$的$10^{136}$的一位可能有一位进位，因此我们截取$n-10^{136}$整除$10^{136}$的值和$n \mod 10^{19}$的值，就可以得出$pq$了，然后分解即可得到$p,q$。最后按照题目的构造方法求解就行了。(也可以盲猜$p^2$的最低位，因为$p^2$的最低位只有可能是$1$或者$9$），然后利用$n$的$10^{19}$那一位

1
2
3
4
5
6
#Sagemath
n=9802...4043
n-=10**136
H,L=n//10**136,n%10**19
factor(int(str(H)+str(L)))
#9324884768249686093 * 10512422984265378151
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from given import n,c
from Crypto.Util.number import *
def getpq(p,q):
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    return PP,QQ
p,q=9324884768249686093 , 10512422984265378151
p,q=getpq(p,q)
phi=(p-1)*(q-1)
d=inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))
#CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}

5.KEYBASE

一个远程交互题，先看看是什么内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from Crypto.Util import number
from Crypto.Cipher import AES
import os, sys, random
from flag import flag
def keygen():
	iv, key = [os.urandom(16) for _ in '01']
	return iv, key
def encrypt(msg, iv, key):
	aes = AES.new(key, AES.MODE_CBC, iv)
	return aes.encrypt(msg)
def decrypt(enc, iv, key):
	aes = AES.new(key, AES.MODE_CBC, iv)
	return aes.decrypt(enc)
def die(*args):
	pr(*args)
	quit()
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
def sc():
	return sys.stdin.readline().strip()
def main():
	border = "+"
	pr(border*72)
	pr(border, " hi all, welcome to the simple KEYBASE cryptography task, try to    ", border)
	pr(border, " decrypt the encrypted message and get the flag as a nice prize!    ", border)
	pr(border*72)
	iv, key = keygen()
	flag_enc = encrypt(flag, iv, key).hex()
	while True:
		pr("| Options: \n|\t[G]et the encrypted flag \n|\t[T]est the encryption \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 'g':
			pr("| encrypt(flag) =", flag_enc)
		elif ans == 't':
			pr("| Please send your 32 bytes message to encrypt: ")
			msg_inp = sc()
			if len(msg_inp) == 32:
				enc = encrypt(msg_inp, iv, key).hex()
				r = random.randint(0, 4)
				s = 4 - r
				mask_key = key[:-2].hex() + '*' * 4
				mask_enc = enc[:r] + '*' * 28 + enc[32-s:]
				pr("| enc =", mask_enc)
				pr("| key =", mask_key)
			else:
				die("| SEND 32 BYTES MESSAGE :X")
		elif ans == 'q':
			die("Quitting ...")
		else:
			die("Bye ...")
if __name__ == '__main__':
	main()

算法实际上看起来还是很简单的，就是一个AESCBC的主动攻击，先连上去看看，以下是连上去后的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
huangx607087@huangx607087-virtual-machine:~/桌面/CTF/Apr-Jul 21$ python 7.py
[+] Opening connection to 01.cr.yp.toc.tf on port 17010: Done
[*] Switching to interactive mode
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+  hi all, welcome to the simple KEYBASE cryptography task, try to     +
+  decrypt the encrypted message and get the flag as a nice prize!     +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options: 
|    [G]et the encrypted flag 
|    [T]est the encryption 
|    [Q]uit
$ g
| encrypt(flag) = b27e9095ded98a14bdb678e3a30fbbfc79b9cefc9a71b2c963804ce692e0b61e
| Options: 
|    [G]et the encrypted flag 
|    [T]est the encryption 
|    [Q]uit
$ t
| Please send your 32 bytes message to encrypt: 
$ 00000000000000000000000000000000
| enc = 9a****************************3d531aec9dfc944f408d4df08e8f25aeaa
| key = 52ab970fd21f2526aa7421630068****
| Options: 
|    [G]et the encrypted flag 
|    [T]est the encryption 
|    [Q]uit
[*] Got EOF while reading in interactive

我们得到了flag的密文，同时也得到了自己发过去的一组明文的加密结果——但我们发现到最后我们只知道选择明文的后半段的加密结果，前半段的加密结果我们是不知道的。

先来看一下AESCBC的加密结构：

3

很显然，由于密钥只被省略了4位，因此我们可以爆破这个密钥，然后将flag密文的前半段内容作为iv，后半段内容作为AES解密密文，然后进行解密，如果出现了可读的内容，那就算解密成功——因此我们很快地得到了flag的后半段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from Crypto.Cipher import AES
from string import printable
cipher=0xb27e9095ded98a14bdb678e3a30fbbfc79b9cefc9a71b2c963804ce692e0b61e
key=0x52ab970fd21f2526aa74216300680000
cipher=long_to_bytes(cipher)
c1,c2=cipher[:16],cipher[16:]
def check(s):
    for i in s[:15]:
        #print(chr(i))
        if chr(i) not in printable:
            return 0
    return 1
for i in range(65536):
    K=long_to_bytes(key+i)
    aes=AES.new(K, AES.MODE_CBC, c1)
    m2=aes.decrypt(c2)
    if(check(m2)):
        print(m2,K)
"""
m2=b'_7He_5eCrET_1V?}'
K=b'R\xab\x97\x0f\xd2\x1f%&\xaat!c\x00h\x86\xeb'
"""

但是求flag的前半段，就需要用到求一开始的iv了。这就需要用到我们对服务器发送的结果进行解了。

注意到第二段明文在加密前与第一段密文进行了异或，而根据异或的性质，如果我们iv是第一段密文，解密出来就是第二段明文——所以iv如果使第二段明文，解密出来就是第一段密文。而我们发送的32个字符0是已知的内容，第二段密文也是已知内容。因此我们就可以得到第一段的完整密文。

根据完整密文、key、完整明文，我们就可以求出iv了，这个内容我们会在后面一篇专门研究AES的博客里讲解相关内容，这次就先上个代码（PART 3），可以先自己了解一下是怎么一回事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Util.number import *
from Crypto.Cipher import AES
from string import printable
cipher=0xb27e9095ded98a14bdb678e3a30fbbfc79b9cefc9a71b2c963804ce692e0b61e
key=0x52ab970fd21f2526aa74216300680000
cipher=long_to_bytes(cipher)
c1,c2=cipher[:16],cipher[16:]
def check(s):
    for i in s[:15]:
        #print(chr(i))
        if chr(i) not in printable:
            return 0
    return 1
for i in range(65536):
    K=long_to_bytes(key+i)
    aes=AES.new(K, AES.MODE_CBC, c1)
    m2=aes.decrypt(c2)
    if(check(m2)):
        print(m2,K.hex())
#------PART 2 BELOW----------#
m2=b'_7He_5eCrET_1V?}'
m10,m11=b'0'*16,b'0'*16
c11=long_to_bytes(0x531aec9dfc944f408d4df08e8f25aeaa)
K=b'R\xab\x97\x0f\xd2\x1f%&\xaat!c\x00h\x86\xeb'
aes=AES.new(K, AES.MODE_CBC,m11)
c10=aes.decrypt(c11)
print(c10.hex())
#------PART 3 BELOW----------#
fakeiv=b'a'*16
fakeivaes=AES.new(K,AES.MODE_CBC,fakeiv)
fakem=fakeivaes.decrypt(c10)
encmsg=long_to_bytes(bytes_to_long(fakem)^bytes_to_long(fakeiv))
iv=long_to_bytes(bytes_to_long(encmsg)^bytes_to_long(m10))
print(iv.hex())
#------PART 4 BELOW----------#
aesfinal=AES.new(K,AES.MODE_CBC,iv)
m1=aesfinal.decrypt(c1)
print(m1+m2)
"""
b'_7He_5eCrET_1V?}' 52ab970fd21f2526aa742163006886eb
9a941fc86867bc19161554cc6f08a73d
1c27639adabb0672f976a6d979d0d981
b'CCTF{h0W_R3cOVER_7He_5eCrET_1V?}'
"""

6.总结

这几道题还是稍微有一点难度的——尤其是第4题和第5题。

7月摸了几次🐟，开发了机器人blockbot，进入8月突然感觉事情真的好多啊，不能再摸鱼了。。。。

文章作者: huangx607087
文章链接: http://example.com/2021/08/03/CryptoCTFWriteUp1/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
WriteUp
赏
  目录