Translation of LatticeHacks

Posted on Edited on In Word count in article: 9.5k Reading time ≈ 9 mins.

打了个比赛NTRU不会做, 翻密码爷爷的博客发现一个宝藏网站https://latticehacks.cr.yp.to
虽然内容不多, 还是英语的. 这里翻译翻译也顺便学习一下.

NTRU

多项式

Zx.<x> = ZZ[]

这里创建了一个Zx类, 一个Zx对象, 一个Zx对象是关于x的整系数多项式, 举个栗子:

1
2
3
sage : f = Zx([3,1,4])
sage : f
4*x^2 + x + 3

这个多项式f是这三部分的和. 每一部分都是整数系数(分别为4,1,3) 乘(times?)上一个的次幂(为别为)

也可以将上面的例子复制黏贴进Sage源代码里

1
2
3
f = Zx([3,1,4])
f
# output: 4*x^2 + x + 3

多项式乘法

Zx类有一个把每一部分相乘并相加的内置乘法. 比如说, 乘一个, 或者是的任意次方, 不过这样也就是在移动的参数:

1
2
3
4
f
# output: 4*x^2 + x + 3
f*x
# output: 4*x^3 + x^2 + 3*x

再来个例子:

1
2
3
4
5
g = Zx([2,7,1])
g
# output: x^2 + 7*x + 2
f*g
# output: 4*x^4 + 29*3^3 + 18*x^2 + 23*x + 6

循环卷积

顺便学习一下循环卷积是怎样的
卷积分三种: 线性卷积, 周期卷积, 循环卷积
线性卷积: 就是普通的多项式乘法
循环卷积与周期卷积并没有本质区别, 循环卷积就是保留前一部分不动, 把后面的截下来加到前一部分去(就是模吧, 比如模, 对于结果来说, 就是把模成, 再加到前面去变成) 

1
2
def convolution(f,g):
	return (f * g)% (x^n - 1)

这个乘法就是NTRU中使用的乘法. 它就像模一个多项式乘法. 这意味着把替换成1, 把替换成, 把替换成等等

输入两个模的系数多项式和, 那么输出也会是一个次多项式, 因为次及以上的式子都被约掉了. 所以是有可能存在一些甚至是全部项的系数为0. 我们常说的系数多项式并不是说全都存在, 而是说 等等的项不存在.

例子

1
2
3
4
5
n = 3
f*g
# output: 4*x^4 + 29*x^3 + 18*x^2 + 23*x + 6
convolution(f,g)
# output: 18*x^2 + 27*x + 35

另外一个例子, 计算和次幂的卷积, 就是在旋转的系数.

1
2
3
4
5
6
7
n = 3
f
# output: 4*x^2 + x + 3
convolution(f,x)
# output: x^2 + 3*x + 4
convolution(f,x^2)
# output: 3*x^2 + 4*x + 1

注意, 这里的是一个全局变量.

原文这里还有两个练习, 一个是python练习, 一个是数学练习…这里就不翻译了, 也没什么必要.

Sage可以直接用R = Zx.quotient(x^n-1)生成一个加减乘运算都是的类R

“cyclic convolution”(循环卷积) 或者是 “circular convolution” 这个名字来自与信号处理. 在多项式乘法中, 它叫”acyclic convolution”

模约

