5.3.1 古典密碼算法
古典密碼大都比較簡單,這些加密方法是根據(jù)字母的統(tǒng)計特性和語言學知識加密的,在可用計算機進行密碼分析的今天,很容易被破譯。雖然現(xiàn)在很少采用,但研究這些密碼算法的原理,對于理解、構造和分析現(xiàn)代密碼是十分有益的。表5-1給出了英文字母在書報中出現(xiàn)的頻率統(tǒng)計。
表5-1 英文字母在書報中出現(xiàn)的頻率
|
字母
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
頻率
|
13.05
|
9.02
|
8.21
|
7.81
|
7.28
|
6.77
|
6.64
|
6.64
|
5.58
|
4.11
|
3.60
|
2.93
|
2.88
|
字母
|
N
|
O
|
P
|
Q
|
R
|
S
|
T
|
U
|
V
|
W
|
X
|
Y
|
Z
|
頻率
|
2.77
|
2.62
|
2.15
|
1.51
|
1.49
|
1.39
|
1.28
|
1.00
|
0.42
|
0.30
|
0.23
|
0.14
|
0.09
|
|
古典密碼算法主要有代碼加密、替換加密、變位加密、一次性密碼簿加密等幾種算法。 1.代碼加密 代碼加密是一種比較簡單的加密方法,它使用通信雙方預先設定的一組有確切含義的如日常詞匯、專有名詞、特殊用語等的代碼來發(fā)送消息,一般只能用于傳送一組預先約定的消息。 密文:飛機已燒熟。 明文:房子已經過安全檢查。 代碼加密的優(yōu)點是簡單好用,但多次使用后容易喪失安全性。 2.替換加密 將明文字母表M中的每個字母替換成密文字母表C中的字母。這一類密碼包括移位密碼、替換密碼、仿射密碼、乘數(shù)密碼、多項式代替密碼、密鑰短語密碼等。這種方法可以用來傳送任何信息,但安全性不及代碼加密。因為每一種語言都有其特定的統(tǒng)計規(guī)律,如英文字母中各字母出現(xiàn)的頻度相對基本固定,根據(jù)這些規(guī)律可以很容易地對替換加密進行破解。以下是幾種常用的替換加密算法。 1)移位密碼是最簡單的一類代替密碼,將字母表的字母右移k個位置,并對字母表長度作模運算,其形式為:ek(m)=(k+m)=c mod q,解密變換為:dk(c)=(m-k)=m mod q。凱撒(Caesar)密碼是對英文26個字母進行移位代替的密碼,其q=26。這種密碼之所以稱為凱撒密碼,是因為凱撒使用過k=3的這種密碼。 2)乘數(shù)密碼也是一種替換密碼,它將每個字母乘以一個密鑰k,ek(m)=km mod q,其中k和q是互素的,這樣字母表中的字母會產生一個復雜的剩余集合,若是和q不互素,則會有一些明文字母被加密成相同的密文字母,而且不是所有的字母都會出現(xiàn)在密文字母表中。異或運算(XOR)也常用于替換加密,加密:c=m XOR k,解密:m=c XOR k。 3)多名或同音替換。每個字母可加密或替換成多個密文字母,這種方法是一種一對多的映射關系,可以挫敗一般的頻度分析攻擊。 3.變位加密 變位加密不隱藏明文的字符,即明文的字母保持相同,但其順序被打亂重新排列成另一種不同的格式,由于密文字符與明文字符相同,密文中字母的出現(xiàn)頻率與明文中字母的出現(xiàn)頻率相同,密碼分析者可以很容易地由此進行判別。雖然許多現(xiàn)代密碼也使用換位,但由于它對存儲要求很大,有時還要求消息為某個特定的長度,因而比較少用。以下介紹幾種常見的變位加密算法。 1)簡單變位加密。預先約定好一組數(shù)字表示密鑰,將文字依次寫在密鑰下,再按數(shù)字次序重新組織文字實現(xiàn)加密,也有人喜歡將明文逆序輸出作為密文。例如 密鑰:5 2 4 1 6 3 (密文排列次序) 明文:信息安全技術 密文:技息全信術安 2)列變位法。將明文字符分割成個數(shù)固定的分組(如5個一組,5即為密鑰?。?,按一組一行的次序整齊排列,最后不足一組用任意字符填充,完成后按列讀取即成密文。如明文是:InformationSecurityTechnology,則分組排列為: I n f o r m a t i o n S e c u r i t y T e c h n o l o g y 則密文是:ImnrelnaSicoftethgoicynyrouTo ,這里的密鑰是數(shù)字5。解密過程則是按列排列密文,再按行讀取即可。 3)矩陣變位加密。將明文中的字母按給定的順序安排在一個矩陣中,然后用另一種順序選出矩陣的字母來產生密文。一般為按列變換次序,如原列次序為1234,現(xiàn)為2413。如將明文Network Security按行排列在3×6矩陣中,如下所示: 1 2 3 4 5 6 N e t w o r k S e c u r i t y 給定一個置換: ,根據(jù)給定的次序,按5、2、6、4、1、3的列序重新排列,得到:
5 2 6 4 1 3 o e r w N t c u e k S i y r t 所以,密文為:oerwNtc uekS i yrt。解密過程正好相反,按序排列密文后,通過列置換再按行讀取數(shù)據(jù)即可。 4.一次性密碼簿加密 一次性密碼簿加密具有代碼加密的可靠性,又保持了替換加密的靈活性,密碼簿每一頁都是不同的代碼表,可用一頁上的代碼來加密一些詞,用后銷毀,再用另一頁加密另一些詞,直到全部的明文完成加密,破譯的唯一方法就是獲取一份相同的密碼簿。 一次性密碼簿加密,要求密碼簿至少不小于明文長度,即不得重復用來加密明文的不同部分,否則密文就會呈現(xiàn)出某種規(guī)律性,也就可能被破譯。一般這種加密方法只用于高度保密的場合下,因為如何將至少同長度的密碼簿護送到接收端是一個大代價的行動。
5.3.2 單鑰加密算法
傳統(tǒng)加密方法的統(tǒng)計特性是此類算法致命的缺陷。為了提高保密強度,可將這幾種加密算法結合使用,形成秘密密鑰加密算法。由于可以采用計算機硬件和軟件相結合來實現(xiàn)加密和解密,算法的結構可以很復雜,有很長的密鑰,使破譯很困難,甚至不可能。由于算法難以破譯,可將算法公開,攻擊者得不到密鑰,也就不能破譯,因此這類算法的保密性完全依賴于密鑰的保密,且加密密鑰和解密密鑰完全相同或等價,又稱為對稱密鑰加密算法,其加密模式主要有序列密碼(也稱流密碼)和分組密碼兩種方式。 流密碼是將明文劃分成字符(如單個字母),或其編碼的基本單元(如0、1數(shù)字),字符分別與密鑰流作用進行加密,解密時以同步產生的同樣的密鑰流解密。流密碼的強度完全依賴于密鑰流序列的隨機性和不可預測性,其核心問題是密鑰流生成器的設計,流密碼主要應用于政府和軍事等國家要害部門。根據(jù)密鑰流是否依賴于明文流,可將流密碼分為同步流密碼和自同步流密碼,目前,同步流密碼較常見。由于自同步流密碼系統(tǒng)一般需要密文反饋,因而使得分析工作復雜化,但其具有抵抗密文搜索攻擊和認證功能等優(yōu)點,所以這種流密碼也是值得關注的研究方向。 分組密碼是將明文消息編碼表示后的數(shù)字序列x1,x2,…,xi,…,劃分為長為m的組x=(xo,xl,…,xm-1),各組(長為m的矢量),分別在密鑰k=(ko,k1,…,kL-1)控制下變換成等長的輸出數(shù)字序列y=(yo,y1,…,yn-1)(長為n的矢量),其加密函數(shù)E:Vn×K→Vn,Vn是n維矢量空間,K為密鑰空間。它與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應時刻輸入的明文數(shù)字有關,而是還與一組長為m的明文數(shù)字有關。在相同密鑰條件下,分組密碼對長為m的輸入明文組所實施的變換是等同的,所以只需要研究對任一組明文數(shù)字的變換規(guī)則。這種密碼實質上是字長為m的數(shù)字序列的代替密碼。通常取n=m,若n>m,則為有數(shù)據(jù)擴展的分組密碼,若n<m,則為有數(shù)據(jù)壓縮的分組密碼。 圍繞單鑰密鑰體制,密碼學工作者已經開發(fā)了眾多行之有效的單鑰加密算法,并且對基于這些算法的軟硬件實現(xiàn)進行了大量的工作。常用的單鑰加密算法有DES算法、IDEA算法。 1.數(shù)據(jù)加密標準DES算法 DES算法的發(fā)明人是IBM公司的W.Tuchman和C.Meyer,于1971-1972年研制成功。美國商業(yè)部的國家標準局NBS于1973年5月和1974年8月兩次發(fā)布通告,公開征求用于電子計算機的加密算法,經評選從一大批算法中采納了IBM的LUCIFER方案,該算法于1976年11月被美國政府采用,DES隨后被美國國家標準局和美國國家標準協(xié)會(American National Standard Institute,ANSI)承認。1977年1月以數(shù)據(jù)加密標準DES(Data Encryption Standard)的名稱正式向社會公布,并于1977年7月15日生效。 DES算法是一種對二元數(shù)據(jù)進行加密的分組密碼,數(shù)據(jù)分組長度為64bit(8byte),密文分組長度也是64bit,沒有數(shù)據(jù)擴展。密鑰長度為64bit,其中有效密鑰長度56bit,其余8bit為奇偶校驗。DES的整個體制是公開的,系統(tǒng)的安全性主要依賴密鑰的保密,其算法主要由初始置換IP、16輪迭代的乘積變換、逆初始置換IP-1以及16個子密鑰產生器構成。56位DES加密算法的框圖如圖5-9所示。

