第2章-網(wǎng)絡(luò)安全

1

密碼學(xué)的發(fā)展（cryptography）2.1數(shù)據(jù)加密技術(shù)概述?傳統(tǒng)密碼學(xué)~1976/77-1949年Shannon的“保密通信的信息理論”?現(xiàn)代密碼學(xué)1976/77~today

-1976:Diffie&Hellman

“公鑰密碼學(xué)的新方向”，掀起公鑰密碼研究的序幕。

-1977:美國國家標(biāo)準(zhǔn)局公布了美國的數(shù)據(jù)加密標(biāo)準(zhǔn)DES(DataEncryptionStandard)第2章數(shù)據(jù)加密技術(shù)23

加密是一種限制對網(wǎng)絡(luò)上傳輸數(shù)據(jù)的訪問技術(shù)，原始數(shù)據(jù)（明文）被加密設(shè)備和密鑰加密(Encrypt)而產(chǎn)生的經(jīng)過編碼后的數(shù)據(jù)稱為密文。將密文還原為原始明文的過程稱為解密(Decrypt)，它是加密的反向處理。下圖是信息加密傳遞過程。

加密的概念（Encrypt）

其中，E表示加密算法，D表示解密算法，K表示加密密鑰，K’表示解密密鑰。明文M密文C=E(M,K)E(M,K)傳輸終端D(C,K’)傳輸終端明文M出發(fā)地加密密鑰解密密鑰目的地圖2.1數(shù)據(jù)加密模型4

密碼體制5

密碼體制分類

如圖2.1數(shù)據(jù)加密模型所示，當(dāng)加密密鑰K與解密密鑰K’相同時(shí)，這樣的加密體制稱為私鑰（單鑰或?qū)ΨQ）加密體制。當(dāng)加密密鑰K與解密密鑰K’不同時(shí)，這樣的加密體制稱為公鑰（雙鑰或非對稱）加密體制。圖2.2是對稱密碼體制的加密過程。6ENetworkorStoragePlainTextCipherTextCipherTextDOriginalPlainTextBobSecretKeyAliceSecretKey圖2.2對稱密碼加密模型72.2傳統(tǒng)加密技術(shù)

希臘密碼(二維字母編碼查表)公元前2世紀(jì)82.2傳統(tǒng)加密技術(shù)

凱撒密碼

凱撒密碼是每個(gè)字母向前推移k位，并認(rèn)為Z后邊又是A。這種影射關(guān)系表示為：F(a)=(a+k)mod26，其中a是明文字母，k是密鑰。設(shè)k=3，那么字母間的影射關(guān)系為：

假設(shè)明文為COMPUTE，則凱撒密碼是：FRPSXWH。優(yōu)點(diǎn)：簡單易記。缺點(diǎn)：安全性差。9

單表置換密碼

在凱撒密碼的基礎(chǔ)上，將字母表重新打亂。比如，在字母表中首先排列出密鑰中出現(xiàn)的字母，然后在密鑰后填上剩余的字母。注意不能出現(xiàn)重復(fù)字母。例如，密鑰是TsinghuaUniversity，那么字母間的影射關(guān)系為：

ABCDEFGHIJKLMNOPQRSTUVWXYZTSINGHUAVERYBCDFJKLMOPQWXZ

假設(shè)明文為COMPUTE，則密碼是：IDBFOMG。假設(shè)密文為LMONGCM，則明文為：STUDENT

優(yōu)點(diǎn)：比凱撒密碼的安全性好。

10

多表置換-維吉利亞密碼

Vigenere是法國的密碼學(xué)家，以他名字命名的加密算法是多表密碼的典型代表。這種加密以26個(gè)字母為基礎(chǔ)進(jìn)行循環(huán)移位，排列在一起，形成26*26的方陣，該方陣稱為維吉利亞方陣（見下頁）。給一個(gè)信息加密時(shí)，把密鑰反復(fù)寫在明文的下面，明文字母對應(yīng)維吉利亞方陣的選擇列，密鑰字母對應(yīng)選擇行，兩者的交叉點(diǎn)就是密文字母。

假設(shè)明文為HOWAREYOU，密鑰為YOUR。則加密過程為：

11

ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABDDEFGHIJKLMNOPQRSTUVWXYZABCEEFGHIJKLMNOPQRSTUVWXYZABCDFFGHIJKLMNOPQRSTUVWXYZABCDEGGHIJKLMNOPQRSTUVWXYZABCDEFHHIJKLMNOPQRSTUVWXYZABCDEFGIIJKLMNOPQRSTUVWXYZABCDEFGHJJKLMNOPQRSTUVWXYZABCDEFGHIKKLMNOPQRSTUVWXYZABCDEFGHIJLLMNOPQRSTUVWXYZABCDEFGHIJKMMNOPQRSTUVWXYZABCDEFGHIJKLNNOPQRSTUVWXYZABCDEFGHIJKLMOOPQRSTUVWXYZABCDEFGHIJKLMNPPQRSTUVWXYZABCDEFGHIJKLMNOQQRSTUVWXYZABCDEFGHIJKLMNOPRRSTUVWXYZABCDEFGHIJKLMNOPQSSTUVWXYZABCDEFGHIJKLMNOPQRTTUVWXYZABCDEFGHIJKLMNOPQRSUUVWXYZABCDEFGHIJKLMNOPQRSTVVWXYZABCDEFGHIJKLMNOPQRSTUWWXYZABCDEFGHIJKLMNOPQRSTUVXXYZABCDEFGHIJKLMNOPQRSTUVWYYZABCDEFGHIJKLMNOPQRSTUVYXZZABCDEFGHIJKLMNOPQRSTUVYXY12

