The NTRU Cryptosystem
A Java implementation of the NTRU public-key cryptosystem, consisting of
the encryption scheme NTRUEncrypt and the signature scheme NTRUSign.
NTRU's main strengths are high performance and resistance to quantum
computer attacks.
NTRU keys are longer than ECC keys; they can be longer or shorter than RSA
keys depending on the security level.
NTRU's main drawback is that it is patent encumbered. This means that for
commercial use, a license from the patent holder may be required depending
on your jurisdiction.
http://en.wikipedia.org/wiki/NTRUEncrypt
http://en.wikipedia.org/wiki/NTRUSign
The implementation follows IEEE P1363.1 for NTRUEncrypt and the EESS
(http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf)
for NTRUSign.
NtruEncrypt Usage
The first step is always to create an NtruEncrypt instance by calling the
constructor with an EncryptionParameters object representing the desired
algorithm parameters.
It is recommended to use one of the predefined parameter sets which are
available as constants in EncryptionParameters, but new ones can be created
as well.
After an NtruEncrypt instance has been created, it can be used to generate
new key pairs, and encrypt / decrypt messages.
Encrypting a message is done by calling encrypt() which takes the following
parameters:
1. the message itself as a byte array. Strings can be encrypted after
converting them to byte[] via getBytes()
2. an EncryptionPublicKey, which can be generated via
NtruEncrypt.generateKeyPair() or an existing key can be reconstructed
from a byte array by calling new EncryptionPublicKey(byte[])
The encrypted message is returned as a byte array.
Decrypting a message is done by calling decrypt() which takes the message,
an EncryptionKeyPair containing the public and private keys, and the
encryption parameters. The parameters used for decrypting must be the same
as the ones used to encrypt the message; the same goes for the public key.
Like all public-key encryption schemes, NtruEncrypt can only encrypt a
limited number of data. To find out how long a NTRU message can be, use the
method EncryptionParameters.getMaxMessageLength().
To encrypt larger amounts of data, use symmetric encryption and encrypt the
symmetric key with NTRU. The sample program AesExample shows how to do this.
NtruSign Usage
The first step is always to create an NtruSign instance by calling the
constructor with an SignatureParameters object representing the desired
algorithm parameters.
It is recommended to use one of the predefined parameter sets which are
available as constants in SignatureParameters, but new ones can be created
as well.
After the NtruSign constructor is called, the NtruSign instance can be
used to generate new key pairs, sign messages, and verify signatures.
There are two ways of signing a message. It can be done in one step by
calling sign(byte[], SignatureKeyPair) which takes the following parameters:
1. the message itself as a byte array. Strings can be signed after
converting them to byte[] via getBytes()
2. a SignatureKeyPair, which can be generated via
NtruSign.generateKeyPair() or an existing key pair can be reconstructed
from a byte array using the SignaturePrivateKey(byte[]) and
SignaturePublicKey(byte[]) constructors.
Note: Depending on the parameters, it can take a minute or more to
generate a new key pair.
The signature is returned as a byte array.
The other way is to call initSign with a SignatureKeyPair, then
update(byte[]) zero or more times, and finally sign(byte[]). This way,
long messages can be broken up rather than signing them in one piece.
Just like signing, verifying a message can be done in one step or in several
parts.
The one-step variant works by calling NtruSign.verify() which takes the
message, the signature, and the SignaturePublicKey. The parameters used for
verifying must be the same as the ones used to create the signature; the
same goes for the public key.
The multi-step variant works by calling initSign with a SignaturePublicKey,
then calling update(byte[]) zero or more times, and finally calling
verify(byte[]).
Key Import / Export
Encryption keys and signature keys can be written to a file via the writeTo
methods by supplying a FileOutputStream. The key can then be read from the
file by passing a FileInputStream to the appropriate constructor.
Keys are encoded raw, so the array contains no information about the
parameters used. It is advisable to first write the parameters, then the
key. Parameters can be written to an OutputStream just like keys, and just
like keys they have a constructor that takes an InputStream.
Keys can also be converted to and from byte arrays.
NTRUEncrypt keys (but not NTRUSign keys) can be created from a passphrase
by calling generateKeyPair(char[], byte[]) with a passphrase and a salt
value. The passphrase is a char array rather than a string so it can be
cleared from memory when it is no longer needed.
The salt parameter makes attacks using precomputed keys harder. It should be
a random value that is generated once and stored. The method generateSalt()
can be used to generate a salt value.
Parameter Sets
It is generally recommended to use the APR2011_439_FAST or APR2011_743_FAST
parameter set for encryption, and APR2011_439_PROD or APR2011_743_PROD for
signatures. The security levels are 128 bits for the "439" parameters and
256 bits for the "743" parameters.
Error Conditions
Errors cause a NtruException with an appropriate message and/or cause to be
thrown. NtruException is an unchecked exception.
Sample Programs
The net.sf.ntru.demo package contains several small console programs:
SimpleExample A minimal example showing how to use NTRUEncrypt and
NTRUSign
AesExample Demonstrates how to encrypt arbitrary-length messages
using NTRUEncrypt and AES
Benchmark Benchmarks NTRUEncrypt against RSA and ECC
Timings Similar to Benchmark but only NTRUEncrypt and NTRUSign are
benchmarked, and the output is in table format.
The src/main/android directory contains a simple Android app similar
to SimpleExample. It has been tested with Android 4.0.3.
To build and run the app, follow these steps:
1) Start Eclipse and make sure you have the ADT plugin installed
2) Create a new Android project. Enter net.sf.ntru.demo for the package
name and NtruActivity for the activity.
3) Replace the generated AndroidManifest.xml with the NTRU version from
src/main/android/AndroidManifest.xml
4) Replace the generated NtruActivity.java with the NTRU version from
src/main/android/net/sf/ntru/demo/NtruActivity.java
5) Go to Project -> Properties -> Java Build Path, and either add the NTRU
sources on the Source tab, or add the NTRU .jar on the Libraries tab.
6) In the package explorer, right click on your project and select
Run As -> Android Application.
Maven Artifact
NTRU is available from the Maven central repository.
<dependency>
<groupId>net.sf.ntru</groupId>
<artifactId>ntru</artifactId>
<version>1.2</version>
</dependency>
Other NTRU implementations
* As of Bouncy Castle 1.47 (http://bouncycastle.org/), it contains a fork of
this library in the bprov-ext and lcrypto jars.
* There is a C implementation of NTRUEncrypt at
https://github.com/tbuktu/libntru
Further reading
Original NTRUEncrypt paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.8422&rep=rep1&type=pdf
Follow-up NTRUEncrypt paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.6834&rep=rep1&type=pdf
Original NTRUSign paper: http://www.math.brown.edu/~jpipher/NTRUSign_RSA.pdf
Follow-up NTRUSign paper: http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/NTRUSignParams-2005-08.pdf
NTRU articles (technical and mathematical): http://www.securityinnovation.com/security-lab/crypto.html
Jeffrey Hoffstein et al: An Introduction to Mathematical Cryptography, Springer-Verlag, ISBN 978-0-387-77993-5
EESS: http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf