2.3 現代密碼技術

加密技術經過幾十年的發展已經趨于成熟，對于網絡信息的加密技術也是多種多樣，但從應用方面來講大體分為兩類：一類是對稱密碼技術，另一類是非對稱密碼技術。

2.3.1 對稱密碼技術

對稱密鑰密碼系統使用的加密密鑰和解密密鑰是相同的，或者可以簡單地相互推導出來。典型的對稱密鑰密碼系統是數據加密標準（Data Encryption Standard，DES），此外還有國際數據加密算法（IDEA，International Data Encryption Algorithm）、高級加密標準（AES，Advanced Encryption Standard）等。

1．數據加密標準（DES）

DES加密算法的數據流程如圖2-5所示。該算法輸入的是64bit的明文，在64bit的密鑰控制下，通過初始換位IP變成T₀=IP（T），再對T₀經過16層的加密變換，最后通過逆初始變換（也稱最后變換）得到64bit的密文。密文的每一位都是由明文的每一位和密鑰的每一位聯合確定的。DES的加密過程可分為加密處理、加密變換及子密鑰生成幾個部分，如圖2-6所示。下面，分別說明加密處理、加密變換、子密鑰生成和解密處理幾個過程。

（1）加密處理

1）初始換位：加密處理首先要對64bit的明文按照表2-3所示的初始換位表IP進行換位。

表中的數值表示輸入bit被置換后的新bit位置。例如，輸入的第58bit，在輸出時被置換到第1bit的位置；輸入的第2bit，在輸出時被置換到第8bit的位置；輸入的第1bit，在輸出時被置換到第40bit的位置；輸入的第7bit，在輸出時被置換到第64bit的位置上。

2）加密處理：上述換位處理的輸出，中間要經過16層復雜的加密變換。經過初始換位的64bit的輸出變為下一步的輸入，此64bit分成左、右兩個32bit，左為L₀，右為R₀，從L₀和R₀到L₁₆和R₁₆共進行了如圖2-7所示的16層加密變換。變換之后，若經過第n層處理后的左、右32bit分別為L_n和R_n，則L_n和R_n可作如下的定義：

L_n=R_n-1

R_n=L_n-1⊕f（R_n-1，K_n）

這里，K_n是向第n層輸入的48bit的密鑰；L_n-1和R_n-1分別是第n-1層的輸出；f是以R_n-1和K_n為變量的輸出32bit的函數。

3）最后換位：進行16次加密變換之后，將L₁₆和R₁₆合成64bit數據，再按照表2-4所示的最后換位表IP^-1進行換位，得到64bit的密文，這就是DES加密的結果。

由圖2-8可以看出，表2-3和表2-4是完全的逆變換。

（2）加密變換

計算f（R，K）的方式如圖2-9所示。在DES算法中，其他部分都是線性的，而這個f（R，K）變換是非線性的，因此可以產生強度很高的密碼。

32bit的R首先按照表2-5所示的擴展型換位表E進行換位，同時把一部分bit重復使用，便可擴大成48bit，這樣得到48bit的R′。按照從頭算起，每4bit再加上后面的2bit，便形成每6bit一組的8個分組，即

R ₃₂ R ₁ R ₂ R ₃ R ₄ R ₅，R₄R₅R₆R₇R₈R₉，……，…R₂₈R₂₉，R₂₈R₂₉R₃₀R₃₁R₃₂R₁

這48bit的R′和48bit的密鑰K進行異或運算，并分成每組6bit的8個分組，輸入到S₁～S₈的8個S盒中去，S₁～S₈稱為選擇函數（Selection Function）。這些S盒輸入是6bit，輸出是4bit。

如表2-6所示，此表列舉的是一個S盒中S₁的代替表。一個S盒中備有4種代替表（行號為0，1，2，3），究竟采用哪一種代替表，要通過輸入的6bit的開頭和末尾兩個bit選定，然后按選定的代替表將輸入的6bit的中間4bit進行代替。

下面舉一個例子予以說明。當向S₁輸入一個二進制狀態011011時，因開頭的0和末尾的1合起來為01（即十進制數1），所以選中了編號為1的代替表；又因中間4個bit狀態為1101（十進制數13），表示選第13列。第1行第13列所指示的值為5，即輸出狀態為0101，這4個bit就是經過代替之后的狀態。如表2-7所示，此表給出了S₁～S₈的S盒代替表，其中的每一行代表一種代替表。接著，從8個S盒輸出的32bit，按照表2-8所示的單純換位表P進行換位，這樣便實現了f（R，K）的變換。

（3）子密鑰生成

下面說明子密鑰K₁～K₁₆的16層子密鑰的生成過程。在64bit的密鑰里包含了8位的奇偶校驗位，所以實際密鑰長度是56bit，而每層要生成48bit的子密鑰。

輸入64bit的密鑰，首先通過壓縮型換位PC-1（Permuted Choice 1）去掉奇偶校驗位，再將不含奇偶校驗位的56bit進行輸出，而每層要分成兩部分，上部分的28bit為C₀，下部分的28bit為D₀，如表2-9所示。C₀和D₀依次進行循環左移位，這樣就生成了C₁和D₁，然后將C₁和D₁合成56位，再通過壓縮型換位PC-2（如表2-10所示），輸出的結果即為48位的子密鑰K₁。再將C₁和D₁進行循環左移位和PC-2的轉換，即得子密鑰K₂……依此類推，就可以得出16層的子密鑰K₁，K₂，…，K₁₆。16層子密鑰的生成過程如圖2-6右半部所示。值得注意的是，在產生16層子密鑰的過程中，L₁、L₂、L₉、L₁₆是循環左移1位的變換，而其余的L_n都是循環左移2位的變換。16層變換中的循環左移位次數如表2-11所示。

