代數(shù)在網(wǎng)絡(luò)安全中應(yīng)用培訓(xùn)課件

1、代數(shù)在網(wǎng)絡(luò)安全中應(yīng)用培訓(xùn)課件概述 現(xiàn)有的公鑰密碼體制大多是建立在交換代數(shù)的基礎(chǔ)上, 例如著名的RSA 密碼體制、DiffieHellman 密鑰交換協(xié)議和ELGamal 密碼體制都基于整數(shù)環(huán), 而概率公鑰算法NTRU則基于多項(xiàng)式環(huán)交換代數(shù)結(jié)構(gòu)的優(yōu)點(diǎn)在于有豐富的理論、容易理解的結(jié)構(gòu)并且易于實(shí)現(xiàn)但是, 由于計(jì)算能力的持續(xù)增強(qiáng), 為保證預(yù)期安全水平所需要的密鑰長度也不斷增長, 這就使得基于交換代數(shù)的公鑰密碼遭遇了計(jì)算瓶頸因此有必要尋找基于更加復(fù)雜的代數(shù)結(jié)構(gòu)的密碼技術(shù) 近年出現(xiàn)的一種具有強(qiáng)大競爭力的橢圓曲線密碼學(xué)（ECC）對RSA 提出了挑戰(zhàn)在關(guān)于公鑰密碼學(xué)的IEEEP1363 中, 已經(jīng)考慮了ECC

2、在公鑰密碼學(xué)中使用橢圓曲線是Neal Koblitz和Victor Miller于1985 年各自獨(dú)立地提出的與RSA , ECC 的主要誘人之處在于它可以用比RSA 短得多的密鑰得到相同的安全性, 因此可以減少處理負(fù)荷 近年來, 基于（超奇異）橢圓曲線上雙線性對的密碼體制的研究十分活躍, 解決了構(gòu)造三方一輪DiffieHellman 密鑰協(xié)議、短簽名方案和基于身份加密算法等長期懸而未決的公開問題但是, 正如BarretoLynnScott所指出, （超奇異）橢圓曲線上Weil 對與Tate 對的運(yùn)算成本經(jīng)常使它成為基于雙線性對密碼系統(tǒng)的瓶頸尋找安全高效的雙線性對已成為基于雙線性對密碼學(xué)的首要

3、問題 目前, 已經(jīng)出現(xiàn)了一些使用非交換代數(shù)的公鑰密碼系統(tǒng), 尤其是辮子群密碼學(xué)吸引了大量的研究1999 年,Anshel-Anshel-Goldfeld基于辮子群中的共軛問題構(gòu)建了密鑰交換協(xié)議2000 年, KoLee 等人利用辮子群的子群間的交換關(guān)系構(gòu)建了基于廣義共軛問題的DiffieHellman 密鑰交換協(xié)議, 以及一個類似于ELGamal 體制的加密算法但是, 由于非交換群中沒有像整數(shù)環(huán)中加法那樣與共軛運(yùn)算相容的運(yùn)算, 這使得基于非交換群的簽名方案的設(shè)計(jì)變得困難直到2002 年, Ko-Choi-Cho-Lee才基于共軛問題的計(jì)算形式和判定形式之間的鴻溝（Gap）設(shè)計(jì)了第一個辮子群簽名

4、方案目錄 基于橢圓曲線的密碼算法 循環(huán)矩陣在網(wǎng)絡(luò)安全中的應(yīng)用 DES算法 基于雙線性對的密碼學(xué) 基于辮子群的密碼體制 AES算法 RSA算法 SHA-1算法 離散對數(shù)密碼體制橢圓曲線在網(wǎng)絡(luò)安全中的應(yīng)用 橢圓曲線的定義及點(diǎn)的加法運(yùn)算有限域上的橢圓曲線橢圓曲線的離散對數(shù)問題橢圓曲線密碼體制的概念 橢圓曲線密碼體制是屬于公鑰密碼體制中的一種，它主要的數(shù)學(xué)理論基礎(chǔ)是源于數(shù)論的相關(guān)知識，它是通過有限域中橢圓曲線上的點(diǎn)構(gòu)成的Aebel加法群，在Aebel群中計(jì)算橢圓對數(shù) 。 現(xiàn)在國際上比較流行的密碼體制都是以三種難解的理論為依據(jù)而設(shè)計(jì)的，其中一種是基于大整數(shù)因子分解問題設(shè)計(jì)的比如RSA公鑰密碼體制，還有一

