用python语言实现带输出的NTRUsign算法,阶数N为107,用到的函数都要自己编写
时间: 2024-01-22 07:20:57 浏览: 60
NTRUSign算法是基于NTRU加密算法的一种数字签名算法,其具体实现可以分为以下几个步骤:
1. 生成公私钥对
2. 对消息进行哈希操作
3. 使用私钥对哈希值进行加密得到签名
4. 使用公钥对签名进行解密得到哈希值
5. 对比解密得到的哈希值和原哈希值是否相等,若相等则验证成功
具体代码实现如下:
```python
import random
import hashlib
N = 107 # 阶数
q = 2**8 # 模数
p = 3 # 多项式系数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def poly_add(a, b):
c = [0] * N
for i in range(N):
c[i] = (a[i] + b[i]) % q
return c
def poly_sub(a, b):
c = [0] * N
for i in range(N):
c[i] = (a[i] - b[i]) % q
return c
def poly_mul(a, b):
c = [0] * N
for i in range(N):
for j in range(N):
c[(i+j) % N] += a[i] * b[j]
for i in range(N):
c[i] = (c[i] % q + q) % q
return c
def poly_mod(a):
c = [0] * N
for i in range(N):
c[i] = a[i] % p
return c
def poly_inv(a):
b = [0] * N
c = [0] * N
b[0] = a[0]
c[1] = 1
for i in range(1, N):
for j in range(i):
c[N-i+j] -= b[N-j-1] * c[N-i+j-1]
b[i] = -c[N-i]
return poly_mod(c)
def gen_keys():
f = [0] * N
while True:
while True:
for i in range(N):
f[i] = random.randint(-(q-1), q-1)
if f[0] != 0:
break
G = poly_inv(f)
if gcd(G[0], p) == 1:
break
return f, G
def hash_msg(msg):
h = hashlib.sha256()
h.update(msg.encode('utf-8'))
return int.from_bytes(h.digest(), 'big') % q
def encrypt(f, msg_hash):
r = [0] * N
e = [0] * N
while True:
for i in range(N):
r[i] = random.randint(-(q-1), q-1)
if gcd(poly_mul(f, r)[0], p) == 1:
break
e = poly_mul(f, r)
for i in range(N):
e[i] = (e[i] - msg_hash) % q
return e
def decrypt(G, e):
r = poly_mul(G, e)
for i in range(N):
r[i] = (r[i] % q + q) % q
return r
def verify(f, msg_hash, r):
e = poly_mul(f, r)
for i in range(N):
e[i] = (e[i] - msg_hash) % q
return sum([abs(e[i]) for i in range(N)]) <= q // 2
# 测试样例
msg = "Hello world"
msg_hash = hash_msg(msg)
f, G = gen_keys()
e = encrypt(f, msg_hash)
r = decrypt(G, e)
print("Verify:", verify(f, msg_hash, r))
```
注:由于NTRU算法的特殊性质,这里的多项式系数p不能为2,否则会出现无解的情况。
阅读全文