（4）解密處理

從密文到明文的解密處理可采用與加密算法完全相同的算法。不過，解密要用加密的逆變換，也就是把上述的最后換位表IP^-1和初始換位表IP完全倒過來變換。另外，在16層的變換處理中，由于R_n-1=L_n和L_n-1=R_n⊕f（L_n，K_n），因此要求出R_n-1和L_n-1，只要知道L_n、R_n和K_n，并使用同一個函數f所表示的變換便可以實現，從而在各層變換中，如果采用與加密時相同的K_n來處理，就能實現解密。具體地說，輸入DES算法中的密文，經過初始換位可得到L₁₆和R₁₆，第1層處理時的密鑰是逆序的，用K₁₆可以求出L₁₅和R₁₅，其中f（R，K）即使不可逆也沒有關系；然后用K₁₅進行變換求出L₁₄和R₁₄。依此類推，經過16層的變換即可得到L₀和R₀。

（5）DES加密的評價

DES加密法的保密性到底如何？早在DES被正式公布為數據加密標準之前，就展開了熱烈的討論。由于目前尚無一個評價加密系統性能的統一標準和嚴格的理論，因此人們只能從一個密碼系統抵抗現有解密手段的能力來評價它的好壞。

自1975年以來，美國的許多機構、公司和學者，包括美國國家安全局（NSA）、標準局、IBM公司、DELL實驗室和一大批著名的密碼學專家都對DES進行了大量的研究，但迄今尚未找到破譯DES的一種行之有效的方法。因此，認為DES具有良好的保密性能和抗分析破譯性能，并已廣泛地應用于金融業。不僅在美國，而且日本和西歐多國也使用DES。

20世紀80年代中期，人們看到DES算法迭代次數少，密鑰長度短，其代替函數Si中可能有不安全因素，因而曾經有過不少批評，有人甚至還想取消它，但是DES以它頑強的生命力至今仍占據著加密技術的重要地位。

DES的研究和應用還在不斷發展，出現了一些增強DES的設想，如增長密鑰長度和改進代替函數Si等，對DES的分析和研究還在繼續深入。雖然1984年美國國家安全局決定研制新的數據加密標準CCEP，但從發展趨勢上看，CCEP是按封閉的原則管理的，應用范圍很有限，它不再具有技術上的開放性和使用上的靈活性，因此受到金融界的強烈反對。由于反對的呼聲很高，美國政府不得不于1987年初廢除了1984年簽署的用CCEP取代DES加密標準的命令，所以它很難取代DES的廣泛應用。

然而，1997年，在一項“DES挑戰賽”的活動中，志愿者4次分別用4個月、41天、56個小時和22個小時破解了RSA數據安全公司用56bit DES算法加密的密文。這說明，DES加密算法在計算機運算速度提升后被認為是不安全的。另外，有一些分析報告也提出了DES算法理論上的弱點，如不能對抗差分和線性密碼分析等。在2001年，DES作為一個標準已經被取代。DES也不再作為美國國家標準科技協會（前美國國家標準局）的一個標準。不過，DES作為密碼學史上影響最大、應用最廣的數據加密算法，其成功是當之無愧的。

（6）二重DES

為了提高DES的安全性，并利用實現DES的現有軟硬件，可將DES算法在多密鑰下多重使用。如圖2-10所示為二重DES。

二重DES是多重使用DES時最簡單的形式，其中明文為P，兩個加密密鑰為K₁和K₂，密文為，解密時，以相反順序使用兩個密鑰：。因此，二重DES所用密鑰長度為112bit，強度大增。然而，如果對任意兩個密鑰K₁和K₂，能夠找出另一密鑰K₃，使得。那么，二重DES以及多重DES都沒有意義，因為它們與56bit密鑰的單重DES等價。

但上式對DES并不成立。將DES加密過程64bit分組到64bit分組的映射看作一個置換，如果考慮2⁶⁴個所有可能的輸入分組，則密鑰給定后，DES的加密將把每個輸入分組映射到一個唯一的輸出分組。否則，如果有兩個輸入分組被映射到同一分組，則解密過程就無法實施。對2⁶⁴個輸入分組，總映射個數為（2⁶⁴）！＞（10²⁰）。

另一方面，對每個不同的密鑰，DES都定義了一個映射，總映射數為2⁵⁶＜10¹⁷。

因此，可假定用兩個不同的密鑰兩次使用DES，可得一個新映射，而且這一新映射不出現在單重DES定義的映射中。這一假定已于1992年被證明。所以使用二重DES產生的映射不會等價于單重DES加密。但對二重DES有以下一種稱為“中途相遇攻擊”的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：

如果有，那么（參見圖2-10）。

如果已知一個明—密文對（P，C），可實施以下攻擊：首先，用2⁵⁶個所有可能的K₁對P加密，將加密結果存入一個表中，并對該表按X排序，然后用2⁵⁶個所有可能的K₂對C解密，在上述表中查找與C解密結果匹配的項，如果找到，則記下相應的K₁和K₂。最后再用一新的明—密文對（P′，C′）檢驗上面找到的K₁和K₂，用K₁和K₂對P′兩次加密，若結果等于C′，就可確定K₁和K₂是所要找的密鑰。