5、種是基于離散對數(shù)的難解問題而設(shè)計(jì)的比如ELGamal公鑰密碼體制，最后一種就是同樣基于離散對數(shù)問題設(shè)計(jì)的橢圓曲線密碼體制。構(gòu)造橢圓曲線ElGamal算法 ElGamal算法，是一種較為常見的加密算法，它是基于1984年提出的公鑰密碼體制和橢圓曲線加密體系。既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計(jì)算有限域上離散對數(shù)這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密后都會在密文中生成一個隨機(jī)數(shù)K，在密碼中主要應(yīng)用離散對數(shù)問題的幾個性質(zhì)：求解離散對數(shù)（可能）是困難的，而其逆運(yùn)算指數(shù)運(yùn)算可以應(yīng)用平方-乘的方法有效地計(jì)算。也就是說，在適當(dāng)?shù)娜篏中，指數(shù)函數(shù)是單向函數(shù)。橢圓曲面密碼體

6、制的應(yīng)用背景及優(yōu)勢 我們現(xiàn)在快速的生活節(jié)奏和便捷的生活方式都是顯而易見的，足不出戶的我們就能夠通過計(jì)算機(jī)完成許多的事情，比如工作、購物等，由于需求的增加導(dǎo)致計(jì)算機(jī)也不斷的改進(jìn)提高，尤其是計(jì)算機(jī)速度的提高，同時(shí)也就需要更好更完善的加密方案。由于現(xiàn)在普遍使用的是經(jīng)典的公鑰密碼體制RSA，但在密鑰長度為512比特的情況下卻逐漸變得不安全，通過加長密鑰長度雖然可以提高密碼的安全性能，但是加密解密的效率也會變得越來越低，所以最好的方式就是設(shè)計(jì)一種新的密碼體制替代原本使用的4。 橢圓曲線密碼體制就是在這樣的背景下開始逐漸受到重視的，是一種以橢圓曲線相關(guān)數(shù)學(xué)知識為基礎(chǔ)的公鑰密碼體制4。在公鑰密碼體制中與其它

7、算法相比較，橢圓曲線密碼體制具有密鑰短和計(jì)算效率高等典型優(yōu)點(diǎn)，而其本身的算法及其數(shù)學(xué)理論都是非常深奧難懂的。橢圓曲線密碼體制應(yīng)用在實(shí)際中的主要優(yōu)勢有：安全性能較高，速度快，計(jì)算量小、效率安全性能較高，速度快，計(jì)算量小、效率高高 對于所有的密碼體制而言，它的安全性能毫無疑問的成為了核心的問題，對于橢圓曲線密碼體制來說它的數(shù)學(xué)原理是對它安全性能最有利的左證。該體制的核心是有限域上的離散對數(shù)問題4，而這個問題是不能在多項(xiàng)式時(shí)間內(nèi)使用所有的已知算法來求解的，由此可見該體制的抗攻擊性能與其它體制相比是占有絕對優(yōu)勢的。下面通過一個表格可以更直觀的感受橢圓曲線密碼體制的這點(diǎn)優(yōu)勢 由表格可以看出，將160位的

8、ECC算法和1024位的RSA算法作為比較它們的安全強(qiáng)度相差不多，并且在同等的條件下安全強(qiáng)度要求越高的話ECC算法的短密鑰優(yōu)勢也就顯現(xiàn)的更為明顯。所以，ECC算法與RSA算法相比較在每一比特都是擁有更高的安全性能的，也正是由于擁有這樣的特點(diǎn)，才能廣泛的應(yīng)用于移動的電子商務(wù)以及計(jì)算機(jī)網(wǎng)絡(luò)安全和軟件注冊的相關(guān)領(lǐng)域。 公開密鑰的生成速度主要取決于其中的大數(shù)算術(shù)運(yùn)算而它的運(yùn)算速度自然和它的大小規(guī)模息息相關(guān)，在一個相同的計(jì)算條件下，橢圓曲線密碼體制（ECC）的實(shí)現(xiàn)可以選擇比基于大合數(shù)因子分解困難性的公開密鑰密碼體制（RSA）小很多的大數(shù)，這也就保證了實(shí)現(xiàn)的速度和效率。同樣可以通過下面表格中的數(shù)據(jù)來說明

