writeup for 2021虎符

啊太菜了太菜了…打这CTF也有半年了,还是这么菜,好想有一次能ak啊…..
两道题一题手快找到资料拿了个三血, 另外一题做了半天都没出来, 有条关系式理解错了真的想锤人….

0x00 cubic

problem

from math import gcd
from functools import reduce
from fractions import Fraction as Frac


N = 6

def read_num(prompt):
    try:
        num = int(input(prompt))
    except:
        return 0
    return num if num > 0 else 0


print(f"Please give me {N} pairs of positive integers (x,y,z) "
      f"satisfying the equation `x/(y+z) + y/(z+x) + z/(x+y) = {N}`\n")
anss = []
mark = 0
for i in range(N):
    x = read_num("[>] x: ")
    y = read_num("[>] y: ")
    z = read_num("[>] z: ")
    if x * y * z == 0: # positive integer
        mark = 1
        print("This is not what i want!\n")
        break
    if reduce(gcd, [x, y, z]) != 1: # (kx, ky, kz)
        mark = 1
        print("This is not what i want!\n")
        break
    if Frac(x, y+z) + Frac(y, z+x) + Frac(z, x+y) != N:
        mark = 1
        print("This is not what i want!\n")
        break
    ans = tuple(sorted([x, y, z])) # (y, x, z)
    if ans in anss:
        mark = 1
        print("This is not what i want!\n")
        break
    else:
        print("You are right!\n")
        anss.append(ans)
if mark == 0:
    flag = open('/flag', 'r').read()
    print("flag is: " + flag + "\n")
else:
    print("Something wrong!\n")

analyses

找到6组$a,b,c$满足:
$$
{a \over b+c}+{b \over a+c}+{c \over a+b} = 6
$$
这题拿到就直接去搜了, 没想到直接出来一篇知乎的文章, 看完之后才知道原来是椭圆曲线….
原理什么的里面讲的很清楚了, 这边就不再说了, 只是中间有一个化式子为维尔斯特拉斯形式的过程, 我是误打误撞弄成的(因为公式是同一个, 直接改一下知乎里的就行了), 后来找到了paper - > An unusual cubic representation problem, 才找到具体的公式
$$
a={8(N+3)-x+y \over 2(N+3)(4-x)} \\
b={8(N+3)-x-y \over 2(N+3)(4-x)} \\
c={-4(N+3)-x(N+2) \over (N+3)(4-x)}
$$
这里的$N = 6$
有了这个我们就能把式子化成$y^2 = ax^3 + bx^2+cx$的形式了, 这里又有个问题, 该怎么利用上面的式子快速化成我们要的形式呢当然是拿草稿纸算啦

这里可以利用sage的解方程, 解出这个关系式来

a,b,c,x,y = var('a'),var('b'),var('c'),var('x'),var('y')
N = 6
a=(8*(N+3)-x+y)/(2*(N+3)*(4-x))
b=(8*(N+3)-x-y)/(2*(N+3)*(4-x))
c=(-4*(N+3)-(N+2)*x)/((N+3)*(4-x))
f = a^3 + b^3 +c^3 - 9*a*b*c - 5*(a^2*b+a^2*c+b^2*a+b^2*c+c^2*a+c^2*b)
print(f.solve(y)[0])
# y == -sqrt(x^3 + 213*x^2 + 288*x)

然后利用解出来的参数跟着知乎上的内容写代码就行了, 要知道原理就去知乎看吧, 链接也在上面了

exp

a,b,c,x,y = var('a'),var('b'),var('c'),var('x'),var('y')
N = 6
a=(8*(N+3)-x+y)/(2*(N+3)*(4-x))
b=(8*(N+3)-x-y)/(2*(N+3)*(4-x))
c=(-4*(N+3)-(N+2)*x)/((N+3)*(4-x))
f = a^3 + b^3 +c^3 - 9*a*b*c - 5*(a^2*b+a^2*c+b^2*a+b^2*c+c^2*a+c^2*b)
print(f.solve(y)[0])