對已知的明文P，二重DES能產生2⁶⁴個可能的密文。而可能的密鑰個數為2¹¹²，所以平均來說，對一個已知的明文，有2¹¹²/2⁶⁴=2⁴⁸個密鑰可產生已知的密文。而再經過另外一對明—密文的檢驗，誤報率將下降到2^48-64=2^-16。所以在實施“中途相遇攻擊”時，如果已知兩對明—密文，則找到正確密鑰的概率為1-2^-16。

（7）兩個密鑰的三重DES

抵抗“中途相遇攻擊”的一種方法是使用三個不同的密鑰做三次加密，從而可使已知明文攻擊的代價增加到2¹¹²。然而又會使密鑰長度增加到56×3=168bit，因而過于笨重。一種實用的方法是僅使用兩個密鑰做三次加密，實現方式為加密—解密—加密，簡記為EDE（Encrypt-Decrypt-Encrypt），如圖2-11所示。

第二步解密的目的僅在于使得用戶可對一重DES加密的數據解密。此方案已在密鑰管理標準ANS X.917和ISO 8732中采用。

（8）三個密鑰的三重DES

三個密鑰的三重DES密鑰長度為168bit，加密方式為，令K₃=K₂或K₁=K₂，則變為一重DES。

三個密鑰的三重DES已在互聯網的許多應用（如PGP和S/MIME）中采用。

2．國際數據加密算法（IDEA）

國際數據加密算法IDEA是瑞士的學者提出的。1990年XueJia Lai和Massey開發出IDEA加密算法雛形，稱為PES，即“建議的加密標準”。第二年，根據有關專家對這一密碼算法的分析結果，設計者對該算法進行了強化并稱之為IPES，即“改進的建議加密標準”。該算法于1992年更名為IDEA，即“國際加密標準”。這種算法是在DES算法的基礎上發展出來的，類似于三重DES。發展IDEA也是因為感到DES具有密鑰太短等缺點。

IDEA算法的密鑰長度為128位，針對64位的數據進行加密或解密操作。XueJia Lai已證明IDEA算法在其8輪迭代的第4圈之后便不受差分密碼分析的影響了。假定窮舉法攻擊有效的話，那么即使設計一種每秒鐘可以試驗10億個密鑰的專用芯片，并將10億片這樣的芯片用于此項工作，仍需10²³年才能解決問題；另一方面，若用10²⁴片這樣的芯片，有可能在一天內找到密鑰，不過人們還無法找到足夠的硅原子來制造這樣一臺機器。目前，尚無公開發表的試圖對IDEA進行密碼分析的文章。因此，就現在來看，應當說IDEA是非常安全的。

IDEA有大量的弱密鑰，這些弱密鑰是否會威脅它的安全性還是一個謎。IDEA密碼能夠抵抗差分分析和線性分析。設計者Lai認為IDEA不是一個群，但目前仍未得到證實。

類似于DES，IDEA算法也是一種數據塊加密算法，它設計了一系列加密輪次，每輪加密都使用從完整的加密密鑰中生成的一個子密鑰。與DES的不同處在于，它采用軟件實現和采用硬件實現同樣快速。

由于IDEA是在美國之外提出并發展起來的，避開了美國法律上對加密技術的諸多限制，因此，有關IDEA算法和實現技術的書籍都可以自由出版和交流，可極大地促進IDEA的發展和完善。但由于該算法出現的時間不長，針對它的攻擊也還不多，還未經過較長時間的考驗。因此，尚不能判斷出它的優勢和缺陷。

3．高級加密標準（AES）

數據加密標準（DES）作為20世紀70年代的加密標準，其加密強度越來越不能滿足人們的要求。DES的密鑰長度只有56bit，隨著計算能力的不斷提高，利用窮搜索的方法攻破DES是完全可能的，特別是在政府或者其他組織的支持下使用專門設計的硬件來攻擊DES已經是輕而易舉的事情。在這種情況下，美國國家標準技術局（NIST）在1997年開始倡導制定高級加密標準（AES）替代DES，以滿足21世紀的信息加密需求。經過幾年的招標、篩選，NIST于2000年底最終確定了AES（RIJNDAEL）標準。AES是由比利時密碼專家Joan Daemen和Vincent Rijmen共同設計的。下面簡單地介紹AES。

AES的信息塊長度和加密密鑰長度都是可變的，它們都可以是128bit、192bit和256bit。為了方便數據的計算和算法的描述，首先把信息塊做如下的處理。以192bit的信息塊為例，假設信息塊是m₀m₁…m₁₉₁，寫成字節形式就是a₀₀a₀₁…a₀₅a₁₀a₁₁…a₁₅…a₃₀a₃₁…a₃₅，或者寫成字的形式就是w₀w₁…w₅，如圖2-12所示。

也可以對加密密鑰做類似的處理。設N_b為信息塊經過上述處理后得到的字的個數，N_k為加密密鑰經過上述處理后得到的字的個數。那么根據信息塊的長度，N_b=4，6，8，根據加密密鑰的長度，N_k=4，6，8，加密的輪數N_r如表2-12所示，由N_b和N_k控制。

整個算法包括加密過程與輪密鑰生成兩個獨立的部分。

（1）加密過程

設信息塊是M，輪密鑰分別是K₀，K₁，…，，加密過程如圖2-13所示。解密過程把加密過程完全反過來即可。

1）ByteSub函數。

把每個8bit的字節看成有限域GF（2⁸）中的一個元素，那么函數ByteSub是作用在每個字節上的非線性變換，它定義為：ByteSub：GF（2⁸）→GF（2⁸）

