加密算法介紹

褚慶東

一.          密碼學(xué)簡(jiǎn)介

據(jù)記載，公元前400年，古希臘人發(fā)明了置換密碼。1881年世界上的第一個(gè)電話(huà)保密專(zhuān)利出現(xiàn)。在第二次世界大戰(zhàn)期間，德國(guó)軍方啟用“恩尼格瑪”密碼機(jī)，密碼學(xué)在戰(zhàn)爭(zhēng)中起著非常重要的作用。

隨著信息化和數(shù)字化社會(huì)的發(fā)展，人們對(duì)信息安全和保密的重要性認(rèn)識(shí)不斷提高，于是在1997年，美國(guó)國(guó)家標(biāo)準(zhǔn)局公布實(shí)施了“美國(guó)數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）”，民間力量開(kāi)始全面介入密碼學(xué)的研究和應(yīng)用中，采用的加密算法有DES、RSA、SHA等。隨著對(duì)加密強(qiáng)度需求的不斷提高，近期又出現(xiàn)了AES、ECC等。

使用密碼學(xué)可以達(dá)到以下目的：

保密性：防止用戶(hù)的標(biāo)識(shí)或數(shù)據(jù)被讀取。

數(shù)據(jù)完整性：防止數(shù)據(jù)被更改。

身份驗(yàn)證：確保數(shù)據(jù)發(fā)自特定的一方。

二.          加密算法介紹

根據(jù)密鑰類(lèi)型不同將現(xiàn)代密碼技術(shù)分為兩類(lèi)：對(duì)稱(chēng)加密算法（秘密鑰匙加密）和非對(duì)稱(chēng)加密算法（公開(kāi)密鑰加密）。

對(duì)稱(chēng)鑰匙加密系統(tǒng)是加密和解密均采用同一把秘密鑰匙，而且通信雙方都必須獲得這把鑰匙，并保持鑰匙的秘密。

非對(duì)稱(chēng)密鑰加密系統(tǒng)采用的加密鑰匙（公鑰）和解密鑰匙（私鑰）是不同的。

對(duì)稱(chēng)加密算法

對(duì)稱(chēng)加密算法用來(lái)對(duì)敏感數(shù)據(jù)等信息進(jìn)行加密，常用的算法包括：

DES（Data Encryption Standard）：數(shù)據(jù)加密標(biāo)準(zhǔn)，速度較快，適用于加密大量數(shù)據(jù)的場(chǎng)合。

3DES（Triple DES）：是基于DES，對(duì)一塊數(shù)據(jù)用三個(gè)不同的密鑰進(jìn)行三次加密，強(qiáng)度更高。

AES（Advanced Encryption Standard）：高級(jí)加密標(biāo)準(zhǔn)，是下一代的加密算法標(biāo)準(zhǔn)，速度快，安全級(jí)別高；

AES

2000年10月，NIST（美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)）宣布通過(guò)從15種侯選算法中選出的一項(xiàng)新的密匙加密標(biāo)準(zhǔn)。Rijndael被選中成為將來(lái)的AES。 Rijndael是在 1999 年下半年，由研究員 Joan Daemen 和 Vincent Rijmen 創(chuàng)建的。AES 正日益成為加密各種形式的電子數(shù)據(jù)的實(shí)際標(biāo)準(zhǔn)。

美國(guó)標(biāo)準(zhǔn)與技術(shù)研究院 (NIST) 于 2002 年 5 月 26 日制定了新的高級(jí)加密標(biāo)準(zhǔn) (AES) 規(guī)范。

算法原理

AES 算法基于排列和置換運(yùn)算。排列是對(duì)數(shù)據(jù)重新進(jìn)行安排，置換是將一個(gè)數(shù)據(jù)單元替換為另一個(gè)。AES 使用幾種不同的方法來(lái)執(zhí)行排列和置換運(yùn)算。

AES 是一個(gè)迭代的、對(duì)稱(chēng)密鑰分組的密碼，它可以使用128、192 和 256 位密鑰，并且用 128 位（16字節(jié)）分組加密和解密數(shù)據(jù)。與公共密鑰密碼使用密鑰對(duì)不同，對(duì)稱(chēng)密鑰密碼使用相同的密鑰加密和解密數(shù)據(jù)。通過(guò)分組密碼返回的加密數(shù)據(jù)的位數(shù)與輸入數(shù)據(jù)相同。迭代加密使用一個(gè)循環(huán)結(jié)構(gòu)，在該循環(huán)中重復(fù)置換和替換輸入數(shù)據(jù)。

