NTRU加密算法

一，介绍

NTRU是1998年由 Brown大学三位数学家 Silverman、Hoffstein和 Pipher提出的公钥密码算法,将其命名为NTRU。

NTRU密码系统是第一个基于多项式环结构设计出的密码系统，也就是所谓的代数结构格。

RSA,ECC和ElGamal等公钥密码系统的安全性是基于大整数分解难题或离散对数问题，这些数学问题很容易被量子计算机攻破。因此在可预见的未来它们有被破解的风险。而NTRU在原理上，可以被认为是能够抵抗量子计算机攻击的，这是NTRU密码系统的优势之一。因为NTRU的安全性是基于SVP问题，而目前还没有算法可以在多项式时间内解决这个问题。

二，加密过程

  1. 选择多项式 ，NTRU是在 多项式环中进行的。

意味着在环中，多项式的系数都为整数，且多项式进行模f(x)的运算，即多项式都表示为次数小于n的多项式，更高的项则会被模掉。 选择素数 ，将多项式的系数限制在模 的整数范围。

[NSSRound#11 Basi]NTR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import *
 
def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

题解如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
z=int(binz,2)
p=int(binp,2)
c=int(binc,2)
def decrypto(z,p,c):
    M=Matrix(ZZ,[[1,z],
                 [0,p]])
    x,y=M.LLL()[0]
    print(x,y)
    x=abs(x)
    y=abs(y)
    m=(c*x)%p*int(inverse(x,y))%y
    return m

m=decrypto(z,p,c)
print(long_to_bytes(m))