格密码

admin 2021年10月11日22:32:41格密码已关闭评论382 views1字数 6262阅读20分52秒阅读模式

格密码

线性独立空间上有集合

v1,,vnRn

,格(Lattices)就是这些向量的线性组合,用公式表示为:

L=a1v1+a2v2++anvna1,a2,,anZ

L

的维数等于格中向量的个数。

假定

v1,v2,,vn

是格

L

的基,

w1,w2,,wnL

,则必然存在整系数

aij

使得:

{w1=a11v1+a12v2++a1nvn w2=a21v1+a22v2++a2nvn  wn=an1v1+an2v2++annvn

这样,格的问题就是矩阵运算了。

最短向量问题SVP,The Shortest Vector Problem):

寻找一个格

L

中最短的非零向量。即,寻找一个

vL

满足其欧几里德范数

v

最小。

最接近向量问题CVP,The Closest Vector Problem):

对于一个非格

L

中的向量

w

,在格中寻找一个向量

v

,使得

wv

最小。

CVP和SVP都是NP完备问题,因此求解起来十分困难,因此这两个问题都是可以作为密钥体制的基础的。

构造示例

bmknc=r[m1k][10b 02400c 00n]=[m2400r]

NRTU格密码

NTRU是一个带有专利保护的开源公开密钥加密系统,使用基于格的加密算法来加密数据。它包括两部分算法:NTRUEncrypt用来加密,NTRUSign用来进行数字签名。与其他流行的公钥加密系统不同,它可以防止被Shor算法破解,并显著提升了性能。

在同等加密强度下,NTRU执行大开销的私钥操作比RSA算法快得多。RSA算法的私钥操作耗时与密钥长度呈三次方关系,而NTRU相应操作为二次方关系。

NTRU密码体制,需要三个整数参数

(N,p,q)

和四个次数为

N1

的整系数多项式集合

Lf,Lg,Lφ,Lm

,在这里

N

为一素数,

p,q

可以不必为素数,但为安全,要求

gcd(p,q)=1

,且

q

远大于

p

NTRU工作于多项式整数环

R=Z[x]/(xN1)

,当

FR

,可以把

F

表示为多项式或向量形式,

F=i=0N1Fixi=[F0,F1,,FN1]

在这里记

L(d1,d2)=FR:F$$d1$$1$$d2$$1$$0

,选取三个确定的整数

df,dg,dφ

,多项式集合

Lf=L(df,df1),Lg=L(dg,dg),Lφ=L(dφ,dφ)

,而

Lm=mR:m$$[p12,p12]$$p$$

  • 密钥生成

    B随机选择两个多项式

    f

    g

    fLf,gLg

    ,要求

    f

    关于模

    p

    和模

    q

    的逆

    Fp,Fq

    都存在,也即

    Fqf1(modq)

    Fpf1(modp)

    ,这里可以用扩展欧几里得算法计算出

    Fp

    Fq

    。为此,

    f

    首先应满足

    gcd(f(1),pq)=1

    ,如果有一个逆不存在,需重新选择

    f

    然后,B计算

    hFqg(modq)

    ,则公钥为

    h

    ,私钥为

    f

    ,但在实际中,还将存储

    Fp

    ,因而一般认为私钥为

    (f,Fp)

  • 加密

    假设A想发送信息

    mLm

    给B,他将根据参数

    dφ

    随机选择一个

    φLφ

    ,然后,他利用B的公钥

    h

    计算

    eφh+m(modq)

    A把密文

    e

    发送给B。

  • 解密

    当B收到密文

    e

    后,他首先利用私钥

    f

    计算

    afe(modq)

    选择

    a

    的系数位于

    [p12,p12]

    之间,然后计算

    ba(modp)

    cFpb(modp)

    则多项式

    c

    就是明文

    m

  • 构造矩阵

    B^{NT}= left(begin {array}{c} I & H  0 & q end{array} right) =left(begin {array}{cccc|cccc} lambda & 0 & cdots & 0 & h_0 & h_1 & cdots & h_{N-1}  0 & lambda & cdots & 0 & h_{N-1} & h_0 & cdots & h_{N-2} vdots & vdots & ddots & vdots & vdots & vdots & ddots & vdots  0 & 0 & cdots & lambda & h_1 & h_2 & cdots & h_0  hline 0 & 0 & cdots & 0 & q & 0 & cdots & 0  0 & 0 & cdots & 0 & 0 & q & cdots & 0  vdots & vdots & ddots & vdots & vdots & vdots & ddots & vdots  0 & 0 & cdots & 0 & 0 & 0 & cdots & q end{array} right)

    其中

    H

    是根据公钥多项式的系数生成的循环矩阵。

    构建一个这样的矩阵,然后进行LLL算法得到解密密钥。

  • 参考

    从一道CTF题初探NTRU格密码

    Practical lattice-based cryptography: NTRUEncrypt and NTRUSign

