- 已编辑
如题,主要讲:理论、代码和漏洞利用
原文链接:https://tover.xyz/p/NTRU
NTRU是目前据我所知的最快的抗量子加密算法(当然NTRU也有也有签名算法)。
关于算法的Introduction我就不多说了,如果你之前了解过NTRU,那么我写的不一定会比你所了解的多;如果没了解过,可以先去谷歌或维基了解一下,也可以参考其官网上的文章。
NTRU到目前为止已经有很多版本,我参考的是[HPS14] 7.10 节的教科书版本,顺带一题,作者也是提出NTRU的三人(https://ntru.org/f/hps96.pdf)
参考:
PS:第一版好像是08年的,但我参考的是14年的第二版。
PS:这篇主要讲的是参数设置。
要看懂下面的内容你可能需要:
- 数论知识(特别群论、环论);
- 线性代数知识,多项式运算等;
- 基础的密码学知识(起码你得知道加密算法是干什么的吧);
- Sagemath代码的读写经验;
- 足够的耐心。
理论知识
多项式环和参数选取
首先[HPS14]的7.10.1节一开始就扔出了三个卷积多项式环(Convolution Polynomial Rings),、和,理解这三个环其实是理解NTRU的关键,接下来细说。
首先看,分子(姑且先叫分子吧)的指的是整数域上的多项式,以符号作为多项式的未知数,实际上也就是小学/初中开始接触的多项,比如、等。
然后,横线其实不是指除法,比起除法其实更像一个取余,或者叫商环(Quotient Ring,可以参考[HPS14]的2.10),大概意思是,“分子”上的多项式模上后就会落在上,其中N是NTRU的参数。其实跟RSA在中运算所以要模类似,可以做个类比方便理解。
举个栗子,假设取,那就是,现在尝试把上的转换到上,由于“模数”是,所以有
把这个关系利用到上可以得到:
就是最终落在上的结果。
另一个栗子,,这里偷一下懒,对其作分解后可以得到:
所以有:
一般来说中的多项式最高项不会大于等于次,因为,所以每出现都可以用代替,可以利用这个方法检验最终结果的正确性(虽然我都是直接用Sage算的,逃)。
其实类似,只不过其“分子”是系数模的多项式,也就是多项式的系数需要进行模操作,使其落在中(其实就是的另一种写法)。
举个栗子,设,下面尝试把转换到中:
其实只是系数模。
然后中的取余操作和的类似,不再累赘。和类似,只是模数不同。
以上的、和是NTRU的公开参数,在[HPS14]中的参数要求是,为素数,且
以下更详细的参数设置建议摘抄自[HPS17],大概意思是:一般取,为了加快运算一般取的幂次方(盲猜是二进制有利于计算机优化),同样取素数,不过某些特殊版本的基于理想格的NTRU会取形如,然后模数取,这里超纲了,略。
三元多项式和密钥生成
接下来会说到一个叫的函数:
的输入为两个整数和,输出为一个三元多项式(Ternary Polynomial),三元即,大概意思是,函数会采样一个符合条件:有个项系数为、有个项系数为,其余项系数为(即没有)的多项式,且这个多项式落在上。
接下来利用采样密钥,首先是私钥,我就直接上图不再码一遍了:
其中的也是公开参数(上面也有说了),和是两个主要的私钥(甚至可以把看作一个随机数),落在中(因为的返回值落在中,先记住,后面会用到),和分别是在和上的逆元,这里写出来的意思是,把和存储起来可以加快运算速度,因为计算多项式环的逆元需要一段时间(虽然也不是很久)。
多嘴说一句,取自是因为需要可逆,书中有提到的不可逆,也可以自己推一遍。
这里隐藏的一个信息是,上的多项式可以转换到或中,系数模或者模而已,挺显然的,略。
然后计算公钥:
换一种写法其实也就是:
Center-lift和加解密
首先说Center-lift,上面说了,上的多项式可以转换到或中,而Center-lift则是把或中的多项式转换回中,而且使得多项式系数的绝对值最小(相比于其他的转换方式)。
Center-lift的定义可以看[HSP14]的7.9节,主要是针对多项式系数的操作,可以和补码类比。
上面假设是多项式的Center-lift,即转换到。上图的为上的一个多项式,为其Center-lift到后的结果,为的次项系数,为的次项系数。
Center-lift后的结果是,所有的系数会落在区间,而且还能保证。
Center-lift的方法也不难,和转补码类似,在砍一半,小于等于的不动,大于的平移到,也就是:
检验一下,上面的划分可以覆盖整个,当时显然,而且落在;时,,由于落在,所以落在,也即,自然落在,检验通过。
然后接着看加密,明文空间是做Center-lift后的空间,也即在上,系数取值落在的空间,加密使用的随机数在中采样,然后加密操作就是下图的公式,密文是。
在继续解密操作前,先分析一下密文的结构。
首先如果要解密的话,其实只用把这一项去除,先剧透一下,由于,所以直观上把放入中就可以把去除,而由于明文空间是做Center-lift后的空间,所以把放入中并不会改变的结构,即可以恢复明文。
剩下的问题是我其实并不能保证,除非(这种情况在前几天讲OU98时有讲过),但因为,所以这种情况并不存在。
这样的栗子可以举很多,可以直接看整数的栗子(反正也是模在多项式系数上),设、、,计算可得
显然不等,也即不能直接转换到上。
但是前面说过,可以转换到上,所以可以考虑先把转换(Center-lift)到上,然后再转到上。
但新的问题是,直接把上的转到上,其结果不一定是原来上的,举个整数域上的栗子即,除了一种情况,即把放在上运算后的系数本来就落在,也即上的元素做Center-lift后的区间。
在讲如何把系数转化到前,可能先需要了解一下多项式的乘法。
多项式卷积乘法
在继续讲解密思路前,先“简要”介绍一下多项式卷积。
在这篇我曾经写过,多项式的卷积乘法可以看成一个矩阵操作,这里多嘴推导一下这个矩阵是怎么来的,如果不关心推导则可以跳过。
下面假设和在中相乘(假设而已),先把多项式表述为:
那么有(参考多项式乘法,用分配律推也行):
由于的结果肯定也是个多项式(封闭性),所以先把上面结构调整到像一个多项式,即合并次数相同的项(注意和最高项只能是,所以不考虑模的时候乘起来最高项只能是,然后小于次的项和大于等于次的项分开处理):
最开始讲环的时候说到,是模的,所以,所以有
即未知数的指数部分需要模,所以可以继续化简:
其中的即为的次项系数。
粗略检验一下正确性,设、、,则:
检验通过。
以下用矩阵的形式表达,姑且记的次项系数为,即为
解密与参数关系计算
首先直接贴解密过程,
公式推导我也懒得再码一遍了,直接截图:
现在的目标是要把的系数转化到区间,而观察的结构可发现,要达成这个目标最大的阻碍是,因为,其中的取逆操作会把系数“打乱”,从而产生很大(规模)的系数,所以需要想方法消去。
消去方法如上面的推导,乘上一个,把转换成,,其系数只会是小系数、或。
虽然消去,但其实还不能保证的绝对值系数严格落在,所以接下来需要先计算的最大和最小系数,计算方法稍微引用下原文:
可以把分成两部分,即“+”分割的和。
首先看的最大和最小系数,由于是常数,所以可以先看,翻看上面内容,和都采样自,即只有个系数为的项和个系数为的项,其余项系数为。
上一节已经推出了,为的次项系数,由于只会在和都取或者都取时可以取得最大值,所以在拥有最多的出现最大值的情况下的次项系数出现最大值,这个情况即是:值为的刚好匹配上值为的、值为的刚好匹配上值为的、且值为的刚好匹配上值为的的情况,产生的最大值是。
再把常数考虑进去,即的最大值是。
类似地,当和匹配上的时候,出现最小值,即得的最小值是。
再来看得最大和最小系数,采样自,即有个项系数为、有个项系数为、其余项为;的系数落在,即做Center-lift后的区间。
类似地,为的次项系数,只会在取、取时和在取、取(虽然取不到,但可以用来计算界)时取得最大值,这些情况总共可以出现次(中的个数加上的个数),所以的系数最大值是。
再类似地,在取、取时和在取、取时,取得最小值,总可出现次,所以所以的系数最小值是。
最后的最大系数就是和两部分的最大系数之和,即
同理,最小系数是。(希望到这里还没看晕,逃)
接下来,要保证的系数落在,只需要保证其最大系数严格小于且最小系数严格大于即可,(经过上面计算可发现其实这两个是等价的,多了个负号而已),所以即需要保证:
化简也即:
即需要在设置四个公开参数时保证以上关系,才能让正确地转换到上,保证解密的正确性。
接着按前文说的,现在在上,可以转换到上以消除:
为了恢复出还需要消去,这直接乘上即可:
到这可以已经解密出,但这个落在,即系数取值在,而实际的取值应该是在,所以最后还要把做一次Center-lift才解出真正的。
总结
公开参数:,其中是素数、一般取、一般取的幂,还需要保证,和;
密钥生成:采样、,计算和,计算公钥。
- 私钥为:
- 公钥为:
加密:明文的系数需落在(虽然很奇怪下面表中说明文取自),采样随机数,密文为;
解密:计算并做Center-lift到,计算,最后把做Center-lift到(如果明文取自则不需要这一步)。
参考代码
参照上面理论部分写了个代码,其实我在很久以前就写过一个NTRU的代码,但因为穷拿去投题了,所以有保密协议就不能发,这次代码的加了很多骚操作,整体来说也更美观,所以感觉还是值得发一下。
首先是三个环、和,需要先做出、和,在Sage代码中写作:
R_ = PolynomialRing(ZZ,'x')
Rp_ = PolynomialRing(Zmod(p),'xp')
Rq_ = PolynomialRing(Zmod(q),'xq')
其中为了防止混淆,和的未知数在代码中我称作xp
和xq
。
然后使用上面三个东西做商环(模)就得到三个环、和:
R = R_.quotient(x^N - 1, 'y')
Rp = Rp_.quotient(xp^N - 1, 'yp')
Rq = Rq_.quotient(xq^N - 1, 'yq')
其中也是为了防混淆,我把、和上的未知数称作y
、yp
和yq
。
然后采样三元多项式的函数,我选择先固定个系数和个系数,然后再用shuffle
将其打乱以获得随机的输出,然后要注意的输出落在(毕竟有负数):
def T(self, d1, d2):
assert self.N >= d1+d2
t = [1]*d1 + [-1]*d2 + [0]*(self.N-d1-d2)
shuffle(t)
return self.R(t)
Center-lift函数基本照抄理论部分的公式就可以了,但由于作为函数我并不知道需要Lift的是环还是环,所以需要用“曲线救国”的方法在输入中提取模数(估计有更好的方法,懒):
def lift(self, fx):
mod = Integer(fx.base_ring()(-1)) + 1 # emmm
return self.R([Integer(x)-mod if x > mod//2 else x for x in list(fx)])
然后是密钥生成,首先和直接用采样即可。的计算,由于在上,而是素数,所以用Sage可以很方便地求逆:
Fp = self.Rp(list(fx)) ^ (-1)
上面需要先把fx
转换到Rp
上再做求逆,而由于前面设置的未知数名称不一致,不能直接用Rp(fx)
做转换,曲线救国,先用list(fx)
提取fx
的系数,然后用系数转到Rp
。
的计算则有点复杂,由于不为素数所以不能直接用Sage像上面那样求逆,目前网上查到的流行做法如这个教程的invertmodpowerof2
做递归求逆,但是我后来想到了一种更美观的“曲线救国”方法。
参考整数域上的求逆,比如要求,除了用egcd求逆外,还有一种方法是(借助欧拉定理):
其中的即的阶。
所以只要求出的阶即可利用类似方法求逆,问题是如何求的阶。
经过计算加实验,我发现在的阶(只是针对)为:
的因子。(原理未明,留坑)
而在的阶为:
的因子。这个结果和之前求阶的结果类似,毕竟为素数时,两个东西同构(如果我没记错的话,逃)。
为了方便表述,姑且把上面两个阶记作和,所以通过计算
即可算出和。
然后加密好像没啥可说的,只是为了统一,我把返回值转成字符串再输出,这样在输进解密函数时也不需要考虑类型问题。
解密函数也没啥好说,关注Center-lift的时机即可。
最后的参考代码:
# Sage
# Ref: https://www.osgeo.cn/sagemath/constructions/rings.html
class NTRU:
def __init__(self, N, p, q, d):
self.debug = False
assert q > (6*d+1)*p
assert is_prime(N)
assert gcd(N, q) == 1 and gcd(p, q) == 1
self.N = N
self.p = p
self.q = q
self.d = d
self.R_ = PolynomialRing(ZZ,'x')
self.Rp_ = PolynomialRing(Zmod(p),'xp')
self.Rq_ = PolynomialRing(Zmod(q),'xq')
x = self.R_.gen()
xp = self.Rp_.gen()
xq = self.Rq_.gen()
self.R = self.R_.quotient(x^N - 1, 'y')
self.Rp = self.Rp_.quotient(xp^N - 1, 'yp')
self.Rq = self.Rq_.quotient(xq^N - 1, 'yq')
# order check in keyGen
#self.RpOrder = self.p^self.N - self.p
#self.RqOrder = self.q^self.N - self.q
self.RpOrder = self.p^(self.N - 1) - 1
self.RqOrder = (self.q^self.N - self.q) // (self.q-1)
self.sk, self.pk = self.keyGen()
def test(self):
assert self.debug == True
pass
def T(self, d1, d2):
assert self.N >= d1+d2
t = [1]*d1 + [-1]*d2 + [0]*(self.N-d1-d2)
shuffle(t)
return self.R(t)
# center lift
def lift(self, fx):
mod = Integer(fx.base_ring()(-1)) + 1 # emmm
return self.R([Integer(x)-mod if x > mod//2 else x for x in list(fx)])
def keyGen(self):
fx = self.T(self.d+1, self.d)
gx = self.T(self.d, self.d)
Fp = self.Rp(list(fx)) ^ (-1) # list emmm
assert pow(self.Rp(list(fx)), self.RpOrder-1) == Fp # order checked
assert self.Rp(list(fx)) * Fp == 1
# Fq = self.Rq(fx) ^ (-1) # wasted
Fq = pow(self.Rq(list(fx)), self.RqOrder - 1) # invert
assert self.Rq(list(fx)) * Fq == 1 # order checked
hx = Fq * self.Rq(list(gx))
sk = (fx, gx, Fp, Fq, hx)
pk = hx
return sk, pk
def setKey(self, fx, gx):
assert type(fx) == type('x^2 + 1') # e.g.
assert type(gx) == type('x^2 - 1') # emmm
try:
fx = self.R(fx)
gx = self.R(gx)
Fp = self.Rp(list(fx)) ^ (-1)
Fq = pow(self.Rq(list(fx)), self.RqOrder - 1)
hx = Fq * self.Rq(list(gx))
self.sk = (fx, gx, Fp, Fq, hx)
self.pk = hx
return True
except:
return False
def getKey(self):
ssk = (
str(self.R_(list(self.sk[0]))), # fx
str(self.R_(list(self.sk[1]))) # gx
)
spk = str(self.Rq_(list(self.pk))) # hx
return ssk, spk
def encrypt(self, m):
assert type(m) == type('x^2 + 1') # e.g.
assert self.pk != None
hx = self.pk
mx = self.R(m)
mx = self.Rp(list(mx)) # change m to Rp, TODO: assert m in Rp
mx = self.Rq(list(mx)) # change m to Rq
rx = self.T(self.d, self.d)
rx = self.Rq(list(rx))
e = self.p * rx * hx + mx
#return e
return str(self.Rq_(list(e)))
def decrypt(self, e):
assert type(e) == type('xq^2 - 1') # e.g.
assert self.sk != None
fx, gx, Fp, Fq, hx = self.sk
e = self.Rq(e)
ax = self.Rq(list(fx)) * e
a = self.lift(ax) # center lift
bx = Fp * self.Rp(list(a))
b = self.lift(bx)
#return bx
return str(self.R_(list(b)))
if __name__ == '__main__':
mm = '-x^2 + x + 1'
ntru = NTRU(N=11, p=3, q=512, d=3)
#ntru.setKey('xp^2+1', 'xq^2-1')
print('keyGen check:')
sk, pk = ntru.getKey()
print("fx = '%s'" % sk[0])
print("gx = '%s'" % sk[1])
print("hx = '%s'" % pk)
print('\nencrypt/decrypt check:')
e = ntru.encrypt(mm)
print("e = '%s'" % e)
m = ntru.decrypt(e)
print(m)
assert m == mm
print(m)
print('\ncheck setKey:')
fx = 'x^10 + x^9 - x^8 - x^5 + x^4 + x - 1'
gx = '-x^10 + x^9 - x^6 - x^5 + x^4 + 1'
hx = '357*xq^10 + 156*xq^9 + 22*xq^8 + 467*xq^7 + 356*xq^6 + 23*xq^5 + 422*xq^4 + 490*xq^3 + 200*xq^2 + 201*xq + 378'
e = '286*xq^10 + 336*xq^9 + 355*xq^8 + 220*xq^7 + 330*xq^6 + 198*xq^5 + 182*xq^4 + 443*xq^3 + 454*xq^2 + 45*xq + 227'
ntru.setKey(fx, gx)
m = ntru.decrypt(e)
assert m == mm
print(m)
攻击方法
下面说一下[HPS14]里提到的两种攻击方法。
小密钥空间
[HPS14]的7.10.2中提到:
即和的取值不合理的话,会导致的取值空间过小,从而可以被攻击者枚举出密钥。
这个在参数设置上注意就好了,做题的话看见和过小可以考虑直接枚举。
格规约攻击
这里参考[HPS14]的7.11的内容,主要关注公钥的生成:
把模数去除,参考[HPS14]的写法即存在一个多项式使得:
写成矩阵形式也即(如果熟悉格规约的话,会把已知的放进矩阵):
这个只是一个写着方便的表述,实际上、、和都是多项式,不能这样简单地占一个位置,应该
- 多项式相乘:用前面说的多项式卷积乘法的矩阵写法;
- 多项式数乘:用多项式的系数向量和对角线上为该常数的对角矩阵相乘;
这里我就直接抄书了:
用书中的简化写法是(为了混淆我用了,是单位矩阵):
存在关系(记为的系数向量,记为的系数向量):
直观上和上元素的绝对值最大是,所以是“小”向量,用LLL对规约即可出,这里先计算一下,我就直接借用[HPS14]的计算(懒):
但实际操作的情况是,LLL实际上解的是apprSVP,当矩阵规模变大时,求出的能力会变小,所以只要设置足够大的即可防止这类攻击。
贴个攻击参考代码:
# Sage
def matrix_overview(BB):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
if BB[ii, jj] == 0:
a += ' '
else:
a += 'X'
if BB.dimensions()[0] < 60:
a += ' '
print(a)
# cp NTRU.sage.py NTRU.py
from NTRU import NTRU
N = 11
q = 512
p = 3
d = 3
hx = '357*xq^10 + 156*xq^9 + 22*xq^8 + 467*xq^7 + 356*xq^6 + 23*xq^5 + 422*xq^4 + 490*xq^3 + 200*xq^2 + 201*xq + 378'
e = '286*xq^10 + 336*xq^9 + 355*xq^8 + 220*xq^7 + 330*xq^6 + 198*xq^5 + 182*xq^4 + 443*xq^3 + 454*xq^2 + 45*xq + 227'
Rq_ = PolynomialRing(Zmod(q),'xq')
h = vector(list(Rq_(hx)))
print(h)
M = matrix(ZZ, 2*N)
for i in range(N):
M[i, i] = 1
M[N+i, N+i] = q
for j in range(N):
M[i, N+j] = h[(j-i) % N]
matrix_overview(M)
#print(M)
L = M.LLL()
#L = M.BKZ(block_size=32)
def inT(f, d1, d2, N):
fl = list(f)
c1 = fl.count(1)
c_1 = fl.count(-1)
c0 = fl.count(0)
return c1==d1 and c_1==d2 and c1+c0+c_1 == N
R_ = PolynomialRing(ZZ,'x')
ntru = NTRU(N=N, p=p, q=q, d=d)
for i in range(N):
fg = L[i]
f = vector(ZZ, fg[:N])
g = vector(ZZ, fg[N:])
if inT(f, d+1, d, N):
pass
elif inT(-f, d+1, d, N):
f = -f
else:
continue
if inT(g, d, d, N):
pass
elif inT(-g, d, d, N):
g = -g # duoyu
else:
continue
print('Trying in i = %d' % i)
fx = str(R_(list(f)))
gx = str(R_(list(g)))
print('f = %s' % fx)
print('g = %s' % gx)
ntru.setKey(fx, gx)
m = ntru.decrypt(e)
print('m = %s' % m)
print('----------------\n')
有一个尴尬的情况是,是一个N-Gap的格,也即LLL/BKZ规约后的矩阵中,前N行向量的规模是相近的,这会导致LLL/BKZ规约后的第一行不一定是,当然也会有不是最短向量的情况。
曲线救国的方法是,把前N行向量都试一遍,先检测其是否落在,再尝试解密。
另外,实验测出有多个多个都可以实现解密的情况,合理怀疑一个公钥可以对应多个私钥,也就是有可能上面解出来的前行都是对的,emmmm。