如圖2-14所示，描述了信息塊長度是192bit時，函數ByteSub的作用情況。

2）ShiftRow函數。

把信息塊記為4行、N_b列的矩陣形式，函數ShiftRow就是對每行實行不同的左移位，每行的左移位數C₁、C₂、C₃分別由N_b決定，見表2-13。

函數ShiftRow的作用如圖2-15所示。

3）MixColumn函數。

MixColumn函數是GF（2⁸）⁴上的一個線性變換，變換矩陣C定義為：

其中的運算均為在GF（2⁸）中進行。如圖2-16所示，描述了信息塊長度是192bit時，MixColumn函數的作用情況。此處矩陣C中的元素理解為兩個4bit長的二進制數的串接，比如02理解為0000 0010。

（2）輪密鑰生成

輪密鑰的生成過程包括加密密鑰的擴張和輪密鑰的選取兩個部分。

1）加密密鑰的擴張。

假設信息塊的長度是N_b個32bit字，由于整個加密過程需要N_r+1個輪密鑰，每個輪密鑰的長度是N_b個32bit字，因此密鑰的擴張過程需要產生N_b（N_r+1）個32bit字，記為w₀，w₁，…，。加密密鑰的擴張根據密鑰長度N_k的不同，有兩種不同的擴張方式。假設加密密鑰為wk₀wk₁…，令w₀=wk₀，。

當N_r≤6時，對于N_k≤i＜N_b（N_r+1），如圖2-17a所示。

當N_r＞6時，對于N_k≤i＜N_b（N_r+1），如圖2-17b所示。

其中，RotByte把（a，b，c，d）變為（b，c，d，a），a，b，c，d是8bit。

Rcont[i]=（RC[i]，00，00，00）；RC[1]=1，RC[i]=xRC[i-1]=x^i-1，即RC[i]表示有限域GF（2⁸）中值為x^i-1的元素。Rcont[i/N_k]為輪常數，其值與N_k無關。

2）輪密鑰的選取。

加密密鑰經過擴張產生了N_b（N_r+1）個32bit字，把它們等分成N_r+l塊，每塊包含N_b個32bit字，那么第一個輪密鑰就是第一個塊，第二個輪密鑰就是第二個塊，依此類推得到所有的輪密鑰。

（3）關于AES的討論

AES的原型是Square算法，它的設計策略是寬軌跡策略（Wide Trail Strategy）。這種策略是針對差分分析和線性分析提出來的，它是一個分組迭代密碼，具有可變的分組長度和密鑰長度。2000年10月，AES選擇Rijndael加密算法作為自己的算法，Rijndael具備了安全、性能好、效率高、易實現和靈活等優點，Rijndael對內存的需求非常低，也使它很適合用于受限制的環境中，Rijndael操作簡單，并可抵御強大和實時的攻擊，此外，它還有許多未被特別強調的防御性。

與其他分組碼相比，AES具有如下特點：①可變的密鑰長度；②混合的運算方式；③數據相關的圈數；④密鑰相關的圈數；⑤密鑰相關的S盒；⑥長密鑰調度算法；⑦可變長明文/密文塊長度；⑧可變圈數；⑨每圈操作作用于全部數據。

2.3.2 非對稱密碼技術

20世紀70年代，一個數學上的突破震驚了世界密碼學家，這就是公鑰加密技術。與傳統的加密方法不同，它使用兩把密鑰：一把公開密鑰和一把秘密密鑰。前者用于加密，后者用于解密，它也稱為“非對稱式”加密方法。公鑰加密技術解決了對稱加密方法的根本性缺陷，極大地簡化了密鑰分發過程。它若與對稱加密方法結合，可以進一步增強對稱加密方法的可靠性。此外，還可能利用公鑰加密技術來進行數字簽名。

1．公鑰加密技術原理概述

1976年Diffie和Hellman在其劃時代的文獻New Directions in Cryptography（密碼學新方向）中提出公鑰加密的概念，公鑰加密是基于單向陷門（trap door）函數來實現的，單向陷門函數是指滿足下列條件的函數f（x）：

1）給定x，計算y=f（x）是容易的。

2）給定y，計算x=f^-1（y）是困難的。

3）存在δ，已知δ時，對給定的任何y，若相應的x存在，則計算x=f^-1（y）是容易的。

僅滿足第1）條、第2）條的稱為單向函數，第3）條稱為陷門性，δ稱為陷門信息。當用陷門函數f（x）作為加密函數時可將f（x）公開，這相當于公鑰。f（x）函數的設計者將δ保密，用作解密密鑰，這相當于私鑰。由于加密函數是公開的，任何人都可以將信息x加密成y=f（x），然后送給函數的設計者，當然可以通過不安全信道傳送，由于設計者擁有δ（私鑰），他可以容易地解出x=f^-1（y）。單向陷門函數的第2）條性質表明竊聽者由截獲的密文y=f（x）推測x是不可行的。

目前公鑰密碼系統單向陷門函數的設計主要依賴下面3個數學難題：

1）背包問題。

2）大整數因子分解問題。

3）離散對數問題。

