apbq

三段 RSA ，第一段简单，第二段原题，第三段纯纯nt

第一段

第一段是一个已知 $p+q$ 的 RSA ，很简单

from Crypto.Util.number import *

p_plus_q = ...
n = ...
e = ...
c = ...

phi = n-p_plus_q+1
d = pow(e,-1,phi)
m = pow(c,d,n)
flag1 = long_to_bytes(m)
print(flag1)
# flag{yOu_can_

第二段

第二段是 DownUnderCTF 2023 原题，这里记录一下学习过程

apbq rsa i

原题是 apbq rsa ii ，是在 apbq rsa i 的基础上

apbq rsa i 题目如下

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

hints = []
for _ in range(2):
    a, b = randint(0, 2**12), randint(0, 2**312)
    hints.append(a * p + b * q)

FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')

给了两个等式 \[ \begin{cases} h_1=a_1p+b_1q\\ h_2=a_2p+b_2q \end{cases} \] 消去$p$ \[ a_2h_1-a_1h_2=(a_2b_1-a_1b_2)q \] 于是 $a_2h_1-a_1h_2$ 是 $q$ 的倍数，于是 $q$ 是 $a_2h_1-a_1h_2$ 和 $n$ 的 $gcd$，而a1和a2的位数很小，于是可以爆破

from itertools import *
from math import gcd

from Crypto.Util.number import *
n = ...
c = ...
hints = [...]
# 参数见原题
h1 = hints[0]
h2 = hints[1]
for a1, a2 in product(range(2**12), repeat=2):	# 相当于product(range(2**12), range(2**12))
    q = gcd(a2 * h1 - a1 * h2, n)
    if q != 1 and q < n:
        print("q found:",q)
        break

p = n // q
phi = (p-1)*(q-1)
e = 65537
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# DUCTF{gcd_1s_a_g00d_alg0r1thm_f0r_th3_t00lbox}

apbq rsa ii

接下来是 apbq rsa ii ，题目如下

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

hints = []
for _ in range(3):
    a, b = randint(0, 2**312), randint(0, 2**312)
    hints.append(a * p + b * q)

FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')

和上一道差不多，区别在于多了一个提示，同时a的位数变大了，现在和b一样

2024.11.7 实在看不懂，只能先把大佬文章先留下来

DownUnderCTF 2023 Writeups

2024-强网杯-wp-crypto

初步推导

和上一题差不多的推导，由三个等式可以消去 $p$ 和 $q$ 两个变量 \[ a_1a_3b_2h_1-a_1a_2b_3h_1-a_1a_3b_1h_2+a_1^2b_3h_2+a_1a_2b_1h_3-a_1^2b_2h_3=0 \] 提取公因子 $a_1$ \[ (a_3b_2-a_2b_3)h_1+(a_1b_3-a_3b_1)h_2+(a_2b_1-a_1b_2)h_3=0 \] 于是构造格 \[ \begin{pmatrix} a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 \end{pmatrix} \begin{pmatrix} h_1 & 1 & 0 &0 \\\\ h_2 & 0 & 1 & 0 \\\\ h_3 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 \end{pmatrix} \] 做一下范数平衡，验证Hermite定理

\[ ||v||=\sqrt{0^2+(a_3b_2-a_2b_3)^2+(a_1b_3-a_3b_1)^2+(a_2b_1-a_1b_2)^2} \] 约为 $312*2=624$ 位

非方阵的行列式见笔记另一篇笔记 Lattice \[ det(L)=\sqrt{1+\sum_{i = 0}^{n}\alpha_i^2}=\sqrt{1+h_1^2+h_2^2+h_3^2} \] 约为 $h_1$ 的位数，$1336$ 位，所以 $\sqrt {n}det(L)^\frac{1}{n}$ 约为 $1336/4\approx334$ 位，不满足条件，于是第一列乘 $n$（题目给的 $n$，不是维数）

