2023-CryptoCTF-wp-crypto

CryptoCTF，如果是学密码的师傅的话，应该不需要再介绍这个比赛了。复现过程中学到了不少东西，而且有一个好处就是，不会的题目都有详细的wp可以看(๑¯ω¯๑)。

写这篇文章的目的主要是记录和分享自己复现的思路与过程。因此，对于我不看wp做不出来的的题目，标个*常看常新；对于我看了wp也暂时做不明白的题目标个$，希望以后某天可以学会。

每个题目就放一下题面，可以在NSS平台上下载完整题目附件。题目顺序就按春乎里看到的easy、medium、hard、tough来。

easy

Did it!

题目：

#!/usr/bin/env python3

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.buffer.readline()

def did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
	return R

def main():
	border = "+"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border*72)

	_flag = False
	n, l = 127, 20
	N = set(list(range(0, n)))
	K = [randint(0, n-1) for _ in range(l)]
	cnt, STEP = 0, 2 * n // l - 1
	
	while True:
		ans = sc().decode().strip()
		try:
			_A = [int(_) for _  in ans.split(',')]
			if len(_A) <= l and set(_A).issubset(N):
				DID = did(n, l, K, _A)
				pr(border, f'DID = {DID}')
				if set(_A) == set(K):
					_flag = True
			else:
				die(border, 'Exception! Bye!!')
		except:
			die(border, 'Your input is not valid! Bye!!')
		if _flag:
			die(border, f'Congrats! the flag: {flag}')
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
		cnt += 1

if __name__ == '__main__':
	main()

题目是一个猜数游戏，其步骤为：

• 生成一个列表K，K中元素是20个0到126的随机数(可以相同)
• 有最多11次猜测机会，每次机会可以：
• • 最多输入20个数字，要求每个数字也在0到126之间，这些输入的数字构成一个集合A
  • 对于集合A-K中的每个数，靶机计算该数模127下的平方，并随机返回这个值或这个值+1
• 如果某次输入的集合A和K相等，就得到flag

也就是说任务是要利用这最多11次靶机的返回信息，把集合K猜全，然后在第12次输入K集合给靶机，就能得到flag。

那最简单的思路，就是每次传20个不同的数字进去，这样7次就可以传完所有0-126之间的数。然后对于每一次靶机的返回，如果其返回长度和我们传入的长度不一样，说明传入的数字里有在K中的数。而我们知道，返回的值都是在A中、却不在K中的数字产生的，那么我们可以逐个核验我们传入的数字，看他们平方后的值或平方后的值+1是否在返回值中，如果不在，那么这个数字就是K中的数字。

但是这样做有个问题就是，即使一个数字确实在K中，他平方后的值或平方后的值+1也可能在返回值里，所以可能会被错误地认为他不在K中，导致我们找不全。而这也很好处理，我们只需要把所有平方后的值或平方后的值+1均两两不同的数字放在同一次传入里就可以了，这样就不会漏掉K中的任何一个数字。

exp：

from Crypto.Util.number import *
from pwn import *

sh = remote("node4.anna.nssctf.cn",28552)

#part1 construct division of number
def construct_set(n):
    setlist = [[] for i in range(11)]
    for i in range(n):
        for j in range(len(setlist)):
            Issame = 0
            if(len(setlist[j]) < 20):
                for k in setlist[j]:
                    if(pow(i,2,n) == pow(k,2,n) or pow(i,2,n) == pow(k,2,n)-1 or pow(i,2,n) == pow(k,2,n)+1):
                        Issame = 1
                if(Issame == 0):
                    setlist[j].append(i)
                    break
    while([] in setlist):
        setlist=setlist[:-1]
    return setlist
n = 127
setlist = construct_set(n)


#part2 send set by set and get flag
K = []
for i in range(len(setlist)):
    ans = setlist[i]
    sh.sendline(str(ans)[1:-1].encode())
    sh.recvuntil(b"DID = ")
    did = eval(sh.recvline().strip().decode())
    if(len(did) != len(ans)):
        for j in ans:
            if(pow(j,2,n) not in did and pow(j,2,n)+1 not in did):
                K.append(j)

sh.sendline(str(K)[1:-1].encode())
sh.recvline()
print(sh.recvline())

#NSSCTF{437477ea-448e-4737-8f69-d491a82f8188}

Suction

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		e, n = getPrime(16), p * q
		phi = (p - 1) * (q - 1)
		if GCD(e, phi) == 1:
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

题目基于一个RSA，n由128bit的素数p、q组成。并且隐去了n、e、c的低8位。

除了128bit较小外，没有看出什么特别的攻击点，那么应该就只能先爆破n的低位，然后去查factordb看看他的分解是不是两个128bit的素数。得到n的分解后，就继续爆破e、c的低位并且尝试进行解密，看解出来的是不是都是可见字符就可以了。

三个低八位未知，那么一起爆的话是2^24的复杂度，并且里面涉及到要查factordb，显然比较慢。一些优化的思路就是：

• n的最低位一定是1，减少1bit的爆破量。并且单独爆破n得到其分解
• e的最低位也一定是1，且可以check他是不是素数

如此就可以一分钟左右就得到结果。

exp：

from Crypto.Util.number import *
from tqdm import *
from factordb.factordb import FactorDB
from gmpy2 import *

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
eh = int(bin(PKEY)[2:][-8:],2)*2**8
nh = int(bin(PKEY)[2:][:-8],2)*2**8
ch = int(bin(ENC)[2:],2)*2**8

#part1 bruteforce to factor n
for nl in trange(2**7):
    n = nh + 2*nl + 1

    f = FactorDB(n)
    f.connect()
    fs = f.get_factor_list()
    if(len(fs) == 2):
        p = fs[0]
        q = fs[1]
        if(isPrime(p) and isPrime(q) and len(bin(p)[2:]) == 128):
            phi = (p-1)*(q-1)
            break


#part2 bruteforce c,e
for el in trange(2**7):
    e = eh + 2*el + 1
    if(not isPrime(e)):
        continue
    for cl in range(2**8):
        try:
            c = ch + cl
            d = invert(e,phi)
            flag = long_to_bytes(pow(c,d,n)).decode()
            print(flag)
        except:
            pass

#CCTF{6oRYGy&Dc$G2ZS}

Blue Office

题目：

#!/usr/bin/enc python3

import binascii
from secret import seed, flag

def gen_seed(s):
	i, j, k = 0, len(s), 0
	while i < j:
		k = k + ord(s[i])
		i += 1
	i = 0
	while i < j:
		if (i % 2) != 0:
			k = k - (ord(s[i]) * (j - i + 1))            
		else:
			k = k + (ord(s[i]) * (j - i + 1))
	
		k = k % 2147483647
		i += 1

	k = (k * j) % 2147483647
	return k

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')

genseed函数看着并不是很简单，但是细看发现根本就没有用到。而加密过程是逐字符的，设当前待加密字符是m，那么加密过程就是：

• 更新d：d = ad+b
• 取用d的低24位的高8位，与m异或得到c

也就是说每次用到的其实都只是d的低24位而已，那么可以把整个过程都视作模2^24下的，那么seed也就只需要其模2^24下的值，那么爆破2^24就可以了。

exp：

from Crypto.Util.number import *
from tqdm import *

enc = long_to_bytes(int('b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce',16))

mod = 2**24
for seed in trange(2**24):
    s = seed
    flag = ""
    for i in range(len(enc)):
        s = (s*214013+2531011)%(mod)
        flag += chr(enc[i] ^ ((s>>16)&0xff))
    if("CCTF" in flag):
        print(flag)

#CCTF{__B4ck_0r!F1c3__C1pHeR_!!}

medium

Derik

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import C, e, d, p, q, r, flag

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

assert isPrime(e) and isPrime(d) and isPrime(p) and isPrime(q) and isPrime(r)
assert C[0] * p - C[1] * q >= 0
assert C[2] * q - C[3] * r >= 0
assert C[4] * r - C[5] * p >= 0
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (C[4] * r - C[5] * p) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (C[4] * r - C[5] * p)
assert C[6] * e - C[7] * d == O[3]

n = e * d * p * q * r
m = bytes_to_long(flag)
c = pow(m, 65537, n)
print(f'C = {C}')
print(f'c = {c}')

题目给了两组方程：

$$X^e+Y^e+Z^e = dXYZ$$ $$C_6e-C_7d = O_3$$

其中，X、Y、Z分别是如下正整数：

$$X = C_0p-C_1q$$ $$Y = C_2q-C_3r$$ $$Z = C_4r-C_5p$$

