5.3.1  古典密碼算法

　　古典密碼大都比較簡單，這些加密方法是根據(jù)字母的統(tǒng)計(jì)特性和語言學(xué)知識(shí)加密的，在可用計(jì)算機(jī)進(jìn)行密碼分析的今天，很容易被破譯。雖然現(xiàn)在很少采用，但研究這些密碼算法的原理，對(duì)于理解、構(gòu)造和分析現(xiàn)代密碼是十分有益的。表5-1給出了英文字母在書報(bào)中出現(xiàn)的頻率統(tǒng)計(jì)。

　　古典密碼算法主要有代碼加密、替換加密、變位加密、一次性密碼簿加密等幾種算法。
　　1．代碼加密
　　代碼加密是一種比較簡單的加密方法，它使用通信雙方預(yù)先設(shè)定的一組有確切含義的如日常詞匯、專有名詞、特殊用語等的代碼來發(fā)送消息，一般只能用于傳送一組預(yù)先約定的消息。
　　密文：飛機(jī)已燒熟。
　　明文：房子已經(jīng)過安全檢查。
　　代碼加密的優(yōu)點(diǎn)是簡單好用，但多次使用后容易喪失安全性。
　　2．替換加密
　　將明文字母表M中的每個(gè)字母替換成密文字母表C中的字母。這一類密碼包括移位密碼、替換密碼、仿射密碼、乘數(shù)密碼、多項(xiàng)式代替密碼、密鑰短語密碼等。這種方法可以用來傳送任何信息，但安全性不及代碼加密。因?yàn)槊恳环N語言都有其特定的統(tǒng)計(jì)規(guī)律，如英文字母中各字母出現(xiàn)的頻度相對(duì)基本固定，根據(jù)這些規(guī)律可以很容易地對(duì)替換加密進(jìn)行破解。以下是幾種常用的替換加密算法。
　　1）移位密碼是最簡單的一類代替密碼，將字母表的字母右移k個(gè)位置，并對(duì)字母表長度作模運(yùn)算，其形式為：e_k(m)=(k+m)=c mod q，解密變換為：d_k(c)=(m-k)=m mod q。凱撒(Caesar)密碼是對(duì)英文26個(gè)字母進(jìn)行移位代替的密碼，其q=26。這種密碼之所以稱為凱撒密碼，是因?yàn)閯P撒使用過k=3的這種密碼。
　　2）乘數(shù)密碼也是一種替換密碼，它將每個(gè)字母乘以一個(gè)密鑰k，e_k(m)=km mod q，其中k和q是互素的，這樣字母表中的字母會(huì)產(chǎn)生一個(gè)復(fù)雜的剩余集合，若是和q不互素，則會(huì)有一些明文字母被加密成相同的密文字母，而且不是所有的字母都會(huì)出現(xiàn)在密文字母表中。異或運(yùn)算（XOR）也常用于替換加密，加密：c=m XOR k，解密：m=c XOR k。
　　3）多名或同音替換。每個(gè)字母可加密或替換成多個(gè)密文字母，這種方法是一種一對(duì)多的映射關(guān)系，可以挫敗一般的頻度分析攻擊。
　　3．變位加密
　　變位加密不隱藏明文的字符，即明文的字母保持相同，但其順序被打亂重新排列成另一種不同的格式，由于密文字符與明文字符相同，密文中字母的出現(xiàn)頻率與明文中字母的出現(xiàn)頻率相同，密碼分析者可以很容易地由此進(jìn)行判別。雖然許多現(xiàn)代密碼也使用換位，但由于它對(duì)存儲(chǔ)要求很大，有時(shí)還要求消息為某個(gè)特定的長度，因而比較少用。以下介紹幾種常見的變位加密算法。
　　1）簡單變位加密。預(yù)先約定好一組數(shù)字表示密鑰，將文字依次寫在密鑰下，再按數(shù)字次序重新組織文字實(shí)現(xiàn)加密，也有人喜歡將明文逆序輸出作為密文。例如
　　　　密鑰：5 2 4 1 6 3   (密文排列次序)
　　　　明文：信息安全技術(shù)
　　　　密文：技息全信術(shù)安
　　2）列變位法。將明文字符分割成個(gè)數(shù)固定的分組（如5個(gè)一組，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）矩陣變位加密。將明文中的字母按給定的順序安排在一個(gè)矩陣中，然后用另一種順序選出矩陣的字母來產(chǎn)生密文。一般為按列變換次序，如原列次序?yàn)?234，現(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   
給定一個(gè)置換：，根據(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．一次性密碼簿加密
　　一次性密碼簿加密具有代碼加密的可靠性，又保持了替換加密的靈活性，密碼簿每一頁都是不同的代碼表，可用一頁上的代碼來加密一些詞，用后銷毀，再用另一頁加密另一些詞，直到全部的明文完成加密，破譯的唯一方法就是獲取一份相同的密碼簿。
　　一次性密碼簿加密，要求密碼簿至少不小于明文長度，即不得重復(fù)用來加密明文的不同部分，否則密文就會(huì)呈現(xiàn)出某種規(guī)律性，也就可能被破譯。一般這種加密方法只用于高度保密的場合下，因?yàn)槿绾螌⒅辽偻L度的密碼簿護(hù)送到接收端是一個(gè)大代價(jià)的行動(dòng)。

5.3.2  單鑰加密算法

　　傳統(tǒng)加密方法的統(tǒng)計(jì)特性是此類算法致命的缺陷。為了提高保密強(qiáng)度，可將這幾種加密算法結(jié)合使用，形成秘密密鑰加密算法。由于可以采用計(jì)算機(jī)硬件和軟件相結(jié)合來實(shí)現(xiàn)加密和解密，算法的結(jié)構(gòu)可以很復(fù)雜，有很長的密鑰，使破譯很困難，甚至不可能。由于算法難以破譯，可將算法公開，攻擊者得不到密鑰，也就不能破譯，因此這類算法的保密性完全依賴于密鑰的保密，且加密密鑰和解密密鑰完全相同或等價(jià)，又稱為對(duì)稱密鑰加密算法，其加密模式主要有序列密碼（也稱流密碼）和分組密碼兩種方式。
　　流密碼是將明文劃分成字符（如單個(gè)字母），或其編碼的基本單元（如0、1數(shù)字），字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流解密。流密碼的強(qiáng)度完全依賴于密鑰流序列的隨機(jī)性和不可預(yù)測性，其核心問題是密鑰流生成器的設(shè)計(jì)，流密碼主要應(yīng)用于政府和軍事等國家要害部門。根據(jù)密鑰流是否依賴于明文流，可將流密碼分為同步流密碼和自同步流密碼，目前，同步流密碼較常見。由于自同步流密碼系統(tǒng)一般需要密文反饋，因而使得分析工作復(fù)雜化，但其具有抵抗密文搜索攻擊和認(rèn)證功能等優(yōu)點(diǎn)，所以這種流密碼也是值得關(guān)注的研究方向。
　　分組密碼是將明文消息編碼表示后的數(shù)字序列x₁，x₂，…，x_i，…，劃分為長為m的組x=(x_o，x_l，…，x_m-1)，各組(長為m的矢量)，分別在密鑰k=(k_o，k₁，…，k_L-1)控制下變換成等長的輸出數(shù)字序列y=(y_o，y₁，…，y_n-1)(長為n的矢量)，其加密函數(shù)E：V_n×K→V_n，V_n是n維矢量空間，K為密鑰空間。它與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應(yīng)時(shí)刻輸入的明文數(shù)字有關(guān)，而是還與一組長為m的明文數(shù)字有關(guān)。在相同密鑰條件下，分組密碼對(duì)長為m的輸入明文組所實(shí)施的變換是等同的，所以只需要研究對(duì)任一組明文數(shù)字的變換規(guī)則。這種密碼實(shí)質(zhì)上是字長為m的數(shù)字序列的代替密碼。通常取n=m，若n>m，則為有數(shù)據(jù)擴(kuò)展的分組密碼，若n<m，則為有數(shù)據(jù)壓縮的分組密碼。
　　圍繞單鑰密鑰體制，密碼學(xué)工作者已經(jīng)開發(fā)了眾多行之有效的單鑰加密算法，并且對(duì)基于這些算法的軟硬件實(shí)現(xiàn)進(jìn)行了大量的工作。常用的單鑰加密算法有DES算法、IDEA算法。
　　1．?dāng)?shù)據(jù)加密標(biāo)準(zhǔn)DES算法
　　DES算法的發(fā)明人是IBM公司的W.Tuchman和C.Meyer，于1971-1972年研制成功。美國商業(yè)部的國家標(biāo)準(zhǔn)局NBS于1973年5月和1974年8月兩次發(fā)布通告，公開征求用于電子計(jì)算機(jī)的加密算法，經(jīng)評(píng)選從一大批算法中采納了IBM的LUCIFER方案，該算法于1976年11月被美國政府采用，DES隨后被美國國家標(biāo)準(zhǔn)局和美國國家標(biāo)準(zhǔn)協(xié)會(huì)(American National Standard Institute，ANSI)承認(rèn)。1977年1月以數(shù)據(jù)加密標(biāo)準(zhǔn)DES（Data Encryption Standard）的名稱正式向社會(huì)公布，并于1977年7月15日生效。
　　DES算法是一種對(duì)二元數(shù)據(jù)進(jìn)行加密的分組密碼，數(shù)據(jù)分組長度為64bit(8byte)，密文分組長度也是64bit，沒有數(shù)據(jù)擴(kuò)展。密鑰長度為64bit，其中有效密鑰長度56bit，其余8bit為奇偶校驗(yàn)。DES的整個(gè)體制是公開的，系統(tǒng)的安全性主要依賴密鑰的保密，其算法主要由初始置換IP、16輪迭代的乘積變換、逆初始置換IP^-1以及16個(gè)子密鑰產(chǎn)生器構(gòu)成。56位DES加密算法的框圖如圖5-9所示。

