NTRU

参数选择：

p为任意的正整数

f g为规定范围内的两个数，作为私钥，并满足如下条件

$f<\sqrt{}q/2$$f < \sqrt{}{q/2}$ $\sqrt{}q/4<g<\sqrt{}q/2$$\sqrt{}{q/4} < g < \sqrt{}{q/2}$ gcd(f,g) = 1

h为满足如下条件的一个量

h = $f^{-1}$$f^{-1}$g (mod q) 0 < h < q

r为选取的临时量，满足如下条件

$0<m<\sqrt{}q/4$$0 < m < \sqrt{}{q/4}$ $0<r<\sqrt{}q/2$$0 < r < \sqrt{}{q/2}$

加密

$e=rh+m(modq)$$e = rh + m (mod q)$

解密

a = fe (mod q) m = $f^{-1}a(modg)$$f^{-1}a (mod g)$

验证

首先对a式进行化简

$a=fe=f\ast (rh+m)=f\ast (r{f}^{-1}g+m)=rg+fm(modq)$$a = fe = f*(rh + m) = f*(rf^{-1}g + m) = rg + fm (mod q)$

根据如上对r g f m参数范围的控制，rg + fm < q

那么等式可以化简成a = rg + fm

接下来对m式进行化简

m = $f^{-1}a$$f^{-1}a$ = $f^{-1}$$f^{-1}$*(rg + fm) = m (mod g)

构造格子求解f g

对于式子h = $f^{-1}$$f^{-1}$g (mod q)，进行相应的化简

h*f = g (mod q)

h*f -kq =g

构造相应的二元格子为

那么求解上述格子的LLL，即可得到(f,g)

背包加密系统

首先简单介绍一下子集问题

M = (M1 , M2 , M3 , ...... , Mn) 整数 S

M中的元素均为整数

从M中找到几个元素和为S的问题被称为subsum-set problem

Bob to Alice

public key $M=(M_1,M_2,M_3,\dots ,M_n)$$M = (M_1 , M_2 , M_3 ,\dots, M_n)$

plaintext $x=(x_1,x_2,x_3,\dots ,x_n)$$x = (x_1 , x_2 , x_3 , \dots , x_n)$$ 二进制字符 0 or 1

cipher $S=\sum _{i=1}^n{x}_i\ast M_i$$S = \sum_{i=1}^n{x_i*M_i}$

由于x中的元素均为二进制字符，所以此类问题可以归为subsum-set问题

solve : 在位数不多的情况下可以使用遍历爆破的形式进行求解，那么算法的时间复杂度为$O(2^n)$$O(2^{n})$

如果利用如下的碰撞算法，可以降低复杂度至一半$O(2^{n/2})$$O(2^{n/2})$

$I\subset 1<i<\frac{1}{2}n$$I \subset { 1 < i < \frac{1}{2}n}$ $J\subset \frac{1}{2}n<i<n$$J \subset { \frac{1}{2}n < i < n}$

$A_I=\sum _{i\subset I}{M}_i$$A_I = \sum_{i \subset I}{M_i}$ $B_J=S-\sum _{j\subset J}{M}_J$$B_J = S - \sum_{j \subset J}{M_J}$

当存在$I_0$$I_0$与$J_0$$J_0$满足$A_I$$A_I$=$B_J$$B_J$时，$I_0$$I_0$与$J_0$$J_0$即为此问题的解

$S=\sum _{i\subset I_0}{M}_i+\sum _{j\subset J_0}{M}_j$$S = \sum_{i \subset I_0}{M_i} + \sum_{j \subset J_0}{M_j}$

那么对于一般的背包问题，只能通过爆破的手段去进行解密，但是当M序列为超递增序列时，就可以使用格的方式进行解密

超递增序列

对于超递增序列，有两个性质

1.$r_{i+1}>r_i$$r_{i+1} > r_i$

2.$r_{i+1}>\sum _{k=1}^i{r}_k$$r_{i+1} > \sum_{k =1}^{i}r_k$

在超增序列的基础上，就可以简单解密此类问题

1）$x_i=1$$x_i = 1$ $S_i>M_i$$S_i > M_i$

2. $x_i=0$$x_i = 0$ $S_i<Mi$$S_i < Mi$

如果得到加密过程中的此序列，那么就可以轻松解密，为了解决这一问题出现了Merkle–Hellman算法

Merkle–Hellman

在一般的子集问题上，制定了新的公钥生成的方式