9、通過上表就可以明顯的看出ECC在密鑰對的生成速度、簽名速度和認(rèn)證方面的速度都快得多，計(jì)算量小且計(jì)算速度快，尤其是在存儲容量不大運(yùn)算能力比較低的情況下是具有顯著優(yōu)勢的。所需存儲的空間比較小，帶寬要求較低橢圓曲線密碼體制的密鑰長度與基于大合數(shù)因子分解困難性的公開密鑰密碼體制相比就要小很多，這一點(diǎn)也可以從表1中看出來，比如RSA需要512位元元而ECC只需要106位即可，這也就表明了ECC對存儲空間的需求要較小，在計(jì)算上的開銷也很小，所以ECC會廣泛的應(yīng)用在類似這些存儲空間有限制的設(shè)備中。同樣也是由于這樣的優(yōu)勢決定了ECC可以廣泛的使用在移動通信設(shè)備和智能卡等存儲空間小計(jì)算能力相對較差的設(shè)備上。帶寬

10、即頻帶寬度是指可以有效通過某信道的信號最大頻帶寬度。因?yàn)闄E圓曲線密碼體制和其它加密算法相比具有密鑰短的特點(diǎn)，所以在傳輸中要求的帶寬也更低，當(dāng)對一個長的數(shù)據(jù)信息進(jìn)行加密時(shí)ECC和RSA密碼系統(tǒng)有同樣的帶寬要求8，但是應(yīng)用在較短的數(shù)據(jù)信息中ECC的帶寬要求卻低很多，這也是ECC能夠廣泛的應(yīng)用于無線網(wǎng)絡(luò)中的重要原因。ECC的使用可以減少一定的帶寬開銷所以使得通信的效率也大幅提高，并且在Web服務(wù)器上使用帶寬的費(fèi)用是十分高昂的，ECC的出現(xiàn)既解決了需要節(jié)省計(jì)算時(shí)間的要求又節(jié)約了因帶寬需要的花費(fèi)。在3G網(wǎng)絡(luò)中針對計(jì)算效率低、帶寬資源有限的限制，基于橢圓曲線密碼體制而涉及安全的支付流程是可以實(shí)現(xiàn)端對端的安

11、全數(shù)據(jù)信息傳送。 在對系統(tǒng)初始化以及設(shè)置系統(tǒng)參數(shù)時(shí)橢圓曲線密碼體制也有不同于其它密碼體制的優(yōu)勢，比如與RSA算法相比，RSA需要選取兩個素?cái)?shù)才能初始化，而ECC則需要選擇一個素?cái)?shù)并在有限域上選取不同的橢圓曲線，因?yàn)檫x擇橢圓曲線時(shí)有很多的選擇所以初始化的選擇空間就很大。 基于以上的這些優(yōu)點(diǎn)，橢圓曲線密碼體制在實(shí)際中的應(yīng)用十分廣泛，比如虛擬專用網(wǎng)絡(luò)VPN安全隧道方面由于要考慮到計(jì)算機(jī)存儲和資源方面對嵌入式應(yīng)用的局限性，依據(jù)ECC加密解密速度較快、節(jié)省帶寬和節(jié)省所需要的存儲資源的特點(diǎn)可以選擇使用橢圓曲線密碼體制設(shè)計(jì)應(yīng)用于身份鑒別中，在網(wǎng)絡(luò)的通信中必須要高效率的對數(shù)據(jù)信息進(jìn)行加密，而ECC的快速處理速

12、度可以使通信不再受限于存儲的容量大小和計(jì)算能力的高低。除此之外，橢圓曲線密碼體制在數(shù)字簽名等需要高加密速度的方面也能快速實(shí)現(xiàn)安全高效的加密、簽名。指紋加密與橢圓曲線 隨著近幾年科技的發(fā)展，尤其是生物特征識別技術(shù)的逐步成熟，通過利用生物體本身具有唯一穩(wěn)定不變性的特征將其運(yùn)用到確保信息安全的領(lǐng)域，指紋加密技術(shù)就是生物識別技術(shù)與信息安全融洽結(jié)合的最好體現(xiàn)。由于生物特征的唯一性就可以保證使用指紋信息進(jìn)行身份驗(yàn)證會比其他方案有更高的安全性、準(zhǔn)確性。 指紋采集端和指紋認(rèn)證端是分開工作的，它們之間通過網(wǎng)絡(luò)傳輸數(shù)據(jù)信息，這也是指紋識別認(rèn)證系統(tǒng)中的一個特點(diǎn)。首先是采集指紋信息的過程，用戶通過提取指紋的儀器完成該