矩陣換位密碼

把明文中的字母按給定的順序安排在一個(gè)矩陣中，然后用另一種順序選擇矩陣的字母產(chǎn)生密文。在該方案中，矩陣的行數(shù)和列數(shù)，以及給定的置換矩陣就是密鑰。

假設(shè)將明文ENGINEERING安排在3*4的矩陣中，即：

1234ENGINEERING

給定一個(gè)置換為：

13現(xiàn)在根據(jù)給定的位置，按第2列，第4列，第1列，第3列的次序排列，得到：

1234NIEGERNENIG則密文為：NIEGERNENIG，密鑰K=(3*4,f)。其解密過程為：第3列為明文的第1列，第1列為明文的第2列，第4列為明文的第3列，第2列為明文的第4列。得到：

1234ENGINEERING則明文為：ENGINEERING14

簡單異或運(yùn)算

異或運(yùn)算規(guī)則：

經(jīng)?？梢杂卯惢蜻\(yùn)算對文件做一些簡單的加密運(yùn)算

15#include"stdio.h"main(){FILE*fi,*fo;charfname1[50],fname2[50];charc;intk=1;/*key*/printf("input_filename:");scanf("%s",fname1);printf("output_filename:");scanf("%s",fname2);if((fi=fopen(fname1,"rb"))!=NULL){ if((fo=fopen(fname2,"wb"))!=NULL) {while((c=fgetc(fi))!=EOF){ c^=k; fputc(c,fo); }fclose(fo); } fclose(fi);}}162.4現(xiàn)代加密技術(shù)

密碼分析

常用的密碼分析攻擊有四類：

(1)唯密文攻擊(ciphertext-onlyattack)

密碼分析者有一些消息的密文，這些消息都是用同一加密算法加密。密碼分析者的任務(wù)是恢復(fù)盡可能多的明文，或者是加密消息的密鑰。

(2)已知明文攻擊(known-plaintextattack)

密碼分析者不僅可得到一些消息的密文，而且知道這些消息的明文。密碼分析者的任務(wù)是用加密信息推出加密的密鑰或?qū)С鲆粋€(gè)算法，此算法可以對用同一密鑰加密的任何新的消息進(jìn)行解密。17

(3)選擇明文攻擊(chosen-plaintextattack)

密碼分析者可得到所需要的任何明文所對應(yīng)的密文，這些密文與待解的密文是用同一密鑰加密得來的。

(4)選擇密文攻擊(chosen-ciphertextattack)

密碼分析者可得到所需要的任何密文所對應(yīng)的明文，解密這些密文所使用的密鑰與待解的密文的密鑰是一樣的。

上述四種攻擊的強(qiáng)度按順序遞增，唯密文攻擊是最弱的一種攻擊，選擇密文攻擊是最強(qiáng)的一種攻擊。18

對稱密碼體制

序列密碼一直作為軍事和外交場合使用的主要密碼技術(shù)之一。其工作原理是：將明文M看成連續(xù)的比特流或字符流(m1m2m3???.)，并用密鑰序列K(k1k2k3???)中第i個(gè)元素ki對明文中的mi進(jìn)行逐位加密，即：

EK(M)=Ek1(m1)Ek2(m2)???

加密和解密過程如圖2.3所示。

1、流密碼（序列密碼）對稱密碼算法分為流密碼和分組密碼兩類。19密鑰序列發(fā)生器加密算法密鑰序列發(fā)生器解密算法I0I0mi明文信息mi明文信息mi’密文信息其中，I0用于初始化密鑰序列產(chǎn)生器圖2.3序列密碼加密和解密過程kiki20...10101101...01110100...11011001流密碼加密的例子plaintextstreamkeystreamciphertextstream21...10101101...01110100...11011001流密碼解密的例子plaintextstream(thesame!)keystreamciphertextstream22Apseudo-randomnumbergenerator(PRNG)isanalgorithmthatexpandsarandombutrelativelyshortkey,sayof64bits,intoalongbitsequencethatpreservestherandomnesspropertyoftheoriginalshortkeyrelativelyshortkey(say64bits)longoutput為了加強(qiáng)算法的安全性，常常使用偽隨機(jī)數(shù)產(chǎn)生器增加密鑰的長度。23...10101101...01110100...11011001Encryptionplaintextstreamlongoutputkeystreamciphertextstream24...10101101...01110100...11011001Decryptionplaintextstreamlongoutputkeystreamciphertextstream25

2、分組密碼（BlockCiphers）迭代密碼明文：X=Y(0)密文：Y=Y(r)迭代函數(shù):F迭代次數(shù):r種子密鑰：k迭代的子密鑰：Z(i)（1）DES算法(DataEncryptionStandard)DES由IBM在70年代提出的，1976年被美國政府定為數(shù)據(jù)加密標(biāo)準(zhǔn)。其工作原理是：將一個(gè)需要加密的明文分為若干個(gè)長度為64比特的數(shù)據(jù)塊，逐次對每一個(gè)數(shù)據(jù)塊進(jìn)行加密。

