格密码笔记六

一、GGH加密1

1997年，Goldreich、Goldwasser、Halevi三人提出了一个基于格中最近向量难题的非对称密码学算法：GGH Cryptosystem。

1999年，Nguyen发现在这个密码学算法设计中，有一个很大的缺陷，可以使攻击者从密文中获取到明文的部分信息，且可以将原来的最近向量难题转化为一个较为简单的最近向量难题。

1:格基规约相关 - Coinc1dens’ Lotus Land

（一）定义

GGH包含一个私钥和一个公钥，选取格 L 的一组好基 B 和一个幺模矩阵 U 作为私钥，计算 L 的另一组基 B′=UB作为公钥。

选定 M值，明文向量$ (m_1,m_2,⋯,m_n),m_i∈(−M,M)$。

  • 加密
    1. 给定明文$m=(m_1,m_2,⋯,m_n)$，误差向量 e，和公钥 B′，计算 $v=m⋅B^′=∑m_ib′_i$；
    2. 密文 $c=v+e=m⋅B′+e$。
  • 解密
    1. 计算 $c⋅B^{−1}=(m⋅B′+e)B^{−1}=m⋅U⋅B⋅B^{−1}+e⋅B−1=m⋅U+e⋅B^{−1}；
    2. 如果 $e⋅B^{−1} $足够小，可利用Babai最近平面算法2的变种Babai rounding technique去除；
    3. 最后计算$ m=m⋅U⋅U^{−1}$得到明文。

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

2:(1条消息) 格密码最近平面算法：如何解决最近向量CVP问题（1）_唠嗑！的博客-CSDN博客

（二）解决方法

利用Nguyen’s Attack算法3。

3:Intended Solution to GGH in GYCTF 2020 | Soreat_u’s Blog (soreatu.com)

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
# Sage 
# Read ciphertext and public key.
c = []
c = vector(ZZ, c)

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

# Nguyen's Attack.
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)

# embedded technique
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:]))
1
2
3
4
5
6
7
8
9
10
11
12
13
# Sage
# e=mW+r
from sage.modules.free_module_integer import IntegerLattice

W = 
e = 

B = W.stack(e).augment(vector([0] * W.ncols() + [1]))
r = IntegerLattice(B).shortest_vector()
print('r = {}'.format(r))

m = W.solve_left(e - r[:-1])
print('m = {}'.format(m))

:GGH encryption scheme - Wikipedia

:Intended Solution to GGH in GYCTF 2020 | Soreat_u’s Blog (soreatu.com)

二、LWE问题

容错学习问题 5（LWE问题， Learning With Errors）是一个机器学习领域中的怀疑难解问题，由Oded Regev 在2005年提出，这是一个极性学习问题的一般形式。4

4:(1条消息) 强化学习目前存在的一些问题Chou_pijiang的博客-CSDN博客强化学习缺点

（一）定义

随机选取一个矩阵 $A∈Z^{m×n}_q$，一个随机向量$s∈Z^n_q$，和一个随机的噪音 $e∈ε^m$。

一个LWE系统的输出 $g_A(s,e)=As+e(mod\ q)$。

一个LWE问题是，给定一个矩阵 A，和LWE系统的输出 $g_A(s,e)$，还原 s。

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

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

（二）解决方法

构造矩阵：

L=

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

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
#脚本1-小规模
#Sage
from sage.modules.free_module_integer import IntegerLattice

row = 
column = 
prime = 

ma = 
res = 

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

# Babai's Nearest Plane algorithm
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
#脚本2-大规模
#Sage
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
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")

利用Embedding Technique构造一个Embedding Lattice，也可以解SVP。

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
# Sage
DEBUG = False
m = 44
n = 55
p = 2^5
q = 2^10

def errorV():
  return vector(ZZ, [1 - randrange(3) for _ in range(n)])

def vecM():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(m)])

def vecN():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(n)])

def matrixMn():
  mt = matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(m)])
  return mt

A = matrixMn()
e = errorV()
x = vecM()
b = x*A+e

if DEBUG:
  print('A = \n%s' % A)
  print('x = %s' % x)
  print('b = %s' % b)
  print('e = %s' % e)#

