CryptoCTF Wp 3

CryptoCTF WriteUp 3 By huangx607087

0.About

这两天又试着做了两题，越来越难，也不知道为什么突然想出去玩了。可能是我太菜了吧，整天就想着摸鱼，还有玩自己的bot。自己也觉得目前这种高压下确实也学不下去了。。CryptoCTF，10天时间，共27题（不包括两个签到题），做了12题，才发现自己AES还没怎么学，过几天得学了。

1.Ferman

题目没有给什么附件，也没给什么别的东西，连上去也就是获得了这些内容：事后发现每次连上去的内容都不一样

1
2
3
4
5
6
7
8
9
10

e = 65537
isPrime(p) = True
isPrime(q) = True
n = p * q
(p - 68)**2 + (q - 21)**2 = 3269551398869642512241103339368232143434651590868728507355028871910904078338475713578589303262711916750081690332228411866186437460090515664367924851061597536376468220126174928460974557959918017310829528466648372027415953708229130137453296795856556992151797166136297164760842319106620707383001374254866888310103550740311206689346583293426983738736830982428061012656462973476605155219794719926468254375880711360433969868621585139970748294149897216559703209916963866764044804843930101
m = bytes_to_long(flag)
c = pow(m, e, n)
encrypt(flag) = 1129211205327521826941184390751899392925131920702773335891856613366505909410806899952280135028258342388876508412491223980744621251519356334925886554708700046795586651759818594942792724304963126886525647156824946261462652999258718878583493830408651605063608560126743568477583982018994138693209851132638425082838330606425689175153335674463330275554714300992424492537349839226295570411855545265032582057186364143746536638616951994802510125990494183100416729103612848938139639080478806

很显然，这里有一个平方和的形式$(p-68)^{2}+(q-21)^{2}$，想到之前在数论概论上看到过关于将某个素数拆成$2$个数的平方和的算法，因此猜测这里可能会用得到。

但是很显然，等号右边的这个数字我感觉看起来不是素数——因此我分解了一下它：这个数的表达式为
$$
p^7q^7=881^7×501130658240331371910024384924248009800259836627015214670629231821^7
$$
看来是一个数的$7$次方，并且这两个素数都满足模$4$余$1$的条件，因此可以分解成两个平方和。

其中：$p=25^2+16^2$，$q=707783305101597694376018027941686^2+13170089589294489230801449847315^2$。

然后自己就根据数上的方法，设$g=p^3q^3$，然后用公式$(u^2+v^2)(a^2+b^2)=(ua+vb)^2+(va-ub)^2$，然后将两个平方项同时乘上$g$，然后检验的时候发现了问题——构造出来的平方和确实等于等号右边的数值（设为$x$），但两个数无论是加上$68$还是加上$21$，都不是素数。

然后我调换了一下$a,b,u,v$的位置，用同样的方法试了一下，貌似还是不对——或许，一些合数拆解成平方和的时候，也许有不同的方法。从原理上来讲，将一个素数拆解平方和的原理是基于的复数计算：$p=(a+b\mathrm i)(a-b\mathrm i)=a^2+b^2$。因此，对于上面两个数来说，可以写成如此的形式：$x=p^7q^7=(a+b\mathrm i)^7(a-b\mathrm i)^7(c+d\mathrm i)^7(c-d\mathrm i)^7$。因此，最终的$x$可以由这4个复数可以自由组合。构成一堆共轭复数，其乘积为$x$。

因此我们直接枚举其指数即可，但考虑到每一次的$(a,b),(u,v)$的取值不敢定，因此这$4$种情况也要考虑一下，所以到最后一共大概是$16384$种情况，直接枚举指数即可。

不过据说sagemath可以解$x^2+y^2=k$的情况，但解不出$x^2+y^2=k^7$的情况，我这里未实现

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
from Crypto.Util.number import *
class Complex:
    def __init__(self,x,y=0):
        self.real=x
        self.imag=y
    def Pr(self):
        print(self.real,self.imag)