DES密鑰長度56比特(約1018)，進(jìn)行16輪的迭代編碼，獲得長度為64比特的密文。由于DES的密鑰太短，不能抵御窮舉攻擊。1997年，RSA公司以$10,000為懸賞，攻破DES。有人編寫了特定的程序在Internet上發(fā)布，70000個(gè)用戶（機(jī)器）加入了對DES的攻擊，結(jié)果，在遍歷了1/4的密鑰空間后，破解了DES。1998年，電子邊境基金學(xué)會（EFF）使用一臺價(jià)值25萬美圓的電腦在56小時(shí)內(nèi)破譯了56位的DES。27

DES有16輪，這意味著要在明文分組上16次實(shí)施相同的組合技術(shù)。加密過程

DES使用56位密鑰對64位數(shù)據(jù)塊進(jìn)行加密，需要進(jìn)行16輪編碼。2829一輪DES

假設(shè)Bi是第i次迭代的結(jié)果，Li和Ri是Bi的左半部分和右半部分，Ki是第i輪的48位密鑰，且f是實(shí)現(xiàn)代替、置換及密鑰異或等運(yùn)算的函數(shù)，那么每一輪就是：

Li=Ri-1 Ri=Li-1⊕f(Ri-1,Ki)

算法概要

DES對64位的明文分組進(jìn)行操作。通過一個(gè)初始置換，將明文分組分成左半部分和右半部分，各32位長。30初始置換（IP置換） 初始置換在第一輪運(yùn)算之前執(zhí)行，對輸入分組實(shí)施如下表所示的變換。此表應(yīng)從左向右、從上向下讀。例如，初始置換把明文的第58位換到第1位的位置，把第50位換到第2位的位置，把第42位換到第3位的位置，等等。58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157目的：打亂原來輸入x的ASCII碼字的劃分關(guān)系。31密鑰置換 一開始，由于不考慮每個(gè)字節(jié)的第8位，DES的密鑰由64位減至56位，如下表所示。每個(gè)字節(jié)第8位可作為奇偶校驗(yàn)位以確保密鑰不發(fā)生錯(cuò)誤。在DES的每一輪中，從56位密鑰產(chǎn)生出不同的48位子密鑰（SubKey），這些子密鑰Ki由下面的方式確定。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124注意：第8、16、24、32、40、48、56、64共8個(gè)奇偶校驗(yàn)位并未處理。32

首先，56位密鑰被分成兩部分，每部分28位。然后，根據(jù)輪數(shù)，這兩部分分別循環(huán)左移l位或2位。下表給出了每輪移動的位數(shù)。

輪12345678910111213141516位數(shù)112222221222222133

移動后，就從56位中選出48位。因?yàn)檫@個(gè)運(yùn)算不僅置換了每位的順序，同時(shí)也選擇子密鑰，因而被稱作壓縮置換。這個(gè)運(yùn)算提供了一組48位的集。下表定義了壓縮置換（也稱為置換選擇）。例如，處在第33位位置的那一位在輸出時(shí)移到了第35位的位置，而處在第18位位置的那一位被略去了。1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932注意：第9、18、22、25、35、38、43、54被略去了。34

因?yàn)橛幸苿舆\(yùn)算，在每一個(gè)子密鑰中使用了不同的密鑰子集的位。雖然不是所有的位在子密鑰中使用的次數(shù)均相同，但在16個(gè)子密鑰中，每一位大約使用了其中14個(gè)子密鑰。擴(kuò)展置換 這個(gè)運(yùn)算將數(shù)據(jù)的右半部分Ri從32位擴(kuò)展到了48位。由于這個(gè)運(yùn)算改變了位的次序，重復(fù)了某些位，故被稱為擴(kuò)展置換。 這個(gè)操作有兩個(gè)方面的目的：它產(chǎn)生了與密鑰同長度的數(shù)據(jù)以進(jìn)行異或運(yùn)算，它提供了更長的結(jié)果，使得在替代運(yùn)算時(shí)能進(jìn)行壓縮。35

下圖顯示了擴(kuò)展置換，有時(shí)它也叫做E盒。對每個(gè)4位輸入分組，第1和第4位分別表示輸出分組中的兩位，而第2和第3位分別表示輸出分組中的一位。

36

下表給出了哪一輸出位對應(yīng)于哪一輸入位。例如，處于輸入分組中第3位的位置的位移到了輸出分組中第4位的位置，而輸入分組中第21位的位置的位移到了輸出分組中第30和第32位的位置。

盡管輸出分組大于輸入分組，但每一個(gè)輸入分組產(chǎn)生唯一的輸出分組。321234545678989101112131213141516171617181920212021222324252425262728292829303132137S盒代替 壓縮后的密鑰與擴(kuò)展分組異或以后，將48位的結(jié)果送入，進(jìn)行代替運(yùn)算。替代由8個(gè)代替盒，或S盒完成。每一個(gè)S盒都有6位輸入，4位輸出，且這8個(gè)S盒是不同的。（DES的這8個(gè)S盒占的存儲空間為256字節(jié)。）48位的輸入被分為8個(gè)6位的分組，每一分組對應(yīng)一個(gè)S盒代替操作：分組1由S-盒1操作，分組2由S-盒2操作，依次類推。38

