[發明專利]基于矩陣的多變量公鑰加密方法

有效

• 申請號: 201310377035.2
• 申請日: 2013-08-26
• 公開（公告）號: CN103457726A
• 公開（公告）日: 2013-12-18
• 發明（設計）人: 陶成東
• 申請（專利權）人: 華南理工大學
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 蔡茂略

技術領域

本發明涉及一種安全通信技術，特別涉及一種基于矩陣的多變量公鑰加密方法。

背景技術

公鑰密碼系統在安全通信領域扮演著重要的角色，Diffie和Hellman首先提出公鑰密碼系統的思想，Rivest、Shamir和Adleman首先設計了實際可用的公鑰密碼系統——著名的RSA密碼系統(美國專利:4,405,829,1983)。

目前，基于數論理論的密碼系統，如RSA,DSA和ECC，廣泛的應用于安全通信領域。但是,Shor的算法表明:未來的具有大量子位的量子計算機可以攻破基于數論理論的密碼系統[21]，量子計算機的最新進展使得量子計算機對RSA，DSA和ECC等基于數論理論的密碼系統的威脅越來越近。此外，基于數論理論的密碼系統的計算效率是有限的，這就要求密碼研究者設計能夠抵御量子計算機的且在計算上更有效的公鑰密碼系統，通常稱這樣的密碼系統為后量子密碼系統。

多變量公鑰密碼系統屬于后量子密碼系統，多變量公鑰密碼系統的公鑰為有限域上的一組多變量多項式，通常是二次多項式，它的安全性基于已經被證明的事實:求有限域上的多變量多項式方程組的解的問題通常是NP困難問題[9].并且量子計算機不能有效的解決這一問題，從計算效率的角度看，多變量密碼系統要比RSA，DSA和ECC等基于數論理論的密碼系統有效得多。

早期的多變量公鑰密碼系統設計都是失敗的，如Diffie和Fell在文獻[27]中設計的密碼系統，Shamir在文獻[28]中設計的密碼系統。

1988年,Matsumoto和Imai設計了新的多變量公鑰加密方法，即C^＊或MI加密系統[16]。但是，Patarin在1995年用線性化方程攻破這個系統[18]，在文獻[5]中，Ding(丁津泰)指出，C^＊的中心映射多項式所對應的二次型矩陣矩陣的秩很小，事實上它的秩只有2，因而可以用極小秩攻擊方法攻破C^＊加密系統。

1996年，Patarin擴展了C^＊加密系統，設計出隱藏域加密系統(HFE)[19]，HFE加密系統擁有歐洲和美國專利(5,790,675,1996)，但是，Kipnis和Shamir利用極小秩攻擊方法和重線性化方法將HFE加密系統攻破[13]。

1998年，T.T.Moh提出了一個多變量公鑰加密方法，稱為TTM加密系統(美國專利:5,740,250,1998)[15]，但是TTM系統仍然被極小秩攻擊方法攻破[3]。[9]2008年D.Gligoroski等提出MQQ多變量加密系統[29]，2011年，Gao等提出了基于丟潘圖方程的多變量加密系統[30]，但均被攻破。

在過去的三十年里，許多多變量公鑰加密方法被提出，但絕大部分都是不安全的，這些被攻破的多變量公鑰加密方法中，部分是因為中心映射多項式對應的二次型矩陣的秩相對較小，因而容易遭受極小秩攻擊。部分是因為當用代數攻擊時，公鑰多項式方程組的正則度不高，因而容易遭受F4算法或Mutant?XL算法攻擊。

本發明的背景文獻：

[1]Bosma?W.,Cannon?J.J.,Playoust?C.:The?Magma?algebra?system?I:the?user?language.J.Symb.Comput.24(3-4),235-265(1997)。

[2]Bettale?L.,Faugère?J.C.,Perret?L.:Cryptanalysis?of?multivariate?and?odd-characteristic?hfe?variants.In:Public?Key?Cryptography-PKC2011.Lecture?Notes?in?Computer?Science,vol.6571,pp.441-458.Springer,Berlin(2011)。

[3]Courtois?N.,Goubin?L.:Cryptanalysis?of?the?TTM?cryptosystem.In:Advances?in?Cryptology-ASIACRYPT'00,Lecture?Notes?in?Computer?Science,vol.1976,pp.44-57.Springer,Berlin(2000)。