2022第五空间

2022第五空间网络安全大赛

5_vgcd

from random import getrandbits, seed
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from os import urandom
from secret import flag

def sample(rho, eta, gamma, p):
    seed(urandom(8))
    return p * getrandbits(gamma - eta) + getrandbits(rho)

def gen_vector(rho, eta, gamma, m, p, K):
    v = vector([sample(rho, eta, gamma, p) for i in range(m)])
    return K*v 
    
rho = 6
m = 3
eta = 288
gamma = 512
p = getPrime(gamma)
q = getPrime(gamma)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
c = pow(bytes_to_long(flag), e, n)
print(n)
print(c)

pp = p >> (gamma - eta)
assert isPrime(pp)
K = Matrix.random(Integers(pp), m, m).lift()
t1 = [gen_vector(rho, eta, gamma, m, pp, K) for i in range(1024)]
print(t1)
for i in range(4):
    t2 = [gen_vector(rho, eta, gamma, m, pp, K) for i in range(512)]
    print(t2)

t1和t2由若干个$K*v$组成。(这个不应该是$v*K$吗？)
$$
\begin{align}
K*v &=
\left[
\begin{matrix}
k_{11} & k_{12} & k_{13}\\
k_{21} & k_{22} & k_{23}\\
k_{31} & k_{32} & k_{33}
\end{matrix}
\right]
*
\left[
\begin{matrix}
(pp*r_{226}+r_6) & (pp*rr_{226}+rr_6) & (pp*rrr_{226}+rrr_6)
\end{matrix}
\right]
\\&=
\left[
\begin{matrix}
a_1*pp+b_1 & a_2*pp+b_2 & a_3*pp+b_3
\end{matrix}
\right]
\end{align}
$$

其中$a_i,b_i$表示如下
$$
\begin{align}
a_i &= k_{1i}*r_{226}+k_{2i}*rr_{226}+k_{3i}*rrr_{226}\\
b_i &= k_{1i}*r_{6}+k_{2i}*rr_{6}+k_{3i}*rrr_{6}
\end{align}
$$
有这么多形如$a*pp+b$，可以通过消去$b$然后求公约数得到$pp$，最后$coppersmith$已知高位求低位求解$p$。

这里需要用到生日攻击，可以简单理解为在这么多数中，有很大概率存在相同$r_6,r_6,r’’_6$，因此可以循环遍历一下所有的$K*v$。

算一下大致的概率。$r_6,r_6,r’’_6$的组合有$2^{18}$种可能，所给数据有$3072$个，套用公式得存在相同的概率近似$100\%$。

代码如下

from tqdm import tqdm
from gmpy2 import gcd,is_prime,invert
from Crypto.Util.number import *

e = 65537
with open(r'output10.txt','rb') as f:
    n = int(f.readline().decode())
    c = int(f.readline().decode())
    L = eval(f.readline().decode())
    L += eval(f.readline().decode())
    L += eval(f.readline().decode())
    L += eval(f.readline().decode())
    L += eval(f.readline().decode())

print(n)
print(c)
for i in tqdm(range(len(L))):
    for j in range(i+1,len(L)):
        x1 = L[i][0] - L[j][0]
        x2 = L[i][1] - L[j][1]
        pp = int(gcd(x1,x2))
        if pp.bit_length() == 288 and is_prime(pp):
            R.<x> = PolynomialRing(Zmod(n))
            f = (pp << 224) + x
            re = f.small_roots(X = 2^224,beta=0.4)
            if re:
                p = int(f(re[0]))
                q = n//p
                phi = (p-1)*(q-1)
                d = int(invert(e,phi))
                m = pow(c,d,n)
                print(f'p={p},q={q}')
                print(long_to_bytes(m))
                

---

参考：

【2022 第五空间】5_vgcd WriteUP_Mr_AgNO3的博客-CSDN博客