Lattice Encryption (NTRU - Nth degree TRUncated polynomial ring)Lattice-based cryptography uses asymmetric cryptographic primitives based on lattices. It has been known about for several decades, it is now being investigated because it its quantum robustness, whereas many of the existing public key methods such as RSA and Diffie-Hellman cryptosystems can be broken with quantum computers. This page uses the NTRU open source public-key cryptosystem. NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. NTRU was the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve). With Lattice encryption, Bob and Alice agree to share N, p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. Alice receives this, and she generates a random polynomial, and encrypts some data for Bob. Bob then decrypts the message with his private key. We generate the public and private key from N, p and q: |
Examples
- N=7, p=3, q=41. Try [Ref]
- Moderate Security n=167, p=3, q=128. Try [Ref]
- Standard Security n=251, p=3, q=128. Try [Ref]
- Standard Security n=347, p=3, q=128. Try [Ref]
- Highest Security n=503, p=3, q=128. Try [Ref]
Code
Some sample code is:
import sys from ntru import * N=7 p=29 q=491531 if (len(sys.argv)>1): N=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) if (len(sys.argv)>3): q=int(sys.argv[3]) print "==== Bob generates public key =====" Bob=Ntru(N,p,q) print "Bob picks two polynomials (g and f):" f=[1,1,-1,0,-1,1] g=[-1,0,1,1,0,0,-1] d=2 print "f(x)= ",f print "g(x)= ",g print "d = ",d Bob.genPublicKey(f,g,2) pub_key=Bob.getPublicKey() print "Bob's Public Key: ",pub_key print "-------------------------------------------------" print "\n==== Alice generates public key =====" Alice=Ntru(N,p,q) Alice.setPublicKey(pub_key) msg=[1,0,1,0,1,1,1] print "Alice's Message : ",msg ranPol=[-1,-1,1,1] print "Alice's Random Polynomial : ",ranPol encrypt_msg=Alice.encrypt(msg,ranPol) print "Encrypted Message : ", encrypt_msg print "-------------------------------------------------" print "\n==== Bob decrypts =====" print "Decrypted Message : ", Bob.decrypt(encrypt_msg)