第1類公鑰系統的安全性依賴于背包問題的NP完全性。背包問題可以這樣描述：已知一容積為C的背包及體積分別為k₁，k₂，…，k_n的n個物品，若從這些物品中選出若干個正好裝滿這個背包，那么究竟選哪些物品？即求m_i（1≤i≤n），使得C=k₁m₁+k₂m₂+…+k_nm_n，其中k_i和C都是正整數，m_i取0或1。背包問題是著名的NP完全問題，至今沒有很好的求解方法。窮舉搜索的復雜度為O（2ⁿ）。第一個背包公鑰算法是由Merkle和Hellman于1978年提出的MH算法。選取正整數k₁，k₂，…，k_n作為密鑰，設明文分組位串為M=m₁m₂…m_n，則加密后的密文為C=k₁m₁+k₂m₂+…+k_nm_n。那么如何進行解密呢？奧妙在于存在一類特殊的背包問題，其物品體積序列k₁，k₂，…，k_n的每一項都大于它之前的所有項之和，這就是著名的超遞增背包問題，超遞增背包問題的復雜度為O（n）（讀者可想一想為什么）。Merkle和Hellman設計了一種可以將超遞增背包問題轉換為同解非超遞增背包問題的方法。MH算法用超遞增背包問題的體積序列作私鑰，而用同解的非超遞增背包問題的體積序列作公鑰，這樣就很容易用私鑰進行解密了。MH算法后來被證明是不安全的，但這種算法首次將NP完全問題用于公鑰密碼學，在密碼學史上具有開創意義。

第2類公鑰系統是由麻省理工學院的三位科學家Ron L.Rivest，Adi Shamir和Leonard M.Adleman于1978年提出的，簡稱為RSA系統。它的安全性是基于大整數因子分解的困難性，其公鑰和私鑰是一對大素數（100到200位的十進制數或更大）的函數。從一個公鑰和密文中恢復出明文的難度等價于分解兩個大素數之積的難度，而大整數因子分解問題是數學上的著名難題，因而可以確保RSA算法的安全性。RSA系統是公鑰系統的最具有典型意義的方法，自提出以來就一直是人們研究的焦點，經受住了多年來許多資深密碼學家的密碼分析，說明該算法是有相當的可信度的。本節將重點介紹RSA算法。

第3類公鑰系統的安全性依賴于離散對數的計算困難性。離散對數問題可細分為兩類：一類為有限域上的離散對數問題，一類為橢圓曲線上的離散對數問題。下面舉一個簡單的有限域上離散對數的例子，設p為素數，g小于p，如果對每個b從1到p-1都存在x，使得g^x≡bmodp，則稱g為模p的原根（primitive root）。例如5是模7的原根，這是因為：

5¹≡5（mod 7）

5²=5×5≡4（mod 7）

5³=4×5≡6（mod 7）

5⁴=6×5≡2（mod 7）

5⁵=2×5≡3（mod 7）

5⁶=3×5≡1（mod 7）

如果g為模p的原根，則對任意y，總是可以找出y=g^xmodp的解，x稱為y模p的離散對數解（形如g^xmodp的運算稱為模乘運算）。當p很小時，已知y和p可以用觀察法求出x，但是當p為很大的隨機素數時，就很難計算了。所以，可以認為y=g^xmodp是一個單向函數。

著名的橢圓曲線加密算法ECC（Elliptic Curve Cryptography）的安全性就是依賴于定義在橢圓曲線點上的離散對數問題的難解性。ECC算法由Neal Koblit和Victor Miller于1985年首先提出，從那時起ECC的安全性和實現效率就被眾多的數學家和密碼學家所廣泛研究。所得的結果表明，較之RSA算法，ECC具有密鑰長度短，加解密速度快，對計算環境要求低，在需要通信時，對帶寬要求低等特點。近年來，ECC被廣泛應用于商用密碼領域，這可由ECC被許多著名的國際標準組織所采納佐證，如ANSI、IEEE、ISO、NIST。此外，基于離散對數的公鑰系統還有Massey-Omura公鑰系統和ElGamal公鑰系統等。

2．RSA加密算法

RSA算法因其創始人Ronald L.Rivest、Adi Shamir和Leonard M.Adleman而得名。RSA的基礎是數論的歐拉定理，它的安全性依賴于大數的因數。

RSA算法研制的最初理念與目標是努力使互聯網安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發不安全的難題。而實際結果，RSA不但很好地解決了這個難題，還可利用它來完成對電文的數字簽名以對抗對電文的否認與抵賴，同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。

RSA是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數字簽名。在已公開的公鑰算法中，RSA是最容易理解和實現的。

（1）RSA算法的描述

RSA算法的實現步驟如下（B為實現者）：

1）B尋找出兩個大素數p和q。

2）B計算出n=pq和f（n）=（p-1）（q-1）。

3）B選擇一個隨機數e（0＜e＜f（n）），滿足（e，f（n））=1。

4）B使用輾轉相除法計算d=e^-1（modf（n））。

5）B在目錄中公開n和e作為他的公開密鑰，保密p、q和d。

密碼分析者攻擊RSA體制的關鍵在于如何分解n。若分解成功使n=pq，則可以算出f（n）=（p-1）（q-1），然后由公開的e解出秘密的d。

加密時，對每一明文分組如下計算：

解密時，取每一密文分組c并計算：

RSA算法主要用于數據加密和數字簽名。RSA算法用于數字簽名時，公鑰和私鑰的角色變換即可。即將消息用d加密簽名，用e驗證簽名。

（2）RSA算法實例

若B選擇了p=101和q=113，那么，n=11413，f（n）=100×112=11200；再用輾轉相除法（Euclidean算法）來求得e，使（e，f（n）=1）。假設B選擇了e=3533，那么用輾轉相除法將求得：d=e^-1（mod 11200），于是B的解密密鑰d=6597。