ee=EllipticCurve([0,213,0,288,0])
P = ee(-200,680)

def check(num):
    return num if num > 0 else 0

def orig(P,N):
    x=P[0]
    y=P[1]
    a=(8*(N+3)-x+y)/(2*(N+3)*(4-x))
    b=(8*(N+3)-x-y)/(2*(N+3)*(4-x))
    c=(-4*(N+3)-(N+2)*x)/((N+3)*(4-x))
    da=denominator(a)
    db=denominator(b)
    dc=denominator(c)
    l=lcm(da,lcm(db,dc))
    return [a*l,b*l,c*l]
i = 1
arr = []
while True:
    f = True
    res = orig(i*P,6)
    for j in res:
        if check(j) == 0:
            f = False
    if f:
        arr.append(res)
    i+=1
    if len(arr) == 6:
        break
arr

0x01 simultaneous

problem

from functools import reduce
from flag import flag

def encrypt(m, e, n):
    n = int(n)
    size = n.bit_length() // 2
    m_low = m & ((1 << size) - 1)
    m_high = (m >> size)

    b = (m_low**2 - m_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])

    return (EC((m_high, m_low)) * e).xy()

def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2

    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)

    return (m_high << size) | m_low

def gen_prime(size):
    p = random_prime(1 << size, lbound=1 << (size-1))
    while p % 3 != 2:
        p = random_prime(1 << size, lbound=1 << (size-1))

    q = random_prime(1 << size, lbound=1 << (size-1))
    while q % 3 != 2:
        q = random_prime(1 << size, lbound=1 << (size-1))

    if q > p:
        p, q = q, p

    return ZZ(p), ZZ(q)


SIZE = 512
HINTSIZE = 96

assert len(flag) == 42
flag = int.from_bytes(flag, "big")

masks = [randint(1 << (SIZE-1), 1 << SIZE) for _ in range(3)] # 2^512 bits 三个
masked_flag = reduce(lambda a, b: a ^^ b, masks, flag) # 四个一起异或


