Skip to content
/ ntru Public

An attack to NTRUencrypt was implemented using sagemath

Notifications You must be signed in to change notification settings

drazioti/ntru

Repository files navigation

Message recovery attack to NTRU using a lattice independent from the public key

GPLv2 CC BY 2

An attack to NTRUencrypt was implemented using sagemath and Fpylll

The code is in attack.py

References:

[1] Marios Adamoudis, K. A. Draziotis, Message recovery attack to NTRU using a lattice independent from the public key, http://arxiv.org/abs/2203.09620

Authors

credits: Some functions are from https://latticehacks.cr.yp.to/ntru.html

License

This project is licensed under the GPLv2 License

The images are provided with CC BY 2.0

Getting Started

prerequisites : sagemath version >=8.1 and Fpylll.


In generate.md there is sagemath code that generates a pair (pk,sk) for NTRU and a random plaintext and also its encryption (ciphertext).

See attack.md for comments on the attack.py

For large values of N, say N>400, sagemath produces babai's infinite loop for LLL (we used sagemath 8.5).

In fpylll LLL succeeded. For instance, for N=509, it took 5 minutes for the LLL reduction.

For N=509,557 and 677 you can use the already reduced matrices from the directory reduced_matrices/. To compute the LLL- reduction of matrices in fpylll we use the code in ntru_large_matrices_reduction.ipynb

In the code (attack.py) there is an option in the function the_attack(.) to set flag=2, then the code will use the reduced matrix from the file in the directory reduced_matrices/ it and will not compute LLL reduction on it.

In appendix.ipynb there is Fpylll code that checks suitable values (N,q,y) that satisfy the hypotheses of Proposition.

Contribution

Please report bugs (open an issue).

About

An attack to NTRUencrypt was implemented using sagemath

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published