NTRU in python3

NTRU:

• NTRU – Nth Degree Truncated Polynomial Ring Units (or R = Z[X] / ( X^N-1 ))
• NTRU is the first public-key cryptosystem not based on factorization or discrete logarithmic problems.
• NTRU is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice.
• NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data.
• It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures.
• Unlike other popular public-key cryptosystems, it is resistant to attacks using Shor's algorithm.
• NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL.

Example in Python3:

% python3 --version

Python 3.9.1

% pip3 install --user sympy

% pip3 install --user numpy

% pip3 install --user docopt

% git clone https://github.com/jkrauze/ntru.git

Cloning into 'ntru'...

remote: Enumerating objects: 91, done.

remote: Counting objects: 100% (4/4), done.

remote: Compressing objects: 100% (4/4), done.

remote: Total 91 (delta 0), reused 0 (delta 0), pack-reused 87

Receiving objects: 100% (91/91), 22.42 KiB | 883.00 KiB/s, done.

Resolving deltas: 100% (49/49), done.

% cd ntru

% ./ntru.py -h             

NTRU v0.1

Usage:

  ntru.py [options] enc PUB_KEY_FILE [FILE]

  ntru.py [options] dec PRIV_KEY_FILE [FILE]

  ntru.py [options] gen N P Q PRIV_KEY_FILE PUB_KEY_FILE

  ntru.py (-h | --help)

  ntru.py --version

Options:

  -b, --block        Interpret input/output as

                       block stream.

  -i, --poly-input   Interpret input as polynomial

                       represented by integer array.

  -o, --poly-output  Interpret output as polynomial

                       represented by integer array.

  -h, --help         Show this screen.

  --version          Show version.

  -d, --debug        Debug mode.

  -v, --verbose      Verbose mode.

% ./ntru.py -v gen 167 3 128 myKey.priv myKey.pub

NTRU(N=167,p=3,q=128) initiated

g: Poly(x**164 + x**159 - x**157 + x**154 - x**147 + x**144 + x**139 - x**129 - x**128 + x**111 + x**110 - x**107 + x**100 - x**89 - x**85 + x**73 - x**53 - x**51 - x**41 - x**37 + x**25 + x, x, domain='ZZ')

g coeffs: Counter({1: 11, -1: 11})

f: Poly(-x**166 + x**165 + x**163 - x**162 + x**161 - x**160 + x**159 + x**155 - x**151 - x**150 - x**149 - x**146 - x**145 - x**143 + x**138 - x**136 + x**135 - x**134 - x**133 - x**132 - x**131 + x**130 + x**129 - x**128 - x**126 + x**125 - x**123 + x**122 - x**121 - x**120 + x**119 + x**118 - x**115 + x**112 - x**110 - x**109 - x**108 - x**107 - x**105 - x**104 + x**103 - x**102 - x**101 + x**98 + x**97 - x**96 - x**94 + x**93 + x**92 - x**90 + x**88 + x**87 + x**85 + x**84 + x**83 - x**81 - x**76 + x**75 + x**74 - x**70 - x**68 + x**65 + x**64 + x**63 + x**61 + x**60 + x**59 - x**58 - x**57 + x**56 - x**55 - x**54 + x**53 + x**52 - x**51 + x**50 + x**49 + x**48 + x**46 - x**45 + x**43 + x**42 + x**41 - x**38 - x**37 - x**35 + x**34 + x**33 - x**32 - x**31 + x**30 - x**28 - x**27 + x**25 + x**23 + x**20 + x**19 + x**17 + x**16 + x**14 - x**13 - x**12 - x**11 - x**9 - x**8 + x**7 + x**6 - x**5 + x**3, x, domain='ZZ')

f coeffs: Counter({1: 55, -1: 54})

