NTRU attack

NTRU 常见攻击

本文总结了几种NTRU攻击，包括经典格攻击、多次加密同一明文攻击。

NTRU加密流程

有些时候 $h=p*F_q*g$，$e \equiv r*h+m \;(mod\;q)$ ，如果这样做，$p$ 理论上可以不公开。

条件 $q>(6d+1)p$ 需要的原因在于 $p*g*r+f*m\;(mod\; q)$ 的系数要小于 $q$ ，以便进行后一步解密。分析如下：

$p*g*r$ 的系数最大为 $p*2d$ ，而 $f*m$ 系数的最大值为 $(2d+1)*\frac{1}{2}p$ ，从而两者相加系数不超过 $(3d+1)*\frac{1}{2}p$ ， $q>(6d+1)p$ 显然是更高的界。

这也说明，只要 $f, g$ 满足 $h=F_q*g$ 并且 $f, g$ 要足够小，即可作为私钥解密。

格攻击得到私钥

由于 $f(x)*h(x)\equiv g(x)\;(mod\; q)$ ，所以存在多项式 $u(x)$ 使得 $f(x)*h(x)=g(x)+qu(x)$ 。可以构造格子满足：$(f,-u)M^{NTRU}_h = (f, g)$ 。

$M^{NTRU}_h=\left(\begin{matrix} 1&h\\ 0&q \end{matrix} \right)$

重复明文攻击

根据 $e \equiv r*h+m \;(mod\;q)$ ，如果我们让公钥重复加密同一明文，那我们则会得到很多组类似 $e_i-e_0 \equiv h(r_i-r_0)\; (mod\; q)$ 的方程。由于 $r \in \mathcal{I}(d, d) ,\quad d <<N$ ，所以在 $(r_i-r_0)$ 中，系数重复出现最多的可能就是 $r_0$ 的系数，从而得到 $r_0$ 。

而问题在与 $h$ 在商环 $R$ 中不可逆，处理这个的方法有几种，较为方便的就是将 $h,R$ 同时除去它们的公因子，之后 $h$ 就可逆了。

代码

1.NTRU加密

from random import shuffle, getrandbits
from Crypto.Util.number import *
Zx = PolynomialRing(ZZ, 'x')
x = Zx.gen()


def convolution(f, g, R):
    return (f * g) % R