13、步驟，然后再將指紋信息的數(shù)字圖像傳送給計(jì)算機(jī)。之后計(jì)算機(jī)完成指紋特征的采集工作，并將指紋的數(shù)字圖像轉(zhuǎn)換成即將進(jìn)行加密操作的特征序列。此時(shí)就可以將加密后的信息傳送到指紋認(rèn)證的終端了，在終端完成對應(yīng)的解密操作、指紋特征的對比操作，最后將對比的結(jié)果返回，也就是完成了一次通過網(wǎng)絡(luò)對指紋身份的識別認(rèn)證操作。該方案與上文中介紹的EIGamal方案的原理基本相同，具體如下方案的優(yōu)缺點(diǎn) 該方案的優(yōu)點(diǎn)主要體現(xiàn)在指紋的唯一性決定了較高的安全性，也就是說其他的加密方式也能夠達(dá)到同樣安全的效果。換言之，這個方案的安全性并不取決于加密算法的復(fù)雜程度，而是取決于加密的數(shù)據(jù)信息的安全強(qiáng)度。但是，與其他的加密方式相比橢圓曲線

14、使用較少、較小的參數(shù)完成過程，尤其與RSA算法相比計(jì)算過程更不易出錯，所以使用橢圓曲線密碼體制進(jìn)行加密還是比較高效的。橢圓曲線密碼體制與橢圓曲線密碼體制與RSARSA密碼體制在實(shí)際密碼體制在實(shí)際應(yīng)用中的比較應(yīng)用中的比較 橢圓曲線密碼算法和RSA算法相比最大的優(yōu)點(diǎn)就是不需要計(jì)算橢圓曲線有理點(diǎn)群的離散對數(shù)問題的子指數(shù)算法，也就是說當(dāng)在同等安全的條件下，橢圓曲線密碼算法可以選擇比RSA算法更小的參數(shù)進(jìn)行加密解密操作。同時(shí)橢圓曲線密碼算法將實(shí)數(shù)域中乘法的運(yùn)算和指數(shù)的運(yùn)算映像成了橢圓曲線上加法的運(yùn)算。綜上所述，橢圓曲線密碼體制更實(shí)用、更容易、更安全，同時(shí)成本也更低。 將兩種算法作比較可以發(fā)現(xiàn)，RSA算法

15、的過程不僅復(fù)雜還必須嚴(yán)格保密，對于素?cái)?shù)的產(chǎn)生和檢測的計(jì)算過程容易產(chǎn)生錯誤；而橢圓曲線密碼算法雖然生成的參數(shù)復(fù)雜但是不需要保密甚至還可以對外公布，不過雖然保密的密鑰生成復(fù)雜但是計(jì)算公鑰很容易。 橢圓曲線密碼體制具有橢圓曲線豐富、不易被破解、不需要大量的參數(shù)參與計(jì)算及不占用大量存儲空間的優(yōu)勢。比如在數(shù)字簽名中完成各部分的效率方面進(jìn)行比較，RSA算法是幾乎不會受到密鑰位數(shù)變化的影響，一直都可以保持著很快的驗(yàn)證速度，相反地，ECC算法受到的影響很劇烈，與RSA算法受影響程度相比有很大的差距。在使用超過一定的密鑰位數(shù)的范圍中，隨著密鑰位數(shù)逐漸地增大ECC算法就會越優(yōu)于RSA算法。 對于相同使用量的參數(shù)，

16、橢圓曲線密碼體制在每一比特的加密解密過程中都擁有更大的強(qiáng)度，并且所需要的參數(shù)規(guī)模也較小，這在實(shí)際的應(yīng)用中是具有很大優(yōu)勢的。橢圓曲線雖然子在一個有限域中只有有限的幾個乘法子群，但是卻有很高的安全性能，所以成為公鑰密碼學(xué)中應(yīng)用廣泛的新體制。二、循環(huán)矩陣在網(wǎng)絡(luò)安全中的應(yīng)用多變量密碼學(xué)中的循環(huán)矩陣 等價(jià)的多項(xiàng)式定義了相同密碼體制，因此等價(jià)的多項(xiàng)式產(chǎn)生的密碼體制也有相同的密鑰空間和加/解密映射的集合。一個等價(jià)類的勢(cardinality)相當(dāng)于選取不同的仿射變換對所產(chǎn)生的加密映射的個數(shù).這就引出了找到產(chǎn)生相同加密映射的仿射變換的個數(shù)問題.例如:對于一個給定的多變量公鑰密碼體制，找到其等價(jià)密鑰的個數(shù)。在

