Contents

ntru密码算法.md

Contents

[toc]

timing attack

时序攻击属于侧信道攻击/旁路攻击

比如加解密的速度/加解密时芯片引脚的电压/密文传输的流量和途径等进行攻击的方式,一个词形容就是“旁敲侧击”。

某个函数负责比较用户输入的密码和存放在系统内密码是否相同,如果该函数是从第一位开始比较,发现不同就立即返回,那么通过计算返回的速度就知道了大概是哪一位开始不同的

center-lifts ?

ntru密码算法

选取 n p q d

  • n = 109
  • q = 2048
  • p = 3

q > (6d+1)p

为公开参数

q 最好为2的幂,不能为3的倍数

取多项式 f g

prikey

  • f
  • fq*f = 1 mod q
  • g

pubkey $$ h \equiv pg*f_{q};mod;q $$

enc

取随机数 r,msg多项式化为m

c = rh+m mod q

dec

a = f*c= f (rh +m )=fprh + fm = f *r *pg fq mod q

a = rpg + m mod q

m = a mod p

攻击实例

This attack breaks NTRU with n = 7, d = 5, q = 256.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


def convolution(f, g):
    return (f * g) % (x ^ n-1)
Zx.<x> = ZZ[]
n = 7
d = 5
q = 256

h=-82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5

h3 = ((171)*h) % q
# lift(1/Integers(q)(p)) * h
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]
print(M)
print(M.LLL()[0])