每個(gè)S盒是一個(gè)4行、16列的表。盒中的每一項(xiàng)都是一個(gè)4比特位的數(shù)（0-15）。S盒的6個(gè)位輸入確定了其對應(yīng)的輸出在哪一行哪一列。下面列出所有的8個(gè)S盒。

14413121511831061259070157414213110612119538411481362111512973105015128249175113141006131518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S盒1：S盒2：39713143069101285111241513811565034721211014910690121171315131452843150610113894511127214100914631551131271142813709346102851412115113649815301112125101471101306987415143115212S盒3：S盒4：401211015926801334147511101542712956113140113891415528123704101131164321295151011141760813212417101168531513014914112124713150151039864211110137815912563014181271142136150910453S盒5：S盒6：414112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S盒7：S盒8：132846151111093145012711513810374125611014927114191214206101315358211474108131512903561142

輸入位以一種非常特殊的方式確定了S盒中的項(xiàng)。假定將S盒的6位的輸入標(biāo)記為b1、b2、b3、b4、b5、b6。則b1和b6組合構(gòu)成了一個(gè)2位的數(shù)，從0到3，它對應(yīng)著表中的一行。從b2到b5構(gòu)成了一個(gè)4位的數(shù)，從0到15，對應(yīng)著表中的一列。 例如，假設(shè)第6個(gè)S盒的輸入（即異或函數(shù)的第31位到36位）為110011。第1位和最后一位組合形成了11，它對應(yīng)著第6個(gè)S盒的第三行。中間的4位組合在一起形成了1001，它對應(yīng)著同一個(gè)S盒的第9列。S盒6的第三行第9列處的數(shù)是14（記?。盒小⒘械挠洈?shù)均從0開始而不是從1開始），則值1110就代替了110011。43P盒置換

S盒代替運(yùn)算后的32位輸出依照P盒進(jìn)行置換。該置換把每輸入位映射到輸出位，任意一位不能被映射兩次，也不能被略去，這個(gè)置換叫做直接置換。下表給出了每位移到的位置。例如，第21位移到了第4位處，同時(shí)第4位移到了第31位處。最后，將P盒置換的結(jié)果與最初的64位分組的左半部分異或，然后左、右半部分交換，接著開始另一輪。167202129122817115232651831102824143227391913306221142544末置換

末置換是初始置換的逆過程，下表列出了該置換。應(yīng)注意DES在最后一輪后，左半部分和右半部分并未交換，而是將R16與L16并在一起形成一個(gè)分組作為末置換的輸入。4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572545DES解密 在經(jīng)過所有的代替、置換、異或和循環(huán)移動之后，獲得了這樣一個(gè)非常有用的性質(zhì)：加密和解密可使用相同的算法。

DES使得用相同的函數(shù)來加密或解密每個(gè)分組成為可能，二者的唯一不同之處是密鑰的次序相反。這就是說，如果各輪的加密密鑰分別是K1，K2，K3…，K16那么解密密鑰就是K16，K15，K14……，K1。為各輪產(chǎn)生密鑰的算法也是循環(huán)的。密鑰向右移動，每次移動個(gè)數(shù)為0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。46DES舉例 已知明文m=computer，密鑰k=program，用ASCII碼表示為：m=0110001101101111011011010111000001110101011101000110010101110010k=01110000011100100110111101100111011100100110000101101101

因?yàn)閗只有56位，必須插入第8，16，24，32，40，48，56，64位奇偶校驗(yàn)位，合成64位。而這8位對加密過程沒有影響。47m經(jīng)過IP置換后得到L0=11111111101110000111011001010111R0=00000000111111110000011010000011密鑰k通過PC-1得到C0=1110110010011001000110111011D0=1011010001011000100011100110再各自左移一位，通過PC-2得到48位k1=001111011000111111001101001101110011111100000110R0（32位）經(jīng)E作用膨脹為48位，10000000000101111111111010000000110101000000011048再和k1作異或運(yùn)算得到（分成8組）101111011001100000110011101101111110101101001110通過S盒后輸出位32比特，01110110001101000010011010100001S盒的輸出又經(jīng)過P置換得到01000100001000001001111010011111這時(shí)：所以，第一趟的結(jié)果是：000000001111111100000110100000111011101110011000111010001100100049

如此，迭代16次以后，得到密文：0101100010101000010000011011100001101001111111101010111000110011

明文或密鑰每改變一位，都會對結(jié)果密文產(chǎn)生劇烈的影響。任意改變一位，其結(jié)果大致有將近一半的位發(fā)生了變化。DES算法的實(shí)現(xiàn)硬件實(shí)現(xiàn)1984年，DES芯片每秒加密25.6萬次1987年，DES芯片每秒加密51.2萬次目前最快的DES芯片每秒加密1G比特（DEC:美國數(shù)字設(shè)備公司開發(fā)）軟件實(shí)現(xiàn)在IBM3090大型機(jī)上，DES軟件實(shí)現(xiàn)每秒加密3.2萬次在80486處理器，速度為66MHz，總線寬32位的微機(jī)上，DES軟件實(shí)現(xiàn)每秒加密4.3萬次S-盒的設(shè)計(jì)S-盒是DES的心臟S-盒的設(shè)計(jì)原理尚未公開密碼學(xué)家懷疑NSA設(shè)計(jì)S-盒時(shí)隱藏了“陷門”DES的安全性二重DES的結(jié)構(gòu)