17、一個等價(jià)類中的不同多項(xiàng)式方程組的個數(shù)代表可以選擇的不同密鑰的個數(shù)。等價(jià)密鑰的存在可以縮小密鑰空間，這對于多變量公鑰密碼學(xué)的密碼分析是很有幫助的。 多項(xiàng)式同構(gòu)引出多項(xiàng)式方程組的等價(jià)關(guān)系.因此多項(xiàng)式方程組的集合可以被劃分為不同的等價(jià)類。多項(xiàng)式同構(gòu)的計(jì)數(shù)問題則包含以下3個方而: 1)對不同等價(jià)類的計(jì)數(shù); 2)對每一個等價(jià)類的勢進(jìn)行計(jì)數(shù); 3)確定所有的等價(jià)類的代表元.基于循環(huán)矩陣的ElGamal密碼體制 離散對數(shù)問題是公鑰密碼學(xué)中應(yīng)用最廣泛的一個密碼原語。其應(yīng)用之一是最經(jīng)典的ElGamal密碼系統(tǒng)。眾所周知，ElGamal密碼系統(tǒng)的安全性依賴于有限域上的離散對數(shù)問題。為了能夠提出更安全的密碼系統(tǒng)，人

18、們開始將有限域上的離散對數(shù)問題推廣到非交換群上的離散對數(shù)問題，并在此上提出了MOR密碼系統(tǒng)，可以說MOR密碼系統(tǒng)是ElGamal密碼系統(tǒng)在非交換群上的推廣。而這個非交換群是循環(huán)矩陣群的自同構(gòu)群。，循環(huán)矩陣群提供了一個有限域上的同樣大小的安全，且它有一半的計(jì)算成本。循環(huán)矩陣的另一個有趣的事實(shí)是：其能提供一個安全的域的實(shí)現(xiàn)大小。循環(huán)矩陣的算法是在有限域上進(jìn)行運(yùn)算，這與橢圓曲線的情況極為相似。在循環(huán)的情況下，該域的大小甚至可以小于一個用于橢圓曲線的大小。總之，循環(huán)矩陣的優(yōu)點(diǎn)是，它使用較小的域而且運(yùn)算速度更快。在該文獻(xiàn)中，所有矩陣是非奇異循環(huán)矩陣C(d, q)和特殊循環(huán)矩陣，即循環(huán)矩陣的行列式1，記為

19、SC(d, q)。ElGamalElGamal密碼體制在密碼體制在SC(SC(d d, , q q) )的實(shí)現(xiàn)的實(shí)現(xiàn) 在SC(d, q)的ElGamal密碼系統(tǒng)中，需要進(jìn)行十二次的逆操作，這是很容易計(jì)算的。自公鑰密碼學(xué)概念提出以來，許多優(yōu)秀的公鑰密碼體制相繼被提出并得到完善。目前，大多數(shù)未被攻破的公鑰密碼體制都是基于交換代數(shù)結(jié)構(gòu)的困難問題，如大整數(shù)分解問題、有限域上的離散對數(shù)問題等。然而，由于量子計(jì)算的最新研究成果，許多基于交換代數(shù)結(jié)構(gòu)的難題假設(shè)不再困難。迄今為止，人們已經(jīng)提出了許多基于非交換代數(shù)結(jié)構(gòu)的公鑰密碼體制，特別是辮群密碼體制吸引了大量的研究。經(jīng)過本文的探究，我們可以知道，循環(huán)矩陣是數(shù)

20、學(xué)研究中非常重要的一個數(shù)學(xué)計(jì)算手段，它本身具有很多特殊性質(zhì)。本文針對循環(huán)矩陣的特殊性質(zhì)，研究了其在密碼學(xué)中的公鑰密碼加密解密的過程中的應(yīng)用。隨著電子科技的發(fā)展，以及電子通信的普及，密碼學(xué)得到了前所未有的發(fā)展機(jī)遇。我們從數(shù)學(xué)工具，數(shù)學(xué)算法的角度出發(fā)，進(jìn)行創(chuàng)造性思維，使其在密碼學(xué)中發(fā)揮作用，相信對密碼學(xué)的研究會越來越成熟。DES算法 DES是一種分組密碼協(xié)議，有兩個基本指導(dǎo)思想擴(kuò)散（Diffusion）和混亂（Confusion）,以保證密碼算法能滿足要求，所以DES的具體實(shí)現(xiàn)是依賴于多次迭代進(jìn)行乘積密碼加密變換。 這個算法的核心是Feistel密碼，由于其設(shè)計(jì)的巧妙，加密解密都用一個函數(shù)。它的算

