一種基于“陷門收縮”原理的公鑰算法

1、    一種基于“陷門收縮”原理的公鑰算法            作者：佚名時間：2007-11-25 12:33:00                     擇要：本文主要介紹一種基于“陷門收縮”原理的公鑰算法，給出了私有密鑰的構造方法

2、，并對密碼長度、保密強度進行了分析。關鍵詞：加密  解密  陷門收縮 算法1引言   計算機網絡技術使信息科學得到了飛速發(fā)展，同時也帶來了一系列數(shù)據安全問題，需要有高強度的加密安全措施才能保證其安全。近年來，密碼技術有著突飛猛進的發(fā)展，密碼學的研究十分活躍，出現(xiàn)了眾多公鑰密碼系統(tǒng)。本文設計了一種基于“陷門收縮”原理的一種公開密鑰密碼算法，給出了私有密鑰的構造方法，并對密碼長度、保密強度進行了分析。2設計思想   根據Merkle和Hellman提出的經典陷門收縮算法的基本思想，“背包問題”在不知道“陷門信息”的情況下是難以計算求解的，

3、如果知道了“陷門信息”，則求解就變得容易了。    本文算法的私有密鑰(解密密鑰)是在數(shù)論的“陷門收縮”理論基礎上由隨機產生加復雜構造而生成，符合“收縮”計算規(guī)律，并利用陷門原理，由私有密鑰導出公有密鑰(加密密鑰)。加密時根據公有密鑰由明碼導出密碼；解密時，利用陷門原理，由密碼及關鍵數(shù)導出中間密碼，并根據私有密鑰收縮求出明碼。    本算法的一般數(shù)學描述為：    設X為明碼       為密碼    &#

4、160;  為中間密碼       為公有密鑰 (公開)       為私有密鑰 (保密)    加密過程：     解密過程：                   在密碼分析的攻擊中，密鑰占有極其重要的地位，由于公開密鑰密碼體制自身的特點，私有密鑰

5、的設計成為該密碼體制中的關鍵技術。本文所述的關鍵是以“陷門收縮”理論為基礎構造產生出符合收縮計算規(guī)律的私有密鑰。私有密鑰的構造產生方法，體現(xiàn)了本算法的特點，使該算法具有較高的保密強度。3本算法的原理與方法3.1  算法中用到的一些變量及私有密鑰的構造原理(1)設要求加密的數(shù)據為X(明文)，即     ,    (0，1)    (2)關鍵數(shù)據r，t，s滿足      (r，t)1     

6、; r>t      ts(mod  r)1    (3)設計構造一組私有密鑰(解密密鑰) 使其滿足      ,   =2，3，64      r>     算法中應將r，s，t， 私有保存。    (4)求一組加密密鑰  (公開)，使其滿足     &#

7、160;     t(mod  r)3.2  加密過程           密文： 3.3  解密過程       (1)求關鍵數(shù)s，因為          st(mod  r)1       

8、60;  (r，t)1    所以可利用歐幾里得算法求得s。       (2)求中間密碼 ，有           s(mod  r)       (3)收縮求解 ，有              &

9、#160;               1      當 時          即                  0   &#

10、160;  其它                 1      當 時                          

11、;                   ( =n-1,n-2,3,2,1 )  0         其它 4.  私有密鑰的構造與密碼長度分析4.1  私有密鑰的構造私有密鑰的設計構造是本文的目的和重點，也是實現(xiàn)本算法的關鍵。假設一個明碼的長度為64bit，即為  ( 為0或1)，私有密鑰 的個數(shù)應

12、與明碼的長度相等，即i=64。由數(shù)論中的收縮理論可知私有密鑰  應滿足如下公式：             =2，3，64    因此對私有密鑰可進行如下構造：    (1)產生一組隨機整數(shù) ，0 64    (2)構造  ，    1n65使 滿足   ，為符合收縮計算規(guī)律的私有密鑰。它是由困難的收縮問題轉換為易解的收