1
2
3
def balancedmod(f,q):
	g = list(((f[i] + q//2) %q) - q//2 for i in range(n))
	return Zx(g)

balancedmod()有两个输入: 一个整系数多项式和一个正整数. 输出一个也是n整系数, 并且每一个系数都. 数学家们通常定义模约的结果在 之中, 但这个函数的输出会将系数模约到之间, 更详细的说, 当是偶数的时候, 结果的范围是;当是奇数的时候, 范围是

来个例子:

1
2
3
4
5
6
7
8
u = Zx([3,1,4,1,5,9])
u
# output: 9*x^5 + 5*x^4 + x^3 + 4*x^2 + x + 3
n = 7
balancedmod(u,10)
# output: -x^5 - 5*x^4 + x^3 + 4*x^2 + x + 3
balancedmod(u,3)
# output: -x^4 + x^3 + x^2 + x

在函数内部, balancedmod()依旧使用Sage的% q操作, 这个操作的输出会在之间. 但这个函数会调整输入和输出到, 也就是取整数部分.

注意, 负数输入% q后在低级语言中往往会输出负数. 这样会泄露输入的符号(除非输入刚好是的倍数, 那么输出就会是0). 泄露符号可以导致一些严重的安全问题, Sage支持对多项式进行% p这个操作, 但是输出有时候会泄露输入的符号, 比如说:

1
2
3
4
5
6
7
8
9
u = 314 - 159*x
u % 200
# output: -159*x + 114
(u - 400) % 200
# output: -159*x - 86
(u - 600) % 200
# output: -159*x + 114
balancedmod(u,200)
# output: 41*x - 86

d项非零的随机多项式(Random polynomials with d nonzero coefficients)

1
2
3
4
5
6
7
8
9
def randomdpoly():
	assert d <= n
	result = n*[0]
	for j in range(d):
		while True:
			r = randrange(n)
			if not result[r]: break
		result[r] = 1 - 2*randrange(2)
	return Zx(result)

randomdpoly()返回一个有个非零系数(个系数为0)的次多项式. 而且每个非零的系数要么是1, 要么是-1.

来看例子(注意n和d是全局变量):

1
2
3
4
5
6
7
8
n = 7
d = 5
f = randomdpoly()
f
# output: x^6 + x^5 - x^3 + x^2 - 1
f = randomdpoly()
f
# output: -x^4 + x^3 + x^2 - x + 1

模素数的除法

1
2
3
def invertmodprime(f,p):
	T = Zx.change_ring(Integers(p)).quotient(x^n-1)
	return Zx(lift(1 / T(f)))

litf(), 把一个在环R/I中的数, 转成在R中

invertmodprime()会计算一个多项式在下的逆元.

这个函数有两个输入, 一个系数多项式以及一个素数(比如说 3). 输出一个系数多项式, 这个满足(是循环卷积, 也是一个多项式). 如果多项式不存在, 那么这个函数将报错. 举个例子:

1
2
3
4
5
6
7
8
n = 7
f
# output: -x^4 + x^3 + x^2 - x + 1
f3 = invertmodprime(f,3)
f3
# output: x^6 + 2*x^4 + x
convolution(f,f3)
# output: 3*x^6 - 3*x^5 + 3*x^4 + 1

convolution的结果可以看成, 其中

事实上在模非素数的时候也是可能算出结果的, 但是由于invertmodprime使用了Sage中的子程序?(subroutines), 以至于该函数会没那么好的处理非素数模.

模的除法

1
2
3
4
5
6
7
def invertmodpowerof2(f,q):
     assert q.is_power_of(2)
     g = invertmodprime(f,2)
     while True:
       r = balancedmod(convolution(g,f),q)
       if r == 1: return g
       g = balancedmod(convolution(g,2 - r),q)

这个函数跟上面的invertmodprime很像, 唯一的不同是输入是, 比如 

1
2
3
4
5
6
7
n = 7
q = 256
f
# output: -x^4 + x^3 + x^2 - x + 1
fq = invertmodpowerof2(f,q)
convolution(f,fq)
# output: -256*x^6 + 256*x^4 - 256*x ^2 + 257

convolution的结果可以看成, 其中

这里依旧有个数学练习

NTRU 密钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
def keypair():
	while True:
		try:
			f = randomdpoly()
			f3 = invertmodprime(f,3)
			fq = invertmodpowerof(f,q)
			break
		except:
			pass
	g = randomdpoly()
	publickey = balancedmod(3 * convolution(fq,g),q)
	secretkey = f,f3
	return publickey,secretkey

keypair()会生成一个公钥h和对应的私钥f,f3. 公钥看起来就像一个随机的的系数多项式. 比如说, 如果, 那么公钥看起来就像一个7个随机的字节?(bytes):

1
2
3
4
5
6
n = 7
d = 5
q = 256
publickey, secretkey = keypair()
publickey
# output: 54*x^6 - 40*x^5 + 90*x^4 + 101*x^3 - 108*x^2 + 80*x + 76

其中一个私钥是一个有小系数的多项式, 将与公钥卷积再能生成另外一个小系数的多项式, 也就是出现在密钥生成里的

1
2
3
4
5
6
7
f,f3 = secretkey
f
# output:-x^6 + x^5 - x^4 + x^2 + 1
convolution(f, publickey)
# output: 256*x^6 + 3*x^5 - 3*x^3 - 3*x^2 + 253*x - 253
balancedmod(_,q)
# output: 3*x^5 - 3*x^3 - 3*x^2 - 3*x + 3

用于加密的消息

1
2
3
def randommessage():
	result = list(randrange(3) - 1 for j in range(n))
	return Zx(result)

这个函数会返回一个个系数为的多项式

1
2
3
4
5
6
7
8
9
n = 7
randommessage()
# output: -x^6 - x^5 + x^4
randommessage()
# output: x^6 + x^5 - x^4 - 1
randommessage()
# output: -x^4 - x^3 - x + 1
randommessage()
# output: -x^6 + x^4 - x^2 + 1

加密

1
2
3
def encrypt(message,publickey):
     r = randomdpoly()
     return balancedmod(convolution(publickey,r) + message,q)

加密函数输入一个需要加密的消息和公钥, 输出的密文为,其中是消息, 是随机的一个多项式.

例子:

1
2
3
4
5
6
7
8
9
10
11
12
n = 7
d = 5
q = 256
h,secretkey = keypair()
h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
m = randommessage()
m
# output: -x^6 - x^4 + x^2 + 1
c = encrypt(m,h)
c
# output: -66*x^6 + 37*x^5 + 115*x^4 - 15*x^3 - 6*x^2 - 89*x + 27

解密

1
2
3
4
def decrypt(ciphertext,secretkey):
     f,f3 = secretkey
     a = balancedmod(convolution(ciphertext,f),q)
     return balancedmod(convolution(a,f3),3)

解密函数需要输入密文和私钥

这里作者测试了一下解密算法, 就知识简单的重复加完密再解密, 这部分就不写下来了.

下面这个例子就是加解密的时候函数内部的所有过程, 用来说明解密的正确性:

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
n = 7
d = 5
q = 256
h,secretkey = keypair()
h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
m = randommessage()
m
# output: x^6 + x^5 - x^4 - x^3 + x - 1
r = randomdpoly()
r
# output: -x^6 + x^5 + x^4 + x^3 - x^2
f = secretkey[0]
f
# output: -x^6 - x^5 - x^4 - x^3 - x
g3 = balancedmod(convolution(f,h),q)
g3
# output: -3*x^6 - 3*x^3 + 3*x^2 - 3*x - 3
c = balancedmod(convolution(h,r) + m,q)
c
# output: -93*x^6 - 105*x^5 - 110*x^4 - 95*x^3 - 106*x^2 
a = balancedmod(convolution(f,c),q)
a
# output: 3*x^5 - 13*x^4 - 3*x^3 + 2*x^2 - x + 3
convolution(g3,r) + convolution(f,m)
# output: 3*x^5 - 13*x^4 - 3*x^3 + 2*x^2 - x + 3
balancedmod(a,3)
# output: -x^4 - x^2 - x
balancedmod(convolution(f,m),3)
# output: -x^4 - x^2 - x

再看看过程,

所以我们有:

多项式的系数都特别的小, 所以这里对系数的最大值有限制. 只有当这个限制足够小, 小到就是, 这个时候规约就是在计算, 最后再乘就能得到了

注意到解密是有可能失败的, 有一个办法避免对有效密文的解密失败就是标准化的选取, 但是攻击者仍然可以故意选择无效密文来查看解密是否可以正常进行. 所以为了安全采取额外的措施抵抗这种选择密文攻击是很重要的!

一个对参数过小的NTRU的攻击实例

在下面的例子中, 参数将使用

攻击者将会从公钥入手. 我们可以计算

1
2
3
4
5
h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
Integers(q)(1/3)
# output: 171
h3 = (171 * h)%q

我们可以把看成是私钥乘. 记住, 私钥是从通过一些加减得到的. 那么对应的就是从通过一些加减得到的.下面是这些多项式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
h3
# output: 58*x^6 + 210*x^5 + 54*x^4 + 36*x^3 + 194*x^2 + 130*x + 87
convolution(h3,x)
# output: 210*x^6 + 54*x^5 + 36*x^4 + 194*x^3 + 130*x^2 + 87*x + 58
convolution(h3,x^2)
# output: 54*x^6 + 36*x^5 + 194*x^4 + 130*x^3 + 87*x^2 + 58*x + 210
convolution(h3,x^3)
# output: 36*x^6 + 194*x^5 + 130*x^4 + 87*x^3 + 58*x^2 + 210*x + 54
convolution(h3,x^4)
# output: 194*x^6 + 130*x^5 + 87*x^4 + 58*x^3 + 210*x^2 + 54*x + 36
convolution(h3,x^5)
# output: 130*x^6 + 87*x^5 + 58*x^4 + 210*x^3 + 54*x^2 + 36*x + 194
convolution(h3,x^6)
# output: 87*x^6 + 58*x^5 + 210*x^4 + 54*x^3 + 36*x^2 + 194*x + 130

事实上, , 可以从任意的参数通过加减得到. 这意味着可以从组合而来

最后, 连接上面的这些系数并将产生的组合写进下面的矩阵中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
M = Matrix(2*n)
for i in range(n): M[i,i] = q
for i in range(n,2*n): M[i,i] = 1
for i in range(n):
	for j in range(n):
		M[i+n,j] = convolution(h3, x^i)[j]
M
# output: [256   0   0   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0 256   0   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0 256   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0 256   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0 256   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0   0 256   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0   0   0 256   0   0   0   0   0   0   0]
# output: [ 87 130 194  36  54 210  58   1   0   0   0   0   0   0]
# output: [ 58  87 130 194  36  54 210   0   1   0   0   0   0   0]
# output: [210  58  87 130 194  36  54   0   0   1   0   0   0   0]
# output: [ 54 210  58  87 130 194  36   0   0   0   1   0   0   0]
# output: [ 36  54 210  58  87 130 194   0   0   0   0   1   0   0]
# output: [194  36  54 210  58  87 130   0   0   0   0   0   1   0]
# output: [130 194  36  54 210  58  87   0   0   0   0   0   0   1]

然后使用LLL算法可以快速的找出行组合出来的短向量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
M.LLL()
# output: [ -1  -1   1  -1   1   0   0  -1   1  -1  -1   1   0   0]
# output: [  0  -1  -1   1  -1   1   0   0  -1   1  -1  -1   1   0]
# output: [  1  -1   1  -1   0   0   1  -1   1   1  -1   0   0   1]
# output: [ -1   1  -1   0   0   1   1   1   1  -1   0   0   1  -1]
# output: [  1  -1   0   0   1   1  -1   1  -1   0   0   1  -1   1]
# output: [  1   1   1   1   1   1   1   1   1   1   1   1   1   1]
# output: [  0   0   1   1  -1   1  -1   0   0   1  -1   1   1  -1]
# output: [ 39 -28  19  12  11 -48  -4  47   6 -31 -20 -19  36 -18]
# output: [ -5 -34 -14  -3   9 -39 -43  47  54  22   1 -17  19   1]
# output: [  4 -39  28 -19 -12 -11  48  18 -47  -6  31  20  19 -36]
# output: [  9 -40 -43  -5 -32 -13  -1 -17  20   1  47  54  23   3]
# output: [ -1   9 -40 -43  -5 -32 -13   3 -17  20   1  47  54  23]
# output: [ 14   3  -9  40  43   4  32 -22  -3  17 -18  -1 -48 -54]
# output: [ 28 -19 -12 -11  48   4 -39  -6  31  20  19 -36  18 -47]

这里详细的解释一下, 因为多项式g的系数就是由这些项的系数线性组合而来的, 矩阵M左下角那一块就是h3可能出现的系数的排列, 左上角一块是q和相乘的系数(其实就是q), 这些行向量进行线性组合的结果中, 肯定存在的系数, 而又因为的系数都是很小的, 所以利用格基规约, 可以把向量规约出来.

第一行的就是对应的, 事实上, 如果的负数那么产生的也是的负数

1
2
3
4
5
6
M.LLL()[0][n:]
# output: (-1, 1, -1, -1, 1, 0, 0)
Zx(list(_))
# output: x^4 - x^3 - x^2 + x - 1
f
# output: -x^4 + x^3 + x^2 - x + 1

但是攻击者仍然可以解密且不考虑负数. 同样的, LLL 可以产生能够正常用于解密的和, 所以对于NTRU方案, 需要更大的参数来保证它的安全性.

自动化攻击

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
def attack(publickey):
  recip3 = lift(1/Integers(q)(3))
  publickeyover3 = balancedmod(recip3 * publickey,q)
  M = matrix(2 * n)
  for i in range(n):
    M[i,i] = q
  for i in range(n):
    M[i+n,i+n] = 1
    c = convolution(x^i,publickeyover3)
    for j in range(n):
      M[i+n,j] = c[j]
  M = M.LLL()
  for j in range(2 * n):
    try:
      f = Zx(list(M[j][n:]))
      f3 = invertmodprime(f,3)
      return (f,f3)
    except:
      pass
  return (f,f)

n = 120
q = 2^32
d = 81

publickey,secretkey = keypair()
donald = attack(publickey)
print donald[0]
try:
  m = randommessage()
  c = encrypt(m,publickey)
  assert decrypt(c,donald) == m
  print 'attack successfully decrypts'
except:
  print 'attack was unsuccessful'

这个脚本用的是Python2的sage? 真的要用来解题估计还得自己写一个