DES加密算法框圖明文加密過程如下：
　　1）將長的明文分割成64位的明文段，逐段加密。將64位明文段首先進(jìn)行與密鑰無關(guān)的初始變位處理。
　　2）初始變位后結(jié)果，要進(jìn)行16次的迭代處理，每次迭代的框圖相同，但參加迭代的密鑰不同，密鑰共56位，分成左右兩個(gè)28位，第i次迭代用密鑰K_i參加操作，第i次迭代完后，左右28位的密鑰都作循環(huán)移位，形成第i+1次迭代的密鑰。
　　3）經(jīng)過16次迭代處理后的結(jié)果進(jìn)行左、右32位的互換位置。
　　4）將結(jié)果進(jìn)行一次與初始變位相逆的還原變換處理得到了64位的密文。
　　上述加密過程中的基本運(yùn)算包括變位、替換和異或運(yùn)算。DES算法是一種對(duì)稱算法，既可用于加密，也可用于解密。解密時(shí)的過程和加密時(shí)相似，但密鑰使用順序剛好相反。
　　DES是一種分組密碼，是兩種基本的加密組塊替代和換位的細(xì)致而復(fù)雜的結(jié)合，它通過反復(fù)依次應(yīng)用這兩項(xiàng)技術(shù)來提高其強(qiáng)度，經(jīng)過共16輪的替代和換位的變換后，使得密碼分析者無法獲得該算法一般特性以外更多的信息。對(duì)于DES加密，除了嘗試所有可能的密鑰外，還沒有已知的技術(shù)可以求得所用的密鑰。
　　DES算法可以通過軟件或硬件實(shí)現(xiàn)。
　　DES算法的安全性。DES的出現(xiàn)是密碼學(xué)上的一個(gè)創(chuàng)舉，由于其公開了密碼體制及其設(shè)計(jì)細(xì)節(jié)，因此其安全性完全依賴于其所用的密鑰，關(guān)于DES的安全問題，學(xué)術(shù)界有過激烈的爭論，普遍的印象是密鑰僅有56bit有點(diǎn)偏短。Diffie和Hellman曾設(shè)想花千萬美元造一臺(tái)專用機(jī)，渴望一天內(nèi)找到DES的一個(gè)密鑰，其基本思想是窮舉，即強(qiáng)行攻擊（需要2⁵⁵次嘗試）。此外，1990年，Eli Biham和Adi Shamir提出用“微分分析法”對(duì)DES進(jìn)行攻擊，實(shí)際需要2⁴⁷次嘗試，也只有理論上的價(jià)值。后來，有人提出一種明文攻擊法——“線性逼近法”，它需要2⁴³對(duì)明文-密文對(duì)，在這樣強(qiáng)的要求條件下，要十多臺(tái)工作站協(xié)同工作花費(fèi)十幾天才能完成攻擊。表5-2為不同條件下DES攻擊時(shí)間的預(yù)測。