def balancedmod(f, q, R):
    g = list(map(lambda x: ((x + q//2) % q) - q//2, f.list()))
    return Zx(g) % R


def random_poly(n, d1, d2):
    assert d1 + d2 <= n
    result = d1 * [1] + d2 * [-1] + (n - d1 - d2) * [0]
    shuffle(result)
    return Zx(result)


def invert_poly_mod_prime(f, R, p):
    T = Zx.change_ring(Integers(p)).quotient(R)
    return Zx(lift(1 / T(f)))


def invert_poly_mod_powerof2(f, R, q):  #  f 在模 2^16 下的逆
    g = invert_poly_mod_prime(f, R, 2)
    e = log(q, 2)
    for i in range(1, e):
        g = ((2 * g - f * g ** 2) % R) % q
    return g


class NTRUCipher:
    def __init__(self, N, p, q, d):
        self.N = N
        self.p = p
        self.q = q
        self.d = d
        self.R = x ** N - 1
        # key generation
        self.g = random_poly(self.N, d, d)
        # self.g = x^119 - x^115 - x^112 + x^111 + x^110 - x^106 + x^103 - x^101 + x^100 - x^99 + x^98 - x^97 - x^96 + x^95 - x^90 + x^89 - x^88 - x^86 + x^85 + x^83 + x^82 + x^75 - x^74 + x^69 - x^64 + x^62 + x^58 + x^57 + x^54 - x^51 + x^50 - x^45 - x^42 + x^41 - x^40 - x^38 + x^37 - x^36 - x^35 - x^34 - x^32 - x^31 + x^30 - x^29 - x^27 + x^26 + x^25 + x^22 + x^20 - x^18 + x^16 + x^15 - x^14 - x^13 + x^12 - x^8 + x^7 + x^6 - x^4 - x
        while True:
            try:
                self.f = random_poly(self.N, d + 1, d)
                # self.f = x^119 + x^117 + x^114 - x^113 - x^112 - x^110 - x^109 + x^108 + x^107 - x^106 - x^103 - x^102 + x^100 + x^98 + x^97 + x^96 - x^93 + x^92 + x^91 - x^87 + x^85 - x^81 + x^80 - x^75 - x^73 + x^72 - x^71 + x^68 - x^67 - x^66 - x^62 - x^60 - x^57 + x^52 - x^51 + x^50 - x^48 + x^45 - x^43 - x^42 - x^38 + x^37 - x^34 + x^31 + x^30 - x^26 + x^24 + x^22 - x^21 + x^20 - x^17 + x^16 - x^14 - x^13 + x^12 + x^10 + x^8 + x^7 + x^6 - x^5 + x
                self.fp = invert_poly_mod_prime(self.f, self.R, self.p)
                self.fq = invert_poly_mod_powerof2(self.f, self.R, self.q)
                break
            except:
                pass

        self.h = balancedmod(self.p * convolution(self.fq, self.g, self.R), self.q, self.R)
    def getPubKey(self):
        return self.h
    def encrypt(self, m):
        r = random_poly(self.N, self.d, self.d)
        return balancedmod(convolution(self.h, r, self.R) + m, self.q, self.R)

    def decrypt(self, c):
        a = balancedmod(convolution(c, self.f, self.R), self.q, self.R)
        return balancedmod(convolution(a, self.fp, self.R), self.p, self.R)

    def encode(self, val):
        poly = 0
        for i in range(self.N):
            poly += ((val % self.p) - self.p // 2) * (x ** i)
            val //= self.p
        return poly

    def decode(self, poly):
        result = 0
        ll = poly.list()
        for idx, val in enumerate(ll):
            result += (val + self.p // 2) * (self.p ** idx)
        return result

    def poly_from_list(self, l: list):
        return Zx(l)


if __name__ == '__main__':
    N = 160
    d = 30
    p = 3
    q = 65536

    flag = b'cnss{}'
    cipher = NTRUCipher(N, p, q, d)
    # cipher.f = x^31 - x^29 + x^28 - x^27 + x^26 + x^25 + x^24 + x^23 + x^22 - x^21 - x^19 - x^18 + x^17 - x^15 - x^14 - x^11 - x^9 + x^8 - x^6 + x^2 + x
    # cipher.g = -x^31 - x^30 - x^29 - x^28 + x^27 + x^25 - x^23 + x^22 + x^21 - x^19 + x^18 + x^15 - x^13 + x^11 - x^10 - x^9 + x^6 - x^5 + x^2 + x
    
    # print("[Pk]---------")
    h = cipher.getPubKey()
    msg = bytes_to_long(flag)
    encode_msg = cipher.encode(msg)
    c = cipher.encrypt(encode_msg)
    # print(f'c={c}')
    mm = cipher.decrypt(c)
    decode_msg = cipher.decode(mm)
    assert decode_msg == msg

2.格攻击

Zx = PolynomialRing(ZZ, 'x')
x = Zx.gen()

N = 160
d = 40
p = 3
q = 65536

R = x ** N - 1
h = -31082*x^159 - 14617*x^158 + 19918*x^157 - 8036*x^156 + 10147*x^155 + 5021*x^154 - 17815*x^153 + 10103*x^152 + 16807*x^151 + 24567*x^150 - 32433*x^149 - 703*x^148 + 28524*x^147 - 13881*x^146 + 11259*x^145 - 29004*x^144 - 14694*x^143 + 26176*x^142 + 6530*x^141 - 4860*x^140 - 28793*x^139 + 24449*x^138 + 4066*x^137 - 14562*x^136 - 27298*x^135 + 28889*x^134 + 21079*x^133 + 21872*x^132 + 25410*x^131 + 3974*x^130 + 24782*x^129 - 15777*x^128 - 16591*x^127 - 30704*x^126 + 4323*x^125 - 18939*x^124 - 15416*x^123 - 18393*x^122 - 23652*x^121 + 15108*x^120 - 27891*x^119 + 2678*x^118 + 10772*x^117 - 427*x^116 - 26667*x^115 - 25516*x^114 - 6688*x^113 + 28600*x^112 - 18337*x^111 - 12960*x^110 - 21229*x^109 - 27071*x^108 - 1122*x^107 - 30649*x^106 - 25769*x^105 - 26115*x^104 - 5834*x^103 + 14995*x^102 + 19029*x^101 - 22440*x^100 + 1664*x^99 + 9560*x^98 - 25381*x^97 + 20032*x^96 - 18057*x^95 - 17361*x^94 + 12687*x^93 + 1236*x^92 - 9883*x^91 + 29129*x^90 + 3807*x^89 + 12829*x^88 - 20639*x^87 - 11764*x^86 - 25030*x^85 + 15743*x^84 - 3589*x^83 - 1436*x^82 + 21181*x^81 + 13943*x^80 + 31511*x^79 - 19732*x^78 + 6337*x^77 + 22965*x^76 - 23698*x^75 + 10601*x^74 + 8477*x^73 - 31571*x^72 - 27846*x^71 + 28105*x^70 - 29146*x^69 - 29142*x^68 - 32182*x^67 - 11087*x^66 + 6757*x^65 + 16893*x^64 - 30174*x^63 + 1756*x^62 - 14660*x^61 + 24670*x^60 + 9178*x^59 + 25364*x^58 - 15133*x^57 - 6543*x^56 + 2235*x^55 + 22861*x^54 + 26487*x^53 + 1703*x^52 + 15899*x^51 + 8163*x^50 - 16708*x^49 - 4605*x^48 - 27949*x^47 - 4871*x^46 + 1192*x^45 - 415*x^44 + 20678*x^43 + 21537*x^42 + 17271*x^41 + 8947*x^40 + 31942*x^39 - 25564*x^38 - 3313*x^37 - 28654*x^36 - 24128*x^35 + 28209*x^34 - 24904*x^33 + 764*x^32 - 14770*x^31 + 27748*x^30 + 20821*x^29 - 16078*x^28 - 29480*x^27 + 4958*x^26 + 7593*x^25 + 10794*x^24 + 31009*x^23 - 12029*x^22 + 9734*x^21 + 21313*x^20 - 28660*x^19 - 21860*x^18 + 23568*x^17 - 29022*x^16 + 24796*x^15 + 3138*x^14 - 3758*x^13 + 12681*x^12 - 11138*x^11 + 22079*x^10 + 10426*x^9 - 25911*x^8 - 10304*x^7 - 19399*x^6 + 21475*x^5 + 6728*x^4 - 22420*x^3 - 11358*x^2 + 2746*x + 2175
c = 827*x^159 - 28788*x^158 + 11676*x^157 - 9492*x^156 - 15856*x^155 - 19059*x^154 + 6551*x^153 + 7457*x^152 + 3018*x^151 - 3351*x^150 - 25905*x^149 + 27240*x^148 + 24667*x^147 + 13367*x^146 + 10679*x^145 + 4797*x^144 + 32097*x^143 + 11718*x^142 + 7061*x^141 - 1948*x^140 - 11412*x^139 - 23573*x^138 + 28496*x^137 + 32132*x^136 + 5327*x^135 + 30416*x^134 + 6158*x^133 - 20550*x^132 + 18201*x^131 + 21081*x^130 + 21076*x^129 - 22003*x^128 + 22761*x^127 - 20067*x^126 - 28503*x^125 + 14044*x^124 + 14657*x^123 - 19561*x^122 + 15105*x^121 - 13874*x^120 + 4391*x^119 + 10027*x^118 - 5434*x^117 + 5853*x^116 - 28767*x^115 - 20771*x^114 - 32534*x^113 - 28131*x^112 - 14639*x^111 + 30551*x^110 - 5851*x^109 + 12912*x^108 + 9832*x^107 - 27307*x^106 + 31912*x^105 + 12445*x^104 - 13595*x^103 + 180*x^102 - 28864*x^101 + 2697*x^100 - 10658*x^99 - 6828*x^98 + 28310*x^97 - 25950*x^96 + 2790*x^95 + 5194*x^94 + 21198*x^93 - 18733*x^92 - 25159*x^91 - 8584*x^90 + 637*x^89 - 30097*x^88 - 27323*x^87 + 19035*x^86 + 16007*x^85 + 3098*x^84 + 30858*x^83 + 2395*x^82 + 26950*x^81 - 23633*x^80 - 18422*x^79 + 20408*x^78 - 25472*x^77 - 12691*x^76 - 9347*x^75 - 24963*x^74 - 30570*x^73 + 16046*x^72 + 21716*x^71 - 20667*x^70 - 5193*x^69 + 7870*x^68 + 3035*x^67 - 10604*x^66 + 1072*x^65 - 13541*x^64 - 24707*x^63 - 30203*x^62 + 192*x^61 - 9920*x^60 - 26149*x^59 - 6387*x^58 - 25086*x^57 + 29876*x^56 - 7267*x^55 - 20927*x^54 - 15841*x^53 - 14910*x^52 - 30501*x^51 + 14929*x^50 - 5987*x^49 + 2002*x^48 - 20599*x^47 - 13489*x^46 - 26459*x^45 + 26335*x^44 + 26597*x^43 - 30213*x^42 + 8866*x^41 + 18173*x^40 - 3975*x^39 - 15388*x^38 - 5311*x^37 - 19972*x^36 - 9169*x^35 - 17439*x^34 - 22100*x^33 - 22956*x^32 - 19639*x^31 + 7753*x^30 - 32440*x^29 + 14194*x^28 + 6990*x^27 + 13291*x^26 + 15908*x^25 + 20108*x^24 + 19429*x^23 + 1290*x^22 + 29204*x^21 + 10700*x^20 + 10343*x^19 - 18267*x^18 - 1314*x^17 + 6111*x^16 + 19243*x^15 - 31644*x^14 - 23278*x^13 - 14388*x^12 + 29190*x^11 + 25308*x^10 + 16840*x^9 - 31782*x^8 - 16088*x^7 - 9940*x^6 + 13891*x^5 + 15244*x^4 + 14168*x^3 - 21735*x^2 - 24052*x + 5890

A = Matrix(ZZ, 2 * N, 2 * N)

hh = balancedmod(inverse_mod(p, q) * h, q, R) 
hh = inverse_mod(p, q) * h % q
H = hh.coefficients(sparse=False)
for i in range(N):
    A[i, i] = 1
    A[i+N, i+N] = q
    for j in range(N):
        A[i, j+N] = H[-i+j]

C = A.LLL()
for row in range(N):
    ff = C[row][:N]
    gg = C[row][N:]
    f = Zx(list(ff))
    g = Zx(list(gg))
    decrypt = NTRUCipher(N, p, q, d)
    decrypt.f = f
    decrypt.g = g
    try:
        decrypt.fp = invert_poly_mod_prime(f, R, p)
        decrypt.fq = invert_poly_mod_powerof2(f, R, q)
        break
    except:
        continue
mm = decrypt.decrypt(c)
decode_msg = decrypt.decode(mm)
long_to_bytes(decode_msg)

3.重复明文攻击

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

def convolution_new(f,g,quo):
    return (f * g) % quo

def invertmodprime_new(f,p,quo):
    T = Zx.change_ring(Integers(p)).quotient(quo)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2_new(f,q,quo):
    #print(f, q, quo)
    assert q.is_power_of(2)
    g = invertmodprime_new(f,2,quo)
    #print("g:", g)
    while True:
        r = balancedmod_new(convolution_new(g,f,quo),q,quo)
        if r == 1: return g
        g = balancedmod_new(convolution_new(g,2 - r,quo),q,quo)

        
def get_delta_r(delta_e, factor, g):
    quo = (x^n-1) // factor
    h_ = h // factor
    delta_e = delta_e // factor
    delta_r = balancedmod_new(convolution_new(invertmodpowerof2_new(h_, 128, quo), delta_e, quo), 128, quo)
    return delta_r
    
def get_r(num, d):
    for k in range(0, num):
        delta_r = []
        for i in range(0, num):
            if i == k:
                continue
            delta_e = eis[i] - eis[k]
            delta_r.append(get_delta_r(delta_e, x - 1, 2))
        r0 = [[] for _ in range(n)]
        for dr in delta_r:
            coefficient = dr.padded_list()
            for j in range(len(coefficient)):
                r0[j].append(coefficient[j])

        for i in range(len(r0)):
            try:
                r0[i] = -max(r0[i], key = r0[i].count)
            except:
                r0[i] = 0

        r_ans = Zx(r0)
        eff = r_ans.coefficients()
        if eff.count(1) == d and eff.count(-1) == d:
            return r_ans, k
    return 0, 0

def decrypt():
    r, k = get_r(num, d)
    msgpoly = balancedmod(eis[k] - convolution(publickey,r), q)
    msg = decode(msgpoly)
    print(l2b(msg))

decrypt()