def Cmul(a,b):
    Real=a.real*b.real-a.imag*b.imag
    Imag=a.real*b.imag+b.real*a.imag
    return Complex(Real,Imag)
def Cpow(a,e):
    Res=Complex(1)
    e=bin(e)[2:]
    for i in e:
        Res=Cmul(Res,Res)
        if i=='1':
            Res=Cmul(Res,a)
    return Res
def Extract(a):
    if a.imag*a.real==0:
        return max(abs(a.imag),abs(a.real))
    else:
        return 0
def check(p,q):
    if p==0 and q==0:
        return 0
    if (p&1)==(q&1):
        return 0
    if p&1>q&1:
        p,q=q,p
    #print(p+21,q+68)
    if isPrime(p+21) and isPrime(q+68):
        return p+21,q+68
    else:
        return 0
def combine(a,b,u,v):
    z1,z2,z3,z4=Complex(a,b),Complex(a,-b),Complex(u,v),Complex(u,-v)
    for i in range(8):
        for j in range(8):
            for k in range(8):
                for l in range(8):
                   r,s=Complex(1),Complex(1)
                   r=Cmul(Cmul(Cmul(Cpow(z1,i),Cpow(z2,j)),Cpow(z3,k)),Cpow(z4,l))
                   s=Cmul(Cmul(Cmul(Cpow(z1,7-i),Cpow(z2,7-j)),Cpow(z3,7-k)),Cpow(z4,7-l))
                   assert Extract(Cmul(r,s))==3269551398869642512241103339368232143434651590868728507355028871910904078338475713578589303262711916750081690332228411866186437460090515664367924851061597536376468220126174928460974557959918017310829528466648372027415953708229130137453296795856556992151797166136297164760842319106620707383001374254866888310103550740311206689346583293426983738736830982428061012656462973476605155219794719926468254375880711360433969868621585139970748294149897216559703209916963866764044804843930101
                   #p,q=Extract(r),Extract(s)
                   p,q=r.real,r.imag
                   if check(p,q):
                       print(check(p,q))
a,b=25, 16
u,v=13170089589294489230801449847315,707783305101597694376018027941686
combine(a,b,u,v)
combine(a,b,v,u)
combine(b,a,u,v)
combine(b,a,v,u)
'''
p=1367291984765267853480661817191973536196367067942219441094381051490756487227187103253395714048175579203366540871321878072980687796968653546138925128020808999936761834389329636911488062911510719917508501565645614971839792438943508734857447351
q=1183243012768846673615661480426536150503870303790817990055385067161241136558606680343879248138238749140297647629816389281594627601494973568019878375082598163753648048811668067008108623661611923189136565406992832328516940073816055184727720669
'CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}
'''

当然，combine函数也可以这样优化一下

1
2
3
4
5
6
7
8
9
10
11
12
def combine(a,b,u,v):
    z1,z2,z3,z4=Complex(a,b),Complex(a,-b),Complex(u,v),Complex(u,-v)
    print(Extract(Cmul(z1,z2)),Extract(Cmul(z3,z4)))
    for i in range(8):
        for k in range(8):
            r,s=Complex(1),Complex(1)
            r=Cmul(Cmul(Cmul(Cpow(z1,i),Cpow(z2,7-i)),Cpow(z3,k)),Cpow(z4,7-k))
            s=Cmul(Cmul(Cmul(Cpow(z1,7-i),Cpow(z2,i)),Cpow(z3,7-k)),Cpow(z4,k))
            assert r.imag == -s.imag
            assert r.real == s.real
            if check(abs(r.real),abs(r.imag)):
                print(check(abs(r.real),abs(r.imag)))

