我正在寻找一种算法(或代码)来帮助我计算逆多项式,我需要它来实现 NTRUEncrypt。一个容易理解的算法是我喜欢的,有伪代码可以做到这一点,但它们令人困惑且难以实现,而且我无法仅从伪代码中真正理解该过程。
用于计算关于 ring of truncated polynomials 的多项式的逆的任何算法?
最佳答案
我为拥有 NTRU 的 Security Innovation 工作,所以我很高兴看到这种兴趣。
IEEE 标准 1363.1-2008 指定了如何使用最新的参数集实现 NTRUEncrypt。它给出了以下规范来反转多项式:
部门:
输入是 a 和 b,两个多项式,其中 b 的次数为 N-1,b_N 是 b 的首项系数。输出为 q 和 r,满足 a = q*b + r 和 deg(r) < deg(b)。 r_d表示r的d次系数,即r的首项系数。
a) Set r := a and q := 0
b) Set u := (b_N)^–1 mod p
c) While deg r >= N do
1) Set d := deg r(X)
2) Set v := u × r_d × X^(d–N)
3) Set r := r – v × b
4) Set q := q + v
d) Return q, r
这里,r_d是r的d次系数。
扩展欧几里德算法:
a) If b = 0 then return (1, 0, a)
b) Set u := 1
c) Set d := a
d) Set v1 := 0
e) Set v3 := b
f) While v3 ≠ 0 do
1) Use the division algorithm (6.3.3.1) to write d = v3 × q + t3 with deg t3 < deg v3
2) Set t1 := u – q × v1
3) Set u := v1
4) Set d := v3
5) Set v1 := t1
6) Set v3 := t3
g) Set v := (d – a × u)/b [This division is exact, i.e., the remainder is 0]
h) Return (u, v, d)
Z_p 的逆,p 是一个素数:
a) Run the Extended Euclidean Algorithm with input a and (X^N – 1). Let (u, v, d) be the output, such that a × u + (X^N – 1) × v = d = GCD(a, (X^N – 1)).
b) If deg d = 0, return b = d^–1 (mod p) × u
c) Else return FALSE
Z_p^e/(M(X) 中的逆,p 是素数,M(X) 是合适的多项式,例如 X^N-1
a) Use the Inversion Algorithmto compute a polynomial b(X) ε R[X] that gives an inverse of a(X) in (R/pR)[X]/(M(X)). Return FALSE if the inverse does not exist. [The Inversion Algorithm may be applied here because R/pR is a field, and so (R/pR)[X] is a Euclidean ring.]
b) Set n = p
c) While n <= e do
1) b(X) = p × b(X) – a(X) × b(X)^2 (mod M(X)), with coefficients computed modulo p^n
2) Set n = p × n
d) Return b(X) mod M(X) with coefficients computed modulo p^e.
如果您正在全面实现 NTRU,您应该看看是否可以让您的机构购买 1363.1,因为原始 NTRU 加密对于主动攻击者来说并不安全,而 1363.1 描述了消息处理技术来解决这个问题。
(更新 2013-04-18:感谢 Sonel Sharam 发现了之前版本中的一些错误)
关于计算多项式倒数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2421409/