在1977年，人們估計(jì)要耗資2000萬美元才能建成一個(gè)專門計(jì)算機(jī)用于DES的解密，而且需要12h的破解才能得到結(jié)果。1997年開始，RSA公司發(fā)起了一個(gè)稱作“向DES挑戰(zhàn)”的競技賽。1997年1月，用了96天時(shí)間，成功地破解了用DES加密的一段信息；一年之后的記錄是41天；1998年7月，“第二屆DES挑戰(zhàn)賽（DES Challenge II-2）” 把破解DES的時(shí)間縮短到了只需56h；“第三屆DES挑戰(zhàn)賽（DES Challenge III）”把破解DES的時(shí)間縮短到了只需22.5h 。總之，隨著各種針對(duì)DES新攻擊手法的不斷出現(xiàn)，DES已感覺到了實(shí)際的威脅，也許DES即將完成其歷史使命。盡管如此，自DES正式成為美國國家標(biāo)準(zhǔn)以來，已有許多公司設(shè)計(jì)并推廣了實(shí)現(xiàn)DES算法的產(chǎn)品，有的設(shè)計(jì)專用LSI器件或芯片，有的用現(xiàn)成的微處理器實(shí)現(xiàn)，有的只限于實(shí)現(xiàn)DES算法，有的則可以運(yùn)行各種工作模式。
　　2．國際數(shù)據(jù)加密算法IDEA
　　近年來，新的分組加密算法不斷出現(xiàn)，IDEA就是其中的杰出代表。IDEA是International Data Encryption Algorithm的縮寫，即國際數(shù)據(jù)加密算法。它是根據(jù)中國學(xué)者朱學(xué)嘉博士與著名密碼學(xué)家James Massey于1990年聯(lián)合提出的建議標(biāo)準(zhǔn)算法PES(Proposed Encryption Standard)改進(jìn)而來的。它的明文與密文塊都是64bit，密鑰長度為128bit，作為單鑰體制的密碼，其加密與解密過程相似，只是密鑰存在差異，IDEA無論是采用軟件還是硬件實(shí)現(xiàn)都比較容易，而且加、解密的速度很快。
　　IDEA算法是面向塊的單鑰密碼算法，它的安全性與DES類似，不在于算法的保密，而是密鑰的安全性。
　　IDEA的密鑰長為128bit，采用窮舉搜索進(jìn)行破譯，則需要進(jìn)行2¹²⁸次嘗試，這將是用同樣方法對(duì)付DES的2⁷²倍工作量。目前，尚未見到成功對(duì)IDEA進(jìn)行攻擊的報(bào)道，有關(guān)學(xué)者進(jìn)行分析也表明IDEA對(duì)于線性和差分攻擊是安全的。此外，將IDEA的字長由16bit加長為32bit，密鑰相應(yīng)長為256bit，采用2³²模加，2³²+1模乘，可以進(jìn)一步強(qiáng)化IDEA的安全性能。
　　3．單鑰密碼算法性能分析
　　前面詳細(xì)介紹了單鑰密碼體制的典型代表DES算法和IDEA算法，其他一些有意義的算法有SAFER K-64(Secure And Fast Encryption Routine)、GOST、RC-4、RC-5、Blowfish、CAST-128等。為了提高單鑰密碼的安全性，人們還將分組密碼算法通過組合以得到新的分組密碼算法，但這種組合密碼的安全性必須經(jīng)仔細(xì)檢驗(yàn)后才能付諸實(shí)用，如二重DES加密、三重DES加密等。
　　由于各種加密算法的具體實(shí)現(xiàn)方法互不相同，因此其性能也存在較大差異，表5-3對(duì)單鑰密碼體制的主要算法在總體實(shí)現(xiàn)、速度、安全性能和改進(jìn)措施幾個(gè)方面進(jìn)行了比較，并基于比較結(jié)果給出了各算法合適的應(yīng)用場合。

