本文主要是介绍NTRU的加密解密过程以及相应的数学基础,Lattice Attack的代码实现后续补上

环论

定义:环是一个集合并有两种运算,$+$和$*$

加法的性质:

  • 存在加法单位元0,$a+0=0+a=a$
  • 存在加法逆元:$a+b=b+a=0$
  • 结合律:$a+(b+c)=(a+b)+c$
  • 交换律:$a+b=b+a$

到现在看如果一个环$R$只定义了一种加法运算那么他就是一个交换群带有单位元0

乘法的性质:

  • 存在乘法单位元1,$a1=1a=a$
  • 结合律:$a*(bc)=(ab)*c$
  • 交换律:$ab=ba$

乘法并不要求存在逆元

环具有分配律:$a*(b+c)=ab+ac$

定义:一个环中,如果每一个非0元素都有乘法逆元,则称这种环叫

商环

商环是从同余类而来的,在环$R$中取一个值m,m不等于0,对任意的$a\in R$,$a^{\prime}\equiv a\pmod{m}$

$$\frac{R}{(m)}=\frac{R}{mR}={a^{\prime}:a^{\prime} \equiv a\pmod{m}}$$

多项式环

一个多项式$f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx_n$的系数都属于环$R$,称多项式$f(x)$属于多项式环$R[x]$。

$$R[x]={a_0+a_1x+a_2x^2+\cdots+a_nx^n:n\geq 0\ and\ a_0,a_1,\dots,a_n\in R }$$

多项式除法

与一般的整数除法一致

上面的例子可以写成

$$x^5+2x^4+7=(x^2+2x)(x^3-5)+(5x^2+10x+7)$$

作为余数$5x^2+10x+7$的阶一定小于除数

如果多项式是在域$\mathbb{F}[x]$中,那么 $\mathbb{F}[x]$中的多项式都可以运用这种除法。于是在$\mathbb{F}[x]$中就有$\gcd和exgcd$算法。

多项式商环

令$\mathbb{F}$是一个域,$m\in \mathbb{F}[x]$是一个非零多项式,每一个非零同余类$a^{\prime}\in \mathbb{F}[x]$有唯一的表示$r$满足:

$$\deg{r}<\deg{m}\quad and\quad a\equiv r\pmod{m}$$

$a^{\prime}$组成的环就是多项式商环,记$\mathbb{F}[x]/m$。

卷积多项式环

卷积多项式环本质上还是一个商环。

$$R=\frac{\Z[x]}{(x^N-1)}$$

再加上一个模数q

$$R_q=\frac{(\Z/q\Z)[x]}{(x^N-1)}$$

环上的乘法运算:

也可以用矩阵来定义这种运算:

$a(x)=a_0+a_1x+a_2x^2+\cdots+a_Nx^N$

$$A=\begin{bmatrix}a_0 & a_{N-1} & \cdots & a_3 & a_2 & a_1 \\ \vdots & \vdots & \cdots &\vdots & \vdots & \vdots & \\ a_{N-2} & a_{N-3} & \cdots & a_1 & a_0 & a_{N-1} \\ a_{N-1} & a_{N-2} & \cdots & a_2 & a_1 & a_{0} \end{bmatrix}$$

$b(x)=b_0+b_1x+b_2x^2+\cdots+b_Nx^N$

$$B=\begin{bmatrix} b_0 \\ b_1 \\ \vdots \\ b_{N-1} \end{bmatrix}$$

$$a(x)\times b(x)=AB$$

NTRU

NTRU既可以用在整数环上,也可以用在多项式环上。

NTRUEncrypt

确定一个整数$N\geq1$和两个模数p,q。确定三个卷积多项式环。

$$R=\frac{\Z[x]}{(x^N-1)},R_p=\frac{(\Z/p\Z)[x]}{(x^N-1)},R_q=\frac{(\Z/q\Z)[x]}{(x^N-1)}$$

再定义一个函数

Alice先选择公共参数(N,p,q,d)。然后生成两个私钥

Alice计算

再计算公钥

