Simple-Lattice-Attacks

Posted on Edited on In Word count in article: 7.4k Reading time ≈ 7 mins.

《 Introduction of Modern Cryptography》Chapter 7

7.1baby NTRU cryptosystem

算法

Algorithm 1.1.1: Key Creation

Data:

Result: public key

  • Choose modulus (large)
  • Choose with
  • Compute
  • Publish , keep secret

Algorithm 1.1.2: Encryption

Data: public key, plaintext

Result: ciphertext

  • Choose m with
  • Choose r with
  • Compute
  • Return

Algorithm 1.1.3: Decryption

Data: ciphertext ,secret key ,

Result: plaintext

  • Compute
  • Compute
  • Return

算法正确性证明

baby ntru

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gen(self,bound):
    q=getPrime(bound)
    bound1=int(gp.iroot(q//2,2)[0])
    bound2=int(gp.iroot(q//4,2)[0])
    while True:
        f,g=random.randint(1,bound1),random.randint(bound2,bound1)
        if gp.gcd(f,q*g) == 1 :
            break 
    h=(gp.invert(f,q)*g)%q
    return q,h,f,g 

def enc(self,m,bound,q,h):
    m_=long_to_bytes(m)
    assert m_<gp.iroot(bound//4,2)[0]
    r=getPrime(bound//2)
    e=(r*h+m)%q
    return e

def dec(self,e,f,g,q):
    a=f*e%q 
    b=gp.invert(f,g)*a%g 
    return b

攻击

爆破私钥需要复杂度。但可以通过公钥私钥。假设伪造的私钥为,则有 问题转换为：寻找模均为的基向量, 的线性组合，使结果模长为。

也即：在二维基向量 组成的格中，找到最短非零向量。

高斯算法

高斯给出了寻找二维格最短向量的算法：

Algorithm 1.2.1: Gaussian Lattice Reduction

Data: two dimensional lattice with basis vectors

Result: shortest nonzero vector in

Loop

  • If
  • Compute
  • If , Return
  • Replace with

Continue Loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#--------高斯规约--------
def mo(vector):
    return int(gp.iroot(vector[0]**2+vector[1]**2,2)[0])



def dot(v1,v2):
    return v1[0]*v2[0]+v1[1]*v2[1]

def Gaussian_reduction(v1,v2):
    while True: 
        if mo(v2)<mo(v1):
            v1,v2=v2,v1 
        m=dot(v1,v2)//dot(v1,v1) 
        if m == 0:
            return v1,v2 
            break 
        v2=[v2[0]-m*v1[0],v2[1]-m*v1[1]] 

#--------高斯规约--------

7.2 Knapsack Cryptosystem

子集和问题

给定一个集合，共包含n个权重值记为，给出期望和，要求找到,其中，使得如下等式成立： 对于超递增背包问题（每个权重值大于前面所有权重值相加的和），可以在线性时间内恢复出。

Algorithm 2.1.1: Solving the Superincreasing Sequence Knapsack.

Data: Superincreasing Subset , sum

Result: solution

Loop i from down to 1

  • If , set , subtract from
  • Else set

End Loop

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
import random 

def gen_pack(bound):
    a = [0] * bound 
    a[0] = random.randint(0,10)
    c = 0
    for i in range(1,bound):
        c = c+a[i-1]+random.randint(10,20)
        a[i] = c 
    return a 

def gen_m(bound):
    return [1-random.randint(0,1) for _ in range(bound) ]

def enc(pack,m):
    c = 0
    for i in range(len(pack)):
        c += pack[i]*m[i] 
    return c 

def attack(pack,c):
    c_=c
    m=[0]*len(pack)
    for i in range(len(pack)-1,-1,-1):
        if pack[i] > c:
            m[i] = 0 
        else:
            m[i] = 1 
            c -= pack[i] 
    print(enc(pack,m) == c_) 
    return m 


if __name__ == '__main__':
    b=8 
    pack,m = gen_pack(b),gen_m(b) 
    
    c = enc(pack,m)
    m_=attack(pack,c)
    print(m_ == m)

Merkle-Hellman背包加密方案

Algorithm 2.2.1: Key Creation

Data:

Result: public key

  • Choose superincreasing
  • Choose and with and
  • Compute for
  • Publish public key , keep private

Algorithm 2.2.2: Encryption

Data: plaintext , public key

Result: ciphertext

  • Compute
  • Return S

Algorithm 2.2.3: Decryption

Data: ciphertext , secret key

: plaintext

  • Compute
  • Solve the subset-sum problem using the superincreasing sequence
  • Return satifies 
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
import random 
from Crypto.Util.number import * 
import gmpy2 as gp 

def gen(bound):
    r = [0] * bound 
    r[0] = random.randint(0,10)
    c = 0
    for i in range(1,bound):
        c = c+r[i-1]+random.randint(10,20)
        r[i] = c 
    b = getPrime(2*(len(bin(c))-2))
    a=random.randint(1,b)
    m = [0]*bound 
    for i in range(bound):
        m[i] = a*r[i]%b 
    return m,r,a,b 
    
def enc(bound,m,b):
    x = [1-random.randint(0,1) for _ in range(bound) ] 
    s = 0 
    for i in range(bound):
        s += x[i]*m[i]%b 
    return x,s 

def attack(pack,c):
    c_=c
    m=[0]*len(pack)
    for i in range(len(pack)-1,-1,-1):
        if pack[i] > c:
            m[i] = 0 
        else:
            m[i] = 1 
            c -= pack[i] 
   
    return m 

def dec(s,r,a,b):
    s_ = gp.invert(a,b)*s%b 
    x = attack(r,s_)
    return x 

if __name__ == '__main__': 
    bound = 8 
    m,r,a,b = gen(bound)
    x,s = enc(bound,m,b)
    print('x=',x)
    x_=dec(s,r,a,b)
    print('x_=',x_)

攻击

已知条件：公钥（常规递增数列）以及密文（子集和），对于存在的明文，有：。从而有： 将上式记作。易得规范正交，且很小，因此问题可转化为：

在维基向量 组成的格中，找到最短非零向量。

LLL算法

在 lattice 里面找短向量的算法，称为 lattice reduction（格基规约）算法。著名的 LLL 即是一个格基规约算法。

可通过sage中自带的LLL算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
x= matrix([[1, 1, 0, 1, 1, 0, 0, 1]])
s= 29195093
m= [1598667, 9592002, 8512672, 5366297, 2270881, 2708906, 4195908, 10367246]
mat = matrix.zero(9)

for i in range(len(m)):
    mat[i,i] = 1 
    mat[i,-1] = m[i] 
mat[-1,-1] = -s
res = mat.LLL()
print(res[0])

# (1, 1, 0, 1, 1, 0, 0, 1, 0)

7.3 The NTRU Public Key Cryptosystem

与7.1的主要区别是：从整数模运算转换到了多项式模运算。

Definition:

多项式，含有个系数为1，个系数为-1，其余系数为0。

  1. center-lift(我也不知道咋个翻译Orz，就叫中心移位吧)

对多项式进行的中心移位，即计算 ，其中 且系数范围在内。

算法

Algorithm 3.1.1: Public parameter creation

Data:

Result: public key

  • Choose public parameters with and prime, , and
  • Choose private that is invertible in and
  • Choose private
  • Compute
  • Compute
  • Publish the public key

Algorithm 3.1.2: Encryption

Data: plaintext , public key ,public parameters

Result: ciphertext

  • Choose plaintext
  • Choose a random
  • Compute
  • Return

Algorithm 3.1.3: Decryption

Data: ciphertext , private key

Result: plaintext

  • Compute
  • Compute
  • Return 
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
def T(d1, d2):
    assert N >= d1+d2
    s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2)
    shuffle(s)
    return R(s)

def invertModPrime(f, p):
    Rp = R.change_ring(Integers(p)).quotient(x^N-1)
    return R(lift(1 / Rp(f)))

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

def liftMod(f, q):
    g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
    return R(g)

def polyMod(f, q):
    g = [f[i]%q for i in range(N)]
    return R(g)

def invertModPow2(f, q):
    assert q.is_power_of(2)
    g = invertModPrime(f,2)
    while True:
        r = liftMod(convolution(g,f),q)
        if r == 1: return g
        g = liftMod(convolution(g,2 - r),q)

def genMessage():
    result = list(randrange(p) - 1 for j in range(N))
    return R(result)

def genKey():
  while True:
    try:
      f = T(d+1, d)
      g = T(d, d)
      Fp = polyMod(invertModPrime(f, p), p)
      Fq = polyMod(invertModPrime(f, q), q)
      break
    except:
      continue
  h = polyMod(convolution(Fq, g), q)
  return h, (f, g)

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

攻击

对多项式（公钥），构造矩阵 其中为系数的全排列。

利用LLL对上述矩阵进行规约，即可得到的系数。