AES與3DES的比較

非對(duì)稱(chēng)算法

常見(jiàn)的非對(duì)稱(chēng)加密算法如下：

RSA：由 RSA 公司發(fā)明，是一個(gè)支持變長(zhǎng)密鑰的公共密鑰算法，需要加密的文件塊的長(zhǎng)度也是可變的；

DSA（Digital Signature Algorithm）：數(shù)字簽名算法，是一種標(biāo)準(zhǔn)的 DSS（數(shù)字簽名標(biāo)準(zhǔn)）；

ECC（Elliptic Curves Cryptography）：橢圓曲線(xiàn)密碼編碼學(xué)。

ECC

在1976年，由于對(duì)稱(chēng)加密算法已經(jīng)不能滿(mǎn)足需要，Diffie 和Hellman發(fā)表了一篇叫《密碼學(xué)新動(dòng)向》的文章，介紹了公匙加密的概念，由Rivet、Shamir、Adelman提出了RSA算法。

隨著分解大整數(shù)方法的進(jìn)步及完善、計(jì)算機(jī)速度的提高以及計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，為了保障數(shù)據(jù)的安全，RSA的密鑰需要不斷增加，但是，密鑰長(zhǎng)度的增加導(dǎo)致了其加解密的速度大為降低，硬件實(shí)現(xiàn)也變得越來(lái)越難以忍受，這對(duì)使用RSA的應(yīng)用帶來(lái)了很重的負(fù)擔(dān)，因此需要一種新的算法來(lái)代替RSA。

1985年N.Koblitz和Miller提出將橢圓曲線(xiàn)用于密碼算法，根據(jù)是有限域上的橢圓曲線(xiàn)上的點(diǎn)群中的離散對(duì)數(shù)問(wèn)題ECDLP。ECDLP是比因子分解問(wèn)題更難的問(wèn)題，它是指數(shù)級(jí)的難度。

原理——橢圓曲線(xiàn)上的難題

 橢圓曲線(xiàn)上離散對(duì)數(shù)問(wèn)題ECDLP定義如下：給定素?cái)?shù)p和橢圓曲線(xiàn)E，對(duì)Q＝kP，在已知P，Q 的情況下求出小于p的正整數(shù)k?？梢宰C明由k和P計(jì)算Q比較容易，而由Q和P計(jì)算k則比較困難。

將橢圓曲線(xiàn)中的加法運(yùn)算與離散對(duì)數(shù)中的模乘運(yùn)算相對(duì)應(yīng)，將橢圓曲線(xiàn)中的乘法運(yùn)算與離散對(duì)數(shù)中的模冪運(yùn)算相對(duì)應(yīng)，我們就可以建立基于橢圓曲線(xiàn)的對(duì)應(yīng)的密碼體制。

例如，對(duì)應(yīng)Diffie-Hellman公鑰系統(tǒng)，我們可以通過(guò)如下方式在橢圓曲線(xiàn)上予以實(shí)現(xiàn)：在E上選取生成元P，要求由P產(chǎn)生的群元素足夠多，通信雙方A和B分別選取a和b，a和b 予以保密，但將aP和bP公開(kāi)，A和B間通信用的密鑰為abP，這是第三者無(wú)法得知的。

對(duì)應(yīng)ELGamal密碼系統(tǒng)可以采用如下的方式在橢圓曲線(xiàn)上予以實(shí)現(xiàn)：

將明文m嵌入到E上Pm點(diǎn)，選一點(diǎn)B∈E，每一用戶(hù)都選一整數(shù)a，0＜a＜N，N為階數(shù)已知，a保密，aB公開(kāi)。欲向A送m，可送去下面一對(duì)數(shù)偶：［kB，Pm+k(aAB)］，k是隨機(jī)產(chǎn)生的整數(shù)。A可以從kB求得k(aAB)。通過(guò)：Pm+k(aAB)- k(aAB)=Pm恢復(fù)Pm。同樣對(duì)應(yīng)DSA，考慮如下等式：

