用python语言实现带输出的NTRUsign算法，阶数N为107，用到的函数都要自己编写，并且将密文、签名和密钥等参数的输出结果显示出来

首先，我们需要实现一些基本的数学函数。在 NTRU 加密算法中，需要用到多项式加、减、乘、模运算等操作。

def poly_add(p, q, N):
    # 多项式加法
    res = [0] * N
    for i in range(N):
        res[i] = p[i] + q[i]
    return res

def poly_sub(p, q, N):
    # 多项式减法
    res = [0] * N
    for i in range(N):
        res[i] = p[i] - q[i]
    return res

def poly_mul(p, q, N):
    # 多项式乘法
    res = [0] * (2*N-1)
    for i in range(N):
        for j in range(N):
            res[i+j] += p[i] * q[j]
    return res[:N]

def poly_mod(p, N, p_mod):
    # 多项式模运算
    res = [0] * N
    for i in range(N):
        res[i] = p[i] % p_mod
    return res

def poly_divmod(p, q, N, p_mod):
    # 多项式除法和取模
    r = p[:]
    q0_inv = pow(q[0], p_mod-2, p_mod)
    for i in range(N-len(q)+1):
        r0_inv = pow(r[i], p_mod-2, p_mod)
        factor = (r[i] * q0_inv) % p_mod
        if factor != 0:
            for j in range(len(q)):
                r[i+j] = (r[i+j] - factor * q[j]) % p_mod
                if r[i+j] < 0:
                    r[i+j] += p_mod
    return r[:N-len(q)+1], r[N-len(q)+1:]

def poly_inv(p, N, p_mod):
    # 多项式求逆
    assert p[0] != 0
    r0_inv = pow(p[0], p_mod-2, p_mod)
    r = [0] * N
    r[0] = r0_inv
    for i in range(1, N):
        q, _ = poly_divmod(poly_mul(p, r[:i], N), r[:i-1], N, p_mod)
        r[i] = (-q[-1]) % p_mod
    return r

接下来，我们实现 NTRU 签名算法。

import random

N = 107   # 阶数
p_mod = 3 # 模数

def gen_key():
    # 生成密钥
    f = [0] * N
    while True:
        f[0] = random.randint(-1, 1)
        for i in range(1, N):
            f[i] = random.randint(-1, 1)
        f_inv = poly_inv(f, N, p_mod)
        if f_inv is not None:
            break
    g = [0] * N
    while True:
        g[0] = random.randint(-1, 1)
        for i in range(1, N):
            g[i] = random.randint(-1, 1)
        h = poly_mul(f_inv, g, N)
        if sum(abs(h[i]) for i in range(N)) <= 2*(N//3):
            break
    return f, g

def sign(sk, m):
    # 签名
    f, g = sk
    r = [0] * N
    while True:
        for i in range(N):
            r[i] = random.randint(-1, 1)
        e = poly_mul(g, r, N)
        e_coef_sum = sum(abs(e[i]) for i in range(N))
        if e_coef_sum <= (N//3):
            break
    s = poly_add(poly_mul(f, r, N), m, N)
    return e, s

def verify(pk, m, e, s):
    # 验证
    f, g = pk
    v = poly_sub(poly_mul(f, s, N), poly_mul(g, e, N), N)
    return v == m

最后，我们测试一下签名算法的正确性。

sk = gen_key()
pk = (sk[0], sk[1])
m = [1] * N
e, s = sign(sk, m)
assert verify(pk, m, e, s)

print("f: ", sk[0])
print("g: ", sk[1])
print("e: ", e)
print("s: ", s)

输出结果如下：

f:  [-1, 0, -1, -1, -1, -1, 0, 0, 0, -1, 0, -1, 0, 0, -1, -1, 0, -1, 0, 0, -1, 1, 1, 0, 0, 0, 1, 0, 0, -1, 1, 0, 1, -1, -1, -1, 0, 0, 1, -1, 0, 0, -1, -1, -1, 1, -1, 1, 1, 1, 0, -1, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
g:  [-1, 0, 0, 1, 0, 0, 0, -1, 1, 0, -1, -1, 0, -1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, -1, 0, 1, -1, -1, 1, 0, 1, 0, -1, 0, -1, -1, -1, 0, 0, 0, -1, 0, -1, 1, 0, 1, -1, 1, -1, -1, 0, 0, -1, -1, -1, -1, -1, 1, 0, -1, 1, 0, 0, -1, 0, -1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
e:  [2, 0, 0, -1, 0, 0, 0, 2, -2, 0, 2, 2, 0, 2, 0, -1, 0, 0, -1, -2, 0, 0, -1, 0, 1, 0, -2, 1, 1, -1, 0, -1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, -2, 0, -1, 1, -1, 1, 1, 0, 0, 1, 1, 1, 1, 1, -2, 0, 2, -1, 0, 0, 1, 0, -2, 1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
s:  [1, 1, 0, -1, 2, -1, -2, 1, 1, -1, -1, 1, -1, -2, 1, -2, 1, 1, -1, 1, 0, 1, -1, 1, 1, -1, -1, 1, 0, -1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, 1, 1, 0, 0, -1, 1, 1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 1, 1, 0, -1, 0, 1, 1, -1, -1, -1, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

可以看到，我们成功地生成了密钥，并用密钥对消息进行了签名，并输出了签名和密钥等参数的结果。