乘完之后，$||v||$ 还是 $624$ 位，$\sqrt {n}det(L)^\frac{1}{n}$ 增大到 $(1336+2048)/4=846$ 位，满足要求

系数调整

取格出来的第一个行向量，就是我们要的 \[ \begin{pmatrix}0 & a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 \end{pmatrix} \] 但看其它师傅的博客，还有正负号需要调整

_, t, u, v = L[0]
# therefore this should hold
# assert abs(a3*b2 - a2*b3) == abs(t)
# assert abs(a3*b1 - a1*b3) == abs(u)
# assert abs(a2*b1 - a1*b2) == abs(v)
a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens()
for sign in itertools.product((-1,1), repeat=3):
    I = ideal(
        [
            a3s * b2s - a2s * b3s + sign[0] * t,
            a3s * b1s - a1s * b3s + sign[1] * u,
            a2s * b1s - a1s * b2s + sign[2] * v,
        ]
    )
    if I.dimension() != -1:
        print(sign)
        print("dim", I.dimension())

groebner basis

现在得到了理想 \[ (a3s * b2s - a2s * b3s - t, a3s * b1s - a1s * b3s + u, a2s * b1s - a1s * b2s - v) \] 做 groebner_basis...

额额，什么是 groebner_basis？

先参考以下几篇文章，学习了一下groebner basis

https://www.cnblogs.com/ZimaBlue/articles/16927952.html

https://zhuanlan.zhihu.com/p/262906557

groebner basis定义即

其中，S-polynomial函数的定义为

即 groebner basis （本身是一个生成元组）中的生成元均满足：对任意两个生成元，二者首项的最小公倍项除以各自的首项后乘以自己本身，得到的项相减，也就是S-polynomial函数的结果，能够整除 groebner basis 自己

我自己的认识是：

通过做 groebner basis ，可以将复杂的等式按照变量进行剥离，得到更“干净”的关系

在本题中，对理想 I 做 groebner basis 后，可以得到三个更简单的等式，其中第二个等式是一个 $k_1a_1+k_2a_2+k_3a_3=0$ 的简单等式，第三个等式是一个 $k_1b_1+k_2b_2+k_3b_3=0$ 的简单等式

后续

接下来，用这两个等式，我们再LLL规一次即可 \[ \begin{pmatrix} a_1 & a_2 &a_3 \end{pmatrix} \begin{pmatrix} k_1 & 1 & 0 &0 \\\\ k_2 & 0 & 1 & 0 \\\\ k_3 & 0 & 0 & 1\end{pmatrix} = \begin{pmatrix}0 & a_1 & a_2 & a_3\end{pmatrix} \] 对$b_1、b_2、b_3$也同理

这个格满足Hermite定理，能直接规出来结果，用规出来的 $a_1、a_2和a_3$ ，接下来用 apbq rsa i 的思路解即可

2024.11.13 原wp部分如下，其中的线性组合我没理解是干啥的，组合的系数范围也不知道怎么定的，反正我规出来的结果可以直接用

xs = []
for c1, c2 in product((-2, -1, 0, 1, 2), repeat=2):
	v = c1 * v1 + c2 * v2
    _, x1, x2, x3 = v
    if all([0 <= x <= 2**312 for x in (x1, x2, x3)]):
    	xs.append((x1, x2, x3))
# we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
# just try all combinations
for g1, g2 in combinations(xs, 2):
	a1r, a2r, a3r = g1
	b1r, b2r, b3r = g2

同时，我还做了验证

for c1, c2 in itertools.product((0, 1), repeat=2):
    v = c1 * v1 + c2 * v2
    _, x1, x2, x3 = v
    print(f"c1: {c1}, c2:{c2}, v:{v}")
    if all([0 <= x <= 2**312 for x in (x1, x2, x3)]):
        xs.append((x1, x2, x3))
# we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
# just try all combinations
for g1, g2 in itertools.combinations(xs, 2):
	a1r, a2r, a3r = g1
	print("g1:",g1)
	b1r, b2r, b3r = g2

