CryptoCTF Wp 2

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

CryptoCTF WriteUp 2 By huangx607087

0.About

再探CryptoCTF，这里面有些题目难度确实还是比较大的，这几天的解题进度也基本上是一天一题的进度吧，不过确实非常扩展思维的。然而我这么菜的肯定比不上群里那些大佬们。今天的RARCTF还有很多东西没看呢，事情的确多得有亿点点忙不过来了。

好在最近外面疫情严重，自己基本上也就一天待在家里，打CTF，配置Blockbot，摸鱼摸鱼在摸鱼，Hadoop的项目还没测试呢，院科协也有两天没打卡，好在还是补上了。

希望新学期能正常开学，我不想上网课，我只是期末想考61而已。

1.Tuti

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
l = len(flag)
m_1, m_2 = flag[: l // 2], flag[l // 2:]
x, y = bytes_to_long(m_1), bytes_to_long(m_2)
k = '''
000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe91124fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
'''.replace('\n', '')
assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))

很显然，这道题告诉你了两段密文之间的关系：$(x^2+1)(y^2+1)-2(x-y)(xy-1)=4(k+xy)$。

第一反应肯定是要把$xy$之类的未知量移到等号一边，然后等号两边展开，自己就什么也看不出来了。

然后我想到了sagemath，这个东西可以分解因数，说不定可以分解因式呢——貌似确实可行，$4xy$移到左边后对左边式子的分解因式结果是$(x+1)^2(y+1)^2$，这确实是一个非常好的结果，很多大佬都是手搓的——然而自己就不行了，因为自己解一元二次方程如果二次项不为$1$自己就分解不出这个式子了（比如$2x^2+7x+3=0$，笔者遇到直接上求根公式——define huangx607087 fw）。

然后对右边直接开平方就是$(x+1)(y+1)$的值了，至于分解右边的那个数字（实测是$14$个因数），根据$x,y$的位数差不多，在加上flag一定是可读字符，直接枚举各种可能性就行了。

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
from Crypto.Util.number import *
from gmpy2 import iroot
from string import printable
def check(a,b):
    if abs(len(a)-len(b))>1:
        return 0
    for i in a:
        if chr(i) not in printable:
            return 0
    for i in b:
        if(chr(i)) not in printable:
            return 0
    return 1
k = '''
000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe9112
4fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe
71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
'''.replace('\n', '')
k=int(k,16)
mul=iroot(4*k,2)
assert mul[1]
mul=mul[0]
S=[2,2,3,11,11,19,47,71,3449,11953,5485619,2035395403834744453,17258104558019725087,1357459302115148222329561139218955500171643099]
for i in range(2**14):
    M1,M2=1,1
    for j in range(14):
        if i&(1<<j):
            M1*=S[j]
        else:
            M2*=S[j]
    a,b=long_to_bytes(M1-1),long_to_bytes(M2+1)
    if(check(a,b)):
        print(a+b)
#CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}

最后解出来为什么又是丢番图方程，看来CryptoCTF出题人对丢番图情有独钟啊，这让我想起来当年那个科协里的那个对话

1
2
A:让我们讨论一下丢番图
B:番图是什么，为什么要丢掉

2.RSAphantine

看名字，很明显，又是跟丢番图有关的

题目就给出了一个方程组，和一个RSA加密的结果

1
2
3
4
5
6
7
8
9
10
2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
p = nextPrime(x**2 + z**2 + y**2 << 76)
q = nextPrime(z**2 + y**3 - y*x*z ^ 67)
n, e = p * q, 31337
m = bytes_to_long(FLAG)
c = pow(m, e, n)
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672

第一次乍一看，似乎并没有什么思路，因为三个都是高次方程的组合，三个未知数，确实是求不出来了的。想要消元降次也几乎不可能——因为自己实测过了（