z = matrix(ZZ, [0 for _ in range(m)]).transpose()
beta = matrix(ZZ, [1])
T = block_matrix([[A, z], [matrix(b), beta]])
if DEBUG:
  print('T = \n%s' % T)

print('-----')
L = T.LLL()
print(L[0])
print(L[0][:n] == e)

:祥云杯2020，easy_matrix，LWE problem (github.com)

:Aero CTF 2020 - Magic II (Crypto, 496pts) - HackMD

:Writeup for Crypto Problems in XNUCA2020 | Soreat_u’s Blog (soreatu.com)

:DASCTF｜2022DASCTF7月赋能赛官方Write Up | CTF导航 (ctfiot.com)

三、隐子集和问题（HSSP / Hidden Subset Sum Problem）

w=vG，其中 w,v为 GF(p)上的向量，G 为01矩阵$(g_{ij}∈{0,1}）$，已知 w，恢复矩阵 G。

求解算法 Nguyen-Stern Algorithm，使用 orthogonal lattice 实现。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
from Crypto.Util.number import *

n = 60
m = 330
p = ...
w = ...
MM = ...

e = 0x10001
MM = matrix(GF(2), MM)

def allpmones(v):
    return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)

# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b, x0):
    m = b.length()
    M = Matrix(ZZ, m, m)

    for i in range(1, m):
        M[i, i] = 1
    M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
    M[0, 0] = x0

    for i in range(1, m):
        M[i, 0] = mod(M[i, 0], x0)

    return M

def allones(v):
    if len([vj for vj in v if vj in [0, 1]]) == len(v):
        return v
    if len([vj for vj in v if vj in [0, -1]]) == len(v):
        return -v
    return None

def recoverBinary(M5):
    lv = [allones(vi) for vi in M5 if allones(vi)]
    n = M5.nrows()
    for v in lv:
        for i in range(n):
            nv = allones(M5[i] - v)
            if nv and nv not in lv:
                lv.append(nv)
            nv = allones(M5[i] + v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)

