格基础

记录格的学习。

格中运算(线性代数相关)

​ 有基向量v_1,v_2,v_3构成三维向量空间，这个向量空间中任一向量都可由这三个基向量的线性组合表示，

在格中，要求其中每个向量都能由其基向量的整系数线性组合表示，也就是说，用来表示格中任一向量的每个基向量前的系数必须为整数。

最基础的

$$\begin{aligned} &v_1=(2,1,3),v_2=(1,2,0),v_3=(2,-3,-5)\\ &设A=(v_1,v_2,v_3)^T\\ &格中任一向量都能由此向量组的整系数组合表示\\ &有L中其他三维向量组：\\ &w_1=v_1+v_3,w_2=v_1-v_2+2v_2,w_3=v_1+2v_2\\ &也就是w_1=A*(1,0,1),w_2=A*(1,-1,2),w_3=A*(1,2,0)\\ &设W=(w_1,w_2,w_3)^T\\ &有A* \begin{pmatrix} 1&0&1\\ 1&-1&2\\ 1&2&0\\ \end{pmatrix} =W，设A *U=W,有A=W *A^{-1}\\ &设A *U=W,有A=W *A^{-1} \end{aligned}$$

SVP最短向量问题

在格L中存在无数多个不同的向量，而最短向量问题就是指找出这个格L中最短的非零向量，即寻找这个格中欧几里得范数(该集合的每一个元素的平方和再开方)最小,范数就是指长度。

1. 那我们该如何找到这个最短向量呢？

先从简单的栗子出发

由向量v_1=（0,1）和v_2=（1,0）张成的格，由于其他向量都是这两个向量的整系数线性组合，即a=2v_1+1 v_2,b=2 v_1+0v_2，无论是（2,1）还是（2,0），只要系数是整数，必然系数>=1,（我们可以放到向量空间里去理解，任一向量都能看成是在v_1方向上延伸k倍在加上在v_2方向上延伸m倍，而m,k恒大于等于1）所以对于v_1和v_2来说，没有比他们前面的系数1更小的了，他俩就是最短向量。

扩展开来，由于格中基向量可以是任意的，那么有可能此基向量非正交（正交在空间中理解就是向量互相垂直）

首先我们要明白两个关系：

1. 假设v不是基中的向量，此刻该向量一定可以通过在其他基向量方向的投影来得到一个更短的向量。（非正交的向量比正交向量长）
2. 假设v是这个基中的某个向量，在其他向量上的投影长度为0（正交向量是短向量）

所以求任意格中最短向量问题的通用解法就出来了

若v不是基中向量，通过LLL算法 得到正交基或者是最接近正交基，最短向量就在这组正交基上。

若是，那最短向量就在这组基上。

2. 现在思考我们为什么要找到这个最短向量？

对于像

$$\begin{aligned} \begin{pmatrix} f'&-k \end{pmatrix} \begin{pmatrix} 1&h\\ 0&p\\ \end{pmatrix} = \begin{pmatrix} f'&g \end{pmatrix} \end{aligned}$$

的式子，

考虑它的几何意义:（以下左边右边指等号左边两向量的相对位置）

左边乘以右边相当于将左边的向量放在了右边向量组构成的向量空间里，而左边的向量也变成了这个向量空间中的向量。

如果右边是个足够大的向量空间，而等式右边的向量是个足够小的向量，那这就是SVP问题了。

做法：若（1,0)和（h,p）不正交，则需使用LLL算法将其正交化并找到其中最短向量，就是（f,g)，

实战题目一：

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

assert len(flag) == 47

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p

print('h =', h)
print('p =', p)