y=DESK2(z)=DESK2(DESK1(x))明文:xzDES密鑰:K1DES密鑰:K2密文:y二重DES的安全性密鑰長度為112bit,強(qiáng)度極大增加.(2)二重DES（3）三重DES(TripleDES)

三重DES是DES的加強(qiáng)版，它能夠使用兩個(gè)密鑰，主要對信息逐次做三次加密。密鑰長度是112位。加密：E=DES,解密：D=DES-1y=EK1[DK2(EK1(x))]明文:xE密鑰:K1E密鑰:K1密文:yuD密鑰:K2v加密-解密-加密模式(EDE:encrypt-decrypt-encrypt)已被密鑰管理標(biāo)準(zhǔn)ANSX.917和ISO8732采用缺點(diǎn)是要花費(fèi)3倍DES的運(yùn)行時(shí)間54(4)國際數(shù)據(jù)加密IDEA-------

（InternationalDataEncryptionAlgorithm)算法1990年，XuejiaLai(來學(xué)嘉，旅居瑞士中國學(xué)者)和J.L.Massey(國際著名密碼學(xué)家)提出一個(gè)建議加密標(biāo)準(zhǔn)(PES:proposedencryptionstandard)1991年，設(shè)計(jì)出改進(jìn)型建議加密標(biāo)準(zhǔn)(IPES),能夠抗擊差分密碼分析1992年，改名為國際數(shù)據(jù)加密算法

(IDEA:internationaldataencryptionalgorithm)是DES之后又一個(gè)成功的分組密碼，已被用于Internet的E-mail加密系統(tǒng)PGP和其他加密系統(tǒng)分組長度:64密鑰長度:12855XuejiaLai(來學(xué)嘉)簡介國際著名密碼學(xué)家1982年獲西安電子科技大學(xué)學(xué)士學(xué)位1984年獲該校應(yīng)用數(shù)學(xué)碩士學(xué)位1988年獲瑞士蘇黎世高工通信技術(shù)碩士學(xué)位1992年獲瑞士蘇黎世高工技術(shù)科學(xué)博士學(xué)位1994年加入瑞士r3安全工程中心，該中心于1998年6月成為Entrust(瑞士)公司2001年加入瑞士S.W.I.S.中心2004年到上海交大任教，兼任科學(xué)院研究生院名譽(yù)教授，西南交通大學(xué)顧問教授設(shè)計(jì)了IDEA加密算法。對Hash函數(shù)的分析和構(gòu)造研究的成果得到國際上普遍應(yīng)用,包括最近對MD4,SHA的碰撞攻擊。在差分破譯法的研究中，提出差分，高階差分，馬爾科夫密碼的概念,用馬爾科夫鏈理論將差分破譯法公式化，使得推導(dǎo)差分密碼分析復(fù)雜度的下界成為可能。設(shè)計(jì)了歐洲Eurochip電話卡中的認(rèn)證算法。審核過歐洲銀行Eurocard智能卡系統(tǒng)的安全性。分析評估歐洲電訊標(biāo)準(zhǔn)局的專用密碼。分析及改進(jìn)付費(fèi)電視系統(tǒng)中使用的密碼及密鑰管理系統(tǒng)。參與過中國金融認(rèn)證中心的建設(shè)。主編了ISO-13888不可抵賴標(biāo)準(zhǔn)、ISO-11770密鑰管理標(biāo)準(zhǔn)及ISO-18033加密算法標(biāo)準(zhǔn)。并參與歐盟KRISIS，ICE-CAR和PKIChallenge項(xiàng)目?，F(xiàn)任2006亞密會(Asiacrypt)程序委員會主席,中國密碼學(xué)會常務(wù)理事。XuejiaLai(來學(xué)嘉)簡介國際著名密碼學(xué)家來學(xué)嘉博士2005年6月在西南交通大學(xué)講學(xué)IDEA基本運(yùn)算逐位異或:

全體16位二進(jìn)制向量(Z216,)是一個(gè)群mod(216=65536)整數(shù)加法:?

全體小于216的非負(fù)整數(shù)(Z65536,?)是一個(gè)群mod(216+1=65537)整數(shù)乘法:⊙

全體小于216+1的正整數(shù)(Z65537*,⊙)是一個(gè)群將216=65536視為0，則(Z65537*,⊙)等同于(Z65536,⊙)

例:0000000000000000⊙1000000000000000=0⊙215=216⊙215=216215

mod(216+1)=(216+1-1)215

mod(216+1)=(216+1)215-1215

mod(216+1)=-215

mod(216+1)=216+1-215

mod(216+1)=215+1=1000000000000001.58IDEA基本運(yùn)算三個(gè)運(yùn)算

,?,⊙都使Z216成為群Z216中三個(gè)運(yùn)算

,

?,⊙任何兩個(gè)都不滿足分配律,例