不过这个时候可以把重点聚焦到第一个和第三个式子上，因为第一个式子和第三个式子都有公共的部分就是$2z^5$，并且这两个式子算出来的结果有很长的高位时相同的，这确实是一个令人怀疑的地方——因此，我们可以猜测：对这两个数字除以$2$后直接开五次方，那么就可以得出$z$的准确值。

事实上确实如此，借助python中的iroot直接开根——可以发现这两个数字除以$2$后开五次方根的结果是一样的，而这个数字我们可以认为是解出来的$z$值——事实上解出来确实如此。

解出来之后，$x,y$两个数字就可以很容易地求出来了——我这边用的是$y^6+zy=a_3-2z^5$这个式子通过二分得出结果的，当然也可以用其他的办法求$y$，求出$y$后就可以直接求$x$了，不过最后$x$是负的令我没想到，但assert对了那就说明没问题了。

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
from gmpy2 import iroot,next_prime
from Crypto.Util.number import *
a1=47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
a2=89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
a3=47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
Tz1,Tz3=iroot(a1//2,5)[0],iroot(a3//2,5)[0]
assert Tz1==Tz3
z=Tz1
x,y=None,None
L,R=0,10**1000
while L<=R:
    M=(L+R)//2
    if(M**6+M*z<a3-2*z**5):
        L=M+1
    if(M**6+M*z>a3-2*z**5):
        R=M-1
    if(M**6+M*z==a3-2*z**5):
        y=M
        break
assert y**6+2*z**5+z*y==a3
x=iroot(a1-2*z**5-y*z,3)
assert x[1]
x=-x[0]
assert x**4 + y**5 + x*y*z ==a2
p = next_prime(x**2 + z**2 + y**2 << 76)
q = next_prime(z**2 + y**3 - y*x*z ^ 67)
c=486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
d=inverse(31337,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))
print(x)
print(y)
print(z)
'''
flag=CCTF{y0Ur_jO8_C4l13D_Diophantine_An4LySI5!}
x=-97319611529501810510904538298668204056042623868316550440771307534558768612892
y=311960913464334198969500852124413736815
z=29896806674955692028025365368202021035722548934827533460297089
'''

3.Onlude

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
#Sagemath
from sage.all import *
from flag import flag
global p, alphabet
p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
flag = flag.lstrip('CCTF{').rstrip('}')
assert len(flag) == 24
def cross(m):
	return alphabet.index(m)
def prepare(msg):
	A = zero_matrix(GF(p), 11, 11)
	for k in range(len(msg)):
		i, j = 5*k // 11, 5*k % 11
		A[i, j] = cross(msg[k])
	return A
def keygen():
	R = random_matrix(GF(p), 11, 11)
	while True:
		S = random_matrix(GF(p), 11, 11)
		if S.rank() == 11:
			_, L, U = S.LU()
			return R, L, U
def encrypt(A, key):
	R, L, U = key
	S = L * U
	X = A + R
	Y = S * X
	E = L.inverse() * Y
	return E
A = prepare(flag)
key = keygen()
R, L, U = key
S = L * U
E = encrypt(A, key)
print(f'E = \n{E}')#E
print(f'L * U * L = \n{L * U * L}')#M1
print(f'L^(-1) * S^2 * L = \n{L.inverse() * S**2 * L}')#M2
print(f'R^(-1) * S^8 = \n{R.inverse() * S**8}')#M10

一道矩阵题，加密方法不难，涉及矩阵运算。

题目给出了密文$E$，还有三个辅助量$M_1=LUL,M_2=L^{-1}S^2L,M_{10}=R^{-1}S^8$。 其中$R$是一个随机矩阵，$L,U$是$S$的$LU$分解，即$S=LU$。加密方法为$E=L^{-1}S(A+R)$，$A$就是明文

这边简单地提一下什么是矩阵的$LU$分解，就是对于任意一个矩阵$M$，可以将其沿主对角线拆分成一个上三角矩阵$U$和一个下三角矩阵$L$，使得$LU=S$，其中$\det L=1,\det U=\det S$，因此这种分解方法是唯一的。