K=kG  [其中 K，G為Ep(a,b)上的點(diǎn)，k為小于n（n是點(diǎn)G的階）的整數(shù)]

不難發(fā)現(xiàn)，給定k和G，根據(jù)加法法則，計(jì)算K很容易；但給定K和G，求k就相對(duì)困難了。

這就是橢圓曲線(xiàn)加密算法采用的難題。我們把點(diǎn)G稱(chēng)為基點(diǎn)（base point），k（k<n，n為基點(diǎn)G的階）稱(chēng)為私有密鑰（privte key），K稱(chēng)為公開(kāi)密鑰（public key)。

ECC與RSA的比較

ECC和RSA相比，在許多方面都有對(duì)絕對(duì)的優(yōu)勢(shì)，主要體現(xiàn)在以下方面：

抗攻擊性強(qiáng)。相同的密鑰長(zhǎng)度，其抗攻擊性要強(qiáng)很多倍。

計(jì)算量小，處理速度快。ECC總的速度比RSA、DSA要快得多。

存儲(chǔ)空間占用小。ECC的密鑰尺寸和系統(tǒng)參數(shù)與RSA、DSA相比要小得多，意味著它所占的存貯空間要小得多。這對(duì)于加密算法在IC卡上的應(yīng)用具有特別重要的意義。

帶寬要求低。當(dāng)對(duì)長(zhǎng)消息進(jìn)行加解密時(shí)，三類(lèi)密碼系統(tǒng)有相同的帶寬要求，但應(yīng)用于短消息時(shí)ECC帶寬要求卻低得多。帶寬要求低使ECC在無(wú)線(xiàn)網(wǎng)絡(luò)領(lǐng)域具有廣泛的應(yīng)用前景。

ECC的這些特點(diǎn)使它必將取代RSA，成為通用的公鑰加密算法。比如SET協(xié)議的制定者已把它作為下一代SET協(xié)議中缺省的公鑰密碼算法。

下面兩張表示是RSA和ECC的安全性和速度的比較。

RSA和ECC安全模長(zhǎng)得比較

RSA和ECC速度比較

散列算法

散列是信息的提煉，通常其長(zhǎng)度要比信息小得多，且為一個(gè)固定長(zhǎng)度。加密性強(qiáng)的散列一定是不可逆的，這就意味著通過(guò)散列結(jié)果，無(wú)法推出任何部分的原始信息。任何輸入信息的變化，哪怕僅一位，都將導(dǎo)致散列結(jié)果的明顯變化，這稱(chēng)之為雪崩效應(yīng)。散列還應(yīng)該是防沖突的，即找不出具有相同散列結(jié)果的兩條信息。具有這些特性的散列結(jié)果就可以用于驗(yàn)證信息是否被修改。

單向散列函數(shù)一般用于產(chǎn)生消息摘要，密鑰加密等，常見(jiàn)的有：

l         MD5（Message Digest Algorithm 5）：是RSA數(shù)據(jù)安全公司開(kāi)發(fā)的一種單向散列算法。

l         SHA（Secure Hash Algorithm）：可以對(duì)任意長(zhǎng)度的數(shù)據(jù)運(yùn)算生成一個(gè)160位的數(shù)值；

SHA-1

在1993年，安全散列算法（SHA）由美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)(NIST)提出，并作為聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPS PUB 180）公布；1995年又發(fā)布了一個(gè)修訂版FIPS PUB 180-1，通常稱(chēng)之為SHA-1。SHA-1是基于MD4算法的，并且它的設(shè)計(jì)在很大程度上是模仿MD4的?，F(xiàn)在已成為公認(rèn)的最安全的散列算法之一，并被廣泛使用。

原理

SHA-1是一種數(shù)據(jù)加密算法，該算法的思想是接收一段明文，然后以一種不可逆的方式將它轉(zhuǎn)換成一段（通常更?。┟芪?，也可以簡(jiǎn)單的理解為取一串輸入碼（稱(chēng)為預(yù)映射或信息），并把它們轉(zhuǎn)化為長(zhǎng)度較短、位數(shù)固定的輸出序列即散列值（也稱(chēng)為信息摘要或信息認(rèn)證代碼）的過(guò)程。