可以根据下面的打印调试信息知道，遍历出来的结果，系数其实就是1和0，也就是直接用规出来的结果

我自己调整过的exp如下

import itertools
from Crypto.Util.number import *

n = ...
c = ...
hints = [...]


# assert a2 * h1 - a1 * h2 == (a2 * b1 - a1 * b2) * q
# assert a3 * h1 - a1 * h3 == (a3 * b1 - a1 * b3) * q
# assert (a3 * b1 - a1 * b3) * (a2 * h1 - a1 * h2) == (a2 * b1 - a1 * b2) * (a3 * h1 - a1 * h3)
# so: a1*a3*b2*h1 - a1*a2*b3*h1 - a1*a3*b1*h2 + a1^2*b3*h2 + a1*a2*b1*h3 - a1^2*b2*h3 == 0
# we try to use LLL to find them

h1, h2, h3 = hints
L = matrix(hints).T.augment(matrix.identity(3))
L[:, 0] *= n
L = L.LLL()
for v in L:
    print(v)
    print([int(x).bit_length() for x in v])

# the expected vector is (a1*a3*b1-a1*a2*b3, -a1*a3*b1+a1**2*b3, a1*a2*b1-a1**2*b2)
# but we can see that a1 divides all of them
# assuming gcd(gcd((a1*a3*b2-a1*a2*b3), (-a1*a3*b1+a1**2*b3)), (a1*a2*b1-a1**2*b2)) == 1 here
# the shortest vector should be (a3*b2-a2*b3, -a3*b1+a1*b3, a2*b1-a1*b2)

_, t, u, v = L[0]
# therefore this should hold
# assert abs(a3*b2 - a2*b3) == abs(t)
# assert abs(a3*b1 - a1*b3) == abs(u)
# assert abs(a2*b1 - a1*b2) == abs(v)
a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens()
for sign in itertools.product((-1,1), repeat=3):
    I = ideal(
        [
            a3s * b2s - a2s * b3s + sign[0] * t,
            a3s * b1s - a1s * b3s + sign[1] * u,
            a2s * b1s - a1s * b2s + sign[2] * v,
        ]
    )
    if I.dimension() != -1:
        print(sign)
        print("dim", I.dimension())
        print("groebner_basis",I.groebner_basis())
        def step2(f):
            # this f is in the form of k1*a1+k2*a2+k3*a3==0
            # for some reason, k1*b1+k2*b2+k3*b3==0 also holds
            # use LLL to find it
            print("=" * 40)
            print(f)
            L = matrix(f.coefficients()).T.augment(matrix.identity(3))
            L[:, 0] *= n
            L = L.LLL()
            print(L[0])
            print(L[1])
            _ , a1r, a2r, a3r = L[0]
            q = gcd(a2r * h1 - a1r * h2, n)
            if 1 < q < n:
                p = n // q
                e = 0x10001
                d = inverse_mod(e, (p - 1) * (q - 1))
                m = pow(c, d, n)
                flag = int(m).to_bytes(1024, "big").strip(b"\x00")
                print(flag)
                exit()

        step2(I.groebner_basis()[1])
# DUCTF{0rtho_l4tt1c3_1s_a_fun_and_gr34t_t3chn1que_f0r_the_t00lbox!}

原exp有几个地方需要注意，一个是下面这个调试打印的地方

1
2
3

for v in L:
    print(v)
    print([x.bit_length() for x in v])

要改成

1
2
3

for v in L:
    print(v)
    print([int(x).bit_length() for x in v])

然后是用product函数遍历的时候会报错'int' object is not iterable sage

for sign in product((-1,1), repeat=3):
    I = ideal(
        [
            a3s * b2s - a2s * b3s + sign[0] * t,
            a3s * b1s - a1s * b3s + sign[1] * u,
            a2s * b1s - a1s * b2s + sign[2] * v,
        ]
    )