a?(b⊙c)(a?b)⊙(a?c).Z216中三個(gè)運(yùn)算

,?,⊙任何兩個(gè)都不滿足結(jié)合律,例

a?(bc)(a?b)c.三個(gè)運(yùn)算

,?,⊙

的混合使用,獲得良好的非線性性，混淆與擴(kuò)散效果顯著，具有很高的安全性.例：設(shè)運(yùn)算數(shù)長為2bit，22=4,a=10,b=11,有

ab=1011=01;

a?b=10?11=2+3=5=1=01mod4;a⊙b=10⊙11=23=6=1=01mod5.59IDEA基本運(yùn)算乘/加結(jié)構(gòu)MA(multiplication/addition)?⊙?⊙K2(16bit)K1(16bit)G2(16bit)G1(16bit)F2(16bit)F1(16bit)輸入：

F1,F2:16bit

子密鑰K1,K2:16bit輸出：

G1,G2:16bit非線性結(jié)構(gòu)

MA:{0,1}16{0,1}16{0,1}16{0,1}16{0,1}16{0,1}1660IDEA算法框圖8輪迭代輸入:4個(gè)16bit子串

6個(gè)16bit子密鑰輸出:4個(gè)16bit子串輸出變換輸入:4個(gè)16bit子串

4個(gè)16bit子密鑰輸出:4個(gè)16bit子串子密鑰生成算法

K(128bit)

K1,K2,…,K52(16bit).…………

第2輪W21W23W22W24W11W13W12W14K7K12…

第1輪K1K6…X1X3X2X4

明文:X(64bit)

第8輪W81W83W82W84W71W73W72W74K43K48…

輸出變換K49K52…Y4Y3Y2Y1

密文:Y(64bit)61IDEA的子密鑰生成算法將128bit的K依次分為8個(gè)16bit的子密鑰:

K1,K2,…K8將K循環(huán)左移25位得L25K，依次分為8個(gè)16bit的子密鑰:K9,K10,…K16重復(fù)上一步…62IDEA的輪結(jié)構(gòu)輸入:4個(gè)16bit子串:I1,I2,I3,I46個(gè)16bit子密鑰:

Z1,Z2,Z3,Z4,Z5,Z6輸出:4個(gè)16bit子串O1,O2,O3,O4??⊙⊙?⊙?⊙O1O2O3O4I1I2I3I4Z2Z1Z3Z4Z5Z663IDEA的輸出變換輸入:4個(gè)16bit子串:W81,W82,W83,W844個(gè)16bit子密鑰:

K49,K50,K51,K52輸出:4個(gè)16bit子串Y1,Y2,Y3,Y4W81W82W83W84??⊙⊙Y1Y2Y3Y4K51K52K50K49密文:Y=IDEAK(X)=Y1||Y2||Y3||Y464IDEA特性IDEA算法軟、硬件實(shí)現(xiàn)容易，速度快。軟件實(shí)現(xiàn)比DES快兩倍安全性好：用窮舉攻擊要試探2128=1038個(gè)密鑰，如用每秒運(yùn)行100萬次的計(jì)算機(jī)進(jìn)行搜索，大約需要1013年.IDEA能抵抗差分攻擊和線性攻擊IDEA的安全缺陷：存在大量的弱密鑰IDEA的設(shè)計(jì)適合于16位CPU,對于32CPU實(shí)現(xiàn)不太方便65（4）AES（AdvancedEncryptionStandard）1997年4月15日，（美國）國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）發(fā)起征集高級加密標(biāo)準(zhǔn)（AdvancedEncryptionStandard）AES的活動，活動目的是確定一個(gè)非保密的、可以公開技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。作為進(jìn)入AES候選過程的一個(gè)條件，開發(fā)者承諾放棄被選中算法的知識產(chǎn)權(quán)。

對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。661998年8月12日，在首屆AES會議上指定了15個(gè)候選算法。1999年3月22日第二次AES會議上，將候選名單減少為5個(gè)，這5個(gè)算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES會議上，對這5個(gè)候選算法的各種分析結(jié)果進(jìn)行了討論。2000年10月2日，NIST宣布了獲勝者—Rijndael算法，2001年11月出版了最終標(biāo)準(zhǔn)FIPSPUB197。67分組長度（bit）128192256密鑰長度（bit）128192256表1.分組長度和密鑰長度的不同取值68AES

算法的一般描述69RijndaelRound的構(gòu)成ByteSubstitution(字節(jié)置換)ByteRotation(字節(jié)移位)MixColumn(列混合)+RoundKey一般的輪變換ByteSubstitutionByteRotation+RoundKey最后一輪的輪變換輪密鑰加7071AES

算法加密部分的實(shí)現(xiàn)明文分組和密鑰的組織排列方式01234567891011121314150481215913261014371115Fig1.以明文分組為128bits為例組成的陣列72048121591326101437111504812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731Fig2.以明文分組（或密鑰）為128bits、192bits、256bits為例組成的陣列73