單向散列函數(shù)的安全性在于其產(chǎn)生散列值的操作過(guò)程具有較強(qiáng)的單向性。如果在輸入序列中嵌入密碼，那么任何人在不知道密碼的情況下都不能產(chǎn)生正確的散列值，從而保證了其安全性。ＳＨＡ將輸入流按照每塊５１２位（６４個(gè)字節(jié)）進(jìn)行分塊，并產(chǎn)生２０個(gè)字節(jié)的被稱(chēng)為信息認(rèn)證代碼或信息摘要的輸出。

該算法輸入報(bào)文的最大長(zhǎng)度不超過(guò)264位，產(chǎn)生的輸出是一個(gè)160位的報(bào)文摘要。輸入是按512 位的分組進(jìn)行處理的。SHA-1是不可逆的、防沖突，并具有良好的雪崩效應(yīng)。

通過(guò)散列算法可實(shí)現(xiàn)數(shù)字簽名實(shí)現(xiàn)，數(shù)字簽名的原理是將要傳送的明文通過(guò)一種函數(shù)運(yùn)算（Hash）轉(zhuǎn)換成報(bào)文摘要（不同的明文對(duì)應(yīng)不同的報(bào)文摘要），報(bào)文摘要加密后與明文一起傳送給接受方，接受方將接受的明文產(chǎn)生新的報(bào)文摘要與發(fā)送方的發(fā)來(lái)報(bào)文摘要解密比較，比較結(jié)果一致表示明文未被改動(dòng)，如果不一致表示明文已被篡改。

MAC (信息認(rèn)證代碼)就是一個(gè)散列結(jié)果，其中部分輸入信息是密碼，只有知道這個(gè)密碼的參與者才能再次計(jì)算和驗(yàn)證MAC碼的合法性。MAC的產(chǎn)生參見(jiàn)下圖。

SHA-1與MD5的比較

因?yàn)槎呔?/span>MD4導(dǎo)出，SHA-1和MD5彼此很相似。相應(yīng)的，他們的強(qiáng)度和其他特性也是相似，但還有以下幾點(diǎn)不同：

l         對(duì)強(qiáng)行供給的安全性：最顯著和最重要的區(qū)別是SHA-1摘要比MD5摘要長(zhǎng)32 位。使用強(qiáng)行技術(shù)，產(chǎn)生任何一個(gè)報(bào)文使其摘要等于給定報(bào)摘要的難度對(duì)MD5是2¹²⁸數(shù)量級(jí)的操作，而對(duì)SHA-1則是2¹⁶⁰數(shù)量級(jí)的操作。這樣，SHA-1對(duì)強(qiáng)行攻擊有更大的強(qiáng)度。

l         對(duì)密碼分析的安全性：由于MD5的設(shè)計(jì)，易受密碼分析的攻擊，SHA-1顯得不易受這樣的攻擊。

l         速度：在相同的硬件上，SHA-1的運(yùn)行速度比MD5慢。

對(duì)稱(chēng)與非對(duì)稱(chēng)算法比較

    以上綜述了兩種加密方法的原理，總體來(lái)說(shuō)主要有下面幾個(gè)方面的不同：

l         在管理方面：公鑰密碼算法只需要較少的資源就可以實(shí)現(xiàn)目的，在密鑰的分配上，兩者之間相差一個(gè)指數(shù)級(jí)別（一個(gè)是n一個(gè)是n²）。所以私鑰密碼算法不適應(yīng)廣域網(wǎng)的使用，而且更重要的一點(diǎn)是它不支持?jǐn)?shù)字簽名。

l         在安全方面：由于公鑰密碼算法基于未解決的數(shù)學(xué)難題，在破解上幾乎不可能。對(duì)于私鑰密碼算法，到了AES雖說(shuō)從理論來(lái)說(shuō)是不可能破解的，但從計(jì)算機(jī)的發(fā)展角度來(lái)看。公鑰更具有優(yōu)越性。