当然，这里再重现一下上次的将一共模$4$余$1$的素数分解成两个平方和的情形，即$p=a^2+b^2$解$(a,b)$的情况，这个脚本之前在NumberTheory 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
from random import *
from os import urandom
from Crypto.Util.number import *
def getA(p):
    assert(p%4==1)
    while 1:
        t=bytes_to_long(urandom(195))%p
        s=pow(t,(p-1)//4,p)
        if(pow(s,2,p)==p-1):
            return s
def getAns(A,B,M,p):
    #print(A,B,M,p)
    if(M==1):
        return (abs(A),abs(B))
    #print(A,B,M,p)
    u,v=A%M,B%M
    if(u>M//2):
        u-=M
    if(v>M//2):
        v-=M
    assert((u**2+v**2)%M==0 and (A**2+B**2)%M==0 )
    r=(u**2+v**2)//M
    A2=(u*A+v*B)//M
    B2=(-u*B+v*A)//M
    return getAns(A2,B2,r,p)
def solve(p):
    A=getA(p)
    B=1
    assert(A**2+B**2)%p==0
    M=(A**2+B**2)//p
    return getAns(A,B,M,p)
print(solve(881))
#(25, 16)

扩展：形如
$$
m=M^2\prod_{i=1}^n p_i
$$
的整数$m$可以写成两个平方和的形式，其中$p_i$是各不相同且模$4$余$1$的素数，$M$是整数

2.maid

先看一下题目：

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import *
from flag import flag
global nbit
nbit = 1024
def keygen(nbit):
	while True:
		p, q = [getStrongPrime(nbit) for _ in '01']
		if p % 4 == q % 4 == 3:
			return (p**2)*q, p

def encrypt(m, pubkey):
	if GCD(m, pubkey) != 1 or m >= 2**(2*nbit - 2):
		return None
	return pow(m, 2, pubkey)
def flag_encrypt(flag, p, q):
	m = bytes_to_long(flag)
	assert m < p * q
	return pow(m, 65537, p * q)
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 Rooney Oracle, you can encrypt and decrypt any ", border)
	pr(border, "  message in this oracle, but the flag is still encrypted, Rooney   ", border)
	pr(border, "  asked me to find the encrypted flag, I'm trying now, please help! ", border)
	pr(border*72)
	pubkey, privkey = keygen(nbit)
	p, q = privkey, pubkey // (privkey ** 2)
	while True:
		pr("| Options: \n|\t[E]ncrypt message \n|\t[D]ecrypt ciphertext \n|\t[S]how encrypted flag \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 'e':
			pr("| Send the message to encrypt: ")
			msg = sc()
			try:
				msg = int(msg)
			except:
				die("| your message is not integer!!")
			pr(f"| encrypt(msg, pubkey) = {encrypt(msg, pubkey)} ")
		elif ans == 'd':
			pr("| Send the ciphertext to decrypt: ")
			enc = sc()
			try:
				enc = int(enc)
			except:
				die("| your message is not integer!!")
			pr(f"| decrypt(enc, privkey) = {decrypt(enc, privkey)} ")
		elif ans == 's':
			pr(f'| enc = {flag_encrypt(flag, p, q)}')
		elif ans == 'q':
			die("Quitting ...")
		else:
			die("Bye ...")
if __name__ == '__main__':
	main()

可以看出：$p\equiv q\equiv 3 \pmod 4$，因此若$x^2\equiv a \pmod p$，那么可以直接得到$x\equiv a^{(p+1)/4} \pmod p$。

题目给出了公钥是$n=p^2q$，私钥是$p$，而这里我们可以自定义明文$m$，题目返回$c\equiv m^2 \pmod n$，并且如果我们发送$c$，服务器也可以给我们返回解密的结果$m$。——不过解密函数这里并没有告诉我们。

我们发现这里的指数是$2$，一开始我手动发送了个$10$进行加密，服务器返回了$100$，说明也仅仅是平方而已，如果不取模，我们可以直接通过二分的方法爆破$n=p^2q$——因为总存在一个临界点$r$使得$r^2<n,(r+1)^2>n$，而这里$(r+1)^2$（真实值）减去服务器返回的取模后的值，就是我们所要求的$n$了。

不过据说也可以对服务器发送$m_0,k_1m_0,k_2m_0$，然后求公约数也可以，但这里$m$似乎很大的样子，因此我没有尝试过——但这确实只需要$3$次交互就能求出$n$，后期会尝试一下——因为整个二分爆破过程很长，用了$10$分钟。

然后我们就只需要一次解密即可——对服务器发送我们自己的密文$c’$，获得其解密结果$m’$，计算$\gcd(n,m’^2-c’)$。就有可能获得$p^2$的值，然后就能解密了。但这是个概率算法，据说成功与否与$c’$是否是$q$的二次剩余有关。

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
from pwn import *
from Crypto.Util.number import *
from datetime import *
from os import urandom
def getsqrt(x):
	L,R=0,x
	while L<=R:
		M=(L+R)//2
		if M**2 >x:
			R=M-1
		elif M**2<x:
			L=M+1
		else:
			return M
T1=str(datetime.now())
print(T1)
sh=remote("04.cr.yp.toc.tf",38010)
sh.recvuntil(b"]uit")
sh.send(b"s\n")
sh.recvuntil(b"c = ")
c=int(sh.recvline(keepends=False))
#print(c)
L=1000000000000
while True:
	sh.recvuntil(b"]uit")
	sh.send(b"e\n")
	sh.recvuntil(b"rypt:")
	sh.send((str(L)+"\n").encode())
	sh.recvuntil(b"key) =")
	rec=int(sh.recvline(keepends=False))
	print("rec=",rec)
	if rec%100000000000000!=0:
		print(L)
		break
	L=L*1000
L,R=L//1000,L
while L<=R:
	print(L,R)
	M=(L+R)//2
	sh.recvuntil(b"]uit")
	sh.send(b"e\n")
	sh.recvuntil(b"rypt:")
	sh.send((str(M)+"\n").encode())
	sh.recvuntil(b"key) =")
	rec=int(sh.recvline(keepends=False))
	if rec==M**2:
		L=M+1
	else:
		R=M-1
for i in range(-8,8):
	print(i)
	x=M+i
	sh.recvuntil(b"]uit")
	sh.send(b"e\n")
	sh.recvuntil(b"rypt:")
	sh.send((str(x)+"\n").encode())
	sh.recvuntil(b"key) =")
	rec1=int(sh.recvline(keepends=False))
	if rec1!=x*x:
		n=x*x-rec1
		print('n=',x*x-rec1)
		break
Count,Judge=0,1
while Judge==1 or Judge==n:
	Count+=1
	testc=bytes_to_long(urandom(99))
	sh.recvuntil(b"]uit")
	sh.send(b"d\n")
	sh.recvuntil(b"rypt:")
	sh.send((str(testc)+"\n").encode())
	sh.recvuntil(b"key) =")
	testm=int(sh.recvline(keepends=False))
	Judge=GCD(n,testm*testm-testc)
print('Judge Found After'+str(Count)+'Times:',Judge)
p=getsqrt(Judge)
q=n//(p*p)
assert isPrime(p) and isPrime(q)
print(long_to_bytes(pow(c,inverse(65537,(p-1)*(q-1)),p*q)))
T2=str(datetime.now())
print(T1)
print(T2)
sh.close()
#CCTF{___Ra8!N_H_Cryp70_5YsT3M___}
#Start Time: 2021-08-09 13:04:49.819341
#End Time  : 2021-08-09 13:16:40.294261

整个交互过程跑一次$12$分钟，调了我$3$个多小时。

3.总结

CryptoCTF的这两道题目确实挺难的——主要是有的原理可能自己以前确实没有懂，加上自己太菜所导致的。

感觉后面的一些题目还是非常难的，至少到现在可能还是超出了自己的范围了，明天得开始学AES了。

CTFSeason3
#WriteUp
CryptoCTF Wp 3
http://example.com/2021/08/09/CryptoCTFWriteUp3/
作者
huangx607087
发布于
2021年8月9日
许可协议