这个问题困扰我挺久的，我把数据类型换来换去都不对，后来查看了product的类型，也是function，但万万没想到原来这里的function不是预期的function

1	<function symbolic_prod at 0x7f2ea9d2f8b0>

可以看到，product函数已经变成了symbolic_prod，而这是一个sage里的函数

因为这里本意是使用python里的product函数，但这是一个sage脚本，在sage环境里跑的时候，会使用sage里面的同名函数，所以会报参数错误

解决办法很简单，在导入product函数的时候换个名字就行

1	from itertools import product as it_product

然后后面在使用product的地方修改为

1	for sign in it_product((-1,1), repeat=3):

或者是指定一下使用的是itertools库中的product函数

1	for sign in itertools.product((-1,1), repeat=3):

这样的话导入的时候就要改成

1	import itertools

另一版 exp

import itertools
from Crypto.Util.number import long_to_bytes

# n, c, hints
exec(open('../src/output.txt', 'r').read())

V = hints
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]

for s, t in itertools.product(range(4), repeat=2):
    T = s*B[0] + t*B[1]
    a1, a2, a3 = T
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    if 1 < kq < n:
        print('find!', kq, s, t)
        break
for i in range(2**16, 1, -1):
    if kq % i == 0:
        kq //= i
q = int(kq)
p = int(n // kq)
d = pow(0x10001, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag)

其实思路差不多，这段里面的线性组合也可以去掉

import itertools

from Crypto.Util.number import long_to_bytes

n = ...
c = ...
hints = [...]

V = hints
k = 2^800

M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
print(M.LLL())
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
print(M.LLL())
B = [b[1:] for b in M.LLL() if set(b[:1]) == {0}]
print(B)

a1, a2, a3 = B[0]
kq = gcd(a1 * hints[1] - a2 * hints[0], n)
if 1 < kq < n:
    print('find!', kq)

for i in range(2**16, 1, -1):
    if kq % i == 0:
        kq //= i
q = int(kq)
p = int(n // kq)
d = pow(0x10001, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
flag = long_to_bytes(int(m)).decode()
print(flag)

回到这道题目

这道题唯一的区别就是3组变成了100组

1、2与任一其它等式联立得到 \[ (a_ib_2-a_2b_i)h_1+(a_1b_i-a_ib_1)h_2+(a_2b_1-a_1b_2)h_i=0 \] 构造格如下 \[ \begin{pmatrix} a_2b_1-a_1b_2 & a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_4b_2-a_2b_4 & a_1b_4-a_4b_1 & \dots & a_{100}b_2-a_2b_{100} & a_1b_{100}-a_{100}b_1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & h_3 & h_4 & h_5 & \dots & h_{100}\\\\ 0 & 1 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & h_1 & 0 & 0 & \dots & 0\\\\ 0 & 0 & 1 & 0 & 0 & 0 & \dots & 0 & 0 & h_2 & 0 & 0 & \dots & 0\\\\ 0 & 0 & 0 & 1 & 0 & 0 & \dots & 0 & 0 & 0 & h_1 & 0 & \dots & 0\\\\ 0 & 0 & 0 & 0 & 1 & 0 & \dots & 0 & 0 & 0 & h_2 & 0 & \dots & 0\\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\\\ 0 & 0 & 0 & 0 & 0 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & \dots & h_1\\\\ 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 1 & 0 & 0 & 0 & \dots & h_2 \end{pmatrix} = \begin{pmatrix} a_2b_1-a_1b_2 & a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_4b_2-a_2b_4 & a_1b_4-a_4b_1 & \dots & a_{100}b_2-a_2b_{100} & a_1b_{100}-a_{100}b_1 & 0 & \dots & 0 \end{pmatrix} \]

平衡范数和之前一样，规出来之后，就和那个题一样了

大佬的exp

#stage2
from re import findall
from subprocess import check_output
from itertools import *

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

hint2 =
n2, e2 = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

h = hint2
nums = 98
L = Matrix(ZZ, 1+nums*2, 1+nums*3)
for i in range(1+nums*2):
    L[i,i] = 1
for i in range(nums):
    L[0,1+nums*2+i] = h[i+2]
    L[2*i+1,1+nums*2+i] = h[0]
    L[2*i+2,1+nums*2+i] = h[1]
L[:,-nums:] *= 2^512
L = flatter(L)

# 后面和apbq rsa ii的一样

这里用的是flatter来做格基规约，会更快一点，用普通的LLL也可以的

1 2	L[:,-nums:] *= 2^512 L = L.LLL()

同样的，这段exp里step2部分也可以像之前说的一样，线性组合部分也可以去掉

这道题的另一种解法——正交格

其实如果直接顺着 apbq rsa ii 的思路来，应该可以得到下面这个等式

（$h_1\sim h_{100}$ 放在第一列和最后一列一样) \[ \begin{pmatrix} a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 &0 & 0 &\dots & 0 \\\\ a_4b_2-a_2b_4 & a_1b_4-a_4b_1 &0 & a_2b_1-a_1b_2 & 0 &\dots & 0\\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots &\vdots\\\\ a_{100}b_2-a_2b_{100} & a_1b_{100}-a_{100}b_1 &0 &\dots &\dots &\dots & a_2b_1-a_1b_2 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & \dots & 0 & h_1\\\\ 0 & 1 & 0 & \dots & 0 & h_2\\\\ 0 & 0 & 1 & \dots & 0 & h_3\\\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\\\ 0 & 0 & 0 & \dots & 1 & h_{100} \end{pmatrix} = \begin{pmatrix} a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 & 0 & 0 & \dots & 0 & 0\\\\ a_4b_2-a_2b_4 & a_1b_4-a_4b_1 &0 & a_2b_1-a_1b_2 & 0 & \dots & 0 & 0\\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\\\ a_{100}b_2-a_2b_{100} & a_1b_{100}-a_{100}b_1 &0 &\dots &\dots &\dots & a_2b_1-a_1b_2 & 0 \end{pmatrix} \] 由于格的学习不是很系统，我错误地以为这个是上一种构造格的方式，直接认为对 $$ \[\begin{pmatrix} 1 & 0 & 0 & \dots & 0 & h_1 \\\\ 0 & 1 & 0 & \dots & 0 & h_2\\\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\\\ 0 & 0 & 0 & \dots & 1 & h_{100} \end{pmatrix}\] \[ 格基规约后的结果，第一个行向量就是 \] \[\begin{pmatrix} a_3b_2-a_2b_3 & a_1b_3-a_3b_1 & a_2b_1-a_1b_2 & 0 & 0 & \dots & 0 & 0 \end{pmatrix}\]

$$ 实际上不是这样的，这个等式是用来做正交格的

正交格学习

强烈推荐的大佬，一直在持续更新

Crypto趣题-曲线

右核学习

右核的定义

对于矩阵 $M$（形状为 $m \times n$），右核是所有使得 $M \cdot \mathbf{v} = 0$ 的向量 $\mathbf{v}$ 的集合，即 \[ \text{Ker}(M) = \{\mathbf{v} \in \mathbb{R}^n \ | \ M \cdot \mathbf{v} = \mathbf{0} \} \] 右核是一个向量空间，因此它有以下性质：

它的维度称为右核的维数，由维数定理（Rank-Nullity Theorem）确定
右核空间的基是一组线性无关的向量，可以生成整个右核空间

要知道满足条件 $M \cdot \mathbf{v} = \mathbf{0}$ 的列向量有多少个，我们需要确定右核（null space）向量空间的维数，即右核的维度（nullity）

秩-零化维数定理

线性代数中的 Rank-Nullity Theorem 提供了直接的答案。对于一个 $m \times n$ 的矩阵 $M$，有以下关系 \[ \text{rank}(M) + \text{nullity}(M) = n \] 其中

$\text{rank}(M)$：矩阵 $M$ 的秩，表示 $M$ 的行向量空间的维数（或列向量空间的维数）
$\text{nullity}(M)$：矩阵右核的维数（null space 的维数）
$n$：矩阵列的总数

结论

右核的维数（nullity）决定了满足 $M \cdot \mathbf{v} = \mathbf{0}$ 的独立列向量的数量
若 nullity 是 $k$，则右核空间有 $k$ 个线性无关的基向量，满足条件的列向量数量是无穷多的，因为这些基向量可以任意线性组合

右核矩阵

右核矩阵指的是矩阵的右零空间的一种表示方式，右零空间是指所有使得矩阵与其右边乘积结果为零向量的向量的集合。右核空间的基可以使用sagemath中的right_kernel().basis()函数求出

例题

2023巅峰极客 Crypto Rosita

巅峰极客2023 Crypto Rosita

回到本题

按照大佬博客中的思路分析这道题，我们现在有 \[ a_ip+b_iq=h_i \] 即 \[ \begin{pmatrix} a_i & b_i \end{pmatrix} \begin{pmatrix} p\\\\ q \end{pmatrix} = \mathbf{h_i} \] 将100个等式拼接起来 \[ AB_{100\times2} \begin{pmatrix} p\\\\ q \end{pmatrix} = H_{100\times1} \] 目标是求短列向量 $A$ 与 $B$，考虑 $AB$ 矩阵的正交矩阵，不妨令为 $M$，有 \[ M_{k\times100} \cdot AB_{100\times2}=\mathbf{0}_{k\times2} \] 那么 \[ M_{k\times100} \cdot AB_{100\times2} \cdot \begin{pmatrix} p\\\\ q \end{pmatrix} = \mathbf{0}_{k\times1} \] 也就是 \[ M_{k\times100} \cdot H_{100\times1}=\mathbf{0}_{k\times1} \] 因为我们已知的是 $H$，所以要往 $H$ 上推导

得到这个关系之后，我们可以知道

$M$ 与 $H$ 正交
$AB$ 的两列均在 $M$ 的右核空间中
$AB$ 的两列均是 $M$ 的右核空间中的一个短向量

于是我们要做的就是

求 $H$ 的正交矩阵 $M$
对 $M$ 的右核空间做格基规约得到最短列

找到 $M$ 所构造的格是固定的，为 \[ \begin{pmatrix} E_{100\times100} & H_{100\times1}\\\\ 0 & p \end{pmatrix} \] 其中， $E$ 是单位矩阵，$H$ 是已知条件的列向量，$p$ 是曲线的阶

构造原理如下 \[ \begin{pmatrix} M_{k\times100} & t \end{pmatrix} \begin{pmatrix} E_{100\times100} & H_{100\times1}\\\\ 0 & p \end{pmatrix} = \begin{pmatrix} M_{k\times100} & 0 \end{pmatrix} \] 对构造出来的格做格基规约，就能得到 \[ \begin{pmatrix} M_{k\times100} & \mathbf{0}\\\\ \mathbf{0} & p \end{pmatrix} \] 为什么构造的格要多一行 $(\mathbf{0},p)$ ?

这里规约出的矩阵，只要行向量的最后一个元素为 $0$，就可以作为一行加入到 $M$ 中，所以我们可以对格的最后一列配上一个大系数，从而保证规约出 $0$

是的，也就是说规出来的矩阵，理想情况下最后一列都会被规约成 $0$，代表了被正交化，但不一定全部会被规约成 $0$，所以需要筛选一下

但是，这里其实可以直接取规出来的前 $98$ 行，因为规出来矩阵的秩一定为 $98$，根据上面的秩-零化维数定理可以知道；同时，一定是前 $98$ 行为正交成功的，这个暂时不知道为什么

M = []
for i in L:
    if(i[-1] == 0):
        M.append(i[:-1])
M = Matrix(ZZ,M)

接下来对 $M$ 的右核空间中再做格基规约即可

1
2
3

Ker = M.right_kernel().basis()
Ker = Matrix(ZZ, Ker)
AB = Ker.LLL()

需要注意的是，规出来的结果是什么？

实际上找到的是 $B$ 和与 $B$ 约减过的 $A$，所以直接用 $B$ 可以，但是 $A$ 是需要计算的

1 2	B = list(map(abs, AB[1])) A = [i+j for i,j in zip(AB[0], B)]

接下来就和之前一样了，求 $GCD$ 即可

正交格的另一份exp

来自2024 强网杯部分题解

clist = [...]
n, e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

from Crypto.Util.number import *

def gao_ortho(c, N):
    n = 100
    C = matrix(ZZ, n, 1, c)
    C = block_matrix([[identity_matrix(n), C]])
    C = C.LLL()
    C1 = C[:-2, :-1]
    C1 = C1.T.left_kernel().matrix()
    C1 = C1.LLL()
    a0 = C1[0]
    a1 = C1[1]
    c_ = vector(ZZ, c)
    res = C1.solve_left(c_)
    for p in res:
        if N % p == 0:
            return p, N // p
    else:
        raise Exception("GG")

p, q = gao_ortho(clist, n)
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(int(m)))

有空再研究吧

P.S.

这道题其实 $4$ 组值就能解

exp2_apbq.sage里改成

1 2	h = hint2[:4] nums = 2

或exp22_apbq.sage里改成

1 2	V = hints[:4] k = 2^800

但是exp222_apbq.sage里至少需要 $5$ 组

1	hint2 = hint2[:5]

第三段

题解

第三段是最nt的...

用的是第二段的公私钥

正解

但是这个题也是可以解的

给的条件是 \[ c_1=ap+q\\ c_2=p+bq \] 可以构造模 $n$ 等式 \[ (c_1-q)(c_2-p)=0 \bmod n \] 展开有 \[ c_1c_2-c_1p-c_2q=0 \bmod n \] 即 \[ c_1p+c_2q-c_1c_2+kn=0 \] 构造格如下 \[ \begin{pmatrix} p & q & 1 & k \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & c_1\\\\ 0 & 1 & 0 & c_2\\\\ 0 & 0 & 1 & -c_1c_2\\\\ 0 & 0 & 0 & n \end{pmatrix} = \begin{pmatrix} p & q & 1 & 0 \end{pmatrix} \] 但这个格是做不出来的，正确的格构造如下

\[ \begin{pmatrix} p_h & q_h & 1 & k \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 2^{brute}\cdot c_1\\\\ 0 & 1 & 0 & 2^{brute}\cdot c_2\\\\ 0 & 0 & 2^{512-brute} & c_1i+c_2j-c_1c_2\\\\ 0 & 0 & 0 & n \end{pmatrix} = \begin{pmatrix} p_h & q_h & 2^{512-brute} & 0 \end{pmatrix} \]

为什么要用 $p_h\ q_h$ 而不是 $p\ q$ ?

$p$ 和 $q$ 均约为512位，比较接近LLL可以规约出来的范围，但稍微长了一点，需要缩短一点

\[ c_1c_2-c_1(2^{brute}p_h+i)-c_2(2^{brute}q_h+j)=0 \bmod n \]

\[ 2^{brute}c_1p_h+2^{brute}c_2q_h+c_1i+c_2j-c_1c_2+kn=0 \]

为什么要用 $2^{512-brute}$ 而不是 $1$ ？

因为规约出来的向量会趋于等长正交，所以如果用一开始的向量 \[ \begin{pmatrix} p & q & 1 & 0 \end{pmatrix} \] p和q的位数会被“拖累”，变成大概 $512*2/3=341$ 位

所以配一个位数一样的做平衡，经过测试，指数取 $508-511$ 都能规出来

WP-[2024.11强网初赛]apbq