c++ - NTRUEncrypt：无法正确找到使用开源标准算法中描述的两个多项式的 GCD，无法定义是否存在 poly 的逆

问题描述

我已经实现了用于查找多项式逆的算法，如板载安全资源中所述，但这些算法意味着我想要反转的多边形的 GCD 并且 X^N - 1 为 1。

对于正确的 NTRU 实现，我需要随机生成小多项式并定义它们的逆是否存在，目前我没有这样的功能。为了让它工作，我尝试按照NTRU 开源项目文档中的描述实现欧几里得算法。但我发现有些事情非常不一致，这让我很恼火。除法和欧几里得算法可以在命名文档的第 19 页找到。

因此，在除法算法中，输入是多项式 a 和 b。据说多项式 b 必须是 N-1 次。

除法算法的伪代码（取自此答案）：

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

为了找到两个多项式的 GCD，必须调用欧几里得算法，输入为 a（某个多项式）和 X^N-1。然后将这些输入传递给除法算法。

问题是：如果明确规定第二个参数应该是度数为 N-1 的 poly，如何将 X^N-1 传递给除法算法？

忽略这个问题，还有一些我不明白的地方：

除法算法中的N是什么？是来自 NTRU 参数的 N 还是多项式 b 的次数？
无论哪种方式，条件 c) 怎么可能是真的？NTRU 使用次数小于 N 的多项式进行运算

对于更大的上下文，这是我对欧几里得和除法算法的 C++ 实现。给定输入 a = {-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}, b = {-1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1}, p = 3 and N = 11 在除法算法中进入无限循环

using tPoly = std::deque<int>;

std::pair<tPoly, tPoly> divisionAlg(tPoly a, tPoly b, int p, int N)
{
    tPoly r = a;
    tPoly q{0};
    int b_degree = degree(b);
    int u = Helper::getInverseNumber(b[b_degree], p);

    while (degree(r) >= N)
    {
        int d = degree(r);
        tPoly v = genXDegreePoly(d-N); // X^(d-N)
        v[d-N] = u*r[d]; // coefficient of v
        r -= multiply(v, b, N);
        q += v;
    }
    return {q, r};
}

struct sEucl
{
    sEucl(int U=0, int V=0, int D=0)
        : u{U}
        , v{V}
        , d{D}
    {}

    tPoly u;
    tPoly v;
    tPoly d;
};

sEucl euclidean(tPoly a, tPoly b, int p, int N)
{
    sEucl res;
    if ((degree(b) == 0) && (b[0] == 0))
    {
        res = sEucl(1, 0);
        res.d = a;
        Helper::printPoly(res.d);
        return res;
    }

    tPoly u{1};
    tPoly d = a;
    tPoly v1{0};
    tPoly v3 = b;

    while ((0 != degree(v3)) && (0 != v3[0]))
    {
        std::pair<tPoly, tPoly> division = divisionAlg(d, v3, p, N);
        tPoly q = division.first;
        tPoly t3 = division.second;
        tPoly t1 = u;
        t1 -= PolyMath::multiply(q, v1, N);
        u = v1;
        d = v3;
        v1 = t1;
        v3 = t3;
    }
    d -= multiply(a, u, N);
    tPoly v = divide(d, b).first;

    res.u = u;
    res.v = v;
    res.d = d;
    return res;
}

此外，此清单中使用的多项式运算可以在github 页面找到

标签： c++cryptographypolynomialsntruencrypt

c++ - NTRUEncrypt：无法正确找到使用开源标准算法中描述的两个多项式的 GCD，无法定义是否存在 poly 的逆

问题描述

解决方案

推荐阅读