f_p: Poly(-x**165 - x**164 - x**161 + x**160 + x**158 + x**157 - x**155 - x**154 + x**153 + x**152 - x**151 + x**150 + x**149 - x**148 - x**147 + x**145 - x**143 + x**139 + x**138 + x**137 + x**136 + x**134 - x**133 - x**132 + x**131 - x**130 - x**128 - x**127 - x**126 - x**120 + x**118 + x**115 - x**114 + x**111 - x**110 - x**109 + x**108 + x**107 + x**106 - x**104 - x**103 - x**102 + x**101 + x**98 - x**96 - x**94 + x**93 - x**91 - x**90 - x**89 - x**86 + x**85 - x**83 + x**82 + x**80 + x**79 - x**78 - x**77 - x**74 + x**72 - x**69 + x**68 + x**67 - x**66 - x**65 + x**64 + x**63 + x**62 - x**61 - x**60 + x**59 + x**58 + x**56 + x**55 + x**51 - x**50 - x**49 + x**48 - x**47 - x**46 - x**44 - x**43 + x**42 - x**41 - x**40 + x**39 - x**37 - x**36 - x**34 + x**33 + x**32 + x**31 - x**29 - x**28 - x**27 - x**26 + x**25 + x**24 + x**22 - x**20 - x**19 + x**18 - x**17 - x**16 + x**15 + x**11 + x**9 - x**8 - x**7 + x**5 - x**3 + x**2 + 1, x, modulus=3)

f_q: Poly(-18*x**166 + 55*x**165 - 62*x**164 + 27*x**163 - 16*x**162 + 31*x**161 - 21*x**160 + 3*x**159 - 38*x**158 + 7*x**157 + 27*x**156 - 42*x**155 + 17*x**154 - 37*x**153 + 37*x**152 - 34*x**151 - 14*x**150 - 49*x**149 + 62*x**148 + 2*x**147 + 59*x**146 - 49*x**145 + 8*x**144 + 22*x**143 + 33*x**142 + 5*x**141 + 18*x**140 - 15*x**139 + 13*x**138 - 47*x**137 + 59*x**136 - 36*x**135 + 11*x**134 - 53*x**133 + 4*x**132 + 32*x**131 - 55*x**130 + 51*x**129 - 31*x**128 - 54*x**127 - 42*x**126 - 8*x**125 - 18*x**124 - 24*x**123 - 17*x**122 - 45*x**121 + 16*x**120 + 34*x**119 + 48*x**118 + 3*x**117 - 19*x**116 - 2*x**115 + 37*x**114 + 14*x**113 + 36*x**112 - 37*x**111 - 13*x**110 - 34*x**109 - 51*x**108 + 25*x**107 + 42*x**106 + 21*x**105 + 57*x**104 - 30*x**103 - 19*x**102 - 25*x**101 + 61*x**100 + 17*x**99 + 63*x**98 - 13*x**97 - 25*x**96 - 35*x**95 - 55*x**94 - 15*x**93 + 38*x**92 - 23*x**91 - 52*x**90 - 14*x**89 + 8*x**88 - 14*x**87 - 50*x**86 + 24*x**85 + 49*x**84 + 49*x**83 + 51*x**82 + 50*x**81 - 34*x**80 - 31*x**79 + 22*x**78 - 22*x**77 - 52*x**76 - 12*x**75 + 42*x**74 + 11*x**73 - 57*x**72 - 61*x**71 - 60*x**70 + 58*x**69 - 36*x**68 - 43*x**67 - 5*x**66 - 63*x**65 - 36*x**64 - 18*x**63 - 54*x**62 + 29*x**61 - 35*x**60 - 29*x**59 - 59*x**58 + 57*x**57 + 61*x**56 + 34*x**55 - 42*x**54 - 61*x**53 + 64*x**52 + 59*x**51 + 48*x**50 - 8*x**49 + 40*x**48 - 44*x**47 + 17*x**46 - 48*x**45 + 43*x**44 + 25*x**43 - 51*x**42 - 9*x**41 - 16*x**40 + x**39 + 25*x**38 - 48*x**37 + 3*x**36 + 15*x**35 + 46*x**34 + 60*x**33 - 34*x**32 + 57*x**31 - 14*x**30 - 33*x**29 + 17*x**28 + 27*x**27 - 62*x**26 - 3*x**25 - 35*x**24 - 40*x**23 + 27*x**22 - 23*x**21 + 53*x**20 + 16*x**19 + 3*x**18 - 47*x**17 - 13*x**16 + 48*x**15 - 42*x**14 + 53*x**13 + 37*x**12 + 47*x**11 + 7*x**10 + 38*x**9 - 41*x**8 - 63*x**7 + 49*x**6 - 36*x**5 + 62*x**4 - 29*x**3 - 7*x**2 + 29*x - 4, x, domain='ZZ')