l         從速度上來(lái)看：AES的軟件實(shí)現(xiàn)速度已經(jīng)達(dá)到了每秒數(shù)兆或數(shù)十兆比特。是公鑰的100倍，如果用硬件來(lái)實(shí)現(xiàn)的話(huà)這個(gè)比值將擴(kuò)大到1000倍。

三.          加密算法的選擇

前面的章節(jié)已經(jīng)介紹了對(duì)稱(chēng)解密算法和非對(duì)稱(chēng)加密算法，有很多人疑惑：那我們?cè)趯?shí)際使用的過(guò)程中究竟該使用哪一種比較好呢？

我們應(yīng)該根據(jù)自己的使用特點(diǎn)來(lái)確定，由于非對(duì)稱(chēng)加密算法的運(yùn)行速度比對(duì)稱(chēng)加密算法的速度慢很多，當(dāng)我們需要加密大量的數(shù)據(jù)時(shí)，建議采用對(duì)稱(chēng)加密算法，提高加解密速度。

對(duì)稱(chēng)加密算法不能實(shí)現(xiàn)簽名，因此簽名只能非對(duì)稱(chēng)算法。

由于對(duì)稱(chēng)加密算法的密鑰管理是一個(gè)復(fù)雜的過(guò)程，密鑰的管理直接決定著他的安全性，因此當(dāng)數(shù)據(jù)量很小時(shí)，我們可以考慮采用非對(duì)稱(chēng)加密算法。

在實(shí)際的操作過(guò)程中，我們通常采用的方式是：采用非對(duì)稱(chēng)加密算法管理對(duì)稱(chēng)算法的密鑰，然后用對(duì)稱(chēng)加密算法加密數(shù)據(jù)，這樣我們就集成了兩類(lèi)加密算法的優(yōu)點(diǎn)，既實(shí)現(xiàn)了加密速度快的優(yōu)點(diǎn)，又實(shí)現(xiàn)了安全方便管理密鑰的優(yōu)點(diǎn)。

如果在選定了加密算法后，那采用多少位的密鑰呢？一般來(lái)說(shuō)，密鑰越長(zhǎng)，運(yùn)行的速度就越慢，應(yīng)該根據(jù)的我們實(shí)際需要的安全級(jí)別來(lái)選擇，一般來(lái)說(shuō)，RSA建議采用1024位的數(shù)字，ECC建議采用160位，AES采用128為即可。

四.          密碼學(xué)在現(xiàn)代的應(yīng)用

隨著密碼學(xué)商業(yè)應(yīng)用的普及，公鑰密碼學(xué)受到前所未有的重視。除傳統(tǒng)的密碼應(yīng)用系統(tǒng)外，PKI系統(tǒng)以公鑰密碼技術(shù)為主，提供加密、簽名、認(rèn)證、密鑰管理、分配等功能。

保密通信：保密通信是密碼學(xué)產(chǎn)生的動(dòng)因。使用公私鑰密碼體制進(jìn)行保密通信時(shí)，信息接收者只有知道對(duì)應(yīng)的密鑰才可以解密該信息。

數(shù)字簽名：數(shù)字簽名技術(shù)可以代替?zhèn)鹘y(tǒng)的手寫(xiě)簽名，而且從安全的角度考慮，數(shù)字簽名具有很好的防偽造功能。在政府機(jī)關(guān)、軍事領(lǐng)域、商業(yè)領(lǐng)域有廣泛的應(yīng)用環(huán)境。

秘密共享：秘密共享技術(shù)是指將一個(gè)秘密信息利用密碼技術(shù)分拆成n個(gè)稱(chēng)為共享因子的信息，分發(fā)給n個(gè)成員，只有k(k≤n)個(gè)合法成員的共享因子才可以恢復(fù)該秘密信息，其中任何一個(gè)或m(m≤k)個(gè)成員合作都不知道該秘密信息。利用秘密共享技術(shù)可以控制任何需要多個(gè)人共同控制的秘密信息、命令等。

認(rèn)證功能：在公開(kāi)的信道上進(jìn)行敏感信息的傳輸，采用簽名技術(shù)實(shí)現(xiàn)對(duì)消息的真實(shí)性、完整性進(jìn)行驗(yàn)證，通過(guò)驗(yàn)證公鑰證書(shū)實(shí)現(xiàn)對(duì)通信主體的身份驗(yàn)證。