Alice把公钥发给Bob,Bob的明文为多项式$m(x)$,系数满足$-\frac{1}{2}p<m_i\leq\frac{1}{2}p$。随后选择一个随机多项式$r(x)$,计算密文

Alice要解密先计算

把得到的$a(x)$做center-lifts操作再带到下面的计算

$b(x)$就是明文了。

The NTRU Lattice

令公钥h(x):

则NTRU Lattice可以表示成

简化一下

$$M^{NTRU}_{h}=\begin{bmatrix}I & h \\ 0 & qI\end{bmatrix}$$

解决NTRU密码的难点就是找到一组私钥(f, g)满足

$$f(x)\times h(x)\equiv g(x)\pmod{q}$$

假设有u(x)

$$f(x)\times h(x)=g(x) + qu(x)$$

那么

$$(f, -u)M^{NTRU}_{h}=(f, g)$$

怎么保证(f, g)是格中最短向量呢

$$\det(M^{NTRU}_{h})=q^N$$

根据Gaussian heuristic predicts 格中非零最短向量的长度大约为

$$\sigma(M^{NTRU}_{h})\approx \sqrt{Nq/\pi e}$$

当$\sigma$的大小和$||(f, g)||$的大小相差不大的时候,(f, g)就很大概率是最短向量了。

example

Basic Encrypt and Decrypt:

from sage.all import *
import logging
N, p, q, d = 7, 3, 41, 2
assert q>(6*d+1)*p

R = ZZ['x']
Rp = R.change_ring(Integers(p)).quotient(x^N-1)
Rq = R.change_ring(Integers(q)).quotient(x^N-1)

def T(d1, d2):
    assert N >= d1+d2
    s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2)
    shuffle(s)
    return R(s)

def genKey():
    while True:
        f = T(d+1, d)
        g = T(d, d)
        try:
            Fp = Rp(f)^(-1)
            Fq = Rq(f)^(-1)
            break
        except:
            continue
    h = Fq*g
    return h, (f, g)

def center_lift(a):
    return R([coeff.lift_centered() for coeff in a])

def encrypt(m, h):
    r = T(d, d)
    e = (p*(r*h) + m)
    return e

def decrypt(e, f):
    a = f*e
    aa = center_lift(a)
    Fp = Rp(f)^(-1)
    return center_lift(Fp*aa)

h, privKey = genKey()
print(f'h = {h}')
print(f'key = {privKey}')
m = T(d, d)
print(f'm = {m}')
e = encrypt(m, h)
print(f'encrypt = {e}')
b = decrypt(e, privKey[0])
print(f'decrypt: {b}')
if b == m:
    print("Done")
else:
    print("faild to decrypt")

运行结果:

Lattice Attack:

from sage.all import *

def center_lift(a):
    return R([coeff.lift_centered() for coeff in a])

def decrypt(e, f):
    a = f*e
    aa = center_lift(a)
    Fp = Rp(f)^(-1)
    return center_lift(Fp*aa)

N, p, q, d = 7, 3, 41, 2
R = ZZ['x']
Rp = R.change_ring(Integers(p)).quotient(x^N-1)
Rq = R.change_ring(Integers(q)).quotient(x^N-1)

e = "38*xbar^6 + 22*xbar^5 + 2*xbar^4 + 20*xbar^3 + 11*xbar^2 + 38*xbar + 33".replace("bar", "")
h = "22*xbar^6 + 6*xbar^5 + 22*xbar^4 + 10*xbar^3 + 38*xbar^2 + 30*xbar + 36".replace("bar", "")
h = Rq(h)
e = Rq(e)

L = zero_matrix(2*N, 2*N)
j = 0
for i in range(N):
    L[i, i] = 1
    for j in range(N):
        L[i, j + N] = h[(j - i) % N]
    L[i+N, i+N] = q
#print(L)
#print(L.LLL())
f = L.LLL()[1][0:N]
g = L.LLL()[1][N:]
f, g = R(list(f)), R(list(g)) 
print(f, g)
m = decrypt(e, f)
print(m)

运行结果: