ntru is a simple implementation of NTRUEncrypt cryptosystem, written in Python 3.6. Polynomial operations are implemented using SymPy library. It was made as a homework project for "Error-Correcting Codes and Cryptography" workshops on Faculty of Mathematics and Information Science of Warsaw University of Technology.
This package was made as an exercise. It shouldn't be used anywhere to secure data.
You should have Python 3.x installed on your system. To do this on Fedora OS you need to execute
sudo dnf install python3
You should have SymPy, NumPy and docopt package installed.
pip3 install --user sympy
pip3 install --user numpy
pip3 install --user docopt
To print help screen execute ntru.py script with -h argument.
$ ./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.
As you can see there are few commands:
enc- encrypt a file using public keydec- decrypt a file using private keygen- generate a key pair with given parameters
To generate random public and private key pair execute:
$ ./ntru.py -v gen 167 3 128 myKey.priv myKey.pub
The myKey.priv.npz and myKey.pub.npz files should appear in current working directory. These are zip compressed NumPy files which contains:
- both keys:
- N
- p
- q
- public key:
- f
- f_p
- private key:
- h
One can see these parameters by running the program in verbose mode:
$ ./ntru.py -v gen 167 3 128 myKey.priv myKey.pub
NTRU(N=167,p=3,q=128) initiated
g: Poly(x**166 - x**157 + x**128 + x**127 - x**122 - x**121 + x**110 + x**101 + x**93 + x**78 - x**64 - x**63 - x**62 + x**61 - x**56 - x**50 + x**46 - x**44 - x**39 + x**36 + x**32 - x**5, x, domain='ZZ')
g coeffs: Counter({1: 11, -1: 11})
f: Poly(x**165 - x**164 - x**163 + x**158 + x**152 - x**151 - x**150 + x**149 - x**148 + x**147 + x**146 - x**145 + x**142 + x**141 - x**140 + x**139 + x**138 - x**136 - x**134 - x**132 - x**131 + x**130 + x**127 - x**126 - x**125 - x**124 - x**123 - x**121 + x**117 - x**116 + x**115 - x**114 - x**113 + x**112 - x**111 + x**110 - x**109 - x**107 + x**105 - x**104 + x**101 - x**100 - x**99 + x**97 + x**96 + x**94 - x**92 + x**90 + x**85 - x**84 + x**83 - x**82 + x**81 - x**79 - x**77 + x**76 + x**75 + x**74 - x**73 + x**72 + x**71 + x**69 + x**68 + x**67 - x**65 + x**64 + x**63 - x**62 + x**61 + x**60 + x**59 + x**58 - x**54 - x**53 + x**52 - x**51 + x**49 - x**47 - x**45 + x**44 + x**43 - x**41 + x**40 - x**36 + x**35 - x**34 + x**33 + x**31 + x**30 - x**29 + x**28 - x**26 - x**24 + x**22 - x**21 - x**20 - x**18 - x**17 - x**16 - x**15 + x**14 + x**11 - x**10 + x**8 + x**6 - x**5 - x**4 - x**2 + 1, x, domain='ZZ')
f coeffs: Counter({1: 55, -1: 54})
f_p: Poly(-x**166 + x**165 + x**164 - x**162 - x**161 + x**160 - x**159 + x**158 - x**156 - x**155 - x**153 + x**152 + x**151 - x**150 - x**149 + x**148 - x**146 - x**145 + x**144 + x**142 + x**141 + x**140 - x**139 + x**138 + x**137 - x**135 + x**134 - x**132 + x**130 - x**129 + x**128 - x**126 - x**124 - x**123 + x**121 + x**118 + x**116 - x**115 - x**113 - x**112 - x**111 - x**110 + x**109 + x**108 - x**107 + x**106 - x**105 + x**104 + x**103 + x**102 - x**101 + x**100 + x**99 - x**96 + x**94 + x**91 + x**90 + x**88 + x**87 - x**84 + x**83 + x**82 - x**81 - x**79 + x**78 - x**77 + x**71 + x**69 + x**66 - x**65 - x**64 + x**61 + x**59 - x**56 - x**55 - x**54 - x**53 + x**51 + x**49 - x**48 + x**45 - x**44 + x**43 + x**42 + x**40 - x**39 - x**38 - x**37 - x**36 - x**35 - x**34 + x**33 - x**32 + x**31 - x**30 + x**29 + x**27 + x**26 + x**25 + x**22 + x**21 + x**20 - x**19 - x**17 - x**14 + x**12 - x**9 + x**8 - x**6 + x**4 + x**3 - x**2 + 1, x, modulus=3)
f_q: Poly(-45*x**166 + 49*x**165 + 43*x**164 - 5*x**163 - 31*x**162 + 12*x**161 + 46*x**160 - 25*x**159 - 12*x**158 + 50*x**157 - 60*x**156 + 42*x**155 + 3*x**154 + 24*x**153 + 63*x**152 + 41*x**151 + x**150 - 50*x**149 + 16*x**148 + 48*x**147 + 62*x**146 + 59*x**145 - 36*x**144 + 54*x**143 - 16*x**142 + 36*x**141 - 34*x**140 - 43*x**139 + 16*x**138 + 64*x**137 + 36*x**136 - 33*x**135 - 40*x**134 + 11*x**133 - 16*x**132 - 49*x**131 + 51*x**130 + 40*x**129 + 10*x**128 - 53*x**127 - 33*x**126 + 16*x**125 + 64*x**124 - 50*x**123 + 35*x**122 - 59*x**121 - 59*x**120 + 35*x**119 - 58*x**118 + 43*x**117 + 28*x**116 + 5*x**115 - 45*x**114 - 33*x**113 - 14*x**112 - 56*x**111 - 24*x**110 + 31*x**109 + 53*x**108 + 30*x**107 + 59*x**106 + 23*x**105 - 30*x**104 + 50*x**103 - 41*x**102 - 23*x**101 - 51*x**100 - 56*x**99 + 40*x**98 + 25*x**97 + 50*x**96 - 12*x**95 + 11*x**94 - 6*x**93 + 45*x**92 - 2*x**91 - 43*x**90 - 7*x**89 - 51*x**88 + 16*x**87 + 39*x**86 - 57*x**85 + 31*x**83 + 41*x**82 - 40*x**81 + 38*x**80 + 25*x**79 + 49*x**78 - 30*x**77 - 35*x**76 + 22*x**75 + 23*x**74 + 57*x**73 - 45*x**72 - 9*x**71 + 26*x**70 + 41*x**69 + 59*x**68 - 19*x**67 + 17*x**66 - 41*x**65 - 12*x**64 - 60*x**63 + 25*x**62 + 14*x**61 - 26*x**60 + 30*x**59 - 44*x**58 - 19*x**57 - 39*x**56 + 59*x**55 - 42*x**54 + 17*x**53 + 58*x**52 - 40*x**51 + 42*x**50 + 51*x**49 - 30*x**48 + 19*x**47 - 44*x**46 - 45*x**45 + 15*x**44 - 15*x**43 - 48*x**42 - 9*x**41 + 62*x**40 + 25*x**39 - 25*x**38 - x**37 + 61*x**36 - 57*x**35 + 45*x**34 - 24*x**33 - 61*x**32 - 4*x**31 + 59*x**30 + 27*x**29 + 10*x**28 - 22*x**27 - 5*x**26 + 5*x**25 - 10*x**24 - 26*x**23 + 49*x**22 + 63*x**20 - 48*x**19 + 42*x**18 - 49*x**17 - 34*x**16 + 26*x**15 + 2*x**14 + 46*x**13 - 23*x**12 + 11*x**11 + 21*x**10 + 27*x**9 - 9*x**8 - 11*x**7 - 35*x**6 + 23*x**5 - 7*x**4 + 2*x**3 - 52*x**2 - 53*x + 51, x, domain='ZZ')
h: Poly(62*x**166 - 20*x**165 + 48*x**164 + 32*x**163 - 15*x**162 - 22*x**161 + 16*x**160 - 54*x**159 - 17*x**158 - 27*x**157 - 33*x**156 - 40*x**155 - 59*x**154 + 54*x**153 + 30*x**152 - 18*x**151 - 24*x**150 + 48*x**149 - 6*x**148 - 40*x**147 + 10*x**146 + 47*x**145 + 33*x**144 + 51*x**143 + 12*x**142 + 57*x**141 + 52*x**140 + 44*x**139 + 55*x**138 + 53*x**137 + 60*x**136 + 8*x**135 - 63*x**134 + 32*x**133 + 10*x**132 + 36*x**131 - 45*x**130 + 38*x**129 - 59*x**128 + 62*x**127 + 29*x**126 + 11*x**125 - 40*x**124 + 11*x**123 + 48*x**122 + 31*x**121 + 38*x**120 + 54*x**119 + 47*x**118 - 57*x**117 - 27*x**116 + x**115 + 6*x**114 - 24*x**113 - 15*x**112 - 59*x**111 + 45*x**110 - 35*x**109 - 58*x**108 - 43*x**107 + 15*x**106 - 25*x**105 + 4*x**104 - 4*x**103 - x**102 + 58*x**101 - 25*x**100 - 20*x**99 + 42*x**98 + 51*x**97 + 10*x**96 + 29*x**95 + x**94 + 23*x**93 - 40*x**92 - 5*x**91 - 56*x**90 + 21*x**89 - 55*x**88 + x**87 + x**86 + 29*x**85 - 9*x**84 - 47*x**83 + 19*x**82 + 39*x**81 + 47*x**80 + 46*x**79 + 26*x**78 - 19*x**77 + 37*x**76 - 22*x**75 + 25*x**74 - 19*x**73 - 43*x**72 + 22*x**71 + 34*x**70 + 42*x**69 - 36*x**68 + 61*x**67 - 37*x**66 + x**65 - 61*x**64 - 19*x**63 + 55*x**62 + 25*x**61 + 58*x**60 + 5*x**59 - 11*x**58 - 33*x**57 - 44*x**56 + 23*x**55 - 63*x**54 - 20*x**53 - 53*x**52 + 50*x**51 + 57*x**50 + 12*x**49 - 9*x**48 + 50*x**47 - 45*x**46 + 6*x**45 + 17*x**44 - 38*x**43 + 50*x**42 - 52*x**41 - 42*x**40 - 56*x**39 - 29*x**38 + 60*x**37 + 21*x**36 + 35*x**35 + 47*x**34 - 3*x**33 + 55*x**32 - 7*x**31 + 40*x**30 - 19*x**29 + 49*x**28 + 22*x**27 + 2*x**26 - 19*x**25 - 61*x**24 + 19*x**23 + 53*x**22 - 19*x**21 + 23*x**20 + 50*x**19 + 26*x**18 + 28*x**17 + 36*x**16 - 28*x**15 + 54*x**14 + 37*x**13 - 15*x**12 - 36*x**11 - 24*x**10 + 40*x**9 - 36*x**8 + 26*x**7 - 63*x**6 + 55*x**5 - 57*x**4 + 5*x**3 + 39*x**2 - 61*x - 31, x, domain='ZZ')
Private key saved to myKey.priv file
Private key saved to myKey.pub file
There are two ways of providing input to the program and two ways of interpreting this input.
Supported input:
- file
$ ./ntru.py enc myKey.pub.npz test.txt
!֘Tމ���c|���}3i1<pV�9�p��[E�VS��X1�4��ц4�6�A�ƚ�;����˔O)'�G8��5Mt[RXcj0]���y���hq�^1�ē���b944
(�n�'u���y4��W�� ���6����5W�*��
- standard input
$ echo "hello!" | ./ntru.py enc myKey.pub.npz
|�w�T�a�V�"I�&�C�(�i��C���y��~���U��|8� Qg
�f�(�B��?�c{r����giܝ���7LxQwH*�G*�
��Y'��7����f@�F�ɂ�9�TU�ʪ�Oܠ�l���(@�
)e���$�(B���)�
Supported input/output types:
- binary encryption input (decryption output) is translated into (from a) polynomial with coefficients of ones and zeros (we can see the array of this polynomial using debug mode)
$ echo "hello!" | ./ntru.py -d enc myKey.pub.npz
...
---INPUT---
b'hello!\n'
-----------
POLYNOMIAL DEGREE: 54
BINARY: [0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1
1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1]
- binary encryption output (decryption input) is translated from a polynomial with coefficients in Z_q field into binary stream where each coefficient is encoded into log(q) bits
- polynomial as integer array (e.g.
[1,0,1])
$ echo "hello!" | ./ntru.py -o enc myKey.pub.npz
[-13, 39, 0, 14, 7, 19, 40, 61, 45, -24, -32, 41, 12, -58, 42, 2, -48, 63, 14, -26, 22, 41, 35, 22, 16, 50, 62, -17, 30, -60, -20, 50, 17, 16, -58, 54, -45, 4, 20, -11, 33, 59, 43, -32, 60, -18, 60, 20, 57, 3, 47, 55, -54, 9, 37, -30, 43, 30, 55, -25, 17, -45, 37, -54, -56, -52, -49, 21, 24, 64, 9, 34, -59, -8, 64, -10, -49, 17, 2, 31, -48, 39, -20, 64, -42, -22, 7, 0, -34, -40, -20, 27, -9, 60, -25, -57, 45, -4, 62, -50, -22, -13, 59, 9, 15, -49, -60, 31, 2, 38, -13, -17, -55, -40, 36, -22, -42, 46, -63, -56, 28, -32, -51, 13, -27, -28, -57, -62, -17, -3, -9, 35, -6, 16, 56, 31, -14, 48, -20, 54, -30, 59, 61, -53, -44, 44, 49, -58, -20, -19, -9, -7, -55, 52, 10, 7, 18, 24, -49, -57, 61, -38, 48, 55, 11, -54, 43]
$ echo "[0,1,1,0,1,0,0,0,0,1,1,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1]" | ./ntru.py -i enc myKey.pub.npz | ./ntru.py dec myKey.priv.npz
hello!
$ echo "[0,1,1,0,1,0,0,0,0,1,1,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1]" | ./ntru.py -i enc myKey.pub.npz | ./ntru.py dec myKey.priv.npz | xxd -b
00000000: 01101000 01100101 01101100 01101100 01101111 00100001 hello!
00000006: 00001010
The program always returns its output to standard output. You can save the output to file by redirecting standard output to file. Remember not to use verbose or debug mode in this case.
$ ./ntru.py enc myKey.pub.npz test.txt > encrypted_test.txt
$ ./ntru.py dec myKey.priv.npz encrypted_test.txt
hello!
$ cat test.txt
hello!
$ cat encrypted_test.txt
�o�K_�gi���f�H�qlnh�|{��w���r/��)HL)F���9}�8
Ė�bX��pw@�.*�-۬����D!Au��&�@9��/S�J��q]�~�o�O�D��Yp����M�Ly%_��Ѩ*\;�����P!�iAs*��
If the input you provided is too large, the program will return this error.
$ ./ntru.py enc myKey.pub.npz test.txt
Traceback (most recent call last):
File "./ntru.py", line 149, in <module>
output = encrypt(args['PUB_KEY_FILE'], input_arr, bin_output=not poly_output, block=block)
File "./ntru.py", line 58, in encrypt
raise Exception("Input is too large for current N")
Exception: Input is too large for current N
In this case, you can use the block mode, which splits the input into blocks of the requested size. Make sure you are using this mode in both encrypting and decrypting process.
$ ./ntru.py -b enc myKey.pub.npz test.txt | ./ntru.py -b dec myKey.priv.npz
hello!
When running each process in verbose mode, the program prints to standard output all important variables. Meaning of these could be found in papers about NTRUEncrypt (or even Wikipedia).
Most of variables are polynomials in form of:
g: Poly(-x**10 - x**8 + x**5 + x, x, domain='ZZ')
Some polynomials have particular coefficients counted:
g coeffs: Counter({-1: 2, 1: 2})
- Using small N and q values don't work well and leads to the random success of encryption
- Encrypting even quite small files (~100kB) in block stream mode can take a lot of time