21、法是對稱的，既可用于加密又可用于解密。 DES 使用一個 56 位的密鑰以及附加的 8 位奇偶校驗(yàn)位，產(chǎn)生最大 64 位的分組大小。這是一個迭代的分組密碼，使用稱為 Feistel 的技術(shù)，其中將加密的文本塊分成兩半。使用子密鑰對其中一半應(yīng)用循環(huán)功能，然后將輸出與另一半進(jìn)行“異或”運(yùn)算；接著交換這兩半，這一過程會繼續(xù)下去，但 最后一個循環(huán)不交換。DES 使用 16 個循環(huán)，使用異或，置換，代換，移位操作四種基本運(yùn)算。 DES的流程基本是執(zhí)行16輪下面的運(yùn)算： 1 初始變換Initial Permutation 2 右邊32位f函數(shù) 2.1 E置換 2.2 與輪密鑰XOR 2.3 S盒替換 2.

22、4 P置換 2.5 和左邊32位XOR 3 左右交換，最終變換final permutation 需要特別注意的是，最后一輪是不需要做左右交換這一部的。 從具體實(shí)現(xiàn)看DES有幾個已知的方面存在脆弱性：1，加密協(xié)議半公開化 2，密鑰太短 3，軟件的實(shí)現(xiàn)的性能較低。隨著計(jì)算機(jī)的處理能力的提高，只有56位密鑰的DES算法不再被認(rèn)為是安全性的，故現(xiàn)在一般的方案是三重DES，既3DES。AES AES 算法算法 AES（The Advanced Encryption Standard）是一種非Feistel 的對稱分組密碼體制，和DES的基本指導(dǎo)思想一樣都是多次混淆，所不同的是非線性層的由16個S盒進(jìn)行

23、并置混淆。AES具有安全可靠、效率高等優(yōu)點(diǎn)。 AES加密過程是在一個44的字節(jié)矩陣上運(yùn)作，這個矩陣又稱為“狀態(tài)（state）”，其初值就是一個明文區(qū)塊（矩陣中一個元素大小就是明文區(qū)塊中的一個Byte）。（Rijndael加密法因支持更大的區(qū)塊，其矩陣行數(shù)可視情況增加）加密時(shí)，各輪AES加密循環(huán)（除最后一輪外）均包含4個步驟： 1. AddRoundKey 矩陣中的每一個字節(jié)都與該次輪秘鑰（round key）做XOR運(yùn)算；每個子密鑰由密鑰生成方案產(chǎn)生。 2. SubBytes 通過個非線性的替換函數(shù)，用查找表的方式把每個字節(jié)替換成對應(yīng)的字節(jié)。 3. ShiftRows 將矩陣中的每個橫列進(jìn)行循

24、環(huán)式移位。 4. MixColumns 為了充分混合矩陣中各個直行的操作。這個步驟使用線性轉(zhuǎn)換來混合每列的四個字節(jié)。AddRoundKeyAddRoundKey步驟步驟在AddRoundKey步驟中，將每個狀態(tài)中的字節(jié)與該回合密鑰做異或（）。AddRoundKey步驟，回合密鑰將會與原矩陣合并。在每次的加密循環(huán)中，都會由主密鑰產(chǎn)生一把回合密鑰（通過Rijndael密鑰生成方案產(chǎn)生），這把密鑰大小會跟原矩陣一樣，以與原矩陣中每個對應(yīng)的字節(jié)作異或（）加法。SubBytesSubBytes步驟步驟在SubBytes步驟中，矩陣中各字節(jié)被固定的8位查找表中對應(yīng)的特定字節(jié)所替換,S; bij = S（a

25、ij）.在SubBytes步驟中，矩陣中的各字節(jié)通過一個8位的S-box進(jìn)行轉(zhuǎn)換。這個步驟提供了加密法非線性的變換能力。S-box與GF（28）上的乘法反元素有關(guān)，已知具有良好的非線性特性。為了避免簡單代數(shù)性質(zhì)的攻擊，S-box結(jié)合了乘法反元素及一個可逆的仿射變換矩陣建構(gòu)而成。此外在建構(gòu)S-box時(shí)，刻意避開了固定點(diǎn)與反固定點(diǎn)，即以S-box替換字節(jié)的結(jié)果會相當(dāng)于錯排的結(jié)果。ShiftRowsShiftRows步驟步驟在ShiftRows步驟中，矩陣中每一行的各個字節(jié)循環(huán)向左方位移。位移量則隨著行數(shù)遞增而遞增。ShiftRows描述矩陣的行操作。在此步驟中，每一行都向左循環(huán)位移某個偏移量。在A

26、ES中（區(qū)塊大小128位），第一行維持不變，第二行里的每個字節(jié)都向左循環(huán)移動一格。同理，第三行及第四行向左循環(huán)位移的偏移量就分別是2和3。128位和192比特的區(qū)塊在此步驟的循環(huán)位移的模式相同。經(jīng)過ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。Rijndael算法的版本中，偏移量和AES有少許不同；對于長度256比特的區(qū)塊，第一行仍然維持不變，第二行、第三行、第四行的偏移量分別是1字節(jié)、3字節(jié)、4位組。除此之外，ShiftRows操作步驟在Rijndael和AES中完全相同。MixColumnsMixColumns步驟步驟在MixColumns步驟中，每個直

