【文章內(nèi)容簡介】 ；加密與解密算法通常是一些公式、法則或 程序，規(guī)定了明文與密文之間的數(shù)學變換規(guī)則 。 下面用字母分別表示這個概念，密鑰 K=Ke,Kd， Ke表示加密密鑰，Kd表示解密密鑰，設(shè)明文 M，密文 c，加密算法 E，解密算法 D。 把明文加密為密文 : C=E(M,Ke) 把密文解密為明文： M=D(C,Kd)=D(E(M,Ke),Kd) 上述的講解可用圖 21表示 （用安全信道傳輸密鑰） 圖 21 加密過程與密碼分析 公鑰加密體制 公鑰密碼基本概念 公鑰密碼概念是由 Whitfield Diffie和 MartinH ellma于 1976年提出的，它是 密碼學歷史上的一個重大成就。公鑰密碼與以前所有的密碼方法都大相徑庭 :一是以前的密碼算法都基于代換與置換操作，而公鑰密碼使用數(shù)學函加密密鑰 密鑰空間 解密密鑰 明文 明文空間 明文 明文空間 明文 明文空間 加密算法 解密算法 Interner（不安全信道） 傳輸?shù)膬?nèi)容 密碼分析 攻擊者 目的：求明文與密碼 第 2 章 密碼學基本理論及基本概念 7 數(shù)進行變 換；二是公鑰密碼體制使用非對稱的方式，使用兩個密鑰 (加密密鑰與解密密鑰 )，而傳統(tǒng)密碼算法僅僅使用一個密鑰。公鑰密碼體制的提出首先是為了解決利用傳統(tǒng)密碼體制進行密鑰分發(fā)時遇 到的問題，數(shù)字簽名也是其重要應用之一。 從 1976年起，學者們提出了許多種公鑰加密方法，它們的安全性都是基于 復雜的數(shù)學難題。根據(jù)所基于的數(shù)學難題來分類，有以下三類系統(tǒng)目前被認為 是安全和有效的： (1) 基 于大整數(shù)因子分解的： RSA和 RabinWilliams。 (2) 基于離散對數(shù)問題的： DSA和 EIGamal。 (3) 基 于橢圓曲線離散對數(shù)問題的：橢圓曲線密碼系統(tǒng)。 公開密鑰加密算法與對稱密鑰加密算法相比來說，安全性能更好，密鑰管 理、分配都容易實現(xiàn)，其中有些加密算法還能應用在數(shù)字簽名上，但是它們相 對于對稱密鑰加密算法運行速度要慢得多，所以不能加密大量的數(shù)據(jù)。 公鑰密碼原理 公開密鑰密碼理論是 1976年美國發(fā)表的 RSAl41算法，它是以三個發(fā)明人的 名字命名的，后來又有橢圓算法 ECC，但常用的 、成熟的公鑰算法是RSA。它 與傳統(tǒng)的對稱密鑰算法有本質(zhì)的區(qū)別，對稱密鑰算法常用的是 DES算法，加 /解密時用的是同一個密鑰。而公鑰算法利用的是非對稱的密鑰，即利用兩個足夠大的質(zhì)數(shù)與被加密原文相乘生產(chǎn)的積來加 /解密。這兩個質(zhì)數(shù)無論是用哪一個 與被加密的原文相乘 (模乘 )，即對原文件加密，均可由另一個質(zhì)數(shù)再相乘來進行解密。但是，若想用這個乘積來求出另一個質(zhì)數(shù)，就要進行對大數(shù)分解質(zhì)因 子，分解一個大數(shù)的質(zhì)因子是十分困難的，若選用的質(zhì)數(shù)足夠大，這種求解幾 乎是不可能的。因此，將這兩個質(zhì)數(shù)稱密鑰對，其中一個采用私密的安全介質(zhì) 保 密存儲起來，應不對任何外人泄露，簡稱為“私鑰”；一個密鑰可以公開發(fā)表，用數(shù)字證書的方式發(fā)布在稱之為“上黃頁”的目錄服務器上，用 LDAP協(xié) 議進行查詢，也可在網(wǎng)上請對方發(fā)送信息時主動將該公鑰證書傳送給對方，這 個密鑰稱之為“私鑰”。 公、密鑰對的用法是，當發(fā)方向收方通信時發(fā)方用收方的公鑰對原文進 行加密，收方收到發(fā)方的密文后，用自己的私鑰進行解密，其中他人是燕山大學本科生畢業(yè)設(shè)計（論文） 8 無法解 密的，因為他人不擁有自己的私鑰，這就是用公鑰加密，私鑰解密用于通信 。而用私鑰加密文件公鑰解密則是用于簽名，即發(fā)方向收方簽發(fā)文件時，發(fā)方用自己的私鑰加密文件 傳送給收方，收方用發(fā)方的公鑰進行解密。 但是，在實際應用操作中發(fā)出的文件簽名并非是對原文本身進行加密，而 是要對原文進行所謂的“哈?！?(Hash)運算，即對原文作數(shù)字摘要。該密碼算 法也稱單向散列運算，其運算結(jié)果稱為哈希值，或稱數(shù)字摘要，也有人將其稱 為“數(shù)字指紋”。哈希值有固定的長度，運算是不可逆的，不同的明文其哈希值 是不同的，而同樣的明文其哈希值是相同并且是唯一的，原文的任何改動，其 哈希值就要發(fā)生變化。數(shù)字簽名是用私鑰對數(shù)字摘要進行加密，用公鑰進行解 密和驗證。 公鑰證書和私鑰是用加密文件存放在證書介質(zhì)中，證書 是由認證服務機構(gòu) CA所簽發(fā)的權(quán)威電子文檔， CA與數(shù)字證書等是公鑰基礎(chǔ)設(shè)施 PKI的主要組成 機構(gòu)和元素。 公鑰密碼算法使用兩個密鑰，其中一個用于加密 (加密密鑰 )，另外一個用 于解密 (解密密鑰 )。公鑰密碼算法具有如下特征： 加密密鑰與解密密鑰時本質(zhì)上不通的，也就是說如果僅僅知道密碼算法和加密密鑰，而要確定解密密鑰，在計算上是不可行的；大多數(shù)公鑰密碼算法的加密密鑰與解密密鑰具有互換的性質(zhì)。如 RSA算法，密鑰對中的一個用于加密，另一個用于解密。 利用公鑰密碼體制進行數(shù)字簽名 下面舉例簡單介紹用戶 i把消息 x簽名 ，然后傳送給用戶 j的過程。 用戶 i首先產(chǎn)生簽名 )( xDx i? ；然后把 (x ,x )送給用戶 j即可。 用戶 j接受到 (x , x )后，驗證是否為用戶 i的簽名：首先計 )(xEr i? ；然 后通過比較， r=x 表示是用戶 i數(shù) 字 簽 名 ， 否 則 不 是 。 因 為xxDExE iii ?? ))(()( ， 所以可以通過比較 r與 x來判斷簽名的有效性。 因為 iD 是保密的，所以除了用戶 i之外，他人不能產(chǎn)生 x對應的正確的第 2 章 密碼學基本理論及基本概念 9 x ； 也就是說，他人不能假冒用戶 i進行數(shù)字簽名。 公鑰密碼體制的數(shù)學基礎(chǔ) 通觀公鑰密碼算法，它們的數(shù)學基礎(chǔ)是比較狹窄的。大多數(shù)公鑰密碼算法 都是基于以下三種數(shù)學難題之一的： 一是背包問題：給定一個互不相同的數(shù)組成的集合，要找出一個子集，其 和為 N。 二是離散對數(shù)問題：如果 P是素數(shù)， 9和 M是整數(shù)，找出 x，使得)(modpMgx ? ；還有一種方法，就是基于橢圓曲線的離散對數(shù)問題。 三是因數(shù)分解問題：設(shè) N是兩個素數(shù)的乘積，則： （ 1） 分解 N； （ 2） 給定整數(shù) M（明文）和 C（密文），尋找 d滿足 )(mod NCM d ? ； （ 3） 給定整數(shù) e和 C，尋找 M滿足 )(mod NCM e ? ； （ 4） 給定整數(shù) x，判定是否存在整數(shù) y 滿足 )(mod2 Nyx ? ； 對稱加密體制 對稱加密算法，又稱私鑰加密算法，就是加密密鑰能夠從解密密鑰中推出來，反過來也成立，在大多數(shù)對稱算法中，加密解密密鑰是相同的。對稱算法 的加密和解密表示為 : MCDCME kk ?? )(,)( （ 21） 對稱加密算法的典型代表有 :DES， AES， 3DES， RC2， RC4， RCS，RC6， IDEA等。 以 DES為代表的對稱密鑰加密算法的設(shè)計原則主要基于信息論的混亂和擴散?；靵y指的是密鑰和明文及密文之間的依賴關(guān)系應該盡量復雜，以破壞分組間的 統(tǒng)計規(guī)律，通常依靠多輪迭代來實現(xiàn)；擴散則應使密鑰和明文的每一位影響密文中盡可能多的位數(shù)， 這樣可以防止逐段破譯，并通過 S盒的非線性變換來實現(xiàn)。實際上，所有的對稱密鑰加密算法都采用 Feistel網(wǎng)、 S盒及多次迭代等思 想。 燕山大學本科生畢業(yè)設(shè)計（論文） 10 對稱加密有速度上的優(yōu)點，用軟件實現(xiàn)，對稱密鑰比非對稱密鑰快1001000倍。然而，如果一個消息想以密文的形式傳到接收者，我們應該找到一個方法 安全傳輸密鑰。對稱加密系統(tǒng)用鍵長來衡量加密強度， 40比特的鍵長被認為比 較脆弱， 128比特比較健壯。 對稱加密算法的缺點則是密鑰分發(fā)困難，密鑰管理難，無法實現(xiàn)數(shù)字簽名。 常用數(shù)字簽名算法 早在 1979年， 討論應用于美蘇兩國的禁止核試 驗條約的驗證工作中。在 1991年，美國 NIST公布了其數(shù)字簽名標準，DSS(Digital Signature Standard)，于 1994年正式采用為美國聯(lián)邦信息處理標準； DSS標準中采用的簽名算法稱為 DSA。隨后其他一些國家也頒布了自己的數(shù)字 簽名標準，如俄羅斯 1994年頒布的 GOST 。較早出現(xiàn)的數(shù)字簽名算法，如 1978年前后提出的 RSA， Rabin等數(shù)字簽名算法，至今還在使用 。 第 3 章 橢圓曲線密碼算法的研究 11 第 3 章 橢圓曲線密碼算法的研究 群（ Groups） 抽象代數(shù) ]11,10,9[ 不但是數(shù)學的一個重要分之，同時在其他學科如量子力學、結(jié)晶學、原子物理學等中都己經(jīng)稱為研究者的有力武器；群論因為是研究對稱性問題的基礎(chǔ)，例如其在物理學中在諸如時間和空間的對稱性研究、乃至超對稱性問題等研究中都有應用。在密碼學中，抽象代數(shù)也己經(jīng)扮演重要角色，如在橢圓曲線密碼體制中，群以及域上的多項式理論等都是其理論基礎(chǔ)。 設(shè)有一個由任意元素 a， b， c...組成的非空集合 G，即 }{ igG? 。在 G上有一 個針對其中元素進行組合操作的二元運算規(guī)則 *，同時滿足 下列四個條件，則 G對于運算 *稱為群，并稱二元運算 *為群的運算。 (1) 封閉性 對于任意 Gba ?、 ，有 Gab? 。 (2) 結(jié)合律成立 對于任意 Gcba ?, ，有 (ab)c=a(bc)。 (3) 有單位元 e 對任意 Ga? ，有 Ge? ，使得 ae=ea=a。 (4) 存在逆元 對任意 Ga? ，有 Ga ??1 ,使 eaaaa ?? ?? ** 11 ；稱aa,1? 互為逆元。 上述四個條件是構(gòu)成群的充分必要條件，通常被稱為群的公理。若僅滿足 條件 (1)和 (2)，則被稱為半群 (Semigroup)；滿足條件 (1)， (2)和 (3)者，稱 么半群 (Monoid)、弱群或類群。 若群 G對運算還滿足交換律，即對于任意的 ig ， Ggi? ，都有 ig ig =ig ig成立，則稱群 G為交換群或阿貝爾群 (Abel Groups)。此時，通常用符號“ +”來代替“ ”稱群運算“ +”為“加法”，稱 a+b為 a與 b的和，稱 單位元素。為零元素 O，稱逆元素 1?a 為元素 a的負元素，并一記作 a。相應的，稱群運算“”為“乘法”，稱 a b為 a與 b的積，簡寫為 ab。 燕山大學本科生畢業(yè)設(shè)計（論文） 12 例如：全體整數(shù)的集合在通常的加法運算下構(gòu)成一個阿貝爾交換群。 設(shè) n為任意正整數(shù)，對于任意的 Ga? ，定義： nnnn aaeaa aaa )(, 10, ?? ??? ? ?個 則對于任意整數(shù) m，有 nmnmmnnm aaaaa ??? ,)( 。定義 a表示所有的 ma的集合， 則 a也構(gòu)成一個有限群。特別的，若 G中一個元素 a，得 a=G成立，則稱 G為循環(huán)群。顯然，循環(huán)群 G都是阿貝爾群。 例如：由集合 {1， 1}對于乘法運算所構(gòu)成的群就是二階循環(huán)群。 設(shè) n為任意正整數(shù)，對于任意的 Ga? ，稱滿足 Ean? 的最小正整數(shù) n為群元 a的階數(shù)。顯然，對于有限群 G而言，其每一群元的階都是有 限正整數(shù)。 例如：在由集合 {1， 1}對于乘法運算所構(gòu)成的群中，群元一 1的階數(shù)為2。 自 19世紀中葉由拉格朗日、阿貝爾、伽羅瓦等人引入群的概念以來，經(jīng)過一百多年的發(fā)展，群論己經(jīng)成為現(xiàn)代代數(shù)學的重要分支，其內(nèi)容非常豐富。 下面介紹一些與橢圓曲線密碼學有關(guān)的群的重要性質(zhì)： （ 1） 廣義結(jié)合律：對群中的任意 n個元素 g1， g2， g3， ..gn，其積g1g2...gn唯一確定。 由自然歸納法和結(jié)合律很容易得到此結(jié)論。 （ 2） 單位元 e都是唯一的。 用反證法。若 e1和 e2都是群 G的單位元，則根據(jù)群的公有： 21221121 eeeeeeee ??? ，則， 。 （ 3）存在 Gcba ?， ， 若 ab=ac，則 b=c；若 ab=cb，則 a=c。 先證明第一條。若 ab=ac，用 1?a 互乘等式兩端得 : )()( 11 acaaba ?? ? 根據(jù)結(jié)合律，可知 caabaaaba )()()( 111 ??? ?? ,所以， b=c （ 4）每一元素的逆元是唯一的。 用反證法。若不然，設(shè)群元 G存在兩個逆元 Gcb ?, ，則依據(jù)群的公理，有 ab=ac=e 由上述的性質(zhì) (3)可知 b=c， 所以群元的逆元唯一。 第 3 章 橢圓曲線密碼算法的研究 13 有限域（ Finite Field） 只含有有限多個元素的域叫有限域。由于它首先由 ，因而又被稱為伽羅瓦域 (Galois Field)。在同構(gòu)意義下，對任一素數(shù) P和正整數(shù) n，存在且僅存在一個含廠個元素的有限域 ，記作 )( npGF 。有限域 )( npGF的特征為 P，其階為域中元素的個數(shù)，即 np 。另一方面，對 q1整數(shù)而言，q階有限域 GF(q)存在的充要條件是 q是某一素數(shù)的整次冪 (以下簡稱素數(shù)冪 )。 設(shè)有限域 GF(q)上的多項式為： )(,)( 0111 pGFffxfxfxfxf innnn ????? ?? ? ni ,2,0 ?? ,