13、縮問題，求解明碼X的關鍵所在， 也是算法的核心所在。對于掌握了私有密鑰的人來說解密容易，而對于局外人，不知道私有密鑰則求解卻十分困難，包括解密與求解該私有密鑰。4.2  密碼長度分析    如前所述私有密鑰 是由64個隨機數(shù)  (0 64)，根據              =2，3，64    的理論按照公式   構造產生出來的，即：   

14、;            由于 64，其最大值為 =64，據此可分析 可能達到的最大值。因為     那么取 =64，則             因為r>     又因為     所以取r     已知 r-1    

15、60;                          (r-1)           由此可知密文的最大長度可能達到 ， 因此加密后的密碼長度將大于或等于明碼長度(64bit)，因此若加密過程中每次從文件中取8個字節(jié)長的明碼進行加密，那么解密過程中就要每次從加密后的

16、文件中取10個字節(jié)長的密文進行解密。5. 算法的保密強度分析5.1  密碼體制的安全性    密碼體制的安全性在于：一是密鑰的管理。包括密鑰的產生、選擇、傳遞、改變以及取消等安全措施。二是加密、解密算法的設計。即使已知明文X 和相對應的密文Y，甚至掌握了加、解密算法本身，也很難計算出密鑰來， 因而就不可能根據未被破譯的密文，得到原來的明文。由此可知，密碼體制的保密性應取決于對密鑰的保密，而不是算法的保密。這是一個好的密碼體制所應該具備的特征。公鑰密碼體制正具備這樣的優(yōu)點：它公開加密算法和加密密鑰，只對解密密鑰進行保密。   

17、 密碼算法要能夠挫敗對方的攻擊，必須使明文成為密文和密鑰的一個足夠復雜的數(shù)學函數(shù)，并使每個密鑰成為密文和明文的一個足夠復雜的函數(shù)。對于公鑰密碼體制來說，一般保密強度是建立在一種特定的已知問題求解困難這個假設之上的。如RSA公鑰密碼和背包公鑰密碼， 前者其密碼強度建立在具有大素數(shù)因子的合數(shù)因子分解困難這個著名的數(shù)學難題之上，后者其密碼強度建立在著名的古典背包問題的數(shù)學難題之上。因此，公鑰密碼算法本身就應具有較強的保密強度。對于密鑰，由于其在密碼分析攻擊中占有極其重要的地位，而公鑰密碼又只對其解密密鑰進行保密，因此密鑰的設計和保護就成為該加密體制的關鍵技術。5.2  算法的保密強度分析&

18、#160;   一般來說，對密碼的破譯方法有兩種手段：一是采用頻率分析法(即窮舉法)，即以借助機器來試驗可能的取值；二是采用對密文分析的手段，即找到密文中的一些特殊性，或在掌握了部分明文的基礎上對密文進行分析。     對于本算法采用第一種破譯手段是不可行的， 由于該算法明文 的長度為64bit，則可能的X取值有                  若對X的每一取值計算

19、 ，并將結果與密文 比較，若相等，則 就是所求。 假如用一臺每秒作10億次運算的處理器，進行上述算法的窮舉試驗的時間復雜性是( )，所花費的機器時間需要約21296天，即大約58年的時間。若用1000個處理器，則需要21天，因此這種破譯方法顯然不切實際的。    對于本算法采用第二種破譯手段也是無效的。首先該算法即不是“變形”密碼也不是“變位”密碼，其密文不存在“變形”和“變位”特性：其次通過密碼分析獲知的信息來得知X成為計算上的不可行。 本算法是基于一種特定的陷門單向函數(shù)，利用秘密陷門信息 ，r，s，t，使公開密鑰 不能為破譯密文提供信息，在不知道 陷門信息的情況下，僅根據已知的 和加密算法，用求逆的方法求解 將會遇到特定的計算難題，在多項式時間內無解，并且至今尚無有效的求解算法。    對于密鑰的攻擊，由于該算法的私有密鑰(解密密鑰)   ( =1，2，64) 的最大長度可達 ，因此， 由上述可知用窮舉法來求解該算法的私有密鑰是不可行的，64個私有密鑰窮舉其中一個，可能取值就