B公開n=11413和e=3533，現假設A想發送明文9726給B，他計算：9726³⁵³³（mod 11413）=5761，且在一個信道上發送密文5761。當B接收到密文5761時，他用他的秘密解密指數（私鑰）d=6597進行解密：

5761⁶⁵⁹⁷（mod 11413）=9726

（3）關于RSA算法的討論

RSA的發明者Rivest、Shamir和Adleman建議取p和q為100位以上的十進制數，這樣，n為200位的十進制數。按每秒10⁹次運算的高速計算機也要計算106年。

三種可能攻擊RSA算法的方法如下。

1）強行攻擊。這包含對所有的私有密鑰都進行嘗試。

2）數學攻擊。有幾種方法，實際上都等效于對兩個素數的乘積的因子分解。

3）定時攻擊。這依賴于解密算法的運行時間。

對RSA強行攻擊的防范方式與其他秘密系統采用的方法相同，即采用一個大的密鑰，因而e和d的比特數越多越好。然而因為在密鑰產生和加密解密中包含的計算很復雜，密鑰越大則系統運行越慢。

基于安全性考慮，一般在應用RSA時，必須做到以下幾點。

1）絕對不要對陌生人提交的隨機消息進行簽名。

2）不要在一組用戶間共享n。

3）加密之前要用隨機值填充消息，以確保m和n的大小一樣。

4）目前，129位十進制數字的模數是能夠分解的臨界數，因此，n應該大于這個數。

RSA技術既可用于加密通信，又能用于數字簽名和認證。由于RSA的速度大大遜于DES等分組算法，因此RSA多用于加密會話密鑰、數字簽名和認證。RSA以其算法的簡單性和高度的抗攻擊性在實際通信中得到了廣泛的應用。許多操作平臺（如Windows、Sun和Novell等）都應用了RSA算法。另外，幾乎所有的網絡安全通信協議（如SSL和IPsec等）也都應用了RSA算法。ISO幾乎已指定RSA用作數字簽名標準。在ISO 9796中，RSA已成為其信息附件。法國銀行界和澳大利亞銀行界已使RSA標準化，ANSI銀行標準的草案也利用了RSA。許多公司都采用了RSA安全公司的PKCS。RSA在目前和可預見的未來若干年內，在信息安全領域的地位是不可替代的，在沒有良好的分解大數因子的方法以及不能證明RSA的不安全性的時候，RSA的應用領域會越來越廣泛。但是一旦分解大數因子不再困難，那么，RSA的時代也會成為歷史。如今只有短的RSA鑰匙才可能被強力方式解破。迄今為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算和量子計算機理論日趨成熟的今天，RSA加密安全性受到了挑戰。

針對RSA最流行的攻擊一般是基于大數因數分解。1999年，RSA-155（512bits）被成功分解，花了五個月時間（約8000 MIPS年）和224 CPU hours，在一臺有3.2 GB中央內存的Cray C916計算機上完成。2002年，RSA-158也被成功因數分解。2009年12月12日，編號為RSA-768（768bits，232 digits）數也被成功分解。2013年2月15日，《紐約時報》報道，歐美數學家和密碼學家偶然發現，被全世界廣泛應用的公鑰加密算法RSA存在漏洞。他們發現，在700萬個實驗樣本中有2.7萬個公鑰并不是按理論隨機產生的。也就是說，或許有人可以找出產生公鑰的秘密質數。該研究項目是由美國獨立密碼學家James P.Hughes和荷蘭數學家Arjen K.Lenstra牽頭的。他們的報告稱：“我們發現絕大多數公鑰都是按理論產生的，但是每一千個公鑰中會有兩個存在安全隱患。為防止有人利用該漏洞，有問題的公鑰已從公眾訪問的數據庫中移除。為確保系統的安全性，網站需要在終端做出改變。”

3．Rabin加密算法

Rabin方案的安全性基于求合數的模平方根的難度。這個問題等價于因子分解。下面是該方案的描述。

（1）Rabin加密方案

首先選取兩個質數p和q，兩個質數都同余3模4。將這兩個質數作為私人密鑰，n=pq作為公開密鑰。

加密一個信息M（M必須小于n）時，只需計算：

C=M²modn

解密信息一樣容易，但稍微麻煩一些。由于接收者知道p和q，故可以用中國剩余定理解兩個同余式。計算：

m ₁=C^（p+1）/4modp

m ₂=（p-C^（p+1）/4）modp

m ₃=C^（q+1）/4modq

m ₄=（q-C^（q+1）/4）modq

然后選擇整數a=q（q^-1modp）和整數b=p（p^-1modq）。四個可能的等式為：

M ₁=（am₁+bm₃）modn

M ₂=（am₁+bm₄）modn

M ₃=（am₂+bm₃）modn

M ₄=（am₂+bm₄）modn

這四個結果M₁、M₂、M₃和M₄中之一等于M。如果信息是英語文本，很容易選擇正確的M_i。另一方面，如果信息是一個隨機位流（比如，密鑰產生或數字簽名），就沒有辦法決定哪一個M_i是正確的。解決這一問題的方法是在信息加密前加入一個已知的標題。

（2）Williams加密方案

Hugh Williams重新定義了Rabin方案以消除其缺陷。在他的方案中，p和q這樣選取：

p≡3mod 8

q≡7mod 8

且

N=pq

還有一個小整數S，滿足J（S，N）=-1（J是雅可比符號）。N和S公開。私人密鑰k滿足：

k=1/2×（1/4×（p-1）×（q-1）+1）