然后题目用e、d、p、q、r组成一个多素数RSA加密，并给出C和O列表。也就是说要通过上面的方程解出e、d、p、q、r这五个参数进行RSA解密。

那么着手点肯定是这个方程：

$$C_6e-C_7d = O_3$$

二元一次方程，显然有无穷组解，那么就取最小的一组解(3，73)，也刚好都是素数。代入到上面的方程就是：

$$X^3+Y^3+Z^3 = 73XYZ$$

这个之前有见过也是椭圆曲线方程(其实就是在春哥这题的wp里见的)，所以可以直接调sage里的方法直接构建一条椭圆曲线出来，找到它上面的点，并映射回这个方程上看看有无X、Y、Z都是正整数的点。然后就会发现其实列表O的前三项就是待求的X、Y、Z的值，这也侧面说明e和d就是这组解。

所以说其实就算不知道这是椭圆曲线，动动脑洞也可以做，因为列表O的前三项在题目中根本没用到。

然后就是根据X、Y、Z解 出p、q、r了，这一部分可以写作一个矩阵方程形式：

$$\left(\begin{matrix} C_0&-C_1&\\ &C_2&-C_3\\ -C_5&&C_4\\ \end{matrix} \right) \left(\begin{matrix} p\\ q\\ r\\ \end{matrix} \right) = \left(\begin{matrix} X\\ Y\\ Z\\ \end{matrix} \right)$$

那么就可以解得p、q、r。至此参数全部都有了，就可以RSA解密。

exp：

from Crypto.Util.number import *

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]
C = [5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772, 6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079, 1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289, 2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451, 8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613, 5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204, 10543, 4]
c = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854

#part1 get e,d
if(1):
    for e in range(1000000):
        if((C[6]*e-O[3])%C[7]==0):
            d = (C[6]*e-O[3])//C[7]
            if(isPrime(d)):
                print(e,d)
                break
#e,d = 3,73


#part2 construct ECC to get a solution of X^3+Y^3+Z^3=73XYZ
R.<x,y,z> = QQ[]
cubic = x^3 + y^3 + z^3 - 73*x*y*z
P = [1,-1,0]
E = EllipticCurve_from_cubic(cubic, P, morphism=False)
f = EllipticCurve_from_cubic(cubic, P, morphism=True)
finv = f.inverse()
R = E.gens()[0]
PP = f(P)
print(finv(R)) #find solution of original equation


#part3 solve equation of Matrix
L = Matrix(ZZ,[[C[0],  -C[1], 0],
               [0,     C[2],  -C[3]],
               [-C[5], 0,     C[4]]])
vec = vector(ZZ,[1391526622949983,2848691279889518,89200900157319])
p,q,r = L.solve_right(vec)


#part4 get flag
phi = (e-1)*(d-1)*(p-1)*(q-1)*(r-1)
n = e*d*p*q*r
d = inverse(65537,phi)
print(long_to_bytes(int(pow(c,d,n))))


#CCTF{____Sylvester____tHE0r3m_Of_D3r!va7i0n!}

Barak

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def on_barak(P, E):
	c, d, p = E
	x, y = P
	return (x**3 + y**3 + c - d*x*y) % p == 0

def add_barak(P, Q, E):
	if P == (0, 0):
		return Q
	if Q == (0, 0):
		return P
	assert on_barak(P, E) and on_barak(Q, E)
	x1, y1 = P
	x2, y2 = Q
	if P == Q:
		x3 = y1 * (c - x1**3) * inverse(x1**3 - y1**3, p) % p
		y3 = x1 * (y1**3 - c) * inverse(x1**3 - y1**3, p) % p
	else:

		x3 = (y1**2*x2 - y2**2*x1) * inverse(x2*y2 - x1*y1, p) % p
		y3 = (x1**2*y2 - x2**2*y1) * inverse(x2*y2 - x1*y1, p) % p
	return (x3, y3)

def mul_barak(m, P, E):
	if P == (0, 0):
		return P
	R = (0, 0)
	while m != 0:
		if m & 1:
			R = add_barak(R, P, E)
		m = m >> 1
		if m != 0:
			P = add_barak(P, P, E)
	return R

def rand_barak(E):
	c, d, p = E
	while True:
		y = randint(1, p - 1)
		K = Zmod(p)
		P.<x> = PolynomialRing(K) 
		f = x**3 - d*x*y + c + y^3
		R = f.roots()
		try:
			r = R[0][0]
			return (r, y)
		except:
			continue

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
E = (c, d, p)

P = rand_barak(E)

FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
m = bytes_to_long(FLAG) 
assert m < p
Q = mul_barak(m, P, E)
print(f'P = {P}')
print(f'Q = {Q}')

题目给出了一条曲线，其方程是：

$$X^3+ Y^3 +1 = dXY \quad(mod\;p)$$

并且定义了这条曲线上的加法和倍点公式，然后取上面一个随机点P，求得其m倍点Q，给出P、Q要求还原m。

才做完Derik这个题，这个题就倍感亲切，因为显然通过以下换元：

$$X = \frac{X'}{Z'}$$ $$Y = \frac{Y'}{Z'}$$

这样曲线方程就直接变成了刚才才见过的三次齐次方程形式：

$$X'^3+ Y'^3 +Z'^3 = dX'Y'Z' \quad(mod\;p)$$

那么就构建出椭圆曲线直接求DLP就好了。然后有一点需要注意的是，直接求DLP得到的并不是明文，这说明明文大于点P的阶，所以还需要小爆一下。

exp：

from Crypto.Util.number import *

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714)
Q = (40867727924496334272422180051448163594354522440089644, 56052452825146620306694006054673427761687498088402245)


#part1 construct ECC to get a solution of X^3+Y^3+Z^3=dXYZ
R.<x,y,z> = Zmod(p)[]
cubic = x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
m = P.discrete_log(Q)
P_ord = P.order()

for i in range(10000):
    try:
        flag = long_to_bytes(int(m)).decode()
        print(flag)
    except:
        m += P_ord

#CCTF{_hE5S!4n_f0rM_0F_3CC!!}

Risk

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import m, flag