h: Poly(-43*x**166 - 11*x**165 + 10*x**164 + 61*x**163 + 38*x**162 - 37*x**161 - 45*x**160 + 2*x**159 + 49*x**158 + 15*x**157 + 54*x**156 + 51*x**155 - 53*x**154 + 21*x**153 + 4*x**152 + 56*x**151 - 37*x**150 - 10*x**149 - 23*x**148 + 18*x**147 - 24*x**146 + 28*x**145 - 30*x**144 + 15*x**143 - x**142 - 4*x**141 - 31*x**140 + 44*x**139 - 39*x**138 + 14*x**137 + 35*x**136 + 22*x**135 - 52*x**134 - 4*x**133 - 10*x**132 - 20*x**131 - 36*x**130 - 28*x**129 - 47*x**128 - 4*x**127 - 43*x**126 - 56*x**125 - 42*x**124 - 20*x**123 + 11*x**122 - 40*x**121 - 43*x**120 + 39*x**119 + 20*x**118 + 16*x**117 - 46*x**116 - 39*x**115 + 18*x**114 - 36*x**113 + 28*x**112 - 36*x**111 - 17*x**110 - 42*x**109 + 11*x**108 + 36*x**107 + 2*x**105 - 49*x**104 + 59*x**103 - 44*x**102 - 12*x**101 + 20*x**100 + 53*x**99 - 30*x**98 - 18*x**97 - 4*x**96 - 59*x**95 - 26*x**94 + 23*x**93 + 9*x**92 + 59*x**91 + 23*x**90 + 6*x**89 + 57*x**88 - 30*x**87 - 11*x**86 + 12*x**85 + 29*x**84 + 56*x**83 + 12*x**82 - 22*x**81 + 32*x**80 + 46*x**79 + 48*x**78 + 16*x**77 + 38*x**76 + 41*x**75 + 43*x**74 - 58*x**73 - 35*x**72 - 28*x**71 - 58*x**70 - 27*x**69 - 57*x**68 + 21*x**67 - 63*x**65 - 35*x**64 - 13*x**63 + 24*x**62 - 32*x**61 - 28*x**60 + 13*x**59 - 48*x**58 + 24*x**57 + 3*x**56 - 58*x**55 - 51*x**54 + 56*x**53 - 40*x**52 - 48*x**51 + 20*x**50 + 42*x**49 - 22*x**48 + 10*x**47 + 50*x**46 - 41*x**45 - 29*x**44 + 22*x**43 + 47*x**42 + 10*x**41 - 32*x**40 + 15*x**39 + x**38 - 53*x**37 - 46*x**36 + 11*x**35 - 37*x**34 + 64*x**33 + 60*x**32 - 63*x**31 - 62*x**30 - 2*x**29 - 36*x**28 + 46*x**27 + 41*x**26 - 45*x**25 - 13*x**24 - x**23 + 18*x**22 - 61*x**21 + 4*x**20 + 63*x**19 - 7*x**18 - 30*x**17 + 58*x**16 - 42*x**15 - 45*x**14 - 20*x**13 - 41*x**12 - 8*x**11 + 11*x**10 + 19*x**9 + 60*x**8 - 49*x**7 + 51*x**6 + 63*x**5 + 64*x**4 + 35*x**3 - 54*x**2 - 44*x - 22, x, domain='ZZ')

Private key saved to myKey.priv file

Public key saved to myKey.pub file

% echo "hello" | ./ntru.py enc myKey.pub.npz > enc.txt

/Users/devharsh/Downloads/ntru/./ntru.py:55: DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.

Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

  ntru.h_poly = Poly(pub_key['h'].astype(np.int)[::-1], x).set_domain(ZZ)

/Users/devharsh/Downloads/ntru/./ntru.py:157: DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.

Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

  sys.stdout.buffer.write(np.packbits(np.array(output).astype(np.int)).tobytes()

% cat enc.txt 

????Z`u?͙??o?<?{?џX?+???_?P???G?m^??#R%???

??X???o0[X튕H?P?O?,RU??/??VM????/?ֵ?*Ǎ???=YI???f?؋=??t?x??胶?

% ./ntru.py dec myKey.priv.npz enc.txt 

/Users/devharsh/Downloads/ntru/./ntru.py:83: DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.

Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

  ntru.f_poly = Poly(priv_key['f'].astype(np.int)[::-1], x).set_domain(ZZ)

/Users/devharsh/Downloads/ntru/./ntru.py:84: DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.

Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

  ntru.f_p_poly = Poly(priv_key['f_p'].astype(np.int)[::-1], x).set_domain(ZZ)

/Users/devharsh/Downloads/ntru/./ntru.py:157: DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.

Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

  sys.stdout.buffer.write(np.packbits(np.array(output).astype(np.int)).tobytes())

hello