一種基于“陷門(mén)收縮”原理的公鑰算法

一種基于“陷門(mén)收縮”原理的公鑰算法

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

本文算法的私有密鑰(解密密鑰)是在數(shù)論的“陷門(mén)收縮”理論基礎(chǔ)上由隨機(jī)產(chǎn)生加復(fù)雜構(gòu)造而生成，符合“收縮”計(jì)算規(guī)律，并利用陷門(mén)原理，由私有密鑰導(dǎo)出公有密鑰(加密密鑰)。加密時(shí)根據(jù)公有密鑰由明碼導(dǎo)出密碼；解密時(shí)，利用陷門(mén)原理，由密碼及關(guān)鍵數(shù)導(dǎo)出中間密碼，并根據(jù)私有密鑰收縮求出明碼。

本算法的一般數(shù)學(xué)描述為：

設(shè)X為明碼

為密碼

為中間密碼

為公有密鑰(公開(kāi))

為私有密鑰(保密)

加密過(guò)程：

解密過(guò)程：①

②

在密碼分析的攻擊中，密鑰占有極其重要的地位，由于公開(kāi)密鑰密碼體制自身的特點(diǎn)，私有密鑰的設(shè)計(jì)成為該密碼體制中的關(guān)鍵技術(shù)。本文所述的關(guān)鍵是以“陷門(mén)收縮”理論為基礎(chǔ)構(gòu)造產(chǎn)生出符合收縮計(jì)算規(guī)律的私有密鑰。私有密鑰的構(gòu)造產(chǎn)生方法，體現(xiàn)了本算法的特點(diǎn)，使該算法具有較高的保密強(qiáng)度。3．本算法的原理與方法3.1算法中用到的一些變量及私有密鑰的構(gòu)造原理(1)設(shè)要求加密的數(shù)據(jù)為X(明文)，即

，

∈(0，1)

(2)關(guān)鍵數(shù)據(jù)r，t，s滿足

①(r，t)＝1

②r>t

③t?s(modr)＝1

(3)設(shè)計(jì)構(gòu)造一組私有密鑰(解密密鑰)使其滿足

①，=2，3，…，64

②r>

算法中應(yīng)將r，s，t，私有保存。

(4)求一組加密密鑰(公開(kāi))，使其滿足?t(modr)3.2加密過(guò)程密文：3.3解密過(guò)程

(1)求關(guān)鍵數(shù)s，因?yàn)閟?t(modr)＝1(r，t)＝1

所以可利用歐幾里得算法求得s。

(2)求中間密碼，有?s(modr)

(3)收縮求解，有

1

當(dāng)時(shí)

即0

其它1

當(dāng)時(shí)

(=n-1，n-2，…，3，2，1)0其它4.私有密鑰的構(gòu)造與密碼長(zhǎng)度分析4.1私有密鑰的構(gòu)造私有密鑰的設(shè)計(jì)構(gòu)造是本文的目的和重點(diǎn)，也是實(shí)現(xiàn)本算法的關(guān)鍵。假設(shè)一個(gè)明碼的長(zhǎng)度為64bit，即為(為0或1)，私有密鑰的個(gè)數(shù)應(yīng)與明碼的長(zhǎng)度相等，即i=64。由數(shù)論中的收縮理論可知私有密鑰應(yīng)滿足如下公式：

=2，3，…，64

因此對(duì)私有密鑰可進(jìn)行如下構(gòu)造：

(1)產(chǎn)生一組隨機(jī)整數(shù)，0≤≤64

(2)構(gòu)造，

1≤n≤65使?jié)M足，為符合收縮計(jì)算規(guī)律的私有密鑰。它是由困難的收縮問(wèn)題轉(zhuǎn)換為易解的收縮問(wèn)題，求解明碼X的關(guān)鍵所在，也是算法的核心所在。對(duì)于掌握了私有密鑰的人來(lái)說(shuō)解密容易，而對(duì)于局外人，不知道私有密鑰則求解卻十分困難，包括解密與求解該私有密鑰。4.2密碼長(zhǎng)度分析

如前所述私有密鑰是由64個(gè)隨機(jī)數(shù)(0≤≤64)，根據(jù)

=2，3，…，64

的理論按照公式構(gòu)造產(chǎn)生出來(lái)的，即：