27、行都在modulo之下，和一個固定多項(xiàng)式c(x)作乘法。在MixColumns步驟，每一列的四個字節(jié)通過線性變換互相結(jié)合。每一列的四個元素分別當(dāng)作的系數(shù)，合并即為GF（28）中的一個多項(xiàng)式，接著將此多項(xiàng)式和一個固定的多項(xiàng)式在modulo 下相乘。此步驟亦可視為Rijndael有限域之下的矩陣乘法。MixColumns函數(shù)接受4個字節(jié)的輸入，輸出4個字節(jié)，每一個輸入的字節(jié)都會對輸出的四個字節(jié)造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統(tǒng)提供了擴(kuò)散性。大致說來，AES 加密算法的核心有四個操作。AddRoundKey 使用從種子密鑰值中生成的輪密鑰代替 4 組字節(jié)。Su

28、bBytes 替換用一個代替表 替換單個字節(jié)。ShiftRows 通過旋轉(zhuǎn) 4字節(jié)行 的 4 組字節(jié)進(jìn)行序列置換。MixColumns 用域加和域乘的組合來替換字節(jié)。 正如你所看到的，AES 加密算法使用相當(dāng)簡單明了的技術(shù)來代替和置換，除 MixColumns 例程以外。MixColumns 使 用特殊的加法和乘法。AES 所用的加法和乘法是基于數(shù)學(xué)的域論。尤其是 AES 基于有限域GF(28)。GF(28)由一組從 0 x00 到 0 xff 的256個值組成，加上加法和乘法，因此是(28)。GF代表伽羅瓦域，以發(fā)明這一理論的數(shù)學(xué)家的名字命名。GF(28) 的一個特性是一個加法或乘法的操作的

29、結(jié)果必須是在0 x00 . 0 xff這組數(shù)中。雖然域論是相當(dāng)深奧的，但GF(28)加法的最終結(jié)果卻很簡單。GF(28) 加法就是異或（XOR）操作。在GF(28)中用0 x01的乘法是特殊的；它相當(dāng)于普通算術(shù)中用1做乘法并且結(jié)果也同樣任何值乘0 x01等于其自身?，F(xiàn)在讓我們看看用0 x02做乘法。和加法的情況相同，理論是深奧的，但最終結(jié)果十分簡單。只要被乘的值小于0 x80，這時(shí)乘法的結(jié)果就是該值左移1比特位。如果被乘的值大于或等于0 x80，這時(shí)乘法的結(jié)果就是左移1比特位再用值0 x1b異或。它防止了“域溢出”并保持乘法的乘積在范圍以內(nèi)。一旦你在GF(28)中用0 x02建立了加法和乘法，

30、你就可以用任何常量去定義乘法。用0 x03做乘法時(shí)，你可以將 0 x03 分解為2的冪之和。為了用 0 x03 乘以任意字節(jié)b， 因?yàn)?0 x03 = 0 x02 + 0 x01，因此： b * 0 x03 = b * (0 x02 + 0 x01) = (b * 0 x02) + (b * 0 x01) 這是可以行得通的，因?yàn)槟阒廊绾斡?0 x02 和 0 x01 相乘和相加，用0 x0d去乘以任意字節(jié)b可以這樣做： b * 0 x0d = b * (0 x08 + 0 x04 + 0 x01) = (b * 0 x08) + (b * 0 x04) + (b * 0 x01) = (b

31、* 0 x02 * 0 x02 * 0 x02) + (b * 0 x02 * 0 x02) + (b * 0 x01) 在加解密算法中，AES MixColumns 例程的其它乘法遵循大體相同的模式，如下所示： b * 0 x09 = b * (0 x08 + 0 x01) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x01) b * 0 x0b = b * (0 x08 + 0 x02 + 0 x01) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x02) + (b * 0 x01) b * 0 x0e = b * (0

32、x08 + 0 x04 + 0 x02) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x02 * 0 x02) + (b * 0 x02) 總之，在GF(28)中，加法是異或操作。其乘法將分解成加法和用0 x02做的乘法，而用0 x02做的乘法是一個有條件的左移1比特位。AES規(guī)范中包括大量 有關(guān)GF(28)操作的附加信息。有限域有限域GF(28)的加法和乘法的加法和乘法 類似DES，AES等算法中雙方都使用相同的密鑰進(jìn)行加密解密，我們把這種加解密都使用同一個密鑰的密碼體制稱為對稱密碼體制。使用相同的密鑰進(jìn)行加密解密，密鑰的傳輸是一個重要的問題。所以，在公開的