5.3.3  雙鑰加密算法

　　雙鑰密碼體制的加密密鑰和解密密鑰不相同，它們的值不等，屬性也不同，一個(gè)是可公開的公鑰，另一個(gè)則是需要保密的私鑰。雙鑰密碼體制的特點(diǎn)是加密能力和解密能力是分開的，即加密與解密的密鑰不同，或從一個(gè)難以推出另一個(gè)。它可以實(shí)現(xiàn)多個(gè)用戶用公鑰加密的消息只能由一個(gè)用戶用私鑰解讀，或反過來，由一個(gè)用戶用私鑰加密的消息可被多個(gè)用戶用公鑰解讀。其中前一種方式可用于在公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信；后一種方式可用于在認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽名。
　　雙鑰加密算法的主要特點(diǎn)如下：
　　1）用加密密鑰PK對(duì)明文m加密后得到密文，再用解密密鑰SK對(duì)密文解密，即可恢復(fù)出明文m，即
　　　　　　　　　　　　　　　D_SK(E_PK(m))＝m
　　2）加密密鑰不能用來解密，即：
　　　　　　　　　　　　　　　D_PK(E_PK(m))≠m ；D_SK(E_SK(m))≠m
　　3）用SK加密的信息只能用PK解密；用PK加密的信息只能用SK解密。
　　4）從已知的PK不可能推導(dǎo)出SK。
　　5）加密和解密的運(yùn)算可對(duì)調(diào)，即
　　　　　　　　　　　　　　　E_PK(D_SK(m))＝m
　　雙鑰密碼體制大大簡化了復(fù)雜的密鑰分配管理問題，但公鑰算法要比私鑰算法慢得多(約1000倍)。因此，在實(shí)際通信中，雙鑰密碼體制主要用于認(rèn)證（比如數(shù)字簽名、身份識(shí)別等）和密鑰管理等，而消息加密仍利用私鑰密碼體制。下面介紹雙鑰密碼體制的杰出代表――RSA加密算法。
　　1．RSA算法
　　RSA體制是由R.L.Rivest、A.Shamir和L.Adleman設(shè)計(jì)的用數(shù)論構(gòu)造雙鑰的方法，它既可用于加密，也可用于數(shù)字簽名。RSA得到了世界上的最廣泛應(yīng)用，ISO在1992年頒布的國際標(biāo)準(zhǔn)X.509中，將RSA算法正式納入國際標(biāo)準(zhǔn)。1999年，美國參議院已經(jīng)通過了立法，規(guī)定電子數(shù)字簽名與手寫簽名的文件、郵件在美國具有同等的法律效力。在Internet中廣泛使用的電子郵件和文件加密軟件PGP(Pretty Good Privacy)也將RSA作為傳送會(huì)話密鑰和數(shù)字簽名的標(biāo)準(zhǔn)算法。RSA算法的安全性建立在數(shù)論中“大數(shù)分解和素?cái)?shù)檢測”的理論基礎(chǔ)上。
　　（1）大數(shù)分解
　　雙鑰密碼體制算法按由公鑰推算出密鑰的途徑可分為兩類：一類是基于素?cái)?shù)因子分解問題的(如RSA算法)，它的安全性基于100位十進(jìn)制數(shù)以上的所謂“大數(shù)”的素?cái)?shù)因子分解的難題，這是一個(gè)至今沒有有效快速算法的數(shù)學(xué)難題。另一類是基于離散對(duì)數(shù)問題的(如EIGamal算法)，其安全性基于計(jì)算離散對(duì)數(shù)的困難性。離散對(duì)數(shù)問題是指模指數(shù)運(yùn)算的逆問題，即找出一個(gè)數(shù)的離散對(duì)數(shù)。一般地，計(jì)算離散對(duì)數(shù)是非常困難的。
　　RSA算法運(yùn)用了數(shù)論中的Euler同余定理：即a、r是兩個(gè)互質(zhì)的自然數(shù)，則a^z=1 (mod r),其中z為與r互質(zhì)的且不大于r的自然數(shù)，稱z為r的Euler指標(biāo)函數(shù)。
　　（2）RSA算法表述
　　假定用戶A欲送消息m給用戶B，則RSA算法的加／解密過程為：
　　1）首先用戶B產(chǎn)生兩個(gè)大素?cái)?shù)p和q(p、q是保密的)。
　　2）用戶B計(jì)算n=pq和φ(n)=(p-1)(q-1)(φ(n)是保密的)。
　　3）用戶B選擇一個(gè)隨機(jī)數(shù)e(0<e<φ(n))，使得(e，φ(n))=1，即e和φ互素。
　　4）用戶B通過計(jì)算得出d，使得d*e mod φ(n)=1(即在與n互素的數(shù)中選取與φ(n)互素的數(shù)，可以通過Euclidean算法得出。d是用戶B自留且保密的，用作解密密鑰)。
　　5）用戶B將n及e作為公鑰公開。
　　6）用戶A通過公開渠道查到n和e。
　　7）對(duì)m施行加密變換，即E_B(m)=m^e mod n=c。
　　8）用戶B收到密文c后，施行解密變換
　　　　　　　D_B(c)=c^d mod n=(m^e mod n)^d mod n=m^ed mod n=m mod n
　　下面舉一個(gè)簡單的例子用于說明這個(gè)過程：令26個(gè)英文字母對(duì)應(yīng)于0到25的整數(shù)，即a-00，b-01，…，y-24，z-25。設(shè)，m=inclub，則m的十進(jìn)制數(shù)編碼為：m=08 13 02 11 20 01。設(shè)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加密：
　　E_B(i)=08³ mod 33= 17,
　　E_B(n)=13³ mod 33= 19,
　　E_B(c)=02³ mod 33= 8,
　　E_B(l)=11³ mod 33= 11,
　　E_B(u)=20³ mod 33= 14,
　　E_B(b)=01³ mod 33= 1,
則 c= E_B(m) = 17 19 08 11 14 01,它對(duì)應(yīng)的密文為
　　c=rtilob
　　當(dāng)用戶B接到密文c后施行解密變換：
　　D_B(r) = 17⁷ mod 33= 8，即明文i，
　　D_B(t) = 19⁷ mod 33= 13，即明文n，
　　D_B(i) = 08⁷ mod 33= 2，即明文c，
　　D_B(l) = 11⁷ mod 33= 11，即明文l
　　D_B(o) = 14⁷ mod 33= 20，即明文u,
　　D_B(b) = 01⁷ mod 33= 1，即明文b。
　　（3）RSA安全性分析
　　RSA的保密性基于一個(gè)數(shù)學(xué)假設(shè)：對(duì)一個(gè)很大的合數(shù)進(jìn)行質(zhì)因數(shù)分解是不可能的！若RSA用到的兩個(gè)質(zhì)數(shù)足夠大，可以保證使用目前的計(jì)算機(jī)無法分解。即RSA公開密鑰密碼體制的安全性取決于從公開密鑰（n，e）計(jì)算出秘密密鑰（n，d）的困難程度。想要從公開密鑰（n，e）算出d，只能分解整數(shù)n的因子，即從n找出它的兩個(gè)質(zhì)因數(shù)p和q，但大數(shù)分解是一個(gè)十分困難的問題。RSA的安全性取決于模n分解的困難性，但數(shù)學(xué)上至今還未證明分解模就是攻擊RSA的最佳方法。盡管如此，人們還是從消息破譯、密鑰空間選擇等角度提出了針對(duì)RSA的其他攻擊方法，如迭代攻擊法、選擇明文攻擊法、公用模攻擊、低加密指數(shù)攻擊、定時(shí)攻擊法等，但其攻擊成功的概率微乎其微。
　　出于安全考慮，在RSA中，建議使用1024bit的n，對(duì)于重要場合n應(yīng)該使用2048位。
　　2．ElGamal算法
　　RSA算法是基于素?cái)?shù)因子分解的雙鑰密碼，而ElGamal算法則是基于離散對(duì)數(shù)問題的另一種類型的雙鑰密鑰，它既可用于加密，也可用于簽名。
　　（1）ElGamal算法方案
　　1985年，ELGamal第一次在有限域上基于離散對(duì)數(shù)問題設(shè)計(jì)了原始的ElGamal數(shù)字簽名方案。
　　令p是使在GF（p）域計(jì)算離散對(duì)數(shù)在多項(xiàng)式時(shí)間內(nèi)是不可行的大素?cái)?shù)。引進(jìn)集合Zp ={0,1,2,…，p}及其子集Zp*={0,1,2,…，p-1}。令g∈Zp*，是本原元，定義：密鑰集K={（p,g,x,y）:y=g^x  mod p}，這里p,g,y是公鑰，x是用戶選擇的私鑰，x∈Zp*且gcd(x,p-1)=1。即產(chǎn)生密鑰對(duì)時(shí)，首先選擇一個(gè)素?cái)?shù)p，兩個(gè)Zp*中的隨機(jī)數(shù)g和x, 計(jì)算 y = g^x mod p ，則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶共享。
　　（2）ElGamal加、解密及其安全性
　　選擇隨機(jī)數(shù)k∈z_p-1，且(k，p-1)=1，計(jì)算：y₁=g^kmod p(隨機(jī)數(shù)k被加密)，y₂=my^k mod p，這里，m是發(fā)送明文組。密文則由y₁和y₂級(jí)連構(gòu)成，即密文C=y₁‖y₂。這種加密方式的特點(diǎn)是，密文由明文和所選隨機(jī)數(shù)k來決定，因而是非確定性加密，一般稱之為隨機(jī)化加密，對(duì)同一明文由于不同時(shí)刻的隨機(jī)數(shù)k不同而給出不同的密文，這樣做的代價(jià)是使數(shù)據(jù)擴(kuò)展1倍。
　　在收到密文組C后，ElGamal的解密是通過下列計(jì)算得到明文的：
　　　　　　　　　　　　　　