def genPrime(m, nbit):
	assert m >= 2
	while True:
		a = getRandomNBitInteger(nbit // m)
		r = getRandomNBitInteger(m ** 2 - m + 2)
		p = a ** m + r
		if isPrime(p):
			return (p, r)

def genkey(m, nbit):
	p, r = genPrime(m, nbit // 2)
	q, s = genPrime(m, nbit // 2)
	n = p * q
	e = r * s
	return (e, n)

def encrypt(msg, pkey):
	e, n = pkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

pkey = genkey(m, 2048)
enc = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

题目基于RSA加密，只是参数生成方式有一些特殊，具体来说是：

$$p = a_1^m + r$$ $$q = a_2^m + s$$ $$e = rs$$

而观察e的大小可以知道r、s的数量级是14bit，也就知道了m的具体取值是4，同时获取e的分解也是可以得到r、s的具体指的。那么现在就有：

$$n = pq = (a_1^4 + r)(a_2^4 + s)$$

要从这个式子再想办法得到a1、a2的值就可以分解n了。

而copper显然是不行，因为虽然a1、a2的确是小根，但是相应的多项式次数也很高，上界达不到要求。那么为了获得分解我选择把式子展开看看：

$$n =a_1^4a_2^4 + sa_1^4 + ra_2^4 + rs$$

可以发现，由于其他项相对于第一项来说都太小了，那么对n开四次方，得到的就是a1a2的精确值。也就是说，现在整个式子的未知量就剩下：

$$sa_1^4,ra_2^4$$

而我们知道他们的和是：

$$sa_1^4+ra_2^4 = n -a_1^4a_2^4 - rs$$

而又可以构造出他们的积：

$$sa_1^4\times ra_2^4 = rs(a_1^4a_2^4)$$

所以就可以用韦达定理来解出sa1^4和ra2^4，就获得n的全部分解了。

分解完过后发现还不能直接解密，因为e和phi不互素。这里应该用有限域开根或AMM加上CRT来求得明文，但是注意到题目里的p、q都是1024bit的数字了，所以明文很大概率小于他们。因此我偷懒直接模q下有限域开个根就可以解(因为e与p-1的GCD比较大)，明文也确实短的符合预期。

exp：

from Crypto.Util.number import *
from gmpy2 import *

e,n = (150953688, 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
c = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

#part1 factor n
a1a2 = iroot(n,4)[0]
#n=(a1^4+r)(a2^4+s)
#t1=sa1^4,t2=ra2^4
#use Vieta theorem
t1_t2 = n - e - a1a2**4
t1t2 = e*a1a2**4
delta = t1_t2**2-4*t1t2
t1 = (t1_t2+iroot(delta,2)[0])//2
t2 = (t1_t2-iroot(delta,2)[0])//2

for s in range(1,2**14,2):
    if(iroot(t1//s,4)[1]):
        a1 = iroot(t1//s,4)[0]
        r = e // s
        a2 = iroot(t2//r,4)[0]
        break

p = a1**4+r
q = a2**4+s


#part2 get flag
cq = pow(c,inverse(e//72,q-1),q)
PR.<x> = PolynomialRing(Zmod(q))
f = x^72 - cq
resq = f.roots()
for i in resq:
    print(long_to_bytes(int(i[0])))

#CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}

Roldy

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from pyope.ope import OPE as enc
from pyope.ope import ValueRange
import sys
from secret import key, 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.buffer.readline()

def encrypt(msg, key, params):
	if len(msg) % 16 != 0:
		msg += (16 - len(msg) % 16) * b'*'
	p, k1, k2 = params
	msg = [msg[_*16:_*16 + 16] for _ in range(len(msg) // 16)]
	m = [bytes_to_long(_) for _ in msg]
	inra = ValueRange(0, 2**128)
	oura = ValueRange(k1 + 1, k2 * p + 1)
	_enc = enc(key, in_range = inra, out_range = oura)
	C = [_enc.encrypt(_) for _ in m]
	return C

def main():
	border = "|"
	pr(border*72)
	pr(border, " Welcome to Roldy combat, we implemented an encryption method to    ", border)
	pr(border, " protect our secret. Please note that there is a flaw in our method ", border)
	pr(border, " Can you examine it and get the flag?                               ", border)
	pr(border*72)

	pr(border, 'Generating parameters, please wait...')
	p, k1, k2 = [getPrime(129)] + [getPrime(64) for _ in '__']
	C = encrypt(flag, key, (p, k1, k2))

	while True:
			pr("| Options: \n|\t[E]ncrypted flag! \n|\t[T]ry encryption \n|\t[Q]uit")
			ans = sc().decode().lower().strip()
			if ans == 'e':
				pr(border, f'encrypt(flag, key, params) = {C}')
			elif ans == 't':
				pr(border, 'Please send your message to encrypt: ')
				msg = sc().rstrip(b'\n')
				if len(msg) > 64:
					pr(border, 'Your message is too long! Sorry!!')
				C = encrypt(msg, key, (p, k1, k2))
				pr(border, f'C = {C}')
			elif ans == 'q':
				die(border, "Quitting ...")
			else:
				die(border, "Bye ...")

if __name__ == '__main__':
	main()

题目基于OPE加密(一会儿来说这是什么)，他先生成加密需要的p、k1、k2三个参数，然后用这几个参数和秘密的key对flag进行OPE加密。然后我们有无数次交互机会，每次有以下选项：

• 输入e，得到flag的OPE加密结果
• 输入t，可以发送明文，并获取他的所有参数均相同的OPE加密值

我也完全不懂OPE是什么，就上网查了一下，知道它叫做保序加密算法。而顾名思义，他有一个性质是：

• 若明文m1<m2，则密文c1<c2

那么就很简单了，由于有无限次交互机会，我们可以对每一段flag的明文去二分查找，用返回的密文是否大于flag的对应密文值来判断flag在哪一个区间，从而逐步确定flag每段明文的具体值。

我是一段一段来的，实际上也可以所有段一起二分来节省2/3的时间(因为一共有三段)，但是我太懒就不改了。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *

sh = remote("node4.anna.nssctf.cn",28724)
sh.recvuntil(b"Generating parameters, please wait...")

#part1 get flag_enc
sh.sendline(b"e")
sh.recvuntil(b"params) = ")
C = eval(sh.recvline().strip().decode())


#part2 binary_search
for i in range(len(C)):
    left = 0
    right = 2**128
    for j in trange(128):
        temp = (left+right)//2
        sh.recvuntil(b"[Q]uit")
        sh.sendline(b"t")
        sh.recvuntil(b"Please send your message to encrypt: ")
        sh.sendline(long_to_bytes(temp))
        sh.recvuntil(b"C = ")
        ans = eval(sh.recvline().strip().decode())[0]
        if(abs(ans - C[i]) <= 1):
            print(long_to_bytes(temp))
            break
        if(ans < C[i]):
            left = temp
        else:
            right = temp


#NSSCTF{8ce5d404-e7c2-46c7-985d-bc5a74a4eb8c}

* Bertrand

题目基于Hilbert曲线，极客大挑战的wp里有写过，由于涉及到图像加密，感觉有点费事，复现就不做了。

Insights

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def getRandomNBits(n):
	nb = '1' + ''.join([str(randint(0, 1)) for _ in range(n - 1)])
	return nb

def getLeader(L, n):
	nb = L + getRandomNBits(n)
	return int(nb, 2)

def genPrime(L, nbit):
	l = len(L)
	assert nbit >= l
	while True:
		p = getLeader(L, nbit - l)
		if is_prime(p):
			return p

def genKey(L, nbit):
	p, q = [genPrime(L, nbit) for _ in '__']
	n = p * q
	d = next_prime(pow(n, 0.2919))
	phi = (p - 1) * (q - 1)
	e = inverse(d, phi)
	pubkey, privkey = (n, e), (p, q)
	return pubkey, privkey

def encrypt(msg, pubkey):
	n, e = pubkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

nbit = 1024
L = bin(bytes_to_long(b'Practical'))[2:]
pubkey, privkey = genKey(L, nbit)
p, q = privkey
c = encrypt(flag, pubkey)

print('Information:')
print('-' * 85)
print(f'n = {p * q}')
print(f'e = {pubkey[1]}')
print(f'c = {c}')
print(f'p = {bin(p)[2:len(L)]}...[REDACTED]')
print(f'q = {bin(q)[2:len(L)]}...[REDACTED]')
print('-' * 85)

题目基于RSA加密，参数的特殊点在于：

• d是个略大于n^0.2919的量
• p、q高72位相同

这个d的界一看就是boneh的界，所以就是想办法把p、q高位相同想办法利用进boneh and durfee attack去扩大求根的上界。那么就依据boneh and durfee attack的思路，写出下面的式子：

$$ed = 1 + k(p-1)(q-1)$$

由于e和n的数量级很接近，那么k也就比d大不了多少，因此k也可以看作是一个略大于n^0.2919的小量。之后先把式子展开：

$$ed = 1 + k(n-(p+q)+1)$$

由于p、q高位相同，记高位为h，那么p、q可以写作：

$$p = h + p_l$$ $$q = h + q_l$$

代入刚才的式子里：

$$ed = 1 + k(n-(2h + p_l+ q_l)+1)$$

然后整理一下式子：

$$ed = 1 + k(n+1-2h -(p_l+ q_l))$$

那么，因为n是奇数，所以n+1+2h是偶数，并且pl+ql也是偶数，所以式子又可以写成：

$$ed = 1 + 2k(\frac{n+1-2h}{2} -\frac{p_l+ q_l}{2})$$

此时就可以视作一个模e下的X、Y的多项式，去用boneh and durfee attack解小根：

$$f = 1 + X(A +Y) \quad(mod\;e)$$

m改大一点一直到8就能有根，然后就可以得到d的值去进行解密。

exp：

from Crypto.Util.number import *
import itertools

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print (a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print ("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print ("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly


nbit = 1024
n = 12765231982257032754070342601068819788671760506321816381988340379929052646067454855779362773785313297204165444163623633335057895252608396010414744222572161530653104640020689896882490979790275711854268113058363186249545193245142912930804650114934761299016468156185416083682476142929968501395899099376750415294540156026131156551291971922076435528869024742993840057342092865203064721826362149723366381892539617642364692012936270150691803063945919154346756726869466855557344213050973081755499746750276623648407677639812809665472258655462846021403503851719008687214848550916999977775070011121527941755954255781343103086789
e = 459650454686946706615371845737527916539205656667844780634386049268800615782964920944229084502752167395446158290854047696006034750210758341744841762479191173017773034647739346927390580848998121830029134542880713409306092967282675122699586503684943407535067216738556403169403622104762516293879994387324370835718056251706150557820106296417750402984941838652433642298378976899556042987560946508887315484380807248331504458640857234708123277403252632993828101306072382329879857946191508782246793011691530554606521701055094223574951862129713872918021549814674387049788995785872980320871421550616327471735316980754238323013
c = 10992248752412909788626396175372747713079469256270100576886987393986576680666320383209810005318254336440105142571546847427454822405793626080251363454531982746373841267986148332456716023293306870382809568309620264499225135226626560298741596462262513921032733814032790312163314776421380481083058518893602887082464123177575742160690315666730642727773288362853901330620841098230284739614618790097180848133698381487679399364400048499041582830157094876815030301231505774900176910650887780842536610942820066913075027528705150102760422836458745949063992228680293226303245265232017738712226154128654682937687199768621565945171
L = bin(bytes_to_long(b'Practical'))[2:]
ph = int(L+"1",2)*2^(nbit-len(L+"1"))
qh = ph #known 72 high bits


#part1 boneh and durfee to get d
if(1):
    m = 8
    delta = 0.30
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(n^delta)  # this _might_ be too much
    Y = 2^(nbit-len(L+"1"))   # correct if p, q are ~ same size

    A = (n+1)//2 - (ph+qh)//2
    PR.<x,y> = PolynomialRing(ZZ)
    pol = 1+x*(A+y)
    res = boneh_durfee(pol, e, m, t, X, Y)
    print(res)

#part2 get d
k2 = 49977986915659605429345289223812619569200398624947376450000245097914425323254468264973009610079433427753410860067909320180393446912719527813521669872296939128853941260184779168808
pl_ql = -26225793397477672414138436461088692023641486423848109679632696585093272843809115665873260921093208795526382416734843864007298933841051250143140940470093595985249689125607975667724436632465193533116961405126679193559648564948639967803860314403909842190409143666008313060949901033553728989
d = (1+k2*(A+pl_ql)) // e
print(long_to_bytes(int(pow(c,d,n))))


#CCTF{RSA_N3w_rEc0rd5_4Nd_nEw_!nSi9h75!}

Resuction

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

from decimal import *

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		d, n = getPrime(64), p * q
		phi = (p - 1) * (q - 1)
		if GCD(d, phi) == 1:
			e = inverse(d, phi)
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 1024
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

和suction一样隐去了n、e、c的低8位，不同之处在于：

• p、q从128bit提升到了1024位
• d仅有64bit

由于d很小所以想到wiener，并且由于n、e仅有低8位不知道，所以其实有：

$$\frac{e'}{n'} \approx \frac{e}{n}$$

所以直接对e’、n’进行连分数展开就能找到d，然后爆破n、c的低8位就可以解密了，优化的思路也一样，n一定是奇数所以固定了LSB，可以少爆破一位，并且可以用powmod加速。但是因为本身已经很快了所以只是锦上添花。

exp：

from Crypto.Util.number import *
from tqdm import *
from gmpy2 import *

PKEY = 14192646310719975031517528381795548241077678859071194396837281472399230674325587198691913743313024193030641258581477544395982020385534616950314446352119543012689979705497443206671093873748633162188213109347667494028713308821945628880987033909436936504594085029207071182583896573425433818693447573712242776054326253393149643818428222532313129014785625379928796322492111783102063504659053965652092334907431265629283336869752591405010801363428649651892548988084920295512198406822149854508798413366425646089176325412867633899847841343293434518769693835679828109184625256833518392375615524221729773443578746961887429674099018040291053535429314874943299587513900900515776980848746070077651676814430155460898107362207677739452859298842563030631706907437662807884529549746843462830493900480079096937402325307522965877069080418178692616875205678928420840955518031258855869218152431304423803589723140983606576549207164114711076498723237274262054605174412193097533550076687418481230734706280737017543741247718967059747548710091320650704988384742281590019869955579949961574733610565593105027342454880292474482792325237942870408329807427182014062811782475262070063065860763705715879581562335668163076088547827008755841277828137570366416095778
ENC = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

eh = int(bin(PKEY)[2:][2048-8:],2)*2**8
nh = int(bin(PKEY)[2:][:2048-8],2)*2**8
ch = int(bin(ENC)[2:],2)*2**8

def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF

def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)

def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf

#part1 use wiener to get d
if(1):
    cf = continuedFra(eh, nh)
    for d,k in getit(cf):
        if(len(bin(d)[2:]) == 64 and isPrime(d)):
            print(d)
            break
d = 10254340117704573547


#part2 bruteforce n,c
for nl in trange(1,2**8,2):
    for cl in range(2**8):
        n = nh+nl
        c = ch+cl
        flag = powmod(c,d,n)

        try:
            flag = long_to_bytes(flag).decode()
            print(flag)
        except:
            pass

#CCTF{aIr_pr3s5urE_d!Ff3rEn7i4L_8eTw3eN_ArEa5!}

* Blobfish

更偏misc一点，思路应该是用PNG文件头去明文攻击？没有特别想做，就不做了。

ASIv1

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def base(n, l):
    D = []
    while n > 0:
        n, r = divmod(n, l)
        D.append(r)
    return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
	l = len(seed)
	_seed = base(bytes_to_long(seed), 3)
	_seed = [int(_) for _ in _seed]
	_l = len(_seed)
	R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
	S = []
	for r in R:
		s = 0
		for _ in range(_l):
			s += (r[_] * _seed[_]) % 3
		# s += getRandomRange(0, 3)
		s %= 3
		S.append(s)
	return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

其实就是解个矩阵方程就好，这题是之前复现完ASIV2顺手写掉的。

exp：

from Crypto.Util.number import *

with open(r'E:\题\历届赛题\cryptoCTF 2023\ASlv1\ASIv1\output.txt') as f:
    exec(f.read())

l = len(R[0])

R_ = Matrix(GF(3),l+1,l)
S_ = vector(GF(3),l+1)
for i in range(l+1):
    R_[i] = R[i]
    S_[i] = S[i]
print(R_.rank())
seed = R_.solve_right(S_)

temp = list(map(str,seed))
flag = "".join(temp)

print(long_to_bytes(int(flag,3)))

#CCTF{3Xpl0i7eD_bY_AtT4ck3r!}

* TPSD

NSSCTF上没看见这题，在春乎看了下题目和解答，不利用搜索引擎，光靠自己想应该是很难想到。

* Trex

题目：

#!/usr/bin/env python3

import random
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.buffer.readline()

def check_inputs(a, b, c):
	if not all(isinstance(x, int) for x in [a, b, c]):
		return False
	if a == 0 or b == 0 or c == 0:
		return False
	if a == b or b == c or a == c:
		return False
	return True

def check_solution(a, x, y, z):
	return (x*x + y*y - x*y - a*(z**3)) == 0

def main():
	border = "|"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border, "Welcome to the Ternary World! You need to pass each level until 20  ", border)
	pr(border, "to get the flag. Pay attention that your solutions should be nonzero", border)
	pr(border, "distinct integers. Let's start!                                     ", border)
	pr(border*72)

	level, step = 0, 19
	while level <= step:
		a = random.randint(2**(level * 12), 2**(level*12 + 12))
		equation = f'x^2 + y^2 - xy = {a}*z^3'
		pr(f"Level {level + 1}: {equation}")
		inputs = input().strip().split(",")
		try:
			x, y, z = map(int, inputs)
		except:
			die(border, "Invalid input, Bye!!")
		if check_inputs(x, y, z):
			if check_solution(a, x, y, z):
				pr(border, "Correct! Try the next level :)")
				level += 1
			else:
				pr(border, "You didn't provide the correct solution.")
				die(border, "Better luck next time!")			
		else:
			pr(border, "Your solutions should be non-zero distinct integers")
			die(border, "Quiting...")
		if level == step:
			pr(border, "Congratulations! You've successfully solved all the equations!")
			die(border, f"flag: {flag}")

if __name__ == '__main__':
	main()

题目需要完成19轮挑战得到flag，具体来说每轮挑战是：

• 生成一个与轮数有关的数值a并给出
• 需要输入两两不相同且均不为0的整数x、y、z，使他们满足方程：

$$x^2 + y^2 -xy = az^3$$

这题想复杂了，因为观察到这个似乎也挺像一条曲线的形式，所以一直在想有没有办法还原，然后往椭圆曲线上靠，然后去找到整点。看了春哥的wp发现思路其实很简单也很巧妙。

由于题目要求两两不等，所以不妨就把y记作x+t，t不为0，那么代入原式就有：

$$x^2 + (x+t)^2 -x(x+t) = az^3$$

也就是：

$$x^2 + xt + t^2 = az^3$$

而由于我们只需要一个特解，所以在这里构造x=t，就有：

$$3t^2 = az^3$$

所以发现，当$t = 3a^2, z = 3a$时，就获得我们需要的一组解：

$$(x,y,z) = (3a^2,6a^2,3a)$$

exp：

from pwn import *
from tqdm import *

sh = remote("node4.anna.nssctf.cn",28525)

for i in trange(19):
    sh.recvuntil(b"x^2 + y^2 - xy = ")
    temp = sh.recvline().strip().decode()
    a = int(temp[:temp.index("*")])
    
    solution = str(3*a**2)+","+str(6*a**2)+","+str(3*a)
    sh.sendline(solution.encode())
sh.recvline()
sh.recvline()
print(sh.recvline())

#NSSCTF{fe6abdba-5047-47a9-94f6-3d954d3b7734}

Keymoted

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def gen_koymoted(nbit):
	p = getPrime(nbit)
	a, b = [randint(1, p - 1) for _ in '__']
	Ep = EllipticCurve(GF(p), [a, b])
	tp = p + 1 - Ep.order()
	_s = p ^^ ((2 ** (nbit - 1)) + 2 ** (nbit // 2))
	q = next_prime(2 * _s + 1)
	Eq = EllipticCurve(GF(q), [a, b])
	n = p * q
	tq = q + 1 - Eq.order()
	e = 65537
	while True:
		if gcd(e, (p**2 - tp**2) * (q**2 - tq**2)) == 1:
			break
		else:
			e = next_prime(e)
	pkey, skey = (n, e, a, b), (p, q)
	return pkey, skey

def encrypt(msg, pkey, skey):
	n, e, a, b = pkey
	p, q = skey
	m = bytes_to_long(msg)
	assert m < n
	while True:
		xp = (m**3 + a*m + b) % p
		xq = (m**3 + a*m + b) % q
		if pow(xp, (p-1)//2, p) == pow(xq, (q-1)//2, q) == 1:
			break
		else:
			m += 1
	eq1, eq2 = Mod(xp, p), Mod(xq, q)
	rp, rq = sqrt(eq1), sqrt(eq2)
	_, x, y = xgcd(p, q)
	Z = Zmod(n)
	x = (Z(rp) * Z(q) * Z(y) + Z(rq) * Z(p) * Z(x)) % n
	E = EllipticCurve(Z, [a, b])
	P = E(m, x)
	enc = e * P
	return enc

nbit = 256
pkey, skey = gen_koymoted(nbit)
enc = encrypt(flag, pkey, skey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

题目生成两个素数p、q，并依据p、q和随机的a、b造出两个椭圆曲线Ep、Eq，然后将flag值m作为P点的横坐标，在Ep、Eq上分别计算出其纵坐标后crt得到flag在En下的纵坐标，就得到En下的P点。然后给出n和P的e倍点Q，要求还原m。

而p、q的生成方式是有玄机的，注意到q为：

$$2(p \oplus 2^{255} \oplus 2^{128})+1 + delta$$

delta是nextprime产生的小量，并且由于p本身是256bit，所以第一个异或可以看作是减，那么如果爆破delta的话，其实整个式子就可以看作是：

$$2(p - 2^{255} \pm 2^{128})+1 + delta$$

代入到n=pq就有：

$$n = p(2(p - 2^{255} \pm 2^{128})+1 + delta)$$

那么对这个一元二次方程求根就得到p了，然后就得到q。

之后就分别造出Ep、Eq，在两条曲线上分别求出P点，然后crt组合得到En下的横坐标就是flag了。由于要保证y^2在p、q下都是二次剩余所以有一点偏差，不过问题不大。

exp：

from Crypto.Util.number import *

pkey = (6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301, 65537, 5539256645640498184116966196249666621079506508209770360679460869295427007578, 20151017657582479433586370393795140515103572865771721775868586710594524816458)
enc = (6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433,2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972)
n,e,a,b = pkey

#part1 factor n
PR.<p> = PolynomialRing(ZZ)
for delta in range(10000):
    f = p*(2*(p-2^255+2^128)+1+delta)-n
    res = f.roots()
    if(res != []):
        p = int(res[0][0])
        q = n // p
        break
    f = p*(2*(p-2^255-2^128)+1+delta)-n
    res = f.roots()
    if(res != []):
        p = int(res[0][0])
        q = n // p
        break


#part2 get flag
Ep = EllipticCurve(GF(p), [a, b])
Eq = EllipticCurve(GF(q), [a, b])
Cp = Ep(enc)
Mp = inverse(e,Ep.order())*Cp
Cq = Eq(enc)
Mq = inverse(e,Eq.order())*Cq

En = EllipticCurve(Zmod(n), [a, b])
from sympy.ntheory.modular import crt
X = crt([p,q],[int(Mp.xy()[0]),int(Mq.xy()[0])])[0]
print(long_to_bytes(X))

#CCTF{a_n3W_4t7aCk_0n_RSA_a9ain!?}

hard

Big

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from hashlib import sha512
from flag import flag

def genkey(nbit):
	while True:
		p = getPrime(nbit)
		if p % 4 == 3:
			q = int(str(p)[::-1])
			if isPrime(q):
				return p * q, (p, q)

def setup(msg, pkey):
	hid = sha512(msg).digest()
	while True:
		a = bytes_to_long(hid)
		if kronecker(a, pkey) == 1:
			return a
		else:
			hid = sha512(hid).digest()

def encrypt(msg, pkey):
	a, m = setup(msg, pkey), bytes_to_long(msg)
	B, C = bin(m)[2:], []
	for b in B:
		while True:
			t = randint(1, pkey)
			if kronecker(t, pkey) == 2 * int(b) - 1:
				C.append((t - a * inverse(t, pkey)) % pkey)
				break
	return (a, C)


pkey, privkey = genkey(512)
E = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'E = {E}')

题目生成两个素数p、q，他们互为十进制逆序，并取乘积为n。然后题目将flag逐比特加密，加密方式为：

• 若当前bit为0，则取满足$(\frac{t}{n})=-1$的t
• 若当前bit为1，则取满足$(\frac{t}{n})=1$的t
• 给出 $t-at^{-1}$ 模n下的值，记为c

其中的符号是雅可比符号，a为已知量且$(\frac{a}{n})=1$。

那么首先要获得n的分解，由于p、q互为十进制逆序所以可以剪枝。这一部分就不细讲了，我写的另一篇中有类似的题目：

Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

分解出p、q后，就可以在模p和模q下分别解出每一bit中t的值。这里以模p为例，也就是解这个方程：

$$t^2-ct-a = 0 \quad(mod\;p)$$

我们求出t的最终目的是计算出t对n的雅可比符号，从而确定flag的对应bit取值。而雅可比符号有如下性质：

$$(\frac{t}{n}) = (\frac{t}{p})(\frac{t}{q})$$

所以我们可以分别求t对p、t对q的雅可比符号并相乘，就得到t对n的雅可比符号，就可以逐bit确定flag了。

但是有一个问题需要注意，由于我们解的方程是二次方程，所以一般情况下会有两个解。应该取哪一个解去求雅可比符号呢？

事实上取哪一个都没有影响，这是因为，我们记两个解分别为t1、t2，那么由韦达定理有：

$$t_1t_2 = -a \quad(mod\;p)$$

对这个式子应用欧拉判别式：

$$t_1^{\frac{p-1}{2}}t_2^{\frac{p-1}{2}} = (-a)^{\frac{p-1}{2}} \quad(mod\;p)$$

而可以检查，a在模p、模q下均是二次非剩余，并且发现p、q都是4k+3型的素数，所以有：

$$t_1^{\frac{p-1}{2}}t_2^{\frac{p-1}{2}} = (-1)^{2k+1}(-1) = 1 \quad(mod\;p)$$

这说明t1、t2在模p下的二次剩余性相同，在模q下也同理。所以取哪个根计算结果都一样。

春哥的解释里有一点小错误，就是$(\frac{a}{n})=1$并不能说明a就是模n下的二次剩余，反而，由于a在模p下、模q下都是二次非剩余，所以a在模n下也是二次非剩余。这也是QR假设的困难性所在：雅可比映射的核中既有二次剩余也有二次非剩余，目前如果不知道n的分解的话，没有有效的算法来判定。

但是有一点可以说明，如果$(\frac{a}{n})=-1$的话，那a一定不是模n下的二次剩余。

exp：

from Crypto.Util.number import *
from tqdm import *

pkey = 72271787633166084700895603235291055045699965307538401174867474485084272711938364003794151073975875159886045553516299177522950407802715116792937858353646755246888532333536918663888208381012106370000886903776721867958523682675624556576505534100750339626081218194389244007622749982917071344697799413034317147013
E = 

n = pkey
a,tlist = E[0],E[1]

#part1 get p,q
dec_len = 154
def find(ph,qh,pl,ql):
    #check1
    padding0 = (dec_len-len(ph)-len(pl))*"0"
    padding9 = (dec_len-len(ph)-len(pl))*"9"
    if(int(qh+padding0+ql)*int(ph+padding0+pl) > n or int(qh+padding9+ql)*int(ph+padding9+pl) < n):
        return
    #check2
    mask = 10**len(pl)
    if(int(ql)*int(pl) % mask != n % mask):
        return   
    #return
    if(len(ph+pl) == dec_len):
        p = int(ph+pl)
        q = int(qh+ql)
        if(p*q==n):
            print(p)
            print(q)
    #search  
    for i in range(10):
        for j in range(10):
            find(ph + str(i), qh + str(j), str(j) + pl, str(i) + ql)

if(0):
    for i in range(1,10,2):
        for j in range(1,10,2):
            find(str(i),str(j),str(j),str(i))
p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967


#part2 get flag bit by bit
flag = ""
for i in tqdm(tlist):
    PR.<t> = PolynomialRing(Zmod(p))
    f = t^2 -i*t - a
    resp = f.roots()[0][0]
    PR.<t> = PolynomialRing(Zmod(q))
    f = t^2 -i*t - a
    resq = f.roots()[0][0]

    if(kronecker(resp,p)*kronecker(resq,q) == 1):
        flag += "1"
    else:
        flag += "0"
print(long_to_bytes(int(flag,2)))


#CCTF{_Cocks_18e_5chEm3}

Marjan

题目：

#!/usr/bin/env sage

import sys
from Crypto.Util.number import *
from hashlib import sha256
from flag import flag


p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
G = E.random_point()
_o = E.order()
original_msg = 'I love all cryptographers!!!'

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.buffer.readline()

def keygen(E):
	skey = randint(1, _o)
	pkey = skey * G
	return pkey, skey

def encrypt(msg, pkey):
	e, l = randint(1, _o), len(msg)
	m1, m2 = bytes_to_long(msg[:l // 2]), bytes_to_long(msg[l // 2:])
	assert m1 < p and m2 < p
	e1, e2 = (e * pkey).xy()
	c1, c2 = m1 * e1 % p, m2 * e2 % p
	return (c1, c2, e * G)

def sign(msg, skey):
	_tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
	while True:
		K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
		r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
		if r * s != 0:
			break
	h = bytes_to_long(sha256(msg).digest())
	t = inverse(K[0], _o) * (h * r - s * skey) % _o
	return (r, s, t)

def verify(msg, pkey, _sign):
	r, s, t = [int(_) % _o for _ in _sign]
	h = bytes_to_long(sha256(msg.encode('utf-8')).digest())
	u = int(h * r * inverse(t, _o) % _o)
	v = int(s * inverse(t, _o) % _o)
	# u = h * r * inverse(t, _o) % _o
	# v = s * inverse(t, _o) % _o
	_R = (u * G - v * pkey).xy()[0]
	return _R == r

def main():
	border = "|"
	pr(border*72)
	pr(border, "Hi all, now it's time to solve a probably simple ECC challenge about", border)
	pr(border, "encryption and signing in elliptic curves! Follow the questions and ", border)
	pr(border, "find the secret flag, are you ready!?                               ", border)
	pr(border*72)

	pkey, skey = keygen(E)

	while True:
		pr("| Options: \n|\t[E]ncrypt a message! \n|\t[G]et the flag \n|\t[P]ublic Key \n|\t[S]ign a message \n|\t[V]erify signature \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 'e':
			pr(border, 'Send your message here: ')
			_msg = sc()
			_enc = encrypt(_msg, pkey)
			pr(border, f'enc = {_enc}')
		elif ans == 'g':
			pr(border, 'You should send the valid signature for my given message!')
			pr(border, 'Send the signature of original message here: ')
			_sgn = sc().split(b',')
			try:
				_sgn = [int(_) for _ in _sgn]
				if verify(original_msg, pkey, _sgn):
					die(border, f'Congratz! You got the flag: {flag}')
				else:
					pr(border, 'Your signature is not correct!')
			except:
				import traceback; traceback.print_exc()
				pr(border, 'Try to send valid signature!')
				continue
		elif ans == 's':
			pr(border, 'Send your message to sign: ')
			_msg = sc()
			if len(_msg) >= 10:
				die(border, 'Sorry, I sign only short messages! :/')
			_sgn = sign(_msg, skey)
			pr(border, f'sgn = {_sgn}')
		elif ans == 'v':
			pr(border, 'Send your signature to verify: ')
			_sgn = sc().split(b',')
			try:
				_sgn = [int(_) for _ in _sgn]
				pr(border, 'Send your message: ')
				_msg = sc()
				if verify(_msg, pkey, _sgn):
					pr(border, 'Your message successfully verified :)')
				else:
					pr(border, 'Verification failed :(')
			except:
				pr(border, 'Try to send valid signature!')
				continue
		elif ans == 'p':
			pr(border, f'pkey = {pkey}')
			pr(border, f'G = {G}')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

题目基于ECDSA，理论上来说，可以申请无数次不同消息的签名，靶机会返回对应签名值。而如果成功伪造出指定消息

‘I love all cryptographers!!!’的签名的话就可以拿到flag。而由于送去签名的消息有长度限制不能大于等于10，所以没法直接把指定消息拿去签名。

为了方便，把私钥记为d，那么签名过程是这样的：

$$t = K^{-1}(hr+sd) \quad(mod\;o)$$

并返回给你r、s、t。其中o是曲线的阶。

而签名过程中有个极其显眼的地方告诉你要HNP：

K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']

这里直接用了整除，说明K最多也就231bit。那么为了利用HNP，仍然是常用思路，把后面的若干组签名与第0组签名作个差消去d，然后用多组这样的等式造格，从而规约出所有K。

还是写一下吧，比如对于第0组和第1组，分别有：

$$t_0K_0 = h_0r_0+s_0d \quad(mod\;o)$$ $$t_1K_1 = h_1r_1+s_1d \quad(mod\;o)$$

为了消去d，把d的系数配成相同：

$$s_1t_0K_0 = s_1h_0r_0+s_1s_0d \quad(mod\;o)$$ $$s_0t_1K_1 = s_0h_1r_1+s_0s_1d \quad(mod\;o)$$

那么作差就得到：

$$s_1h_0r_0 - s_0h_1r_1 + s_0t_1K_1 - s_1t_0K_0 = 0 \quad(mod\;o)$$

由于r、s、t、h均已知(h是送去签名的消息的哈希值)，所以可以简化写为：

$$A_1K_1 + B_1K_0 + C_1 = 0 \quad(mod\;o)$$

那么申请多组签名，就有多组等式：

$$A_iK_i + B_iK_0 + C_i + u_io = 0$$

然后就可以造格了，假设算上第0组，一共申请了n+1组签名，就有n个上面这样的式子，那么造的格子长下面这样：

$$\left(\begin{matrix} 1&&&&&&A_1&A_2&\cdots&A_n\\ &1&&&&&B_1\\ &&\ddots&&&&&\ddots\\ &&&1&&&&&B_{n-1}\\ &&&&1&&&&&B_{n}\\ &&&&&2^{231}&C_1&C_2&\cdots&C_n\\ &&&&&&o\\ &&&&&&&o\\ &&&&&&&&\ddots\\ &&&&&&&&&o\\ \end{matrix} \right)$$

这个格具有的线性关系是：

$$(K_0,K_1,...K_n,1,u_1,u_2,...u_n) \left(\begin{matrix} 1&&&&&&A_1&A_2&\cdots&A_n\\ &1&&&&&B_1\\ &&\ddots&&&&&\ddots\\ &&&1&&&&&B_{n-1}\\ &&&&1&&&&&B_{n}\\ &&&&&2^{231}&C_1&C_2&\cdots&C_n\\ &&&&&&o\\ &&&&&&&o\\ &&&&&&&&\ddots\\ &&&&&&&&&o\\ \end{matrix} \right) = (K_0,K_1,...K_n,2^{231},0,0,...,0)$$

本来想着反正不限制组数，偷懒就不算高斯启发式了，直接来50组莽试。结果申请签名的中途总是会在某一次的时候断掉，根本就申请不完50组。然后再审了下代码发现，因为曲线阶o并不是一个素数，所以签名中的求逆操作并不总会成功。那就只能少申请一些增大申请完成的概率。

但是还是死活出不来，无奈之下去看了春哥和maple的wp，发现的确是有一个很坑的点就是申请签名操作中：

_msg = sc()

和之前的靶机题目不一样，这里没有取[:-1]的操作，也就是说我们发过去的消息他会加一个换行符”\n”再进行哈希。

那么这样就没有问题了，申请20组数据，然后LLL得到k0后就可以算出d，然后伪造签名并发送过去就拿到flag了。

exp：

from Crypto.Util.number import *
from Pwn4Sage.pwn import *
from hashlib import sha256
from tqdm import *
from random import *
import os

p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
_o = E.order()
original_msg = 'I love all cryptographers!!!'

sh = remote("node4.anna.nssctf.cn",28406)

#part1 get pubkey
sh.recvuntil(b"[Q]uit")
sh.sendline(b"p")
sh.recvuntil(b"pkey = ")
temp = sh.recvline().strip().decode().split(":")
pkey = E(int(temp[0][1:-1]),int(temp[1][1:-1]))
sh.recvuntil(b"G = ")
temp = sh.recvline().strip().decode().split(":")
G = E(int(temp[0][1:-1]),int(temp[1][1:-1]))


#part2 get groups of sign to construct matrix
groups = 20
A = []
B = []
C = []

sh.recvuntil(b"[Q]uit")
sh.sendline(b"s")
msg = long_to_bytes(0)
sh.sendline(msg)
sh.recvuntil(b"sgn = ")
r0,s0,t0 = eval(sh.recvline().strip().decode())
h0 = bytes_to_long(sha256(msg+b"\n").digest())
for i in trange(1,groups):
    sh.recvuntil(b"[Q]uit")
    sh.sendline(b"s")
    msg = os.urandom(8)
    sh.sendline(msg)
    sh.recvuntil(b"sgn = ")
    ri,si,ti = eval(sh.recvline().strip().decode())
    hi = bytes_to_long(sha256(msg+b"\n").digest())
    A.append(t0*si)
    B.append(-ti*s0)
    C.append(hi*ri*s0-h0*r0*si)

T = 2^300
L = Matrix(ZZ,2*groups,2*groups)
for i in range(groups):
    L[i,i] = 1
L[groups,groups] = 2^231
for i in range(groups-1):
    L[0,groups+1+i] = A[i]*T
    L[1+i,groups+1+i] = B[i]*T
    L[groups,groups+1+i] = C[i]*T
    L[groups+1+i,groups+1+i] = _o*T


#part3 LLL to get k
res = L.LLL()
for i in res:
    if(abs(i[groups])==2^231):
        k0 = abs(i[0])
        break


#part4 get skey and get signature of original message
skey = (h0*r0-t0*k0)*inverse(s0,_o) % _o
print(skey*G == pkey)
_tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
while True:
    K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
    r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
    if r * s != 0:
        break
h = bytes_to_long(sha256(original_msg.encode()).digest())
t = inverse(K[0], _o) * (h * r - s * skey) % _o

sh.recvuntil(b"[Q]uit")
sh.sendline(b"g")
sh.sendline((str(r)+","+str(s)+","+str(t)).encode())
sh.recvuntil(b"You got the flag: ")
print(sh.recvline())


#NSSCTF{7255af4f-390f-47c4-9c0c-e0dd2afbc944}

做完题目后看春哥wp里还写了一种非预期，就是发送：

$$(r,0,hr)$$

就可以拿到flag。而之所以会产生这种非预期，是因为验签操作中没有检查s是否为0，而s为0时验签操作就和私钥d没啥关系了，就可以构造t使得R=G。

* Byeween

这题NSSCTF上也没有，不过这个原因我倒是知道。因为这个题目本身只有交互，没有题目的完整源码。而题目的内容是定义了一条有理数域上的椭圆曲线：

$$y^2 = x^3 -ax$$

并给出上面的一个点P，要求计算出所有满足2Q=P的Q点。

这个题目本身没什么可说的，如果知道sage中的division_points方法的话就可以直接调用就能搞定。但是问题在于，既然没有这个题目的源码，那么要搞出这个靶机的话，就要自己实现一下题目逻辑。看上去并不难，然而怎么生成一条曲线上的一个随机点却是个问题。因为有理数域上的ECC好像是不能直接random_points得到某个点的，所以似乎要人为的去构造出点。

那天在工坊群里也和一些师傅讨论了好一会儿，但是想了很久也没想出什么好方法。一些纵坐标为0的点固然可以构造，但是由这些点根本得不到纵坐标不为0的点，所以肯定不是这个思路。

Vinefruit

题目：

#!/usr/bin/env python3

import sys
import random
import binascii
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.buffer.readline()

def vinefruit(msg, mod, flag = 0):
	P = [16777619, 1099511628211, 309485009821345068724781371]
	O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
	assert mod in [0, 1, 2]
	p, o, m = P[mod], O[mod], 2 ** (2 << (4 + mod))
	vine = o
	for b in msg:
		if flag == 1:
			vine = (vine + b) % (2 ** 128)
		else:
			vine = vine ^ b
		vine = (vine * p) % m
	return vine

def main():
	border = "|"
	pr(border*72)
	pr(border, " Hi all, I have designed a gorgeous cryptography hash function in   ", border)
	pr(border, " order to secure the world! Your mission is to find collision for   ", border)
	pr(border, " this function with specific conditions.                            ", border)
	pr(border*72)
	
	step = 19

	while True:
		pr("| Options: \n|\t[S]ubmit collision \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 's':
			S = []
			for level in range(step):
				mod = random.randint(0, 2)
				pr(border, f'Submit two different string such that vinefruit(m1, {mod}, 1) = vinefruit(m2, {mod}, 1)')
				pr(border, f'You are at level: {level + 1}')
				if level == step - 1 and len(S) == step - 1:
					die(border, f'Congrats, you got the flag: {flag}')
				try:
					pr(border, f'Please send first byte string: ')
					s1 = sc()[:-1]
					pr(border, f'Please send second byte string: ')
					s2 = sc()[:-1]
					s1, s2 = binascii.unhexlify(s1), binascii.unhexlify(s2)
				except:
					pr(border, 'You should send valid hex strings.')
					break
				if len(s1) == len(s2) == 35 - level and s1 != s2:
					if vinefruit(s1, mod, 1) == vinefruit(s2, mod, 1):
						if vinefruit(s1, mod, 1) not in S:
							S.append(vinefruit(s1, mod, 1))
							pr(border, 'gj, try the next level :)')
						else:
							break
					else:
						break
				else:
					die(border, 'Kidding me?! Try again and be smart!! Bye!!!')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

题目完成18轮挑战后就得到flag。每轮挑战的内容是：

• 给出两个指定长度(35-level)的不同字节串的十六进制表示，要求他们经过特定函数vinefruit的输出值相同，且没有出现过

而vinefruit的处理过程是，对输入串的每一个字节m1、m2、…mn进行如下迭代得到输出：

$$vine = ((((o+m_1)p+m_2)p + ...+m_{n-1})p + m_n)p \quad(mod\;m)$$

其中，o、p、m由一个0-2的随机数mod决定。式中其实还有模2^128的操作，但由于只是加一个字节而已，所以实际上基本等于没用，就不写在上面了。

那现在的问题就是找到两个串，使他们得到的vine值相同。而这并不难，观察到上面的迭代过程完全可以写作一个关于p的多项式形式：

$$vine = (o+m_1)p^n + m_2p^{n-1} + ... + m_{n-1}p^2 + m_np \quad(mod\;m)$$

那么设s1的字节分别是a1、a2、…、an，s2是b1、b2、…、bn，那么就有：

$$vine = (o+a_1)p^n + a_2p^{n-1} + ... + a_{n-1}p^2 + a_np \quad(mod\;m)$$ $$vine = (o+b_1)p^n + b_2p^{n-1} + ... + b_{n-1}p^2 + b_np \quad(mod\;m)$$

作差就得到：

$$(a_1-b_1)p^n + (a_2-b_2)p^{n-1} + ... + (a_{n-1}-b_{n-1})p^2 + (a_n-b_n)p + km = 0$$

那么我们构造如下格：

$$\left(\begin{matrix} 1&&&&p^n\\ &1&&&p^{n-1}\\ &&\ddots&&\cdots\\ &&&1&p\\ &&&&m \end{matrix} \right)$$

这个格具有的线性关系是：

$$(a_1-b_1,a_2-b_2,...,a_{n-1}-b_{n-1},a_n-b_n,k) \left(\begin{matrix} 1&&&&p^n\\ &1&&&p^{n-1}\\ &&\ddots&&\cdots\\ &&&1&p\\ &&&&m \end{matrix} \right) = (a_1-b_1,a_2-b_2,...,a_{n-1}-b_{n-1},a_n-b_n,0)$$

所以给最后一列配上大系数保证规约出0，就可以LLL得到符合要求的字节差值构成的短向量。随便取其中一组拿来用就可以。为了保证s1、s2的每个字节均落在0-255中，就取s1全为128就可以满足要求了。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from tqdm import *

def gen_s1_s2(level,mod):
    length = 35-level
    P = [16777619, 1099511628211, 309485009821345068724781371]
    O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
    p, o, m = P[mod], O[mod], 2 ** (2 << (4 + mod))

    T = 2^1000
    L = Matrix(ZZ,length+2,length+2)
    for i in range(length):
        L[i,i] = 1
        L[i,-1] = p^(length-i)*T
    L[-2,-2] = T
    L[-2,-1] = (p^length)*T
    L[-1,-1] = m*T

    res = L.LLL()
    for i in res:
        if(i[-2] == 0):
            S = i[:-2]
            break
    s1 = [128 for i in range(length)]
    s2 = [s1[i] + S[i] for i in range(length)]
    assert all (i in range(0,256) for i in s2)

    s1 = hex(bytes_to_long(bytes(s1)))[2:]
    s2 = hex(bytes_to_long(bytes(s2)))[2:]
    return s1,s2


sh = remote("node4.anna.nssctf.cn",28829)
sh.sendline(b"s")

for level in trange(18):
    sh.recvuntil(b"Submit two different string such that vinefruit(m1, ")
    mod = int(sh.recvline().strip().decode()[0])

    s1,s2 = gen_s1_s2(level,mod)
    sh.recvuntil(b"Please send first byte string: ")
    sh.sendline(s1.encode())
    sh.recvuntil(b"Please send second byte string: ")
    sh.sendline(s2.encode())

sh.recvuntil(b"Congrats, you got the flag:")
print(sh.recvline())


#NSSCTF{c926d409-bcc9-4595-93dc-329dad0f30f0}

$ Shevid

看了wp知道找个轮子就可以解，但是我实在是一点都不懂isogeny。这些天断断续续读了很久hashhash师傅给我的isogeny的入门论文，发现抽代水平实在是差的有点太多，很多地方想求个一知半解都不行，就回头又去补抽代了。

希望有朝一日能至少大致弄懂isogeny，感觉入门门槛前所未有的高。

tough

* Slowsum

题目：

#!/usr/bin/env sage

import sys
from itertools import product
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.buffer.readline()

def slowsum(p, n):
	g = 0
	perms = list(product([0, 1], repeat = n))
	for _prm in perms:
		g += p(_prm)
	return g

def h4sh(p, q):
	coeffs = p.coefficients()
	return pow(sum(coeffs), (q - 1) // 2 - sum(coeffs), q) 

def main():
	border = "|"
	pr(border*72)
	pr(border, "Hi all, I have created a basic and rudimentary version of a sumcheck", border)
	pr(border, "protocol. Your task is to generate a false statement and persuade   ", border)
	pr(border, "verifier of its validity.                                           ", border)
	pr(border*72)
	
	q = 2**61 - 1  # Mersenne prime
	F = GF(q)

	while True:
		pr("| Options: \n|\t[C]laim the statement \n|\t[D]etermine parameters and polynomial \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 'd':
			pr(border, f'Please first send the number of variable and the degree of your desired polynomial:')
			_ans = sc()
			try:
				_n, _d = [int(_) for _ in _ans.split(b',')]
				if (_n * _d) // q < 5e-17 and _n >= 5 and _d >= 3:
					R = PolynomialRing(F, _n, 'x')
					x = R.gens()
				else:
					raise Exception()
			except:
				die(border, 'The parameters are not consistent! Try again!!')
			pr(border, f'Now, please send the {_n}-variable polynomial as p: ')
			_p = sc().strip().decode()
			try:
				_p = R(_p)
				p = _p
				_deg = _p.degree(std_grading=True)
				if _deg != _d:
					raise Exception()
			except:
				die(border, 'The polynomial is not valid or does not hold true in the given situations!')
			g = slowsum(_p, _n)
		elif ans == 'c':
			pr(border, 'Please send the g: ')
			_g = sc()
			try:
				_g = int(_g)
				if _g == g:
					die(border, 'Kidding me?! Bye :P')
			except:
				die(border, 'Some exception occurred! Bye!!')
			_P, _H = [], []
			for i in range(_n):
				pr(border, f'Please send the (p_{i}, h4sh(p_{i}, q)): ')
				pr(border, f'Note that the variable of p_{i} should be x. ')
				_ph = sc().strip()
				try:
					_p, _h = [_.decode() for _  in _ph.split(b',')]
					_R = PolynomialRing(F, 'x')
					_p, _h = _R(_p), F(_h)
					if _p.degree() > _d:
						raise Exception()
					_P.append(_p)
					_H.append(_h)
				except:
					die(border, 'Some exception occurred! Bye!!')
			j = 0
			for i in range(_n):
				if i == 0:
					if _P[i](0) + _P[i](1) != _g or h4sh(_P[i], q) != _H[i]:
						break
				else:
					if _P[i](0) + _P[i](1) != _P[i-1](_H[i-1]) or h4sh(_P[i], q) != _H[i]:
						break
				j += 1
			if j < _n or p(_H) != _P[_n-1](_H[_n-1]):
				die(border, 'Oops, verifier believes that the polynomial is not valid! Bye!!')
			die(border, f'Congrats, here the flag: {flag}')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

看了半天题目，人都看晕了也没把过程理明白。最终也失去了耐心选择直接看春哥的wp。

然后就发现，如果把题目条件一条条理清楚，并且发现他并不对0做检查，就可以把题目简化到一种极其简单的所有项均为0的情况，然后此时随便取f为常数项为0的多项式并计算slowsum的g就可以通过核验了。

不过我的确是没有耐心读题、找出这种解法的能力，虽然说如果是真的在比赛的话心态或许会不太一样，但是我觉得我还是暂时做不出来这种代码比较复杂的题目的，希望之后能耐着性子去理解题目内容。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from itertools import product

def slowsum(p, n):
	g = 0
	perms = list(product([0, 1], repeat = n))
	for _prm in perms:
		g += p(_prm)
	return g

q = 2**61 - 1  # Mersenne prime
F = GF(q)
n = 5
d = 3
R = PolynomialRing(F, n, 'x')
x = R.gens()
p = "x0^3"
_p = R(p)
g = slowsum(_p, n)


sh = remote("node4.anna.nssctf.cn",28301)

sh.recvuntil(b"[Q]uit")
sh.sendline(b"d")
sh.recvuntil(b"desired polynomial:")
sh.sendline(b"5,3")
sh.recvuntil(b"polynomial as p: ")
sh.sendline(p.encode())


sh.recvuntil(b"[Q]uit")
sh.sendline(b"c")
sh.recvuntil(b"Please send the g: ")
sh.sendline(b"0")
for i in range(n):
	sh.recvuntil(b"should be x. ")
	sh.sendline(b"0,0")
sh.recvuntil(b"here the flag:")
print(sh.recvline())


#NSSCTF{6110e36c-8e21-4ffc-9e31-4329dba63f65}

* ASIv2

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def base(n, l):
    D = []
    while n > 0:
        n, r = divmod(n, l)
        D.append(r)
    return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
	l = len(seed)
	_seed = base(bytes_to_long(seed), 3)
	_l = len(_seed)
	R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
	S = []
	for r in R:
		s = 0
		for _ in range(_l):
			b = ((int(r[_]) + int(_seed[_])) % 3) % 2
			s = s ^ b
		S.append(s)
	print(len(S))
	return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

这个之前做另一道类似题目的时候已经学习过解法了。wp见：

Crypto趣题-其他 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp：

from Crypto.Util.number import *

with open(r'E:\vscode\output.txt') as f:
    exec(f.read())

n = len(R[0])
A = []
b = []

for i in range(3 * n):
    Aline = []
    bline = S[i]
    for j in range(n):
        if (R[i][j] == 0):
            Aline.extend([0, 1, 0])
        elif (R[i][j] == 1):
            Aline.extend([1, 0, 0])
        elif (R[i][j] == 2):
            Aline.extend([0, 0, 1])
    A.append(Aline)
    b.append(bline)

A = matrix(GF(2), A)
b = vector(GF(2), b)
x = A.solve_right(b)
#print(x)

ans = []
for i in range(n):
    if (x[3*i] == 1) and (x[3*i+1] == 0) and (x[3*i+2] == 0):
        ans.append(0)
    elif (x[3*i] == 0) and (x[3*i+1] == 1) and (x[3*i+2] == 0):
        ans.append(1)
    elif (x[3*i] == 0) and (x[3*i+1] == 0) and (x[3*i+2] == 1):
        ans.append(2)
    elif (x[3*i] == 1) and (x[3*i+1] == 1) and (x[3*i+2] == 0):
        ans.append(2)

from Crypto.Util.number import *
ans = ''.join(str(x) for x in ans)
ans = long_to_bytes(int(ans, 3))
print(ans)