為了加密信息M，計算C₁使之滿足。然后，計算modN。類似于Rabin方案，C=M′²modN，C₂=M′mod 2。最后的密文是三重組：（C，C₁，C₂）。

解密C時，接收者利用：

C^k≡±M″（modN）

計算M″。M″的符號由C₂給出。最后：

Williams后來進一步改進了這個方案：將信息平方代之以立方。大質數必須同余1模3，否則公開密鑰和私人密鑰相同。更好的是，對每個加密僅有唯一的解密。

Rabin和Williams算法在證明其安全性取決于大數因子分解上較RSA算法有優勢。然而，它們對選擇密文攻擊是不安全的。如果你打算在攻擊者能攻擊的地方（例如，在數字簽名算法中，攻擊者選擇簽名的信息的地方）使用這些算法，要保證在簽名前使用單向散列函數。Rabin提出了另一種抵抗這種攻擊的方法：在每條信息散列運算和簽名前添加一個不同的隨機串。不幸的是，一旦你將單向散列函數添加到系統中，其安全性將不再依賴于因子分解，盡管添加的散列值在實際意義上對系統沒有任何削弱。

4．EIGamal加密算法

EIGamal算法既可用于數字簽名，又可用于加密，其安全性依賴于計算有限域上離散對數這一難題。

（1）密鑰對產生方法

密鑰對產生辦法如下。

1）選擇一個素數p，兩個隨機數g和x，要求g和x都小于p。

2）計算y=g^xmodp，則其公鑰為y、g和p；私鑰是x。g和p可由一組用戶共享。

（2）EIGamal用于加密

假定被加密信息為M，首先選擇一個隨機數k，只要k與p-1互質，然后計算：

a=g^kmodp，b=y^kMmodp

（a，b）為密文對，密文是明文的兩倍長。解密時計算：M=b/a^x（modp）

因為a^x≡g^kxmodp以及b/a^x≡y^kM/a^x≡g^xkM/g^xk≡Mmodp都成立（如表2-14所示），除了y是密鑰的一部分以及加密是和y^k相乘得來。

（3）EIGamal用于數字簽名

EIGamal主要用于數字簽名。假定被簽信息為M，首先選擇一個隨機數k，k與p-1互質，然后計算：a=g^kmodp，再用擴展Euclidean算法對下面方程求解b：

M=（xa+kb）mod（p-1）

簽名就是（a，b）。隨機數k必須保密。

要驗證簽名時，只要驗證下式：

y^aa^bmodp=g^Mmodp

同時一定要檢驗是否滿足1≤a＜p，否則簽名容易偽造。

每個EIGamal簽名或加密都需要一個新的k值，該值必須隨機選取。表2-15總結了這種方法。

例如，選擇p=11和g=2，私人密鑰x=8，計算：

y=g^x（modp）=2⁸（mod 11）=3

公開密鑰是y=3，g=2和p=11

為鑒別M=5，首先選擇隨機數k=9，驗證gcd（9，10）=1，計算：

a=g^k（modp）=2⁹（mod 11）=6

利用Euclidean算法求b：

M=（xa+kb）mod（p-1）

5=（8×6+9×b）mod 10

解是b=3，簽名是一對數：a=6和b=3。

驗證簽名時，只需確保：

y^aa^bmodp=g^Mmodp

3⁶6³（mod 11）=2⁵（mod 11）

EIGamal簽名的安全性依賴于乘法群（IFp）?上的離散對數計算。素數p必須足夠大，且p-1至少包含一個大素數因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應采用信息的散列值（如SHA算法）。EIGamal的安全性主要依賴于p和g，若選取不當則簽名容易偽造，應保證e對于p-1的大素數因子不可約。D.Bleichenbache在Generating EIGamal Signatures Without Knowing the Secret Key中提到了一些攻擊方法和對策。EIGamal的一個不足之處是它的密文成倍擴張。

美國的DSS（Digital Signature Standard）的DSA（Digital Signature Algorithm）算法是經EIGamal算法演變而來的。

5．橢圓曲線密碼算法

橢圓曲線第一次運用于公鑰密碼算法是在1985年由Neal Koblitz和Victor Miller分別獨立提出來的。橢圓曲線數字簽名算法（Elliptic Curve Digital Signature Algorithm，ECDSA）由IEEE工作組和ANSI（American National Standards Institute）X9組織開發。隨即學者們展開了橢圓曲線密碼學（Ellipse Curve Cryptography，ECC）研究。

除橢圓曲線外，還有人提出在其他類型的曲線如超橢圓曲線上實現公鑰密碼算法。其根據是有限域上的橢圓曲線上的點群中的離散對數問題（Ellipse Curve Discrete Logarithm Problem，ECDLP）。ECDLP是比因子分解問題更難的問題，許多密碼專家認為它有指數級的難度。

從目前已知的最好求解算法來看，相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全。據研究表明，160位ECC加密安全性相當于1024位RSA加密，210位ECC加密安全性相當于2048位RSA加密。使用短密鑰的好處在于加解密速度快、節省能源、節省帶寬、存儲空間。目前我國居民“二代身份證”正在使用256位的橢圓曲線密碼，虛擬貨幣“比特幣”也選擇ECC作為加密算法。

此外，有人在橢圓曲線上實現了類似EIGamal的加密算法及可恢復明文的數字簽名方案。除有限域上的橢圓曲線密碼算法外，人們還探索了在橢圓曲線上實現RSA算法，如KMOV。

（1）有限域上的橢圓曲線

數學上的橢圓曲線一般由如下形式給出：

E：y²=x³+ax²+bx+c，其中判別式

