NTRUEncrypt, the fastest public key algorithm you've never heard of

NTRUEncrypt, the fastest public key algorithm you've never heard of.

-- Tom

 

It's also worth mentioning that NTRU cannot be broken with quantum computers unlike RSA or ECC.

There is a free and open Java implementation at http://ntru.sf.net/.

 

When it comes to encryption, I'd rather have a slow well known encryption algorithm than a fast unknown (read: untested) one.

 

Eh. Yes and no. It with stands (so far) modern "quantum computers" for breaking it using techniques that reduce the key-strength by half. This affectively kills asymmetric cryptography as a asymmetric key is no where near as strong as a symmetric key. A 1024 bit asymmetric is about the same as a 80 bit symmetric key which is effectively a 40 bit key to a quantum computer using special algorithms (Grover's Algorithm - http://en.wikipedia.org/wiki/Grover's_algorithm). This can be crack pretty fast (near real time). Now this works against symmetric encryption as well but as symmetric keys are stronger than asymmetric keys (in general use) symmetric is not mentioned as much. a 256 bit symmetric key is still reduced to half key-size by Grover's Algorithm but is still not crackable in a reasonable amount of time.

Now when you get into REAL quantum computers (which do NOT exists yet) these can crack any known cryptographic method (which are based on integer factorization ) because of Shor's algorithm. This effectively means a true quantum computer could crack any known cryptographic key using this method (so AES, Serpent etc. ) instantly. Once these machines exist all known forms of cryptography (except quantum cryptography) are dead. Yes DEAD.
more: http://en.wikipedia.org/wiki/Quantum_computer#Potential

 

NTRU 1.0 has been released: http://ntru.sf.net/

 

Quantum computers barely exist

 

True, but if somebody builds one 20 years from now, the keys and encrypted data you create today will still be safe (assuming no mathematical breakthroughs).

 

Not true. Did you read my post? True Quantum computers can break ALL forms of cryptography based on integer factorization aka anything that is math based. The only cryptography not effected is Quantum cryptography. Not to mention a true quantum computer won't be built in our lifetime.

 

but if somebody builds one 20 years from now

Apart from RSA and AES which have already been broken by this thing that does not yet properly exist.

This thread is more a challenge than cryptography itself.

 

Symmetric encryption like AES is a little different in that it won't be completely broken by quantum computing but key sizes will effectively be cut in half.

 

Yes, and here is a quote from the Wikipedia article you linked to:

Which includes NTRU.

NTRU isn't based on integer factorization, neither is ECC, or ElGamal, or Merkle, etc.

 

Very interesting. I apologize the article I read originally (white paper) said it was integer factorization. In that case we may be safe after all. Except wont the keysize still be cut in half by quantum computer? Either way this is all theory and not practical at all. Once a REAL quantum computer exists AES will be dead. and we will need something like NTRU as an intermediate to quantum cryptography.

TO make things more complicated (of course) you need to consider that what we somewhat have now (that we call quantum computers) are not true quantum computers and cannot do this.

 

but is there a program like true crypt that can use this algorithm ?

 

It's public key cryptography that is not a recommended use for it. Public Key (asymmetric cryptography) is far weaker symmetric cryptography. Essientially a 1024 bit asymmetric key is the approximate equivalent of a 60 bit symmetric key which is within cracking time. (NIST is ditching 60 bit under FIPS 140-2 and making 80 bit's the minimum). Now if you increase the bits of a Public Key to approximately 11,000 bits now it is roughly a 256 bit symmetric key in strength. Public key cryptography is best for sensitive information that needs to be exchange securely. Any program that uses it to encrypt a file or volume should ONLY use it as the key for a symmetric algorithm like AES and NOT encrypt the data with the asymmetric algorithm (PGP does this). If it encrypts the file itself with the public key algorithm (like RSA or NTRU) than you COULD run into issues if you don't use a higher key size.

I would recommend at least 4096 bit. All of this information is based on a NIST article (I will post a Link when not on my mobile).

Not to say it could be broken but key size is a bigger issue when it comes to Public key crypto. Than again NTRU may not be subject to this (all though it should be as it is still a public key crypto).