由于≤64，其最大值為=64，據(jù)此可分析可能達(dá)到的最大值。因?yàn)?/p>

那么取=64，則

因?yàn)閞>

又因?yàn)?/p>

所以取r＝

已知r-1?(r-1)由此可知密文的最大長(zhǎng)度可能達(dá)到，因此加密后的密碼長(zhǎng)度將大于或等于明碼長(zhǎng)度(64bit)，因此若加密過(guò)程中每次從文件中取8個(gè)字節(jié)長(zhǎng)的明碼進(jìn)行加密，那么解密過(guò)程中就要每次從加密后的文件中取10個(gè)字節(jié)長(zhǎng)的密文進(jìn)行解密。5.算法的保密強(qiáng)度分析5.1密碼體制的安全性

密碼體制的安全性在于：一是密鑰的管理。包括密鑰的產(chǎn)生、選擇、傳遞、改變以及取消等安全措施。二是加密、解密算法的設(shè)計(jì)。即使已知明文X和相對(duì)應(yīng)的密文Y，甚至掌握了加、解密算法本身，也很難計(jì)算出密鑰來(lái)，因而就不可能根據(jù)未被破譯的密文，得到原來(lái)的明文。由此可知，密碼體制的保密性應(yīng)取決于對(duì)密鑰的保密，而不是算法的保密。這是一個(gè)好的密碼體制所應(yīng)該具備的特征。公鑰密碼體制正具備這樣的優(yōu)點(diǎn)：它公開(kāi)加密算法和加密密鑰，只對(duì)解密密鑰進(jìn)行保密。

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

一般來(lái)說(shuō)，對(duì)密碼的破譯方法有兩種手段：一是采用頻率分析法(即窮舉法)，即以借助機(jī)器來(lái)試驗(yàn)可能的取值；二是采用對(duì)密文分析的手段，即找到密文中的一些特殊性，或在掌握了部分明文的基礎(chǔ)上對(duì)密文進(jìn)行分析。

對(duì)于本算法采用第一種破譯手段是不可行的，由于該算法明文的長(zhǎng)度為64bit，則可能的X取值有若對(duì)X的每一取值計(jì)算，并將結(jié)果與密文比較，若相等，則就是所求。假如用一臺(tái)每秒作10億次運(yùn)算的處理器，進(jìn)行上述算法的窮舉試驗(yàn)的時(shí)間復(fù)雜性是Ｏ()，所花費(fèi)的機(jī)器時(shí)間需要約21296天，即大約58年的時(shí)間。若用1000個(gè)處理器，則需要21天，因此這種破譯方法顯然不切實(shí)際的。

對(duì)于本算法采用第二種破譯手段也是無(wú)效的。首先該算法即不是“變形”密碼也不是“變位”密碼，其密文不存在“變形”和“變位”特性：其次通過(guò)密碼分析獲知的信息來(lái)得知X成為計(jì)算上的不可行。本算法是基于一種特定的陷門(mén)單向函數(shù)，利用秘密陷門(mén)信息，r，s，t，使公開(kāi)密鑰不能為破譯密文提供信息，在不知道陷門(mén)信息的情況下，僅根據(jù)已知的和加密算法，用求逆的方法求解將會(huì)遇到特定的計(jì)算難題，在多項(xiàng)式時(shí)間內(nèi)無(wú)解，并且至今尚無(wú)有效的求解算法。

對(duì)于密鑰的攻擊，由于該算法的私有密鑰(解密密鑰)(=1，2，…，64)的最大長(zhǎng)度可達(dá)，因此，由上述可知用窮舉法來(lái)求解該算法的私有密鑰是不可行的，64個(gè)私有密鑰窮舉其中一個(gè)，可能取值就有

其次該算法的私有密鑰具有隨機(jī)和構(gòu)造雙重性質(zhì)，想通過(guò)已知的公鑰來(lái)推導(dǎo)出也是不可能的。

≡?t(modr)

是隨機(jī)產(chǎn)生加構(gòu)造而確定

(為隨機(jī)整數(shù))

最大長(zhǎng)度可達(dá)bit，窮舉法無(wú)效。

r>

r>t，且(r，t)＝1且，r，t都是保密的，因此無(wú)法由?