count = 0
ciphertexts = []
x = random_prime(floor((1<<(2*SIZE-2))**0.373), proof=False) 
while count < 3:
    try:
        p, q = gen_prime(SIZE)
        n = p * q

        y = random_prime(floor(n**0.373), proof=False)
        zbound = -1 * int(((p-q) * round(n ** 0.25) * y) // (3 * (p + q)))

        z_ = zbound + ((p + 1)*(q + 1)*y - zbound) % x
        e = ((p + 1) * (q + 1) * y - z_) // x

        assert (e*x - y*(p+1)*(q+1) == -z_)
        assert (abs(z_) < abs(zbound))
        assert (gcd(x, y) == 1)

        d = inverse_mod(e, (p+1)*(q+1))
        c = encrypt(masks[count], e, n)
        assert decrypt(c, d, n) == masks[count]

        ciphertexts.append({
            "n": n,
            "e": e,
            "c": c,
            "hint": p & ((1<<HINTSIZE)-1)
        })
        count += 1
    except KeyboardInterrupt:
        break
    except ZeroDivisionError:
        pass


print("masked_flag = ", masked_flag)
print("ciphertexts = ", ciphertexts)

analyses

用的ECC加密了三个masked_flag, 但基本上没办法从ECC上入手. 回来看前面的密钥生成.

这里每一轮的私钥都是不同的, 每一轮都随机生成素数y, 并利用x,y两个素数生成一个公钥e

因为每轮用的x都是相同的, 而且我们有关系式:
$$
\begin{cases}
e_1 x = y_1(p_1+1)(q_1+1) - z_1 \\
e_2 x = y_2(p_2+1)(q_2+1) - z_2 \\
e_3 x = y_3(p_3+1)(q_3+1) - z_1
\end{cases}
$$
化简一下可以有:
$$
\begin{cases}
e_1 x -y_1n_1 = y_1(p_1+q_1+1) - z_1 \\
e_2 x -y_2n_2 = y_2(p_2+q_2+1) - z_2 \\
e_3 x -y_3n_3 = y_3(p_3+q_3+1) - z_3
\end{cases}
$$
记$y_i(p_i+q_i+1) - z_i$为$s_i$, 可以造出这个一个格子
$$
(x,y_1,y_2,y_3)
\begin{pmatrix}
\sqrt n&e_1&e_2&e_3 \\
0&-n_1&0&0 \\
0&0&-n_2&0 \\
0&0&0&-n_3 \\
\end{pmatrix}
=
(\sqrt nx,s_1,s_2,s_3)
$$
这里的$x$和$y$都够小, 足够规约出结果来.
规约出$(\sqrt nx,s_1,s_2,s_3)$可以求出$x$和$y$

当时做到这里, 被超大的$z$卡住了, 做了一下午都没有想出该怎么用Hint,x,y把p搞出来. (zbound有关的式子被我弄错了!! 没有想到这个zbound虽然被消去但还是有作用的!)

比赛结束以后d33师傅发了一篇paper, 但是不能直接用里面的方法求,(界卡的太死了?) 说是要利用coppersmith的姿势和hint一点一点的把p整出来. 看了一天copper也没啥结果, 只能等wp了. 出来了再好好看看到底该怎么调coppersmith

后来翻虎符wp翻到一篇wp里面有一个二分法的方法, 看完才发现原来自己一直把zbound的式子搞错了… 不过就算没搞错自己也可能想不到那个构造方程的方法, 虽然那个方法不算特别复杂, 也算是好好学习了一波

参考这里的二分法

先来看一下生成$zbound$和$z$的等式
$$
zbound = \lfloor {(p-q)\cdot \lfloor n^{1\over 4}\rceil \cdot y \over 3(p+q)} \rceil \\
z = zbound + (y(p+1)(q+1) - zbound \mod x)
$$
这里我一开始做的时候忽略了一个细节, $y(p+1)(q+1) - zbound \mod x$是小于$x$的! 而$y$是略大于$x$的,那么会有
$$
{z \over y} =\lfloor {(p-q)\cdot \lfloor n^{1\over 4}\rceil \over 3(p+q)} \rceil +{(y(p+1)(q+1) - zbound \mod x) \over y} \approx \lfloor {(p-q)\cdot \lfloor n^{1\over 4}\rceil \over 3(p+q)} \rceil \tag 1
$$
第二项, 也就是省略掉的那个项是小于$1$的, 所以这个约等于两边其实是非常非常接近的.

我们上面计算了$s = y(p+q+1) - z$, 再根据$(1)$式, 就可以有
$$
{s \over y} = p + q + 1 - {z \over y} \approx p+q+1-\lfloor {(p-q)\cdot \lfloor n^{1\over 4}\rceil \over 3(p+q)} \rceil
$$
我们可以把后面的$\lfloor \rceil$先忽略, 因为它的影响并不大. 我们记$K = \lfloor {s \over y} \rceil$, 式子会是$p+q$和$p-q$的一个关系(其实这里已经式$p,q$的一个关系式了, 理论上根据$n = pq$已经可以解方程得到$p$的近似了, 但是为了计算上的方便, 才看成$p+q$和$p-q$
$$
K = p+q+1-{(p-q) \cdot \lfloor n^{1\over 4}\rceil \over 3(p+q)}
$$
移项, 并利用$(p-q)^2 = (p+q)^2 - 4pq$,可以把式子化成一个关于$p+q$的方程
$$
9((K-1)(p+q)-(p+q)^2 )^2 - n^{1 \over 2}((p+q)^2 - 4n) = 0 \\
9X^2(K-X-1)^2 - n^{1 \over 2}(X^2 - 4n) = 0
$$
但是前面用了太多的近似, 导致这个方程的解会偏离真正的$p+q$并且不再是整数解(这里我试了sage自带的解方程, 可能是我姿势不对, 解出来的结果再取整并不是正确的), 观察到当$X = K$和$X=0$的时候左边的式子是异号的, 这个时候就可以利用高中的知识! 根存在性定理, 并用二分法去逼近一个靠近解的整数$X_0$.

而这个$X_0 \approx p+q $, 利用这个$X_0$就可以大概率的解出$p,q$了

因为$X_0$只是个近似, 而且求出来还可能是奇数, 所以需要前后调一下, 比如+1 -1 +2 -2 等等
关于为啥不能是奇数, $p+q$怎么会是奇数呢hhh

至此, 我们成功的算出了$p,q$, 所有的参数包括私钥也都可以求出来了, 再利用题目自带的解密算法解密就行了.

exp

# sagemath
from gmpy2 import *
from Crypto.Util.number import long_to_bytes as l2b

def find_p_puls_q(f,k):
    s = 0
    b = k
    for i in range(2000):
        a = (s+b) // 2
        if f.subs(x==a) > 0:
            s = a 
        else:
            b = a
    return a

def find_p(pq,n):
    p = var('p')
    if pq^2 - 4*n<0:
        return []
    f = p^2 - pq*p+n
    r = f.roots()
    res = []
    for i in r:
        if i[0]>0:
            res.append(int(i[0]))
    return (res[0],res[1])

def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2

    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)

    return (m_high << size) | m_low

masked_flag =  10629883656219490982178951599484437698263214790268091560719514148215968944141123323489358824379735126966804354267426040231682908197526817342035901781691470
ciphertexts =  [...]

PK = []
N = [ciphertexts[0]['n'],ciphertexts[1]['n'],ciphertexts[2]['n']]
E = [ciphertexts[0]['e'],ciphertexts[1]['e'],ciphertexts[2]['e']]
C = [ciphertexts[0]['c'],ciphertexts[1]['c'],ciphertexts[2]['c']]

M=iroot(int(N[0]),2)[0]
a=[0]*4
a[0]=[M,E[0],E[1],E[2]]
a[1]=[0,-N[0],0,0]
a[2]=[0,0,-N[1],0]
a[3]=[0,0,0,-N[2]]


Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
x = int(abs(Mat_LLL[0][0])//M)
assert x * M == abs(Mat_LLL[0][0])
S=[Mat_LLL[0][1],Mat_LLL[0][2],Mat_LLL[0][3]]
A=[round(N[0]^0.25)^2,round(N[1]^0.25)^2,round(N[2]^0.25)^2]

assert (E[0] * x - S[0]) % N[0] == 0
assert (E[1] * x - S[1]) % N[1] == 0
assert (E[2] * x - S[2]) % N[2] == 0
Y = [0,0,0]
for i in range(3):
    Y[i] = (E[i]*x - S[i]) // N[i]
KK = [0,0,0]
for i in range(3):
    KK[i] = (E[i] * x -Y[i] * N[i] ) // Y[i]

x = var('x')
FF = [0,0,0]
for i in range(3):
    FF[i] = (3*(KK[i]-1)*x-3*x^2)^2 - A[i]*(x^2-4*N[i])
ppq1 = find_p_puls_q(FF[0],KK[0])
ppq2 = find_p_puls_q(FF[1],KK[1])
ppq3 = find_p_puls_q(FF[2],KK[2])

p1,q1 = find_p(ppq1+1,N[0])
p2,q2 = find_p(ppq2+1,N[1])
p3,q3 = find_p(ppq3+1,N[2])

d1,d2,d3 = inverse_mod(E[0],(p1+1)*(q1+1)),inverse_mod(E[1],(p2+1)*(q2+1)),inverse_mod(E[2],(p3+1)*(q3+1))
l2b(decrypt(C[0],d1,N[0])^^decrypt(C[1],d2,N[1])^^decrypt(C[2],d3,N[2])^^masked_flag)