public key : $M_i=A\ast r_i(modB)$$M_i = A*r_i (mod B)$ $B>2\ast r_n$$B > 2*r_n$ gcd(A,B) = 1

encryption: $ S = x*M = \sum_{i=1}^nx_i*M_i$

decryption: $S_1=A^{-}1\ast S$$S_1 = A^-1*S$

$x\ast r=S_1$$x*r = S_1$

解密是需要得到超递增序列，但如果隐藏掉此序列，只给处理后的M序列，可以构造相应的格子来进行解密

GGH公钥密码系统

Hadamard比率

用于描述一组向量的正交程度

$H(B)={\frac{detL}{|V_1|\ast |V_2|...\ast |V_n|}}^{1/n}$$H(B) = \frac{det L}{|V_1|*|V_2|...*|V_n|}^{1/n}$

0< H（B）≤1，且越接近1，则基中的向量就越接近两两正交

密钥选择

生成一组优质基$v_1,......v_n$$v_1,......v_n$，即Hadamard比率较高

选择一个整数矩阵U，满足det(U) = ±1

几个简单的行列式为±1的矩阵相乘得到，那么构造三角形矩阵，使对角线元素相乘为±1即可

公钥W = U*V

加密

m为明文，选取一个整数小向量

r为干扰向量，选取随机小向量，一般情况下选取3or-3

e为密文，e = m*W +r

解密

公钥W为一组劣质基，使用LLL算法将其转换为优质基$v_1$$v_1$

使用Babai算法计算出在格W上最接近e的格向量$v=round(e\ast v_1^{-1})\ast v_1$$v = round(e*v_1^{-1})*v_1$

明文$m=v\ast W^{-1}$$m = v*W^{-1}$

或者可以利用embedded technique，将CVP转换成SVP的相关问题，可直接求解出干扰项

Nguyen's Attack

干扰项r的每一项一般会为3或者-3，基于此基础上，可以对干扰项进行缩小，简化为更简便的CVP问题

Hidden Number Problem(HNP)

hnp是格上的一个CVP问题，具体可以简化为$k_i=A_i\ast x+B_i(modp)$$k_i = A_i*x + B_i (mod p)$问题

$k_i$$k_i$为每次使用的临时密钥，未知

$A_i$$A_i$、$B_i$$B_i$为可以理解为公钥，已知

$x$$x$为需要求解的私钥

为此我们构建如下的格子，l为临时密钥的bit数

在格子中使用babai算法寻找与向量$A=(A_1,A_2,A_3,...A_n,0)$$A = (A_1,A_2,A_3,...A_n,0)$最近的向量V

可以得到$V=(x\ast B_{1}modp,x\ast B_{2}modp,\dots ,\frac{x}{2^{l+1}})$$V = (x*B_1modp,x*B_2modp,…,\frac{x}{2^{l+1}})$

那么$x=V[-1]\ast 2^{l+1}$$x = V[-1]*{2^{l+1}}$

或者可以利用LLL进行x的求解，其中K为$2^{len(k)}$$2^{len(k)}$

对其进行LLL，可得到$v_k=(k_1,k2,...k_t,Kx/q,K)$$v_k = (k_1,k2,...k_t,Kx/q,K)$

LWE问题的相关学习

主要涉及的还是CVP问题的解决，作用在一个模p上，就需要给格加上一个(row*row)的p矩阵，可以通过一个例题来具体理解

题目

xxxxxxxxxx
import numpy as np
from secret import *

def random_offset(size):
    x = np.random.normal(0, 4.7873, size)
    return np.rint(x)

secret = np.array(list(flag))

column = len(list(secret))
row = 128
prime = 2129

matrix = np.random.randint(512, size=(row, column))
product = matrix.dot(secret) % prime
offset = random_offset(size=row).astype(np.int64)
result = (product + offset) % prime

np.save("matrix.npy", matrix)
np.save("result.npy", result)

首先读取数据得到column为42

matrix是一个(128,42)的随机矩阵

$product=(matrix\ast secret)modp$$product = (matrix*secret) mod p$

offset作为一个干扰向量，参与计算

$result=(product+offset)modp$$result = (product + offset)modp$

化简为等式$r=m\ast s+e+kp$$r = m*s+ e+kp$，现已知m与r，那么构造格子

再使用babai算法对其进行求解r与此格子的最短向量b，那么也就已知$m\ast s=b$$m*s=b$，解方程即可求解s

注：矩阵p可以加在m矩阵的上面