一些相關(guān)的的術(shù)語定義和表示狀態(tài)（State）：密碼運(yùn)算的中間結(jié)果稱為狀態(tài)。State的表示：狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，列數(shù)記為Nb。Nb=分組長度（bits）÷32Nb可以取的值為4，6，8，對應(yīng)的分組長度為128，192，256bits。密碼密鑰（CipherKey）的表示：CipherKey類似地用一個(gè)4行的矩陣陣列來表示，列數(shù)記為Nk。Nk=密鑰長度（bits）÷32Nk可以取的值為4，6，8，對應(yīng)的密鑰長度為128，192，256bits。74Fig3.當(dāng)Nb=6時(shí)的狀態(tài)和Nk=4時(shí)的密鑰布局a0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb=6BlockLength=192bitsK0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk=4KeyLength=128bits75表2.輪數(shù)（Round）的不同取值輪數(shù)（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=2561414147676用偽代碼表示的Rijndael輪變換一般的輪變換Round(State,RoundKey){ByteSubstitution;ByteRotation;MixColumn;AddRounKey;}結(jié)尾輪變換FinalRound(State,RoundKey){ByteSubstituion;ByteRotation;AddRoundKey;}77用偽代碼表示的Rijndael加密算法Rijndael(State,CipherKey){

KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey);For(i=1;i<Rnd;i++)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Rnd);}78與一些其它算法的比較：與DES相比：1.無DES中的弱密鑰和半弱密鑰；2.緊湊的設(shè)計(jì)使得沒有足夠的空間來隱藏陷門。與IDEA相比：無IDEA中的弱密鑰。具有擴(kuò)展性：密鑰長度可以擴(kuò)展到為32bits倍數(shù)的任意密鑰長度，分組長度可以擴(kuò)展到為64bits倍數(shù)的任意分組長度。圈數(shù)和循環(huán)移位偏移量作為參數(shù)，要重新定義。79

3、對稱密碼的弱點(diǎn)

對稱密碼體制的優(yōu)點(diǎn)是計(jì)算速度快，有較強(qiáng)的保密強(qiáng)度。但是，它有三個(gè)致命弱點(diǎn)：

1、密鑰分配非常困難；

2、難以解決數(shù)字簽名驗(yàn)證問題。

3、要為每一個(gè)通信對象維護(hù)一個(gè)密鑰。若要與100人秘密通信，則要保留100個(gè)密鑰。大量密鑰的維護(hù)比較困難、容易泄密。80當(dāng)某一貿(mào)易方有n”個(gè)貿(mào)易關(guān)系,那么他就要維護(hù)“n”個(gè)專用密鑰(即每把密鑰對應(yīng)一貿(mào)易)對稱密鑰加密中的密鑰81

非對稱密碼體制ENetworkPlainTextCipherTextCipherTextDPlainTextAliceBobBob:SecretKey82明文密文非對稱密鑰加密技術(shù)加密我的：私有密鑰或你的：公共密鑰我的：公共密鑰或你的：私有密鑰831、基本概念

為了解決上述問題，1976年，Diffi和Hellman首次提出公開非對稱密鑰加密體制。即每個(gè)人都有一對密鑰，其中一個(gè)為公開的（公鑰），一個(gè)為私有的（私鑰）。使用兩個(gè)密鑰——一個(gè)用來加密數(shù)據(jù)，一個(gè)用來解密數(shù)據(jù)。兩個(gè)密鑰是數(shù)學(xué)上相關(guān)聯(lián)的——用其中之一加密的數(shù)據(jù)，只能夠用另一個(gè)密鑰解密。密鑰對由用戶自己或信任機(jī)構(gòu)產(chǎn)生。當(dāng)與多個(gè)通信對象進(jìn)行通信時(shí)，只要生成一對密鑰。W.Diffie&M.Hellman:NewDirectionsinCryptography,IEEETransactionsonInformationTheory,Vol.IT-22,No.6,Nov.1976,pp.644-654.84通信方甲生成一對密鑰并將其中的一把作為公開密鑰向其他通信方公開非對稱密鑰加密中的密鑰852、非對稱密鑰加密的原理使用數(shù)學(xué)上的理論；數(shù)學(xué)上某些復(fù)雜的計(jì)算問題：正向計(jì)算容易，反向計(jì)算困難。計(jì)算機(jī)不可能在有效的時(shí)間內(nèi)算出反向結(jié)果（從而不可能破解密碼）。例如：計(jì)算兩個(gè)大數(shù)的乘積，非常容易。分解一個(gè)很大的數(shù)（如200多位）非常困難，假如這個(gè)大數(shù)只含有兩個(gè)非常大的素?cái)?shù)（各100多位）作為因子。863、RSA算法（1）RSA背景

RSA算法是由Rivest、Shamir、Adleman于1977年提出的，RSA的取名就來自于這三個(gè)發(fā)明者的姓名的第一個(gè)字母，他們在1982年創(chuàng)辦RSA公司，該公司在公鑰密碼系統(tǒng)的研制和商業(yè)應(yīng)用推廣方面有非常重要的地位。

RSA算法的理論基礎(chǔ)是數(shù)論中的歐拉定理，其安全性是基于大數(shù)分解的困難性。1978年,R.Rivest,A.Shamir,L.Adleman提出RSA密碼體制

