基本介紹
- 中文名：NTRU
- 外文名：Number Theory Research Unit
- 提出時間：1996年
- 提出者：美國布朗大學三位數學教授
- 性質：公開秘密體制
- 學科：密碼學
簡介,國內外研究現狀,歷史,性能,防止量子計算機破解,標準,發行方式,
簡介
這是一個基於多項式環的密碼體制。它的安全性依賴于格中最短向量問題（SVP）。相對於離散對數或大數分解等公開秘密體制來說，它有許多優勢。在安全性方面，NTRU算法具有抵抗量子計算攻擊的能力，而RSA和ECC算法是無法抵抗量子計算的。當前，對於用什麼公鑰密碼來替代正在大量使用的RSA和ECC，主要有以下互相競爭的技術解決方案：NTRU公鑰密碼體制、McEliece 公鑰密碼體制、MQ 公鑰密碼體制。
McEliece 公鑰密碼體制的安全性基於糾錯碼問題，安全性強，但計算效率低。MQ 公鑰密碼體制，即多變元二次多項式公鑰密碼體制（Multivariate Quadratic Polynomials in Public KeyCryptosystem），基於有限域上的多變元二次多項式方程組的難解性，在安全性方面的缺點比較明顯。相比之下，NTRU公鑰加密體制算法簡潔、計算速度快、占用存貯空間小。
國內外研究現狀
隨著信息技術的迅猛發展和一些高技術武器設備、通信指揮系統等的需要，未來軍事部門將大量地使用公鑰密碼技術。由於RSA 和ECC 不能抗量子計算攻擊，而NTRU 能抗量子計算攻擊，且速度快和安全性高，特別別適合用於諸如智慧卡，保密蜂窩電話系統，保密傳真、無線保密數據網，以及認證系統等業務，這也擴大了公鑰密鑰體制的套用範圍。有理由相信NTRU 算法完全有可能在公鑰密鑰體制中占有主導地位。
自從該密碼體制被提出來後，就引起國外一流的密碼學家的關注，這包括Don Coppersmith Johan Hastad, Andres Odlyzko,and Adi Shamir 等。到目前為止，有很多討論NTRU 算法安全性。但還沒有哪一種分析方法能破譯該密碼體制。從現階段研究來看，NTRU 所基於的困難問題是安全的。接下來的研究主要集中在體制的參數設定和適當的使用填充方案。
在2000 年，Jaulmes 和Joux 論證了仔細的選擇填充方案可以防止選擇密文攻擊，Howgrave-Graham 等的研究結果顯示了仔細的選擇參數集可以使得解密失敗機率降為幾乎為0，一旦正確的參數的選擇和適當填充方案的使用，任何對NTRU 的攻擊都可以轉化為對困難格問題的求解。
為了充分利用在學術界和商界的專家的經驗和知識，提供一個完善的、有效的、能共同操作的，正確使用NTRU 公鑰密碼系統的方法，在2002 年10 月出版了一個標準EESS1v1：NTRU 加密和簽名的實施，2003 年5 月對第一版進行完善和修改出台二版:EESS1v2。
歷史
第一個被命名為NTRU的加密系統版本，是數學家Jeffrey Hoffstein，Jill Pipher，和Joseph H. Silverman於1996年開發的。同年，Daniel Lieman加入了NTRU開發團隊，並成立了公司NTRU Cryptosystems, Inc.， 獲得了該加密系統的專利。2009年，該公司被一家名為Security Innovation的軟體安全公司收購。2013年，Damien Stehle和Ron Steinfeld創建了NTRU的一個可靠版本，目前正在由歐盟委員會授權的後量子加密小組進行研究。
2016年5月，Daniel Bernstein，Tanja Lange等人發布了NTRU Prime，通過消除一些令人不安的代數結構以抵抗潛在的攻擊。
性能
在同等加密強度下，NTRU執行大開銷的私鑰操作比RSA算法快得多。RSA算法的私鑰操作耗時與密鑰長度呈三次方關係，而NTRU相應操作為二次方關係。
據魯汶大學電子工程部門表示，“使用一塊現代的GTX280顯示卡，在256 bit加密強度下，最高可達每秒二十萬次的加密的吞吐量。與最新的對稱加密AES實現相比（這並不公平），只慢了大概二十倍。”
防止量子計算機破解
與RSA加密算法和橢圓曲線加密算法（英語：Elliptic Curve Cryptography, ECC）不同，NTRU在基於量子計算機的攻擊面前沒有已知的弱點。國家標準枝術研究所在一份2009年的調查中寫到“目前不存在一種能同時兼顧公鑰加密和數字簽名，並在Shor算法面前沒有弱點的可行替代方案”以及“在基於格的眾多已有加密方案中，NTRU加密算法族看起來是最可行的”。歐盟的PQCRYPTO計畫(Horizon 2020 ICT-645622)正在評估Stehle–Steinfeld可靠版本的NTRU (並非原始版本的NTRU算法)，以作為一項潛在的歐洲標準。然而Stehle-Steinfeld版本的NTRU“比原始版本效率要低得多。"
標準
- IEEE Std 1363.1標準，發布於2008年，標準化了基於格的公鑰加密算法，尤其是NTRUEncrypt。
- X9.98標準，標準化了基於格的公鑰加密算法，尤其是NTRUEncrypt，作為X9金融服務標準的一部分。
- 歐洲委員會的PQCRYPTO計畫正在考慮標準化Stehle-Steinfeld可靠版本的NTRU。
發行方式
最初，NTRU只有一個帶專利保護的付費開源庫可用，打算寫開源實現的作者收到訴訟威脅。直到2011年出現了第一個開源實現，在2013年，Security Innovation豁免了開源項目的專利授權要求，並以GPL v2協定釋放了一份NTRU的參考實現。
Security Innovation依然提供付費的專有軟體選項。
現在存在兩個開源的NTRU實現：
- GPL-licensed下的參考實現
- BSD-licensed下的庫
分別在Java和C下可用。
