NTRUEncrypt
NTRUEncrypt is an asymmetric encryption method that was developed in 1996 by mathematicians Jeffrey Hoffstein , Jill Pipher and Joseph H. Silverman . It is loosely based on lattice problems that are considered unbreakable even with quantum computers . However, NTRUEncrypt has so far not been as well researched as more common methods (e.g. RSA).
The algorithm is patented in the USA; the patents will expire in 2021. NTRUEncrypt is standardized by IEEE P1363.1. It is used z. B. from the US companies WiKID, Echosat and yaSSL.
Description of the procedure
Only the core algorithm is described below. Taken alone, this is susceptible to certain attacks; see the section Pre- and Post-Processing .
Unless otherwise stated, all calculations take place in the ring , i.e. H. the degree of the polynomial never exceeds . The multiplication “*” is a cyclic convolution modulo : The product of two polynomials and is .
Key generation
- Select the parameters with .
- Choosing a random polynomial whose coefficients are in {−1, 0, 1}. The inverses (the inverse modulo ) and (the inverse modulo ) must exist.
- Generation of a random polynomial whose coefficients are in {−1, 0, 1}.
- is the public key, the secret key. (For faster decryption, it can also be included in the secret key.)
Encryption
- Conversion of the plain text into a polynomial .
- Choosing a random polynomial with small coefficients.
- The polynomial is the ciphertext.
Decryption
- Calculation of with choice of the representatives of the coefficients of in the interval .
- Calculation of .
- The plain text is obtained by converting the polynomial into the text representation.
correctness
For polynomial applies: . Because the coefficients are all small, this equation also exists in the ring . Therefore, the calculation is correct in the second step .
Efficiency
To speed up the multiplication, the polynomials and can be chosen so that many coefficients are zero. For this purpose, parameters are selected and in the selection of are coefficients equal to 1, coefficients equal to -1 and the rest set to 0. If you choose , coefficients are set equal to 1, coefficients equal to −1 and the remainder equal to 0 (Note: the number of ones must not be equal to the number of minus ones, otherwise the polynomial cannot be inverted).
Decrypting becomes more efficient when the polynomial according to the formula with forms. Since then applies, the calculation of the inverse modulo is omitted . When choosing parameters, however, it is important to ensure that the desired level of security is maintained, since an attacker can now search through the set of .
Furthermore, to speed up the multiplication, the polynomial can be formed according to the formula , where , and can be very sparsely populated. The three parameters , and , then take the place of the parameter . The increase in efficiency results from the fact that applies ( but still has enough coefficients other than zero) and can therefore be multiplied by faster than by .
Finally, instead of a prime number, a polynomial can be chosen, whereby the most favorable choice is. This variant only appears in older literature.
safety
There is no formal proof of security for NTRUEncrypt as there is for other cryptographic methods, but the method is considered to be secure for sufficiently large parameters. At the beginning of 2011 a work by the cryptologists Damien Stehlé and Ron Steinfeld appeared, in which a security proof for a modified form of NTRUEncrypt is provided.
Various attacks on NTRUEncrypt are possible. The simplest of these is to try out all the polynomials that come into question for the parameters and . A more effective attack is the half attack ( meet-in-the-middle attack ), in which instead of one polynomial of the full length, two polynomials with only coefficients are tried out at the same time. As a result, this attack only needs the square root of the number of steps involved in primitive trial and error. A grid reduction is even more effective , e.g. B. by means of the LLL algorithm .
Pre- and post-processing
The NTRUEncrypt core algorithm does not offer any security against attackers who manipulate the data after encryption. This can be remedied with a special padding , which the recipient can use to recognize manipulated ciphers.
Three such methods are known. SVES-1 and SVES-2 are older and vulnerable to attacks that exploit decryption errors. SVES-3 eliminates these weaknesses and is described in the P1363.1 standard under the designation SVES.
256 bit security level parameters
Originally, values between 167 and 503 were recommended for the length , but the recommendations were adjusted accordingly after various attacks became known. The following parameters meet all currently known (as of 9/2011) attacks:
designation | N | p | q | d _{f} | d _{g} | |
---|---|---|---|---|---|---|
Smallest key length | EES1087EP2 | 1087 | 3 | 2048 | 120 | 362 |
Medium key length, medium duration | EES1171EP1 | 1171 | 3 | 2048 | 106 | 390 |
Shortest closing and closing time | EES1499EP1 | 1499 | 3 | 2048 | 79 | 499 |
See also
Web links
- Description of the algorithm and recommended parameters (registration required)
- Description of the algorithm (accessible without registration) (PDF file; 315 kB)
- NTRUEncrypt as Java source code
- An NTRUEncrypt implementation from TU Darmstadt is available via SVN with the command svn co --username guest --password guest https://svn.cdc.informatik.tu-darmstadt.de/svn/repos/flexiprovider (The NTRU code is located in the directory flexiprovider / trunk / FlexiProvider / src / de / flexiprovider / pqc / ntru /).
Individual evidence
- ↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring Based Public Key Cryptosystem ( Memento of the original from January 30, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. . In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, JP Buhler (Ed.), Lecture Notes in Computer Science 1423, Springer-Verlag Berlin, 1998, 267-288.
- ↑ Patent US7031468 : Speed enhanced cryptographic method and apparatus. Filed August 24, 2001 , published April 18, 2006 , assignee: NTRU Cryptosystems, Inc., inventors: Jeffrey Hoffstein, Joseph H. Silverman. (Expiry of the 20-year period on 24 August 2021)
- ↑ WiKID authentication devices ( Memento of the original dated December 14, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. .
- ↑ Article about NTRU in Networkworld from April 20, 2011 ( page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. .
- ↑ CyaSSL Embedded SSL Library .
- ↑ ^{a } ^{b } ^{c} Hoffstein u. Silverman: Optimizations for NTRU .
- ↑ Damien Stehlé and Ron Steinfeld: Making NTRU as Secure as worst-case problem over ideal lattices . ( ens-lyon.fr [PDF]).
- ↑ The impact of decryption failures on the security of NTRU encryption .
- ↑ IEEE P1363.1 ( Memento of the original from June 29, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. ( PDF ( Memento of the original from December 30, 2016 in the Internet Archive ) Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this note. Of a draft)