R.Rivest,A.Shamir,L.Adleman,Amethodforobtainingdigitalsignaturesandpublic-keycryptosystem,Comm.ACM21(2)(1978),pp.120-126.數(shù)學(xué)基礎(chǔ)是歐拉定理，安全性基于大合數(shù)因式分解的困難性安全,易懂.可用于加密與數(shù)字簽名.ISO,ITU,SWIFT把RSA選為加密標(biāo)準(zhǔn);Internet的E-Mail的保密系統(tǒng)GPG,國際VISA和MASTER組織的電子商務(wù)協(xié)議(SET協(xié)議)都將RSA作為傳送會話密鑰和數(shù)字簽名的標(biāo)準(zhǔn).3、RSA算法RSA密碼體制算法密鑰生成算法(1)選取兩個(gè)大素?cái)?shù)p,q(2)計(jì)算n=pq,(n)=(p-1)(q-1)(3)隨機(jī)選取e:1<e<(n)，與(n)互素(4)根據(jù)歐幾里德算法計(jì)算e的逆d=e1:1<e<(n)，ed1mod(n).(5)公鑰:PK=(n,e),

私鑰:SK=(p,q,d).(6)明文空間和密文空間:

Zn={0,1,2,…,n-1}90加密算法:設(shè)消息m:0m<n，解密算法:設(shè)密文c:0c<n，解密算法正確性證明（P為素?cái)?shù)）例

設(shè)p=11,q=13.令

n=1113=143,

(n)=(p-1)(q-1)=(11-1)(13-1)=120,取公鑰:PK=(n,e)=(143,e=17)，計(jì)算:d=e-1=17-1=113(mod120)(因?yàn)?17113=1921=16120+1).私鑰:SK=(p,q,d)=(11,13,113).對于明文:m=24,密文:c=EPK(m)=2417=7(mod143).對于密文:c=7,解密:m=DSK(c)=7113=24(mod143).RSA密碼算法的實(shí)現(xiàn)模冪算法:me(modn)—(高效算法：平方乘算法)b=0?b(mod2)=0?輸出c==unsignedlongqe2(unsignedlongx,unsignedlongr,unsignedlongn){unsignedlonga,b,c;c=1;a=x;b=r;while(b)/*b非0，則繼續(xù)處理*/{if(b&1)/*表示指數(shù)為奇數(shù)*/c=(c*a)%n;/*把兩個(gè)指數(shù)為1的數(shù)相乘，變?yōu)橐粋€(gè)數(shù)*/b>>=1;/*指數(shù)除以2*/a=(a*a)%n;}returnc;}main(){unsignedlonga=1520,b=13,n=2573,congruent;congruent=qe2(a,b,n);printf(“Resultis:%ld”,congruent);}95RSA密碼體制的安全性攻擊方法

：分解n已知n=pq

(n)=(p-1)(q-1)

d=e-1mod(n).分解n的最新水平:二進(jìn)制表示有512位.n應(yīng)為1024,2048位.96對RSA的選擇密文攻擊它們不攻擊基本的算法，而是攻擊協(xié)議。

情況1：假設(shè)A在B的通信時(shí)進(jìn)行竊聽，得到用B的公鑰加密的密文C。顯然，A要得到明文M，必須計(jì)算：97

情況2：

假設(shè)A想得到B對消息m3的偽造簽名，A可以做如下攻擊：注意：千萬不要對陌生人提交的隨機(jī)消息進(jìn)行簽名。98RSA的公共模數(shù)攻擊

若系統(tǒng)中共有一個(gè)模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那末該信息無需私鑰就可得到恢復(fù)。設(shè)m

為信息明文，兩個(gè)加密密鑰為e1和e2，公共模數(shù)是n，則兩個(gè)密文為：

密碼分析者知道n、e1、e2、C1和C2，就能得到m。因?yàn)閑1和e2互質(zhì)，故用擴(kuò)展Euclidean算法能找到r和s，滿足：r*e1+s*e2=1注意：不要在一組用戶間共享n。99100p和q要足夠大:n=pq

為1024位,或2048位.p和q應(yīng)為強(qiáng)素?cái)?shù)(strongprime).

如果素?cái)?shù)p

滿足以下條件,則稱為強(qiáng)素?cái)?shù).(1)p-1有大素?cái)?shù)因子r;(2)p+1有大素?cái)?shù)因子s;(3)r-1有大素?cái)?shù)因子t.

例如:理想的強(qiáng)素?cái)?shù)為:

r=2t+1;p=2r+1=4t+3;p=2s-1.RSA密碼的安全參數(shù)|p-q|要大.

如果|p-q|較小,則(p+q)/2n1/2,((p-q)/2)2=((p+q)/2)2-n.可求出p和q.

例:對于n=164009,有n1/2405.令

(p+q)/2=405,((p-q)/2)2=4052-n=16p+q=810,p-q=8p=409,q=401164009=409401.加密指數(shù)e的選擇

為使加密速度快,應(yīng)使e的二進(jìn)制表示中,1的個(gè)數(shù)盡量小,但不能太小.

可取:e=3,216+1=65537(在二進(jìn)制表示中只有2個(gè)1).解密指數(shù)d的選擇

在d的二進(jìn)制表示中,1的個(gè)數(shù)盡量小,但不能太小.3dn1/4.1034、ElGamal算法1045、橢圓曲線密碼系統(tǒng)

有限域上的橢圓曲線設(shè)p