格の初探

发表于 更新于 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 8 分钟

因为要给招新赛出题，另一方面格的学习也确实该提上日程了ww咕咕了好久(待填坑)

前面的原理那些我就不多赘述了。和其他师傅写的都大同小异。有很多师傅写的很详细易懂。珠玉在前我就不献丑了

我们直接从hermite定理开始

Hermite’s Theorem

image-20240521130132678

以一个简单的ntru为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from secret import flag
from Crypto.Util.number import *

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

print('h =', h)
print('p =', p)
"""
h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281
"""

目标是求得f。

f′=f+20192020202120222023

h=invert(f′,p)∗g%p

h=f′^(-1)^∗g+kp

g=hf′−kp

根据此构造格为
$$
\left(\begin {array}{c}
f’ &-k \
\end{array}\right)
\left(\begin {array}{c}
1 &h \
0 &p \
\end{array}\right)

\left(\begin {array}{c}
f’ &g \
\end{array}\right)
$$
其中n表示维度，也就是基向量的个数，在本题中n = 2

det(L) = 行列式的值 = 1 * p = p.向量v = （f’， g）.我们在这里可以存一个测试的板子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
b = 2**128
print(b)
import gmpy2
from Crypto.Util.number import *

flag = b''
f = bytes_to_long(flag)
print(f.bit_length())  # 255
p = getPrime(512)
g = getPrime(128)
g = g
#固定
temp = gmpy2.iroot(2 * p, 2)[0]
print(temp.bit_length()) # 257

f = f + 20192020202120222023  #对于bit没有 影响 因为f接近255
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  #255  乘b = 256

最近做题倒是遇到一个hermite定理符合但是仍然无法格基规约的题，一番搜索之后发现了高斯启发式(Gaussian Heuristic)

是一个比hermite更严格的对最短向量长度的定义。

OQgqwl.png

我们仍然可以根据这个定义写出一个测试demo

1
2
3
4
def guass_Heuristic(L):
    n = L.nrows()
    efficient = (n/(2*math.pi*math.e))**(0.5)
    return int(efficient*iroot(abs(L.det()),n)[0])

大部分情况其实hermite已经够了(我目前遇见的题)，但对于一些卡界比较严格的格，就需要使用高斯启发式对其进行一个更详细的分析。

格相关的题型

NTRU密码

例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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     
"""

类似上面的ntru构造格的方法。但是直接这么构造是解不出来的，会发现它并不满足hermite定理。我们将数据代入可以得到

OQgTHB.png

这就涉及到格的配平，这一般是通过同时乘一个大数实现的。我们令b=2**256.会发现成立。此时这里的b一般是根据位数进行尝试得到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947 

b = 2^256
print(b)
Ge = Matrix(ZZ,[[1,b*h],
                [0,b*p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

print(libnum.n2s(int(f)))

这是一道二维的格接下来我们来看一道三维的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *

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

assert m.bit_length() == 351
p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)

a = (b*m + c) % p

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

'''
a = ...
b = ...
p = ...
'''

很明显这里的格我们要构造成
$$
\left(\begin {array}{c}
1 &m &k \
\end{array}\right)
\left(\begin {array}{c}
1 &0 &a \
0 &1 &-b \
0 &0 &p \
\end{array}\right)

\left(\begin {array}{c}
1 &m &c\
\end{array}\right)
$$
我们会发现这个还是不平衡的，仍然要配平。这里有两个方法，将最左上角的1换为2^190^和最后一列乘上2^190^都能解，最终目的就是使其满足hermite定理。

仍然是先进行hermite定理的验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import gmpy2
from Crypto.Util.number import *

b = 2 ** 0   #这是不断调整配平用的
f = flag = getPrime(351)   

p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)

#行列式维数
n = 3
det = p * 2**190

#行列式的值 大于等于下面的即可
temp = gmpy2.iroot(n, 2)[0] * gmpy2.iroot(det, n)[0]  
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(c)**2, 2)[0]  
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():
    print("true")
else:
    print("false")

结果为

OQgU8s.png

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
a = ...
b = ...
p = ...

Ge = Matrix(ZZ, [[2^190, 0, a],
                 [0, 1, -b],
                 [0, 0, p]])

t, m, c = Ge.LLL()[0]
print(m)
m = abs(m)
print(long_to_bytes(int(m)))