def kernelLLL(M):
    n = M.nrows()
    m = M.ncols()
    if m < 2 * n:
        return M.right_kernel().matrix()
    K = 2 ^ (m // 2) * M.height()

    MB = Matrix(ZZ, m + n, m)
    MB[:n] = K * M
    MB[n:] = identity_matrix(m)

    MB2 = MB.T.LLL().T

    assert MB2[:n, : m - n] == 0
    Ke = MB2[n:, : m - n].T

    return Ke

def attack(m, n, p, h):
    # This is the Nguyen-Stern attack, based on BKZ in the second step
    print("n =", n, "m =", m)

    iota = 0.035
    nx0 = int(2 * iota * n ^ 2 + n * log(n, 2))
    print("nx0 =", nx0)

    x0 = p
    b = vector(h)

    # only information we get
    M = orthoLattice(b, x0)

    t = cputime()
    M2 = M.LLL()
    print("LLL step1: %.1f" % cputime(t))

    # assert sum([vi == 0 and 1 or 0 for vi in M2 * X]) == m - n
    MOrtho = M2[: m - n]

    print("  log(Height, 2) = ", int(log(MOrtho.height(), 2)))

    t2 = cputime()
    ke = kernelLLL(MOrtho)

    print("  Kernel: %.1f" % cputime(t2))
    print("  Total step1: %.1f" % cputime(t))

    if n > 170:
        return

    beta = 2
    tbk = cputime()
    while beta < n:
        if beta == 2:
            M5 = ke.LLL()
        else:
            M5 = M5.BKZ(block_size=beta)

        # we break when we only get vectors with {-1,0,1} components
        if len([True for v in M5 if allpmones(v)]) == n:
            break

        if beta == 2:
            beta = 10
        else:
            beta += 10

    print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
    t2 = cputime()
    MB = recoverBinary(M5)
    print("  Recovery: %.1f" % cputime(t2))
    print("  Number of recovered vector = ", MB.nrows())
    print("  Number of recovered vector.T = ", MB.ncols())
    return MB

res = attack(m, n, p, w)

:EDU-CTF Final & AIS3 EOF Quals meow? Write-ups - HackMD

:write-up/2022/zer0pts/Karen at master · pcw109550/write-up (github.com)

四、隐线性组合问题（HLCP / Hidden Linear Combination Problem）

w=vG，其中w,v 为GF(p) 上的向量，G 为 0 至 B 之间整数值矩阵$（g_{ij}∈[0,B]∩Z）$，已知 w，恢复矩阵 G。

一个例子：2022强网杯 - Lattice

附件：task.sage

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
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Cipher import AES
from base64 import b64encode
from hashlib import *
from secret import flag
import signal

n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109

def gen(n, m, r, N):
    t1 = [ZZ.random_element(-2^15, 2^15) for _ in range(n*m)]
    t2 = [ZZ.random_element(N) for _ in range(r*n)]
    B = matrix(ZZ, n, m, t1)
    L = IntegerLattice(B)
    A = matrix(ZZ, r, n, t2)
    C = (A * B) % N
    return L, C

def pad(s):
    return s + (16 - len(s) % 16) * b"\x00"

signal.alarm(60)
token = input("team token:").strip().encode()
L, C = gen(n, m, r, N)
print(C)
key = sha256(str(L.reduced_basis[0]).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = b64encode(aes.encrypt(pad(flag))).decode()
print(ct)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from pwn import *
import requests
import json
import os
import gmpy2
from pwnlib.tubes.tube import *
from hashlib import *
from Crypto.Util.number import *
from tqdm import tqdm, trange
import random
import math
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from factordb.factordb import FactorDB
from sage.modules.free_module_integer import IntegerLattice
import itertools
from fastecdsa.curve import Curve
from random import getrandbits, shuffle, randint
def resultant(p1, p2, var):
    p1 = p1.change_ring(QQ)
    p2 = p2.change_ring(QQ)
    var = var.change_ring(QQ)
    r = p1.resultant(p2, var)
    return r.change_ring(F)
# r = remote('123.56.87.28', '19962')
# context(log_level='debug')
# ALPHABET = string.ascii_letters + string.digits
# rec = r.recvline().decode()
# print(rec)
# suffix = rec[rec.find('+'):rec.find(')')][1:].strip()
# digest = rec[rec.find('==')+3:-1].strip()
# print(f"suffix: {suffix} \ndigest: {digest}")# for i in itertools.product(ALPHABET, repeat=4):
# prefix = ''.join(i)
# guess = prefix + suffix
# if sha256(guess.encode()).hexdigest() == digest:
# # log.info(f"Find XXXX: {prefix}")
# print((f"Find XXXX: {prefix}"))
# break
# r.sendline(prefix.encode())
n = 75
m = 150
r = 10
N=126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109
with open('output.txt', 'r') as f:
    data = f.readlines()
    for i in range(len(data)):
        data[i] = data[i].replace('[', '').replace(']', '').split(' ')
        tmp = []
        for x in data[i]:
            if x != '':
            	tmp.append(int(x))

        data[i] = tmp
        print(len(tmp))
    C = matrix(ZZ, data)
A = matrix(ZZ,m+r,m+r)
for i in range(m):
	A[i,i] = 1
for i in range(r):
	for j in range(m):
		A[j,i+m] = C[i,j]<<200

	A[i+m,i+m] = N<<200

ans = A.LLL()
B = matrix(ZZ,n,m)
for i in range(n):
	assert list(ans[i][m:]) == [0]*r
	B[i] = ans[i][:m]
# print(B)
ans = B.right_kernel().basis()
D = matrix(ZZ,ans)
# print(D)
print('result=')
from base64 import b64decode
res = D.BKZ(block_size=12)[0]
key1 = sha256(str(res).encode()).digest()
key2 = sha256(str(-res).encode()).digest()
c = 'rX4K8nZnib5PN13ct6AMwTos99Vdnu7gxsdLMZekKu7gEKx862hL9voPRJS+GzGm'
c = b64decode(c)
aes = AES.new(key1, AES.MODE_ECB)
print(aes.decrypt(c))
aes = AES.new(key2, AES.MODE_ECB)
print(aes.decrypt(c))