一種基于“陷門收縮”原理的公鑰算法_第1頁
一種基于“陷門收縮”原理的公鑰算法_第2頁
一種基于“陷門收縮”原理的公鑰算法_第3頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

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

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

設(shè)X為明碼

為密碼

為中間密碼

為公有密鑰(公開)

為私有密鑰(保密)

加密過程:

解密過程:①

在密碼分析的攻擊中,密鑰占有極其重要的地位,由于公開密鑰密碼體制自身的特點(diǎn),私有密鑰的設(shè)計成為該密碼體制中的關(guān)鍵技術(shù)。本文所述的關(guān)鍵是以“陷門收縮”理論為基礎(chǔ)構(gòu)造產(chǎn)生出符合收縮計算規(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è)計構(gòu)造一組私有密鑰(解密密鑰)使其滿足

①,=2,3,…,64

②r>

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

(4)求一組加密密鑰(公開),使其滿足?t(modr)3.2加密過程密文:3.3解密過程

(1)求關(guān)鍵數(shù)s,因為s?t(modr)=1(r,t)=1

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

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

(3)收縮求解,有

1

當(dāng)時

即0

其它1

當(dāng)時

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

=2,3,…,64

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

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

(2)構(gòu)造,

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

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

=2,3,…,64

的理論按照公式構(gòu)造產(chǎn)生出來的,即:

由于≤64,其最大值為=64,據(jù)此可分析可能達(dá)到的最大值。因為

那么取=64,則

因為r>

又因為

所以取r=

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

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

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

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

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

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

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

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

≡?t(modr)

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

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

最大長度可達(dá)bit,窮舉法無效。

r>

r>t,且(r,t)=1且,r,t都是保密的,因此無法由?

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論