Sistemul criptografic NTRU pentru criptografia post-cuantică

NTRU este un sistem criptografic cu cheie publică open-source care utilizează criptografia bazată pe rețele pentru a cripta și decripta datele. Acesta constă din doi algoritmi: NTRUEncrypt, care este utilizat pentru criptare, și NTRUSign, care este utilizat pentru semnături digitale. Spre deosebire de alte sisteme criptografice populare cu cheie publică, este rezistent la atacurile care utilizează algoritmul lui Shor. NTRUEncrypt a fost brevetat, dar a fost plasat în domeniul public în 2017. NTRUSign este brevetat, dar poate fi utilizat de software sub licența GPL.[1][2]

Istoric

Prima versiune a sistemului, numită NTRU, a fost dezvoltată în 1996 de matematicienii Jeffrey Hoffstein, Jill Pipher și Joseph H. Silverman. În același an, dezvoltatorii NTRU s-au unit cu Daniel Lieman și au fondat compania NTRU Cryptosystems, Inc. și au primit un brevet pentru criptosistem.[3] Numele „NTRU”, ales pentru companie și aplicat în curând și sistemului, a fost inițial derivat din jocul de cuvinte Number Theorists ‘R’ Us sau, alternativ, a reprezentat Number Theory Research Unit.[4] În 2009, compania a fost achiziționată de Security Innovation, o corporație de securitate software.[5] În 2013, Damien Stehle și Ron Steinfeld au creat o versiune demonstrabil sigură a NTRU,[6] care este studiată de un grup post-cripto cuantic înființat de Comisia Europeană.[7]

În mai 2016, Daniel Bernstein, Chitchanok Chuengsatiansup, Tanja Lange și Christine van Vredendaal au lansat NTRU Prime,[8] care adaugă apărări împotriva unui potențial atac asupra NTRU prin eliminarea structurii algebrice pe care o considerau îngrijorătoare. Cu toate acestea, după mai bine de 20 de ani de examinare, până în prezent nu a fost găsită nicio abordare concretă pentru a ataca NTRU-ul original prin exploatarea structurii sale algebrice.

NTRU a devenit finalist în a treia rundă a proiectului de standardizare a criptografiei post-cuantice al NIST, în timp ce NTRU Prime a devenit un candidat alternativ.

Performanță

La o putere criptografică echivalentă, NTRU efectuează operațiuni costisitoare cu cheie privată mult mai rapid decât RSA.[9] Timpul de efectuare a unei operațiuni private RSA crește odată cu cubul dimensiunii cheii, în timp ce cel al unei operațiuni NTRU crește pătratic.

În 2010, Departamentul de Inginerie Electrică al Universității din Leuven a remarcat că

„[folosind] un GPU GTX280 modern, se poate atinge un debit de până la 200.000 de criptări pe secundă la un nivel de securitate de 256 de biți. Comparând acest lucru cu un cifru simetric (o comparație nu foarte comună), acesta este de doar aproximativ 20 de ori mai lent decât o implementare AES recentă.”[10]

Rezistență la atacurile bazate pe computere cuantice

Spre deosebire de RSA și criptografia cu curbe eliptice, NTRU nu este cunoscut ca fiind vulnerabil la atacurile asupra computerelor cuantice. Institutul Național de Standarde și Tehnologie a scris într-un sondaj din 2009 că „[există] alternative viabile atât pentru criptarea cu cheie publică, cât și pentru semnături, care nu sunt vulnerabile la algoritmul lui Shor” și că „[dintre] diversele scheme criptografice bazate pe rețele care au fost dezvoltate, familia de algoritmi criptografici NTRU pare a fi cea mai practică”.[11] Proiectul PQCRYPTO al Uniunii Europene (Horizon 2020 ICT-645622) evaluează versiunea Stehle-Steinfeld a NTRU, cu siguranță demonstrabilă (nu algoritmul NTRU original în sine), ca potențial standard european.[7] Cu toate acestea, versiunea Stehle-Steinfeld a NTRU este „semnificativ mai puțin eficientă decât schema originală”.[6]

Standardizare

Standardul IEEE Std 1363.1, emis în 2008, standardizează criptografia cu cheie publică bazată pe rețele, în special NTRUEncrypt.[12]

Standardul X9.98 standardizează criptografia cu cheie publică bazată pe rețele, în special NTRUEncrypt, ca parte a standardelor X9 pentru industria serviciilor financiare.[13]

Proiectul PQCRYPTO al Comisiei Europene are în vedere standardizarea versiunii Stehle-Steinfeld a NTRU, cu siguranță demonstrabilă.[6]

Implementări

Inițial, NTRU era disponibil doar ca bibliotecă proprietară, contra cost, iar autorii open-source erau amenințați cu acțiuni în justiție.[14][15] Abia în 2011 a apărut prima implementare open-source,[16] iar în 2013, Security Innovation a exceptat proiectele open-source de la obligația de a obține o licență de brevet[17] și a lansat o implementare de referință NTRU sub GPL v2.[18]