1
2
3
4
5
6
7
8
9
10
11
12
13
14

h =
p =
c =

v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
f, g = m.LLL()[0]
print(f, g)

a = f*c % p % g
m = a * inverse_mod(f, g) % g
print(bytes.fromhex(hex(m)[2:]))
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


N =
p =
q =
Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]

ex =
hx =

print('-------decrypt------')
qq = x^N-1
pp = y^N-1
hn = [int(x) for x in hx.coefficients()]
n = len(hn)
A1 = matrix.identity(n)
A0 = matrix.zero(n)
Aq = matrix.identity(n) * q
Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
M = block_matrix([A1,Ah,A0,Aq],nrows=2)
L = M.LLL()
v = L[0]
f = list(v)[:n]
g = list(v)[n:]
fx = Q(f)
fy = P(f)
gx = Q(g)
Fqx = fx.inverse_mod(qq)
Fpy = fy.inverse_mod(pp)




ax = (fx*ex).mod(qq)
an = [int(x) for x in ax.coefficients()]

for i in range(len(an)):
if an[i] > q//2:
an[i] -= q
ax = P(an)
print(ax)
out = (Fpy * ax).mod(pp)
print(out)

print(bytes(out.coefficients()))

GGH加密

1997年,Goldreich、Goldwasser、Halevi三人受Ajtai在格难题上的研究所启发,提出了一个基于格中最近向量难题的非对称密码学算法:GGH Cryptosystem。

1999年,Nguyen发现在这个密码学算法设计中,有一个很大的缺陷,可以使攻击者从密文中获取到明文的部分信息,且可以将原来的最近向量难题转化为一个较为简单的最近向量难题。基于这个观察,Nguyen解出了设计者放在网上的5个challenge中的4个(其中有2个被设计者认为是不可能攻破的),足以证明该密码算法是broken的。

  • 定义

    GGH包含一个私钥和一个公钥,选取格

    L

    的一组好基

    B

    和一个幺模矩阵

    U

    作为私钥,计算

    L

    的另一组基

    B=UB

    作为公钥。

    选定

    M

    值,明文向量

    (m1,m2,,mn),mi(M,M)

    • 加密
      1. 给定明文

        m=(m1,m2,,mn)

        ,误差向量

        e

        ,和公钥

        B

        ,计算

        v=mB=mibi

      2. 密文

        c=v+e=mB+e

    • 解密
      1. 计算

        cB1=(mB+e)B1=mUBB1+eB1=mU+eB1

      2. 如果

        eB1

        足够小,可利用Babai最近平面算法的变种Babai rounding technique去除;

      3. 最后计算

        m=mUU1

        得到明文。

    GGH中的误差向量的选取是3或者-3。

  • 求解

    利用Nguyen’s Attack算法。

    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


    c = []
    c = vector(ZZ, c)

    B = []
    B = matrix(ZZ, B)


    n = 150
    delta = 3
    s = vector(ZZ, [delta]*n)
    B6 = B.change_ring(Zmod(2*delta))
    left = (c + s).change_ring(Zmod(2*delta))
    m6 = (B6.solve_left(left)).change_ring(ZZ)
    new_c = (c - m6*B) * 2 / (2*delta)


    new_B = (B*2).stack(new_c).augment(vector(ZZ, [0]*n + [1]))
    new_B = new_B.change_ring(ZZ)

    new_B_BKZ = new_B.BKZ()
    shortest_vector = new_B_BKZ[0]
    mbar = (B*2).solve_left(new_c - shortest_vector[:-1])
    m = mbar * (2*delta) + m6

    print(bytes.fromhex(hex(m)[2:]))
  • 参考

    GGH encryption scheme

    GYCTF 2020 - GGH