|
圖5-9 56位DES加密算法的框圖
|
DES加密算法框圖明文加密過程如下: 1)將長的明文分割成64位的明文段,逐段加密。將64位明文段首先進行與密鑰無關的初始變位處理。 2)初始變位后結果,要進行16次的迭代處理,每次迭代的框圖相同,但參加迭代的密鑰不同,密鑰共56位,分成左右兩個28位,第i次迭代用密鑰Ki參加操作,第i次迭代完后,左右28位的密鑰都作循環(huán)移位,形成第i+1次迭代的密鑰。 3)經過16次迭代處理后的結果進行左、右32位的互換位置。 4)將結果進行一次與初始變位相逆的還原變換處理得到了64位的密文。 上述加密過程中的基本運算包括變位、替換和異或運算。DES算法是一種對稱算法,既可用于加密,也可用于解密。解密時的過程和加密時相似,但密鑰使用順序剛好相反。 DES是一種分組密碼,是兩種基本的加密組塊替代和換位的細致而復雜的結合,它通過反復依次應用這兩項技術來提高其強度,經過共16輪的替代和換位的變換后,使得密碼分析者無法獲得該算法一般特性以外更多的信息。對于DES加密,除了嘗試所有可能的密鑰外,還沒有已知的技術可以求得所用的密鑰。 DES算法可以通過軟件或硬件實現(xiàn)。 DES算法的安全性。DES的出現(xiàn)是密碼學上的一個創(chuàng)舉,由于其公開了密碼體制及其設計細節(jié),因此其安全性完全依賴于其所用的密鑰,關于DES的安全問題,學術界有過激烈的爭論,普遍的印象是密鑰僅有56bit有點偏短。Diffie和Hellman曾設想花千萬美元造一臺專用機,渴望一天內找到DES的一個密鑰,其基本思想是窮舉,即強行攻擊(需要255次嘗試)。此外,1990年,Eli Biham和Adi Shamir提出用“微分分析法”對DES進行攻擊,實際需要247次嘗試,也只有理論上的價值。后來,有人提出一種明文攻擊法——“線性逼近法”,它需要243對明文-密文對,在這樣強的要求條件下,要十多臺工作站協(xié)同工作花費十幾天才能完成攻擊。表5-2為不同條件下DES攻擊時間的預測。
表5-2 不同條件下DES攻擊時間的預測
|
攻擊者類型
密鑰長度
|
個人攻擊
|
小組攻擊
|
院校網絡攻擊
|
大公司
|
軍事情報機構
|
計算資源
(假設)
|
1臺高性能計算機
|
16臺高性能計算機
|
256臺高性能計算機
|
大型機
(百萬美元級)
|
大型機
(百萬美元級)及先進攻擊技術
|
40 bit
|
數(shù)周
|
數(shù)日
|
數(shù)小時
|
數(shù)毫秒
|
數(shù)微秒
|
56 bit
|
數(shù)百年
|
數(shù)十年
|
數(shù)年
|
數(shù)小時
|
數(shù)秒鐘
|
64 bit
|
數(shù)千年
|
數(shù)百年
|
數(shù)十年
|
數(shù)日
|
數(shù)分鐘
|
80 bit
|
不可能
|
不可能
|
不可能
|
數(shù)百年
|
數(shù)百年
|
128 bit
|
不可能
|
不可能
|
不可能
|
不可能
|
數(shù)千年
|
|
在1977年,人們估計要耗資2000萬美元才能建成一個專門計算機用于DES的解密,而且需要12h的破解才能得到結果。1997年開始,RSA公司發(fā)起了一個稱作“向DES挑戰(zhàn)”的競技賽。1997年1月,用了96天時間,成功地破解了用DES加密的一段信息;一年之后的記錄是41天;1998年7月,“第二屆DES挑戰(zhàn)賽(DES Challenge II-2)” 把破解DES的時間縮短到了只需56h;“第三屆DES挑戰(zhàn)賽(DES Challenge III)”把破解DES的時間縮短到了只需22.5h ??傊S著各種針對DES新攻擊手法的不斷出現(xiàn),DES已感覺到了實際的威脅,也許DES即將完成其歷史使命。盡管如此,自DES正式成為美國國家標準以來,已有許多公司設計并推廣了實現(xiàn)DES算法的產品,有的設計專用LSI器件或芯片,有的用現(xiàn)成的微處理器實現(xiàn),有的只限于實現(xiàn)DES算法,有的則可以運行各種工作模式。 2.國際數(shù)據(jù)加密算法IDEA 近年來,新的分組加密算法不斷出現(xiàn),IDEA就是其中的杰出代表。IDEA是International Data Encryption Algorithm的縮寫,即國際數(shù)據(jù)加密算法。它是根據(jù)中國學者朱學嘉博士與著名密碼學家James Massey于1990年聯(lián)合提出的建議標準算法PES(Proposed Encryption Standard)改進而來的。它的明文與密文塊都是64bit,密鑰長度為128bit,作為單鑰體制的密碼,其加密與解密過程相似,只是密鑰存在差異,IDEA無論是采用軟件還是硬件實現(xiàn)都比較容易,而且加、解密的速度很快。 IDEA算法是面向塊的單鑰密碼算法,它的安全性與DES類似,不在于算法的保密,而是密鑰的安全性。 IDEA的密鑰長為128bit,采用窮舉搜索進行破譯,則需要進行2128次嘗試,這將是用同樣方法對付DES的272倍工作量。目前,尚未見到成功對IDEA進行攻擊的報道,有關學者進行分析也表明IDEA對于線性和差分攻擊是安全的。此外,將IDEA的字長由16bit加長為32bit,密鑰相應長為256bit,采用232模加,232+1模乘,可以進一步強化IDEA的安全性能。 3.單鑰密碼算法性能分析 前面詳細介紹了單鑰密碼體制的典型代表DES算法和IDEA算法,其他一些有意義的算法有SAFER K-64(Secure And Fast Encryption Routine)、GOST、RC-4、RC-5、Blowfish、CAST-128等。為了提高單鑰密碼的安全性,人們還將分組密碼算法通過組合以得到新的分組密碼算法,但這種組合密碼的安全性必須經仔細檢驗后才能付諸實用,如二重DES加密、三重DES加密等。 由于各種加密算法的具體實現(xiàn)方法互不相同,因此其性能也存在較大差異,表5-3對單鑰密碼體制的主要算法在總體實現(xiàn)、速度、安全性能和改進措施幾個方面進行了比較,并基于比較結果給出了各算法合適的應用場合。
表5-3 單鑰密碼算法性能比較表
|
名稱
|
實現(xiàn)方式
|
運算速度
|
安 全 性
|
改進措施
|
應用場合
|
DES
|
40-56bit
密鑰
|
一般
|
完全依賴密鑰,易受窮舉搜索法攻擊
|
雙重、三重DES,AES
|
適用于硬件實現(xiàn)
|
IDEA
|
128bit密鑰
8輪迭代
|
較慢
|
軍事級,可抗差值分析和相關分析
|
加長字長為32bit、密鑰為256bit,采用232模加、232+1模乘
|
適用于ASIC設計
|
GOST
|
256bit密鑰
32輪迭代
|
較快
|
軍事級
|
加大迭代輪數(shù)
|
S盒可隨機秘
密選擇,便于軟件實現(xiàn)
|
Blowfish
|
256-448bit
密鑰、16輪迭代
|
最快
|
軍事級、可通過改變密鑰長度調整安全性
|
|
適合固定密鑰場合,不適合常換密鑰和智能卡
|
RC4
|
密鑰長度可變
|
快DESl0倍
|
對差分攻擊和線性攻擊具有免疫能力,高度非線性
|
密鑰長度放寬到64bit
|
算法簡單,易于編程實現(xiàn)
|
RC5
|
密鑰長度和迭代輪數(shù)均可變
|
速度可根據(jù)
三個參數(shù)的
值進行選擇
|
六輪以上時即可抗線性攻擊、通過調整字長、密鑰長度和迭代輪數(shù)可以在安全性和速度上取得折中
|
引入數(shù)據(jù)相倚轉
|
適用于不同字長的微處理器
|
CASTl28
|
密鑰長度可變、16輪迭代
|
較快
|
可抵抗線性和差分攻擊
|
增加密鑰長度、形成CAST256
|
適用于PC機和
UNIX工作站
|
|
5.3.3 雙鑰加密算法
雙鑰密碼體制的加密密鑰和解密密鑰不相同,它們的值不等,屬性也不同,一個是可公開的公鑰,另一個則是需要保密的私鑰。雙鑰密碼體制的特點是加密能力和解密能力是分開的,即加密與解密的密鑰不同,或從一個難以推出另一個。它可以實現(xiàn)多個用戶用公鑰加密的消息只能由一個用戶用私鑰解讀,或反過來,由一個用戶用私鑰加密的消息可被多個用戶用公鑰解讀。其中前一種方式可用于在公共網絡中實現(xiàn)保密通信;后一種方式可用于在認證系統(tǒng)中對消息進行數(shù)字簽名。 雙鑰加密算法的主要特點如下: 1)用加密密鑰PK對明文m加密后得到密文,再用解密密鑰SK對密文解密,即可恢復出明文m,即 DSK(EPK(m))=m 2)加密密鑰不能用來解密,即: DPK(EPK(m))≠m ;DSK(ESK(m))≠m 3)用SK加密的信息只能用PK解密;用PK加密的信息只能用SK解密。 4)從已知的PK不可能推導出SK。 5)加密和解密的運算可對調,即 EPK(DSK(m))=m 雙鑰密碼體制大大簡化了復雜的密鑰分配管理問題,但公鑰算法要比私鑰算法慢得多(約1000倍)。因此,在實際通信中,雙鑰密碼體制主要用于認證(比如數(shù)字簽名、身份識別等)和密鑰管理等,而消息加密仍利用私鑰密碼體制。下面介紹雙鑰密碼體制的杰出代表――RSA加密算法。 1.RSA算法 RSA體制是由R.L.Rivest、A.Shamir和L.Adleman設計的用數(shù)論構造雙鑰的方法,它既可用于加密,也可用于數(shù)字簽名。RSA得到了世界上的最廣泛應用,ISO在1992年頒布的國際標準X.509中,將RSA算法正式納入國際標準。1999年,美國參議院已經通過了立法,規(guī)定電子數(shù)字簽名與手寫簽名的文件、郵件在美國具有同等的法律效力。在Internet中廣泛使用的電子郵件和文件加密軟件PGP(Pretty Good Privacy)也將RSA作為傳送會話密鑰和數(shù)字簽名的標準算法。RSA算法的安全性建立在數(shù)論中“大數(shù)分解和素數(shù)檢測”的理論基礎上。 (1)大數(shù)分解 雙鑰密碼體制算法按由公鑰推算出密鑰的途徑可分為兩類:一類是基于素數(shù)因子分解問題的(如RSA算法),它的安全性基于100位十進制數(shù)以上的所謂“大數(shù)”的素數(shù)因子分解的難題,這是一個至今沒有有效快速算法的數(shù)學難題。另一類是基于離散對數(shù)問題的(如EIGamal算法),其安全性基于計算離散對數(shù)的困難性。離散對數(shù)問題是指模指數(shù)運算的逆問題,即找出一個數(shù)的離散對數(shù)。一般地,計算離散對數(shù)是非常困難的。 RSA算法運用了數(shù)論中的Euler同余定理:即a、r是兩個互質的自然數(shù),則az=1 (mod r),其中z為與r互質的且不大于r的自然數(shù),稱z為r的Euler指標函數(shù)。 (2)RSA算法表述 假定用戶A欲送消息m給用戶B,則RSA算法的加/解密過程為: 1)首先用戶B產生兩個大素數(shù)p和q(p、q是保密的)。 2)用戶B計算n=pq和φ(n)=(p-1)(q-1)(φ(n)是保密的)。 3)用戶B選擇一個隨機數(shù)e(0<e<φ(n)),使得(e,φ(n))=1,即e和φ互素。 4)用戶B通過計算得出d,使得d*e mod φ(n)=1(即在與n互素的數(shù)中選取與φ(n)互素的數(shù),可以通過Euclidean算法得出。d是用戶B自留且保密的,用作解密密鑰)。 5)用戶B將n及e作為公鑰公開。 6)用戶A通過公開渠道查到n和e。 7)對m施行加密變換,即EB(m)=me mod n=c。 8)用戶B收到密文c后,施行解密變換 DB(c)=cd mod n=(me mod n)d mod n=med mod n=m mod n 下面舉一個簡單的例子用于說明這個過程:令26個英文字母對應于0到25的整數(shù),即a-00,b-01,…,y-24,z-25。設,m=inclub,則m的十進制數(shù)編碼為:m=08 13 02 11 20 01。設n=3×11=33,p=3,q=11, φ(n)=2×10=20。取e=3,則d=7將n=33和e=3公開,保留d=7。 用戶A查到n和e后,將消息m加密: EB(i)=083 mod 33= 17, EB(n)=133 mod 33= 19, EB(c)=023 mod 33= 8, EB(l)=113 mod 33= 11, EB(u)=203 mod 33= 14, EB(b)=013 mod 33= 1, 則 c= EB(m) = 17 19 08 11 14 01,它對應的密文為 c=rtilob 當用戶B接到密文c后施行解密變換: DB(r) = 177 mod 33= 8,即明文i, DB(t) = 197 mod 33= 13,即明文n, DB(i) = 087 mod 33= 2,即明文c, DB(l) = 117 mod 33= 11,即明文l DB(o) = 147 mod 33= 20,即明文u, DB(b) = 017 mod 33= 1,即明文b。 (3)RSA安全性分析 RSA的保密性基于一個數(shù)學假設:對一個很大的合數(shù)進行質因數(shù)分解是不可能的!若RSA用到的兩個質數(shù)足夠大,可以保證使用目前的計算機無法分解。即RSA公開密鑰密碼體制的安全性取決于從公開密鑰(n,e)計算出秘密密鑰(n,d)的困難程度。想要從公開密鑰(n,e)算出d,只能分解整數(shù)n的因子,即從n找出它的兩個質因數(shù)p和q,但大數(shù)分解是一個十分困難的問題。RSA的安全性取決于模n分解的困難性,但數(shù)學上至今還未證明分解模就是攻擊RSA的最佳方法。盡管如此,人們還是從消息破譯、密鑰空間選擇等角度提出了針對RSA的其他攻擊方法,如迭代攻擊法、選擇明文攻擊法、公用模攻擊、低加密指數(shù)攻擊、定時攻擊法等,但其攻擊成功的概率微乎其微。 出于安全考慮,在RSA中,建議使用1024bit的n,對于重要場合n應該使用2048位。 2.ElGamal算法 RSA算法是基于素數(shù)因子分解的雙鑰密碼,而ElGamal算法則是基于離散對數(shù)問題的另一種類型的雙鑰密鑰,它既可用于加密,也可用于簽名。 (1)ElGamal算法方案 1985年,ELGamal第一次在有限域上基于離散對數(shù)問題設計了原始的ElGamal數(shù)字簽名方案。 令p是使在GF(p)域計算離散對數(shù)在多項式時間內是不可行的大素數(shù)。引進集合Zp ={0,1,2,…,p}及其子集Zp*={0,1,2,…,p-1}。令g∈Zp*,是本原元,定義:密鑰集K={(p,g,x,y):y=gx mod p},這里p,g,y是公鑰,x是用戶選擇的私鑰,x∈Zp*且gcd(x,p-1)=1。即產生密鑰對時,首先選擇一個素數(shù)p,兩個Zp*中的隨機數(shù)g和x, 計算 y = gx mod p ,則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶共享。 (2)ElGamal加、解密及其安全性 選擇隨機數(shù)k∈zp-1,且(k,p-1)=1,計算:y1=gkmod p(隨機數(shù)k被加密),y2=myk mod p,這里,m是發(fā)送明文組。密文則由y1和y2級連構成,即密文C=y1‖y2。這種加密方式的特點是,密文由明文和所選隨機數(shù)k來決定,因而是非確定性加密,一般稱之為隨機化加密,對同一明文由于不同時刻的隨機數(shù)k不同而給出不同的密文,這樣做的代價是使數(shù)據(jù)擴展1倍。 在收到密文組C后,ElGamal的解密是通過下列計算得到明文的: 
ElGamal算法的安全性是基于zP*中有限群上的離散對數(shù)的困難性的。研究表明,mod p生成的離散對數(shù)密碼可能存在陷門,這會造成有些“弱”素數(shù)p下的離散對數(shù)較容易求解,但密碼學家也發(fā)現(xiàn)可以較容易地找到這類陷門以避免選用可能產生脆弱性的這些素數(shù)。 3.雙鑰算法小結 雙鑰密鑰體制的密鑰管理和分配較簡單,尤其可方便地用于數(shù)字簽名和認證。雖然其算法都較復雜,運算量巨大,但其仍不失為一種非常有前途的加密體制,它的出現(xiàn)是密碼學發(fā)展史上的劃時代事件。上面我們分析了雙鑰密碼體制的典型代表RSA算法和ElGamal算法,還有其他一些有意義的算法,如LUC密碼、Rabin密碼,以及DSA密碼等。 對于RSA體制,可以將其推廣為有多個密鑰的雙鑰體制,即在多個密鑰中選用一部分密鑰作為加密密鑰,而另一些作為解密密鑰。同樣地,RSA還可以推廣為多簽名體制,如有k1、k2和k3三個密鑰,可將k1作為A的簽名私密鑰,k2作為B的簽名私密鑰,k3作為公開的驗證簽名用密鑰,實現(xiàn)這種多簽名體制,需要一個可信賴中心對A和B分配秘密簽名密鑰。
|