密鑰管理：密鑰是保密系統(tǒng)中更為脆弱而重要的環(huán)節(jié)，公鑰密碼體制是解決密鑰管理工作的有力工具；利用公鑰密碼體制進(jìn)行密鑰協(xié)商和產(chǎn)生，保密通信雙方不需要事先共享秘密信息；利用公鑰密碼體制進(jìn)行密鑰分發(fā)、保護(hù)、密鑰托管、密鑰恢復(fù)等。

基于公鑰密碼體制可以實(shí)現(xiàn)以上通用功能以外，還可以設(shè)計(jì)實(shí)現(xiàn)以下的系統(tǒng)：安全電子商務(wù)系統(tǒng)、電子現(xiàn)金系統(tǒng)、電子選舉系統(tǒng)、電子招投標(biāo)系統(tǒng)、電子彩票系統(tǒng)等。

公鑰密碼體制的產(chǎn)生是密碼學(xué)由傳統(tǒng)的政府、軍事等應(yīng)用領(lǐng)域走向商用、民用的基礎(chǔ)，同時(shí)互聯(lián)網(wǎng)、電子商務(wù)的發(fā)展為密碼學(xué)的發(fā)展開(kāi)辟了更為廣闊的前景。

五.          加密算法的未來(lái)

隨著計(jì)算方法的改進(jìn)，計(jì)算機(jī)運(yùn)行速度的加快，網(wǎng)絡(luò)的發(fā)展，越來(lái)越多的算法被破解。

在2004年國(guó)際密碼學(xué)會(huì)議(Crypto’2004)上，來(lái)自中國(guó)山東大學(xué)的王小云教授做的破譯MD5、HAVAL-128、MD4和RIPEMD算法的報(bào)告，令在場(chǎng)的國(guó)際頂尖密碼學(xué)專(zhuān)家都為之震驚，意味著這些算法將從應(yīng)用中淘汰。隨后，SHA-1也被宣告被破解。

歷史上有三次對(duì)DES有影響的攻擊實(shí)驗(yàn)。1997年，利用當(dāng)時(shí)各國(guó) 7萬(wàn)臺(tái)計(jì)算機(jī)，歷時(shí)96天破解了DES的密鑰。1998年，電子邊境基金會(huì)（EFF）用25萬(wàn)美元制造的專(zhuān)用計(jì)算機(jī)，用56小時(shí)破解了DES的密鑰。1999年，EFF用22小時(shí)15分完成了破解工作。因此。曾經(jīng)有過(guò)卓越貢獻(xiàn)的DES也不能滿(mǎn)足我們?nèi)找嬖鲩L(zhǎng)的需求了。

最近，一組研究人員成功的把一個(gè)512位的整數(shù)分解因子，宣告了RSA的破解。

我們說(shuō)數(shù)據(jù)的安全是相對(duì)的，可以說(shuō)在一定時(shí)期一定條件下是安全的，隨著硬件和網(wǎng)絡(luò)的發(fā)展，或者是另一個(gè)王小云的出現(xiàn)，目前的常用加密算法都有可能在短時(shí)間內(nèi)被破解，那時(shí)我們不得不使用更長(zhǎng)的密鑰或更加先進(jìn)的算法，才能保證數(shù)據(jù)的安全，因此加密算法依然需要不斷發(fā)展和完善，提供更高的加密安全強(qiáng)度和運(yùn)算速度。

縱觀這兩種算法一個(gè)從DES到3DES再到AES，一個(gè)從RSA到ECC。其發(fā)展角度無(wú)不是從密鑰的簡(jiǎn)單性，成本的低廉性，管理的簡(jiǎn)易性，算法的復(fù)雜性，保密的安全性以及計(jì)算的快速性這幾個(gè)方面去考慮。因此，未來(lái)算法的發(fā)展也必定是從這幾個(gè)角度出發(fā)的，而且在實(shí)際操作中往往把這兩種算法結(jié)合起來(lái)，也需將來(lái)一種集兩種算法優(yōu)點(diǎn)于一身的新型算法將會(huì)出現(xiàn)，到那個(gè)時(shí)候，電子商務(wù)的實(shí)現(xiàn)必將更加的快捷和安全。