33、計(jì)算機(jī)網(wǎng)絡(luò)上安全地傳送和保管密鑰是一個嚴(yán)峻的問題。 于是，密碼學(xué)家們構(gòu)想了一個不一樣的的密碼體制來解決這一問題-公鑰加密算法。公鑰加密算法也稱非對稱密鑰算法，用兩對密鑰：一個公共密鑰和一個專用密鑰。用戶要保障專用密鑰的安全；公共密鑰則可以發(fā)布出去。公共密鑰與專用密鑰是有緊密關(guān)系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由于公鑰算法不需要聯(lián)機(jī)密鑰服務(wù)器，密鑰分配協(xié)議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統(tǒng)還可以提供數(shù)字簽名。 RSA是其中的一種有效實(shí)現(xiàn)。 RSA的基本指導(dǎo)思想是設(shè)計(jì)有效的單向陷門函數(shù)，來使得正向加密計(jì)算容易、沒有密鑰下的反向計(jì)算幾乎不可能。RSA的安全性是

34、建立在大整數(shù)分解的困難性上的。RSARSA算法算法 假設(shè)Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產(chǎn)生一個公鑰公鑰和一個私鑰私鑰： 隨意選擇兩個大的質(zhì)數(shù)p和q，p不等于q，計(jì)算N=pq。 根據(jù)歐拉函數(shù)，求得r = (p-1)(q-1) 選擇一個小于 r 的整數(shù)e，求得 e 關(guān)于模 r 的模反元素，命名為d。（模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)） 將p和q的記錄銷毀。 (N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。公鑰與密鑰的產(chǎn)生公鑰與密鑰的產(chǎn)生 假設(shè)Bob想給Alice送一個消息m，他知道Alic

35、e產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個小于N的整數(shù)n，比如他可以將每一個字轉(zhuǎn)換為這個字的Unicode碼，然后將這些數(shù)字連在一起組成一個數(shù)字。假如他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉(zhuǎn)換為n。用下面這個公式他可以將n加密為c：ne c (mod N) 計(jì)算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。加密消息加密消息 Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉(zhuǎn)換為n： cd n (mod N) 得到n后，她可以將原來的信息m重新復(fù)原。 解碼的原理是： cd n ed(mod N) 以及ed 1 (

36、mod p-1)和ed 1 (mod q-1)。由費(fèi)馬小定理可證明（因?yàn)閜和q是質(zhì)數(shù)） n ed n (mod p) 和 n ed n (mod q) 這說明（因?yàn)閜和q是不同的質(zhì)數(shù)，所以p和q互質(zhì)） n ed n (mod pq)解密消息解密消息 RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話，那么她可以為她的消息計(jì)算一個散列值(Message digest)，然后用她的密鑰(private key)加密這個散列值并將這個“署名”加在消息的后面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息后可以用甲的公鑰解密這個散列值，然后將這個數(shù)據(jù)與他自己為這個消息計(jì)算的散列值相比

37、較。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰，以及這個消息在傳播路徑上沒有被篡改過。簽名消息簽名消息 當(dāng)p和q是一個大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和q，這是一個公認(rèn)的數(shù)學(xué)難題。然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。 1994年彼得秀爾（Peter Shor）證明一臺量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行因數(shù)分解。假如量子計(jì)算機(jī)有朝一日可以成為一種可行的技術(shù)的話，那么秀爾的算法可以淘汰RSA和相關(guān)的衍生算法。（即依賴于分解大整數(shù)困難性的加密算法） 另外，假如N的長度小于或等于256位，那么用一臺個人電腦在幾個小時(shí)內(nèi)就可以分解它的因子了。1999年，數(shù)百臺電腦合作分解了一個512位長的N。1997年后開發(fā)的系統(tǒng)，用戶應(yīng)使用1024位密鑰，證書認(rèn)證機(jī)構(gòu)應(yīng)用2048位或以上。RSARSA加密算法的安全性加密算法的安全性 雖然RSA加密算法作為目前最優(yōu)秀的公鑰方案之一，在發(fā)表三十多年的時(shí)間里，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受。但是，也不是說RSA沒有任何缺點(diǎn)。由于沒有從理論上證明破譯RSA的難度與大數(shù)分解難度的等價(jià)性。所以，RSA的重