"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
"""

要求f,看出f相对于512bits的p和h是微不足道的，就转化成SVP问题找到最短向量，就得到f。

但是

最短向量是有上界的，根据

Hermite’s Theorem：

每一个n维(即基向量的个数)的格L，都包含一个非零向量v属于L满足

$$\begin{aligned} ||v||<=\sqrt n \det(L)^{1/n} \end{aligned}$$

测试是否满足Hermite

import gmpy2
from Crypto.Util.number import *

b = 2 ** 0#有时候需要调整b的值
flag = b'flag{Do_you_like_Laooooooo00000ooottice?Addoil}'
print(len(flag))
f = bytes_to_long(flag)
print(f.bit_length())  
p = getPrime(512)
g = getPrime(128)
g = g

#det(L)
temp = gmpy2.iroot(2 * b * p, 2)[0]  
print(temp.bit_length()) 

#向量v的长度
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0] 

print(temp2.bit_length())  

当b=1时，有357>257,超过上界，此时我们对b的值进行调整，

b=2^256时满足Hermite定理，进行求解。

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757
print(h.nbits(),p.nbits())
D = 2^256  #配平数与位数相关 需要学习补充 237-256次方均可解

v1 = vector(ZZ, [1, D * h])
v2 = vector(ZZ, [0, D * p])
m = matrix([v1,v2]);

import libnum

# Solve SVP.
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)
#BKZ
L = m.BKZ(block_size=2)
shortest_vector = L[0]
f, g = shortest_vector
print(f, g)
print(libnum.n2s(int(abs(f))))
import gmpy2
#验证
print(QQ((f**2+g**2)**0.5))
print(QQ((p/2)**0.5))

实战题目二：背包密码

私钥a：是一个超递增序列（每一个数要比前面所有数之和还要大）。

模数m: 比超递增序列中所有数之和还要大

乘数w：满足gcd(w,m)=1

公钥b：满足b=w*a%m

加密：

$$\begin{aligned} c \equiv \sum_{k=1}^{N} b_i *v_i \pmod m \end{aligned}$$

v_i代表flag的二进制表示的每一位，故而v_i属于{0,1}

看题

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

flag = bytes_to_long(b'******')
flag = bin(flag)[2:]
n = len(flag)

a = [random.randint(1, 4**n)]
s = a[0]
for i in range(1, n):
    a.append(random.randint(s+1, 4**(n+i)))
    s += a[i]

m = random.randint(a[-1] + 1, 2*a[-1])
w = random.randint(1, m)

assert gcd(w, m) == 1
b = [w*i % m for i in a]

c = 0
for i in range(len(b)):
    c = (c + b[i]*int(flag[i]))
with open('output', 'w+') as f:
    print(f'b = {b}', file=f)
    print(f'c = {c}', file=f)

解密时，根据上式，可以构造格L，使得

$$\begin{aligned} \begin{pmatrix} v_1&v_2&v_3&...&v_n&-1 \end{pmatrix} \begin{pmatrix} 1 & 0 &0&0&0&...&b_1 \\ 0 & 1&0&0&0&...&b_2\\ 0&0&1&0&0&...&b_3\\ .&.&.&.&.&...&.\\ 0&0&0&0&1&...&b_n\\ 0&0&0&0&0&...&c \end{pmatrix} = \begin{pmatrix} v_1&v_2&v_3&v_4&...&v_n&0 \end{pmatrix} \end{aligned}$$

现在来确定上界，根据Hermite定理：

$$&\begin{aligned} 向量\begin{pmatrix} v_1&v_2&v_3&v_4&...&v_n&0 \end{pmatrix}的长度\\ ||v||=\sqrt{\sum_{k=1}^{n}v_n}<\sqrt{n} \end{aligned}$$

v_i要么是1，要么是0，取都是1的时候长度最大，最大的时候都符合Hermite

(n是flag长度，大概在287左右，可以认为这个数比较大，1/n约等于0，忽略det(L)^{1/n}进行计算)

第一步：用LLL算法规约出最短正交向量，得flag的二进制表示

L = Matrix(ZZ, n+1, n+1)

for i in range(n):
    L[i,i] = 1
    L[i,-1] = b[i]
L[-1,-1] = -c

res = L.LLL()

第二步：建一个列表存放flag的每个二进制位

for i in range(n + 1):
    flag = res.row(i).list()
    X = True
    for m in flag:
        if m != 0 and m != 1:
            X = False
            break
    if X:
        print(i, flag)

第三步：取出列表中的每个数组成flag的二进制表示

flag = int(''.join(list(map(str, flag))), 2)
print(long_to_bytes(flag))

实战题目三：

from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

c = pow(m, 65537, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')

'''
c,a,b的值
'''

已知

r长度在14-15bits，(p−r)∗a+q(modb)<50

令x≡(p−r)∗a+q(modb)，有(p-r)*a+kb=x-q

已知a,b，取上述多项式系数构造格

$$\begin{aligned} \begin{pmatrix} p-r&k \end{pmatrix} \begin{pmatrix} 1&a\\ 0&b \end{pmatrix} = \begin{pmatrix} p-r&x-q \end{pmatrix} \end{aligned}$$

a = getPrime(1024),b = getPrime(1536)

p = getPrime(512),q = getPrime(512)

手算一下,b^1/2就有768bits了，显然成立（如下）

$$\begin{aligned} \sqrt {p^2+q^2}<\sqrt 2*b^{1/2} \end{aligned}$$

用LLL规约出p-r,x-q。而r,x长度很小，可爆破。

import gmpy2
import libnum
from sympy import Matrix

c=...
a=...
b=...

Ge=Matrix[[1,a],
          [0,b]]
hh=Ge.LLL()

p=hh([0],[0])
q=hh([0],[1])

for i in range(2**14, 2**15):
    for j in range(50):
        pp=p+i
        qq=j-q
        n=pp*qq
        phi_n=(pp-1)*(qq-1)
        if gmpy2.gcd(phi_n,65537)!=1:
            continue
        d=gmpy2.invert(65537,phi_n)
        m=gmpy2.powmod(c,d,n)
        flag=libnum.n2s(int(m))
        if b'NSSCTF' in flag:
            print(m)
            break

NSS密码工坊

https://blog.csdn.net/jayq1/article/details/140872034