由于$M_1=LUL=SL,M_2=L^{-1}S^2L$，根据矩阵的逆运算，因此$M_2^{-1}=L^{-1}S^{-2}L$，因此我们可以有：
$$
M_3=M_1M_2^{-1}=SLL^{-1}S^{-2}L=S^{-1}L=U^{-1}L^{-1}L=U^{-1}
$$
很显然，如果我们想要凑$S$出来，那就要消去$L$，由于我们发现$M_3=S^{-1}L,M_1=SL$，因此我们计算$M_1M_3^{-1}$，有
$$
M_1M_3^{-1}=SLL^{-1}S=S^2
$$
有了$S^2$，那么我们可以计算出$S^8$，进而计算出$S^{-8}$。故
$$
R=(M_{10}(S^{-8}))^{-1}=S^8M_{10}^{-1}
$$
由于$M_3=U^{-1}$，因此对$M_3$直接求逆就得到了$U$。到目前为止，$R,U$都得到了，而$E=L^{-1}S(A+R)=U(A+R)=UA+UR$，因此$A$很容易就可以得到了。然后根据他的规则，将矩阵里对应的数字转化成字典中的内容，这道题就解出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
E=[[25,55,61,28,11,46,19,50,37,5,21],[20,57,39,9,25,37,63,31,70,15,47],[56,31,1,1,50,67,38,14,42,46,14],[42,54,38,22,19,55,7,18,45,53,39],[55,26,42,15,48,6,24,4,17,60,64],[1,38,50,10,19,57,26,48,6,4,14],[13,4,38,54,23,34,54,42,15,56,29],[26,66,8,48,6,70,44,8,67,68,65],[56,67,49,61,18,34,53,21,7,48,32],[15,70,10,34,1,57,70,27,12,33,46],[25,29,20,21,30,55,63,49,11,36,7]]
M1=[[50,8,21,16,13,33,2,12,35,20,14],[36,55,36,34,27,28,23,21,62,17,8],[56,26,49,39,43,30,35,46,0,58,43],[11,25,25,35,29,0,22,38,53,51,58],[34,14,69,68,5,32,27,4,27,62,15],[46,49,36,42,26,12,28,60,54,66,23],[69,55,30,65,56,13,14,36,26,46,48],[25,48,16,20,34,57,64,62,61,25,62],[68,39,11,40,25,11,7,40,24,43,65],[54,20,40,59,52,60,37,14,32,44,4],[45,20,7,26,45,45,50,17,41,59,50]]
M2=[[34,12,70,21,36,2,2,43,7,14,2],[1,54,59,12,64,35,9,7,49,11,49],[69,14,10,19,16,27,11,9,26,10,45],[70,17,41,13,35,58,19,29,70,5,30],[68,69,67,37,63,69,15,64,66,28,26],[18,29,64,38,63,67,15,27,64,6,26],[0,12,40,41,48,30,46,52,39,48,58],[22,3,28,35,55,30,15,17,22,49,55],[50,55,55,61,45,23,24,32,10,59,69],[27,21,68,56,67,49,64,53,42,46,14],[42,66,16,29,42,42,23,49,43,3,23]]
M10=[[51,9,22,61,63,14,2,4,18,18,23],[33,53,31,31,62,21,66,7,66,68,7],[59,19,32,21,13,34,16,43,49,25,7],[44,37,4,29,70,50,46,39,55,4,65],[29,63,29,43,47,28,40,33,0,62,8],[45,62,36,68,10,66,26,48,10,6,61],[43,30,25,18,23,38,61,0,52,46,35],[3,40,6,45,20,55,35,67,25,14,63],[15,30,61,66,25,33,14,20,60,50,50],[29,15,53,22,55,64,69,56,44,40,8],[28,40,69,60,28,41,9,14,29,4,29]]
E,M1,M2,M10=matrix(GF(71),E),matrix(GF(71),M1),matrix(GF(71),M2),matrix(GF(71),M10)
M3=M1*(M2^-1)
S2=M1*(M3^-1)
R=(M10*S2^-4)^-1
U=M3^-1
UA=E-U*R
A=M3*UA
Dic='=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
F,K="",0
while len(F)<24:
    F+=Dic[A[K//11][K%11]]
    K+=5
print('CCTF{'+F+'}')
#CCTF{LU__D3c0mpO517Ion__4L90?}

4.Triplet

一个远程交互的题目，看起来似乎有点难度，也有点脑洞

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
55
56
57
58
59
60
61
62
63
64
65
66
67
from Crypto.Util.number import *
from random import randint
import sys
from flag import FLAG
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 talented cryptographers, the mission is to find the three RSA   ", border)
	pr(border, " modulus with the same public and private exponent! Try your chance!", border)
	pr(border*72)
	nbit = 160
	while True:
		pr("| Options: \n|\t[S]end the three nbit prime pairs \n|\t[Q]uit")
		ans = sc().lower()
		order = ['first', 'second', 'third']
		if ans == 's':
			P, N = [], []
			for i in range(3):
				pr("| Send the " + order[i] + " RSA primes such that nbit >= " + str(nbit) + ": p_" + str(i+1) + ", q_" + str(i+1) + " ")
				params = sc()
				try:
					p, q = params.split(',')
					p, q = int(p), int(q)
				except:
					die("| your primes are not valid!!")
				if isPrime(p) and isPrime(q) and len(bin(p)[2:]) >= nbit and len(bin(q)[2:]) >= nbit:
					P.append((p, q))
					n = p * q
					N.append(n)
				else:
					die("| your input is not desired prime, Bye!")
			if len(set(N)) == 3:
				pr("| Send the public and private exponent: e, d ")
				params = sc()
				try:
					e, d = params.split(',')
					e, d = int(e), int(d)
				except:
					die("| your parameters are not valid!! Bye!!!")
				phi_1 = (P[0][0] - 1)*(P[0][1] - 1)
				phi_2 = (P[1][0] - 1)*(P[1][1] - 1)
				phi_3 = (P[2][0] - 1)*(P[2][1] - 1)
				if 1 < e < min([phi_1, phi_2, phi_3]) and 1 < d < min([phi_1, phi_2, phi_3]):
					b = (e * d % phi_1 == 1) and (e * d % phi_2 == 1) and (e * d % phi_3 == 1)
					if b:
						die("| You got the flag:", FLAG)
					else:
						die("| invalid exponents, bye!!!")
				else:
					die("| the exponents are too small or too large!")
			else:
				die("| kidding me?!!, bye!")
		elif ans == 'q':
			die("Quitting ...")
		else:
			die("Bye ...")
if __name__ == '__main__':
	main()

简单看过代码后，就是你要构造三个不同的RSA模数$n_1,n_2,n_3$，大小必须超过$320$位（也就是两个$160$位的素数相乘）。使得这三个模数拥有一组相同的$(e,d)$，使得$(e,d)$均小于三个$\phi$值。简而言之就是要让$ed$的值很小且不能为$1$。

由于$ed\equiv 1 \pmod \phi$。根据扩展中国剩余定理，由于三个$\phi$不同，但$ed$相同，因此这里$ed$除了$1$，只能让$\mathrm{lcm}(\phi_1,\phi_2,\phi_3)$的值足够小。换句话就是让$\gcd(\phi_1,\phi_2,\phi_3)$足够大。

因此，我们可以构造三个素数$p,q,r=k_ig+1$，其中$i$取值为$1$到$3$，$k_i$远小于$g$，而这个$g$，就是我们所想要的$\gcd(\phi_1,\phi_2,\phi_3)$。我们可以构造$g=2^{158},2^{159},2^{160}$，当然这边为了方便起见，我在这里的$g$选择了$10$的次幂，因为这样看起来顺眼（x

于是可以构造： $p=1537000000000000000000000000000000000000000000001$，$q=1545000000000000000000000000000000000000000000001$，$r=1591000000000000000000000000000000000000000000001$

，这样子三个$\phi$的公约数就很大了。然后我们分别对服务器发送$p,q$，$p,r$，$q,r$，完成第一步。

然后我们计算$L=\mathrm{lcm}(\phi_1,\phi_2,\phi_3)$，得：
$$
L=3778092015000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
$$
分解这个$L$，有
$$
31×32251×3778919598392047858481007340607593062880770888824652598919163296761990876001844403924459456621
$$
因此我们有$e=31×32251=999781$，$d=3778919598392047858481007340607593062880770888824652598919163296761990876001844403924459456621$。直接发送过去就可以得到最后的结果

1

5.Tiny ECC

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
from mini_ecdsa import *#这个包里集成了一些ECC的算法，与题目无关，此处略去
from Crypto.Util.number import *
from flag import flag
def tonelli_shanks(n, p):
	if pow(n, int((p-1)//2), p) == 1:
			s = 1
			q = int((p-1)//2)
			while True:
				if q % 2 == 0:
					q = q // 2
					s += 1
				else:
					break
			if s == 1:
				r1 = pow(n, int((p+1)//4), p)
				r2 = p - r1
				return r1, r2
			else:
				z = 2
				while True:
					if pow(z, int((p-1)//2), p) == p - 1:
						c = pow(z, q, p)
						break
					else:
						z += 1
				r = pow(n, int((q+1)//2), p)
				t = pow(n, q, p)
				m = s
				while True:
					if t == 1:
						r1 = r
						r2 = p - r1
						return r1, r2
					else:
						i = 1
						while True:
							if pow(t, 2**i, p) == 1:
								break
							else:
								i += 1
						b = pow(c, 2**(m-i-1), p)
						r = r * b % p
						t = t * b ** 2 % p
						c = b ** 2 % p
						m = i
	else:
		return False
def random_point(p, a, b):
	while True:
		gx = getRandomRange(1, p-1)
		n = (gx**3 + a*gx + b) % p
		gy = tonelli_shanks(n, p)
		if gy == False:
			continue
		else:
			return (gx, gy[0])
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, "  Dual ECC means two elliptic curve with same coefficients over the ", border)
	pr(border, "  different fields or ring! You should calculate the discrete log   ", border)
	pr(border, "  in dual ECCs. So be smart in choosing the first parameters! Enjoy!", border)
	pr(border*72)
	bool_coef, bool_prime, nbit = False, False, 128
	while True:
		pr(f"| Options: \n|\t[C]hoose the {nbit}-bit prime p \n|\t[A]ssign the coefficients \n|\t[S]olve DLP \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 'a':
			pr('| send the coefficients a and b separated by comma: ')
			COEFS = sc()
			try:
				a, b = [int(_) for _ in COEFS.split(',')]
			except:
				die('| your coefficients are not valid, Bye!!')
			if a*b == 0:
				die('| Kidding me?!! a*b should not be zero!!')
			else:
				bool_coef = True
		elif ans == 'c':
			pr('| send your prime: ')
			p = sc()
			try:
				p = int(p)
			except:
				die('| your input is not valid :(')
			if isPrime(p) and p.bit_length() == nbit and isPrime(2*p + 1):
				q = 2*p + 1
				bool_prime = True
			else:
				die(f'| your integer p is not {nbit}-bit prime or 2p + 1 is not prime, bye!!')
		elif ans == 's':
			if bool_coef == False:
				pr('| please assign the coefficients.')
			if bool_prime == False:
				pr('| please choose your prime first.')
			if bool_prime and bool_coef:
				Ep = CurveOverFp(0, a, b, p)
				Eq = CurveOverFp(0, a, b, q)
				xp, yp = random_point(p, a, b)
				P = Point(xp, yp)
				xq, yq = random_point(q, a, b)
				Q = Point(xq, yq)
				k = getRandomRange(1, p >> 1)
				kP = Ep.mult(P, k)
				l = getRandomRange(1, q >> 1)
				lQ = Eq.mult(Q, l)
				pr('| We know that: ')
				pr(f'| P = {P}')
				pr(f'| k*P = {kP}')
				pr(f'| Q = {Q}')
				pr(f'| l*Q = {lQ}')
				pr('| send the k and l separated by comma: ')
				PRIVS = sc()
				try:
					priv, qriv = [int(s) for s in PRIVS.split(',')]
				except:
					die('| your input is not valid, Bye!!')
				if priv == k and qriv == l:
					die(f'| Congrats, you got the flag: {flag}')
				else:
					die('| sorry, your keys are not correct! Bye!!!')
		elif ans == 'q':
			die("Quitting ...")
		else:
			die("Bye ...")

if __name__ == '__main__':
	main()

又是一个交互题，题目是发送一个素数$p$，且$q=2p+1$也是素数，并自定椭圆曲线系数$a,b$，最后在$GF(p),GF(q)$上分别解一次椭圆曲线上的离散对数即可获得flag。

很显然，这边就是要构造一个特殊的曲线，这样才能很容易地解出ECDLP。很显然，最简单的椭圆曲线就是$y^2=x^3$，也就是此时$(0,0)$点在椭圆曲线上。

这里我选择了$p=207700000000000000000000000000000000001$，$q=2p+1=415400000000000000000000000000000000003$，符合题目条件。

但题目规定：$a,b$均不能为$0$，但是题目只说了$ab≠0$——很显然，这是一个漏洞，因为它这边没有取模。因此我们只需要计算$n=pq$，然后将$a,b$的值都定为$n$即可，此处有
$$
n=86278580000000000000000000000000000001038500000000000000000000000000000000003
$$
然后我们利用有限域上的极其特殊的椭圆曲线$y^2=x^3$的求解dlp的公式，就可以求出最终的结果了。

这个公式很简单，设$P(x,y),Q=kP$，定$f(P)=\dfrac x y$，那么：
$$
k=\dfrac {f(Q)}{f(P)}
$$
所以最后的解题过程就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
def solve(p,P,kP):
    fP = P[0]*inverse(P[1],p)%p
    fkP = kP[0]*inverse(kP[1],p)%p
    return fkP*inverse(fP,p)%p
p,q=207700000000000000000000000000000000001,415400000000000000000000000000000000003
n=86278580000000000000000000000000000001038500000000000000000000000000000000003
assert n==p*q
P = (203229899779000076314358233714424355341,60440074750241244164201445769817870587)
kP = (52410058339877917624863834128227223795,49211699144775676781683504862929553688)
Q = (172334393951679208280736138845997145361,20443831011651348736860400696145266671)
lQ = (145705507629923190180573378828332340194,79769406366840777802969722053757749656)
print(solve(p,P,kP),solve(q,Q,lQ))
#27870828690899416876383090452513900161 495768251079805627828936776109738300

最终解题结果：

2

6.总结

这5道题的思维量明显要比前5题的思维量难度大的，尤其是第4题和第5题，是一种全新的题型，直接就是让你构造特殊的素数和特殊的曲线，并在特殊的条件下求解一些难题——这种出题思维还是很不平常的，长见识了。而第1，2题对数感的要求要非常的好，比如近似数，还有那个分解因式（自己的短板，解二次项不为1的方程直接上公式了）

哦对，顺便提一下我在4，5两题里面构造的这种特殊素数：前面$4$位是随机的，中间一堆$0$，最后一个$1$，这种素数还有一个特点，就是$p-1$极度光滑——因为你除掉所有的$10$因数就还剩几千了，说不定以后会在什么题里遇到。

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