LWE问题

容错学习问题 (LWE问题, Learning With Errors)是一个机器学习领域中的怀疑难解问题,由Oded Regev 在2005年提出,他因此赢得2018年哥德尔奖。这是一个极性学习问题的一般形式。

  • 定义

    随机选取一个矩阵

    AZqm×n

    ,一个随机向量

    sZqn

    ,和一个随机的噪音

    eεm

    一个LWE系统的输出

    gA(s,e)=As+e(modq)

    一个LWE问题是,给定一个矩阵

    A

    ,和LWE系统的输出

    gA(s,e)

    ,还原

    s

    LWE的误差向量是一个满足正态分布的小向量。

    因为加入了一些误差,如果使用高斯消元法的话,这些误差会聚集起来,使得解出来的东西跟实际值差很多。

  • 求解

    利用LLL算法和Babai最近平面算法,可以在多项式时间内找到近似解。

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44


    from sage.modules.free_module_integer import IntegerLattice

    row =
    column =
    prime =

    ma =
    res =

    W = matrix(ZZ, ma)
    cc = vector(ZZ, res)


    def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
    for i in reversed(range(M.nrows())):
    c = ((small * G[i]) / (G[i] * G[i])).round()
    small -= M[i] * c
    return target - small

    A1 = matrix.identity(column)
    Ap = matrix.identity(row) * prime
    B = block_matrix([[Ap], [W]])
    lattice = IntegerLattice(B, lll_reduce=True)
    print("LLL done")
    gram = lattice.reduced_basis.gram_schmidt()[0]
    target = vector(ZZ, res)
    re = Babai_closest_vector(lattice.reduced_basis, gram, target)
    print("Closest Vector: {}".format(re))

    R = IntegerModRing(prime)
    M = Matrix(R, ma)
    M = M.transpose()

    ingredients = M.solve_right(re)
    print("Ingredients: {}".format(ingredients))

    m = ''
    for i in range(len(ingredients)):
    m += chr(ingredients[i])
    print(m)
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49


    from sage.modules.free_module_integer import IntegerLattice
    from random import randint
    import sys
    from itertools import starmap
    from operator import mul



    def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(1):
    for i in reversed(range(M.nrows())):
    c = ((small * G[i]) / (G[i] * G[i])).round()
    small -= M[i] * c
    return target - small

    m =
    n =
    q =

    A_values =
    b_values =

    A = matrix(ZZ, m + n, m)
    for i in range(m):
    A[i, i] = q
    for x in range(m):
    for y in range(n):
    A[m + y, x] = A_values[x][y]
    lattice = IntegerLattice(A, lll_reduce=True)
    print("LLL done")
    gram = lattice.reduced_basis.gram_schmidt()[0]
    target = vector(ZZ, b_values)
    res = Babai_closest_vector(lattice.reduced_basis, gram, target)
    print("Closest Vector: {}".format(res))

    R = IntegerModRing(q)
    M = Matrix(R, A_values)
    ingredients = M.solve_right(res)

    print("Ingredients: {}".format(ingredients))

    for row, b in zip(A_values, b_values):
    effect = sum(starmap(mul, zip(map(int, ingredients), row))) % q
    assert(abs(b - effect) < 2 ** 37)

    print("ok")
  • 参考

    初探全同态加密之二:格密码学与LWE问题

    祥云杯 2020 - easy matrix

    Aero CTF 2020 - Magic II

    XNUCA2020 - diamond

相关推荐: OWASP Top 10 2021 全新出炉

OWASP Top 10 2021 是全新的,具有新的图形设计和一页有用的信息图。2021 年前 10 名发生了什么变化有三个新类别,四个类别的命名和范围发生了变化,并且 2021 年的前 10 名中进行了一些合并。A01:2021-Broken Access…

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2021年10月11日22:32:41
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   格密码https://cn-sec.com/archives/578045.html