Δ（E）=-4a³c+a²b²-4b³-27c²+18abc≠0

橢圓曲線都是關于X軸對稱的曲線。

典型的橢圓曲線如y²=x³-4x²+16，其圖像如下。

更多的橢圓曲線圖像：

在密碼學中用到的橢圓曲線方程一般限定為：

E：y²=x³+ax+b，其中4a³+27b²≠0。

也即是這里的二次項系數為0。

密碼學中普遍采用的是有限域上的橢圓曲線，也即是變元和系數均在有限域中取值的橢圓曲線。使用模素數p的有限域Zp，將模運算引入橢圓曲線算術中，變量和系數從集合0，1，2，…，p-1中取值而非是在實數上取值。

此時橢圓曲線形式如下：

y ²modp=（x³+ax+b）modp

其中（4a³+27b²）modp≠0modp，變量和系數均在Zp中取值。

將滿足上式的所有非負整數對和O點記為集合Ep（a，b），這是一個有限的離散點集。由此可知集合中的點分布在（0，0）到（p-1，p-1）的象限中，集合中的點有可能剛好也在橢圓曲線上，更多的可能是在橢圓曲線外。例如點（13，7）是滿足y²mod 23=（x³+x+1）mod 23的點，但是（13，7）并不在橢圓曲線上。

在后面的ECC加密算法過程中會有一個給定的基點G（也就是生成元）生成一個子群，然后秘鑰空間在此子群取得，一般會要求保證子群的階會盡量大，基點及其子群的階n都是公開的信息。

構造一個數學難題來保證加密的安全性是現代密碼學中加密算法的主要思想。類似RSA算法中大數的質因子分解難題一樣，橢圓曲線也有類似的數學難題。

考慮K=kG，其中K，G∈Ep（a，b），k＜p。

對于給定的k和G，計算K是很容易的；反過來給定K和G，計算k是相當困難的，這就是橢圓曲線的離散對數問題（這里之所以稱之為離散對數問題，大概是為了與其他加密算法的說法保持一致，便于理解）。

正因為如此，可以將K作為公鑰，公開出去；k作為私鑰，秘密保管，通過公鑰來破解私鑰十分困難。

（2）橢圓曲線加密算法ECC

假設私鑰、公鑰分別為k和K。其中K=kG，G為基點。其中K、G為橢圓曲線Ep（a，b）上的點，n為G的階（nG=O∞），k為小于n的整數。則給定k和G，根據加法法則，計算K很容易；但反過來，給定K和G，求k就非常困難。因為實際使用中的ECC原則上把p取得相當大，n也相當大，要把n個解點逐一算出來是不可能的。

公鑰加密過程：

① A選定一條橢圓曲線E，并取橢圓曲線上一點作為基點G。

② A選擇一個私有密鑰k（k＜n），并生成公開密鑰K=kG。

③ A將E和點K、G傳給B。

④ B收到信息后，將待傳輸的明文編碼為一個坐標點M，并產生一個隨機整數r（r＜n，n為G的階數）。

⑤ B計算點C1=M+rK和C2=rG。

⑥ B將C1、C2傳給A。

加密完成，可以看出加密需要公鑰，加密將坐標點M加密為C1、C2兩個坐標點。加密者B只需發送C1、C2給解密者A即可。

私鑰解密過程：

① 由C1=M+rK，可知M=C1-rK。

② 由K=kG，將K代入上式可得M=C1-rkG。

③ 由C2=rG帶入上式，可得M=C1-k（rG）=C1-kC2。

④ A根據收到的C1、C2，用自己的私鑰k，可以計算出加密坐標點M。

參數要求：

① p越大安全性越好，但會導致計算速度變慢，200bit左右可滿足一般安全要求；

② n應為質數。

實例：（具體計算過程遵循有限域橢圓曲線的運算法則）

公鑰加密過程：

① 考慮參數a=0，b=-4，p=199，G=（2，2），橢圓曲線方程為E：y²=x³-4。

② A選定私鑰k=119，其公鑰K=kG=119G=（183，173）。

③ A將E、K、G發給B。

④ B將明文消息編碼為Ep（a，b）中的坐標點M=（76，66），并隨機選定r=133。

⑤ B計算C1=M+rK=（76，66）+133（183，173）=（180，163）；

C2=rG=133（2，2）=（40，147）。

⑥ B將C1、C2發給A。

私鑰解密過程：

A根據收到的C1、C2，用自己的私鑰k=119進行解密：

M=C1-kC2=（180，163）-119（40，147）=（180，163）-（98，52）=（76，66）

由此，A順利解密得到明文消息M，A與B之間完成加密通信。

（3）橢圓曲線簽名算法ECDSA

這里，依然假設私鑰、公鑰分別為k和K。其中K=kG，G為基點。

私鑰簽名過程：

A選擇隨機數r，計算點rG（x，y）。

A根據隨機數r、消息M的哈希h、私鑰k，計算s=（h+kx）/r。

A將消息M和簽名{rG，s}發給接收方。

公鑰驗證過程：

B收到消息M以及簽名{rG=（x，y），s}。

B根據消息M，求哈希h。

使用發送方公鑰K計算：hG/s+xK/s，并與rG比較，如相等即驗簽成功。

驗證原理：

hG/s+xK/s=hG/s+x（kG）/s=（h+xk）G/s=r（h+xk）G/（h+kx）=rG

這里關鍵的一點是引入了隨機數r，提高了簽名的安全性，即使同一條消息，只要改變隨機數r，所得到的簽名也會隨之改變。