　　ElGamal算法的安全性是基于z_P^*中有限群上的離散對(duì)數(shù)的困難性的。研究表明，mod p生成的離散對(duì)數(shù)密碼可能存在陷門，這會(huì)造成有些“弱”素?cái)?shù)p下的離散對(duì)數(shù)較容易求解，但密碼學(xué)家也發(fā)現(xiàn)可以較容易地找到這類陷門以避免選用可能產(chǎn)生脆弱性的這些素?cái)?shù)。
　　3．雙鑰算法小結(jié)
　　雙鑰密鑰體制的密鑰管理和分配較簡單，尤其可方便地用于數(shù)字簽名和認(rèn)證。雖然其算法都較復(fù)雜，運(yùn)算量巨大，但其仍不失為一種非常有前途的加密體制，它的出現(xiàn)是密碼學(xué)發(fā)展史上的劃時(shí)代事件。上面我們分析了雙鑰密碼體制的典型代表RSA算法和ElGamal算法，還有其他一些有意義的算法，如LUC密碼、Rabin密碼，以及DSA密碼等。
　　對(duì)于RSA體制，可以將其推廣為有多個(gè)密鑰的雙鑰體制，即在多個(gè)密鑰中選用一部分密鑰作為加密密鑰，而另一些作為解密密鑰。同樣地，RSA還可以推廣為多簽名體制，如有k₁、k₂和k₃三個(gè)密鑰，可將k₁作為A的簽名私密鑰，k₂作為B的簽名私密鑰，k₃作為公開的驗(yàn)證簽名用密鑰，實(shí)現(xiàn)這種多簽名體制，需要一個(gè)可信賴中心對(duì)A和B分配秘密簽名密鑰。