Implementări:

• OpenSSH utilizează implicit NTRU combinat cu schimbul de chei X25519 ECDH din august 2022, inclus în versiunea 9.0.[19]
• Implementarea de referință licențiată GPL[18]
• bibliotecă licențiată BSD[16]
• bouncycastle[20]
• Lokinet[21] a fost primul router onion care a implementat algoritmul NTRU pentru evenimentele sale intraweb și End-2-End Encrypted.
• GoldBug Messenger[22] a fost primul client de chat și e-mail cu algoritmul NTRU sub licență open-source, care se bazează pe nucleele Spot-On Encryption Suite.[23]
• În plus, wolfSSL oferă suport pentru suite de cifru NTRU într-o implementare C ușoară.[24]

Referințe

1. „Security Innovation Makes NTRUEncrypt Patent-Free”. 2017-03-28. Archived from the original on 2019-02-18.
2. „Ntru-crypto”. GitHub. 25 November 2021.
3. Robertson, Elizabeth D. (August 1, 2002). „RE: NTRU Public Key Algorithms IP Assurance Statement for 802.15.3” (PDF). IEEE. Retrieved February 4, 2013.
4. Kerlin, Janet (September 1, 2000). „Math professors patent computer security system”. George Street Journal. Brown University. Archived from the original on January 25, 2001.
5. Robinson, Maureen (July 22, 2009). „Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market” (Press release). Wilmington, MA: Security Innovation. Archived from the original on December 17, 2013. Retrieved February 4, 2013.
6. Stehlé, Damien; Steinfeld, Ron. „Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices”. Cryptology ePrint Archive. Retrieved 2016-01-18.
7. Lange, Tanja (1 March 2015). „Initial recommendations of long-term secure post-quantum systems” (PDF). PQCRYPTO.EU. Horizon 2020 ICT-645622. Retrieved 18 January 2015.
8. J. Bernstein; C. Chuengsatiansup; T. Lange; C. van Vredendaal (2016-05-12). „NTRU Prime” (PDF). NTRU Prime.
9. „NTRU: Quantum-Resistant High Performance Cryptography”.
10. Hermans, Jens; Vercauteren, Frederik; Preneel, Bart (2010). „Speed Records for NTRU”. In Pieprzyk, Josef (ed.). Topics in Cryptology – CT-RSA 2010. Lecture Notes in Computer Science. Vol. 5985. San Francisco, CA: Springer Berlin Heidelberg. pp. 73–88. doi:10.1007/978-3-642-11925-5_6. ISBN 978-3-642-11924-8. ISSN 0302-9743. Retrieved February 4, 2013.
11. Perlner, Ray A.; Cooper, David A. (2009). „Quantum resistant public key cryptography” (PDF). In Seamons, Kent; McBurnett, Neal; Polk, Tim (eds.). Proceedings of the 8th Symposium on Identity and Trust on the Internet. New York, NY: ACM. pp. 85–93. doi:10.1145/1527017.1527028. ISBN 978-1-60558-474-4. S2CID 12214601. Archived from the original (PDF) on May 14, 2012. Retrieved February 3, 2013.
12. „IEEE P1363: Standard Specifications For Public Key Cryptography”. IEEE. Archived from the original on 19 November 2008. Retrieved 7 December 2014.
13. „Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection”. Business Wire. 11 April 2011. Retrieved 7 December 2014.
14. „Statement by the libtomcrypt (LTC) author”.
15. „Email exchange between Security Innovation and a software author”.
16. Buktu, Tim. „NTRU: Quantum-Resistant cryptography”. Independent / not affiliated with NTRU Cryptosystems, Inc. Retrieved February 4, 2013.
17. „FOSS Exception”. GitHub. Archived from the original on 2019-02-14. Retrieved 2014-12-15.
18. „Open Source NTRU Public Key Cryptography and Reference Code”. GitHub. Archived from the original on 2018-03-31. Retrieved 2014-12-08.
19. „Changes since OpenSSH 8.9 (OpenSSH 9.0 release notes)”. OpenBSDs OpenSSH developers. 2022-04-08.
20. „-ext-„. Independent / not affiliated with NTRU Cryptosystems, Inc. Retrieved February 13, 2016.
21. majestrate (2018). „GitHub Commit in the lokinet repository showing NTRU implementation”. GitHub Pages.
22. Scott Edwards (2018). „GoldBug-manual. Manual of the GoldBug Crypto Messenger”. GitHub Pages.
23. „Spot-On Encryption Suite with NTRU: Democratization of Multiple & Exponential Encryption”. Spot-On. 2016-12-20. ISBN 978-3-7494-3506-7.
24. „wolfSSL Embedded SSL/TLS Library”. wolfSSL Products. Retrieved 2018-10-09.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)