第2章密碼學(xué)基礎(chǔ)

第2章密碼學(xué)基礎(chǔ)密碼學(xué)基礎(chǔ)知識(shí)密碼技術(shù)在信息安全中的作用信息安全的重要和核心部分之一是數(shù)據(jù)安全數(shù)據(jù)安全的目標(biāo)包括機(jī)密性、真實(shí)性、完整性、不可否認(rèn)性、可用性、可控性實(shí)現(xiàn)數(shù)據(jù)安全目標(biāo)的重要手段是密碼技術(shù)密碼技術(shù)具有幾千年的歷史密碼學(xué)（Cryptology）是密碼技術(shù)的基礎(chǔ)，包括：密碼編碼學(xué)（Cryptography）密碼分析學(xué)（Cryptanalysis）密碼學(xué)基礎(chǔ)知識(shí)密碼編碼學(xué)：研究如何進(jìn)行數(shù)據(jù)加密和解密（機(jī)密性），以及防止和發(fā)現(xiàn)數(shù)據(jù)的偽造、篡改（真實(shí)性、完整性、不可否認(rèn)性）密碼分析學(xué)：分析發(fā)現(xiàn)密碼算法的弱點(diǎn)、缺陷，破解密碼算法或者破譯密碼數(shù)據(jù)數(shù)據(jù)加密、解密的基本過(guò)程明文明文密文密文解密加密破解密鑰kc密鑰kd明文:plaintext密文:ciphertext加密:encrypt解密:decrypt密鑰:key密碼算法的基本定義設(shè)：M是可能明文的集合，稱為明文空間C是可能密文的集合，稱為密文空間K是一切可能密鑰構(gòu)成的集合，稱為密鑰空間E為加密算法，對(duì)密鑰空間的任一密鑰k都能進(jìn)行加密運(yùn)算，即Ek:MCD為解密算法，對(duì)密鑰空間的任一密鑰都能進(jìn)行解密運(yùn)算，即Dk:CM則密碼算法具有如下性質(zhì)：（1）Dk(Ek(x))=x，x屬于M，k屬于K（2）密碼破譯者獲得密文c=Ek(x)后無(wú)法在有效的時(shí)間內(nèi)破解出密鑰k和/或明文x密碼體制分類古典密碼(ClassicCryptography)對(duì)稱密鑰密碼(SymmetricKeyCryptography)公開(kāi)密鑰密碼體系(PublicKeyCryptography)古典密碼代替表代換密碼移位密碼乘數(shù)密碼仿射密碼對(duì)照表代替密碼abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDIABCDEFGHIJKLMdlryvohEzxwptNOPQRSTUVWXYZbgfjqnmuskaci加密代替表解密代替表iamateacherZXTXMHXYGHC一些關(guān)于模余數(shù)的基本知識(shí)定義1.設(shè)n為大于1的正整數(shù)，a為任一整數(shù)，a可表示為a=kn+r，r≥0，則記為：amodn=r，稱r為a的模n余數(shù)注意：負(fù)數(shù)的模n余數(shù)是正整數(shù)！例，若–n<a<0，則amodn=n+a定義2.設(shè)n為大于1的正整數(shù)，a、b為任意整數(shù)，如果amodn=bmodn，即a、b有相同模n余數(shù)，則稱a、b模n同余表示為a≡b(modn)a、b模n同余當(dāng)且僅當(dāng)n整除a-b一些關(guān)于模余數(shù)的基本知識(shí)注意以下差別：a=bmodna≡b(modn)前者表示：b的模n余數(shù)是a；后者表示：a和b模n同余，即有相同的模n余數(shù)在本課中用前一種表示，即mod作為一種算子一些關(guān)于模余數(shù)的基本知識(shí)定義3.n為大于1的正整數(shù)，a、b為整數(shù)，則a+bmodn，a*bmodn，abmodn分別稱為整數(shù)的模n加法、乘法和乘方(冪)一些關(guān)于模余數(shù)的基本知識(shí)設(shè)n為大于1的正整數(shù)，a、b為任意整數(shù)，則1)a+bmodn=(amodn)+(bmodn)modn2)a–bmodn=(amodn)+(–bmodn)modn=(amodn)–(bmodn)modn3)abmodn=(amodn)*(bmodn)modn4)amodn=a+knmodn=a–knmodn5)a+(bmodn)modn=a+bmodn一些關(guān)于模余數(shù)的基本知識(shí)6)a*(bmodn)modn=a*bmodn7)(amodn)pmodn=apmodn注意：mod的運(yùn)算優(yōu)先級(jí)最低結(jié)論：

對(duì)于同一個(gè)模n，只要保存最外層的mod算子，給加、減、乘、乘方運(yùn)算中的數(shù)據(jù)加上或去掉mod算子，不影響結(jié)果

請(qǐng)嘗試證明一下！模余數(shù)舉例例1.求9mod69=6+3，故9mod6=3例2.求–7mod6–7=-12+5，故–7mod6=5而2X6+(–7)mod6=5故，–7mod6=2X6+(–7)mod6=5(即amodn=a+knmodn)模余數(shù)舉例(續(xù))例3.求9–7mod69–7=2，故9–7mod6=2而(9mod6)+(–7mod6)mod6=3+5mod6=8mod6=2(9mod6)–(7mod6)mod6=3–1mod6=2故9-7mod6=(9mod6)+(–7mod6)mod6=(9mod6)–(7mod6)mod6(即a–bmodn=(amodn)+(–bmodn)modn=(amodn)–(bmodn)modn)模余數(shù)舉例(續(xù))例4.求2+(9mod6)mod6=2+3mod6=5而2+9mod6=11mod6=5故2+(9mod6)mod6=2+9mod6(即a+(bmodn)modn=a+bmodn)例5.求2*(9mod6)mod6=2*3mod6=0

而2*9mod6=18mod6=0故，2*(9mod6)mod6=2*9mod6(即a*(bmodn)modn=a*bmodn)一些關(guān)于模余數(shù)的基本知識(shí)定義4.設(shè)n為大于1的正整數(shù)，a、b為任意整數(shù)，若a+bmodn=0，則b稱為a的模n加法逆，記為-a注意：a的模n加法逆不止一個(gè)，它們相差kn定義5.設(shè)n為大于1的正整數(shù)，a、b為任意整數(shù)，若abmodn=1，則b稱為a的模n乘法逆，記為a-1注意：a的模n乘法逆不止一個(gè)，它們相差kn模余數(shù)舉例(續(xù))例6.求5的模6加法和乘法逆5+1mod6=0故，1是5的模6加法逆，5的模6加法逆是6k+15*5mod6=25mod6=1故，5是5的模6乘法逆，5的模6乘法逆是6k+5例7.求3的模6加法和乘法逆3+3mod6=0故，3是3的模6加法逆，3的模6加法逆是6k+30,1,..,5都不是3的模6乘法逆，故3無(wú)模6乘法逆一些關(guān)于模余數(shù)的基本知識(shí)定義6.設(shè)p是大于1的正整數(shù)，若p只能分解為1和自己的乘積，則p稱為素?cái)?shù)定義7.設(shè)a和b是大于1的正整數(shù)，

且a和b的最大公因子是1，即

gcd(a,b)=1，則稱為a和b互素定理1.設(shè)a和n是大于1的正整數(shù)，且a和n互素，則a存在模n乘法逆a-1推理1.設(shè)n是素?cái)?shù)，則任何非kn整數(shù)a存在模n乘法逆a-1移位密碼加密函數(shù)：c=Ek(m)=(m+k)modn，其中0≤m<n，m是待加密的明文數(shù)據(jù)(當(dāng)作數(shù))，1<k<n，k是密鑰解密函數(shù)：m=Dk(c)=(c–k)modn–k如何理解？有效性Dk(c)=(c–k)modn=((m+k)modn)-kmodn=m+k–kmodn=mmodn=mc-k<0怎辦？移位密碼凱撒密碼每個(gè)字母用后移3位的字母代換用0,1,…,25對(duì)應(yīng)26個(gè)字母M=C={0,1,…,25},n=26,k=3明文信息M=meetmeafterthetogaparty密文信息C=phhwphdiwhowkhwrjdsduwb乘數(shù)密碼加密函數(shù)：c=Ek(m)=k*mmodn，其中0≤m<n，gcd(k,n)=1，1<k<n解密函數(shù)：m=Dk(c)=k-1*cmodn，其k-1是k的模n乘法逆有效性Dk(c)=k-1*cmodn=k-1*(k*mmodn)modn=(k-1*k*m)modn=((k-1*k)modn)*(mmodn)modn=1*mmodn=m仿射密碼加密函數(shù)：c=Ek(m)=k*m+hmodn其中，0≤m<n,gcd(k,n)=1,0<k<n，0≤h<n(k=1,h=0除外)解密函數(shù)：m=Dk(c)=k-1*(c–h)modn，其中，k-1是k的模n乘法逆仿射密碼對(duì)英文字母的密碼運(yùn)算如下：M=C={0,1,…,25},h∈M模n=26k∈{1,3,5,7,9,11,15,17,19,21,23,25}，k-1是k的模26乘法逆k=1,h=0組合除外，故有26X12-1=311可能仿射密碼例設(shè)k=5,h=3,5的模26乘法逆是21，故，Ek(m)=5m+3mod26Dk(c)=21*(c–3)mod26=21c–11mod26yesEk=254185×+333=192315=txptxpDk=19231521×-111111=25418=yesmod26移位、乘數(shù)、仿射密碼適用性問(wèn)題適用于有限的明文空間MM中的每個(gè)元素對(duì)應(yīng)一個(gè)非負(fù)整數(shù)模數(shù)n大于M中的元素對(duì)應(yīng)的最大整數(shù)，且n大于等于2密文空間是{0,1,2,…,n-1}移位、乘數(shù)、仿射密碼安全性不但k、h要保密，n也要保密，否則，可以采用簡(jiǎn)單的選擇明文攻擊，比如移位密碼k=c–mmodn

乘數(shù)密碼k=c*m-1modn,選擇gcd(m,n)=1仿射密碼k=(c1–c2)*(m1–m2)-1modn,選擇gcd(m1–m2,n)=1n必須非常大，否則，用蠻力攻擊就可破解對(duì)古典代換密碼的攻擊針對(duì)古典代換密碼(包括替換表、移位、乘數(shù)、仿射密碼)可采用統(tǒng)計(jì)分析攻擊蠻力攻擊對(duì)移位、乘數(shù)、仿射密碼，選擇明文攻擊英文字母相對(duì)使用頻度分布英文字母相對(duì)使用頻度分布多表代換密碼用多個(gè)代替表依次對(duì)明文消息的字母進(jìn)行代換的加密方法隱藏字母出現(xiàn)的頻度對(duì)稱密鑰密碼SymmetricKeyCryptography加密和解密使用同一個(gè)密鑰對(duì)稱密鑰數(shù)字加密分為流加密和分組加密非公共網(wǎng)絡(luò)Key安全信道Thisisasecretletter明文密文加密密文解密Thisisasecretletter明文AliceBob流加密(streamcipher)用一個(gè)偽隨機(jī)密鑰流(pseudorandomkeystream)與數(shù)據(jù)流(按位或按字節(jié))進(jìn)行異或(XOR)操作發(fā)送方，用一個(gè)偽隨機(jī)密鑰流對(duì)明文數(shù)據(jù)進(jìn)行異或(XOR)操作(加密)接收方，用同一個(gè)偽隨機(jī)密鑰流對(duì)密文數(shù)據(jù)進(jìn)行異或(XOR)操作(解密)根據(jù)偽隨機(jī)密鑰流生成方式的不同分為同步流加密(synchronousstreamcipher)自同步流加密(self-synchronousstreamcipher)或異步流加密(asynchronousstreamcipher)同步流加密密鑰流的生成與密文流獨(dú)立(無(wú)依賴關(guān)系)σi+1=f(σi,k)zi=g(σi,k)ciσiσi+1+fgmizikci=zi⊕mi加密移位σiσi+1+fgcimizikmi=zi⊕ci解密移位∵mi=zi⊕(zi⊕mi)σi是一位或多位的內(nèi)部狀態(tài)zi

是偽隨機(jī)密鑰流同步流加密的特點(diǎn)發(fā)送和接收方要求嚴(yán)格密鑰流和數(shù)據(jù)同步，如果密碼數(shù)據(jù)流出現(xiàn)丟失或插入，則后續(xù)的整個(gè)解密解密失?。荑€流與密文流失步）無(wú)錯(cuò)誤傳遞，如果傳輸過(guò)程中一位密文出現(xiàn)錯(cuò)誤（非丟失或插入），不會(huì)影響后續(xù)密文的解密易于遭受攻擊：（1）攻擊者通過(guò)刪除、插入或重播密文位導(dǎo)致無(wú)法正確解密；（2）攻擊者可能可通過(guò)改變密文的某些位導(dǎo)致出現(xiàn)他預(yù)期的結(jié)果，比如，修改某些密文位導(dǎo)致訂單數(shù)量的改變自同步流加密密鑰流的生成與密文流的1位或多位相關(guān)σi=(ci-t,…,ci-2,ci-1)zi=g(σi,k)σi=有個(gè)初始值(初始化向量)σi+gmicizikci=zi⊕mi加密ci-t…

ci-2

ci-1mikmi=zi⊕ci解密+gciziσici-t…

ci-2

ci-1σi是狀態(tài)向量zi

是偽隨機(jī)密鑰流自同步流加密的特點(diǎn)接收方能自同步：如果密文的某些位被刪除或插入，接收方能夠自同步，因?yàn)榻邮辗降慕饷軆H依賴于前面固定數(shù)量的密文位有限的錯(cuò)誤傳遞：如果密文的某位出現(xiàn)修改、刪除或插入，最多導(dǎo)致后續(xù)有限位的數(shù)據(jù)解密錯(cuò)誤，因?yàn)榻饷苤灰蕾囉谇懊娴墓潭〝?shù)量的密文位對(duì)密文修改攻擊防護(hù)能力增加：對(duì)一個(gè)密文位的修改，導(dǎo)致多個(gè)密文位解密不正確，因此，更易于發(fā)現(xiàn)對(duì)密文的修改發(fā)散對(duì)明文的統(tǒng)計(jì)分析：因?yàn)橹暗拿魑挠绊懥藢?duì)后面明文加密的結(jié)果，使得攻擊者難于通過(guò)統(tǒng)計(jì)分析找到明文和密文的關(guān)系分組加密LbitLbitLbitLbit……BLOCK1BLOCK2BLOCK3BLOCKn明文分組加密E加密E加密E加密EMbitMbitMbitMbit……密文分組解密D解密D解密D解密DLbitLbitLbitLbit……明文分組BLOCK1BLOCK2BLOCK3BLOCKnBLOCK1BLOCK2BLOCK3BLOCKnKeyKeyKeyKey分組加密算法DES(DataEncryptionStandard)3DES(TripleDES)RC5IDEA(InternationalDataEncryptionAlgorithm)AES(AdvancedEncryptionStandard)DES算法曾經(jīng)使用非常廣泛的著名分組密碼算法(已不安全)其產(chǎn)生過(guò)程是：1973美國(guó)國(guó)家標(biāo)準(zhǔn)局(NationalBureauofStandard,NBS)征集國(guó)家密碼標(biāo)準(zhǔn)方案1974年NBS第二次征集時(shí)，IBM公司提出他們的方案LUCIFER1975年NBS公開(kāi)了IBM算法并安排兩個(gè)小組進(jìn)行評(píng)價(jià)1976年NBS在征詢了美國(guó)國(guó)家安全局(NationalSecurityAgency，NSA)的意見(jiàn)，并由NSA對(duì)IBM算法中的S-Box(替換表，substitutiontable)進(jìn)行微小變化、降低了密鑰長(zhǎng)度后發(fā)表，命名為DES(曾引起密碼界的廣泛懷疑)DES算法64位的分組加密算法密鑰64位，但實(shí)際密鑰長(zhǎng)度是56位，其他8位是奇偶校驗(yàn)位通過(guò)移位(shift)、排列(permutation)、代換(substitution)、異或(ExclusiveOR)操作實(shí)現(xiàn)密碼運(yùn)算加密、解密過(guò)程是對(duì)稱的DES算法的安全性DES最大的安全問(wèn)題是它的密鑰長(zhǎng)度才56位1990年S.Biham和A.Shamir用差分攻擊方法，采用選擇明文攻擊，最終破解了密鑰1994年的世界密碼大會(huì)上，M.Matsui采用線性分析方法，利用243個(gè)已知明文成功地破譯了DES算法1997年RSA公司發(fā)起了首屆“向DES挑戰(zhàn)”的競(jìng)賽，羅克.維瑟用96天破解了用DES加密的一段信息1999年12月，RSA公司發(fā)起第三屆DES挑戰(zhàn)賽，2000年1月電子前沿基金會(huì)研制的DES解密機(jī)以22.5小時(shí)成功破解了DES加密3DES隨著計(jì)算技術(shù)的發(fā)展，DES越來(lái)越不能滿足安全要求，特別是其密鑰長(zhǎng)度56位太短，使得可以通過(guò)蠻力攻擊(brutalforceattack)破解密碼通過(guò)應(yīng)用三重DES算法、使用超過(guò)56位的密鑰提高DES的安全3DES的四種模式DES-EEE3，使用三個(gè)不同的DES密鑰順序進(jìn)行三次加密變換，解密是逆過(guò)程，密鑰長(zhǎng)度168位DES-EDE3，加密時(shí)使用三個(gè)不同的DES密鑰依次進(jìn)行加密-解密-加密變換，解密是逆過(guò)程，密鑰長(zhǎng)度168位DES-EEE2，進(jìn)行三次加密變換，其中第一次、第三次變換的密鑰相同，解密是逆過(guò)程，密鑰長(zhǎng)度112位DES-EDE2，加密時(shí)依次進(jìn)行加密-解密-加密變換，其中第一次、第三次變換的密鑰相同，解密是逆過(guò)程，密鑰長(zhǎng)度112位RC5由RSA公司的首席科學(xué)家RonRivest于1994年設(shè)計(jì)、1995年正式公開(kāi)的一種加密算法一種分組長(zhǎng)度w、密鑰長(zhǎng)度b和迭代輪數(shù)r都可變的分組迭代式密碼，簡(jiǎn)記RC5-w/r/b采用了三種運(yùn)算：異或、加和循環(huán)移位RC5的特點(diǎn)形式簡(jiǎn)單易于軟件或硬件實(shí)現(xiàn)，運(yùn)算速度快能適用于不同字長(zhǎng)的系統(tǒng)，不同字長(zhǎng)派生出相異的算法加密的輪數(shù)可變，這個(gè)參數(shù)用來(lái)調(diào)整加密速度和安全性的程度密鑰長(zhǎng)度可變，加密強(qiáng)度可調(diào)節(jié)對(duì)存儲(chǔ)要求不高，可在SmartCard內(nèi)存有限的系統(tǒng)中使用具有高保密性對(duì)數(shù)據(jù)實(shí)行位循環(huán)位移，增強(qiáng)抗抵賴能力RC5的安全性到目前為止尚未發(fā)現(xiàn)有效的攻擊手段分析表明，r為12的RC5可抵抗差分分析和線性分析攻擊IDEA1990年由瑞士聯(lián)邦技術(shù)學(xué)院的來(lái)學(xué)嘉(X.J.Lai)和Massey提出64位分組密碼算法，密鑰長(zhǎng)度128位使用了異或、模216加法、模216+1乘法1992年命名為IDEA(InternationalDataEncryptionAlgorithm，國(guó)際數(shù)據(jù)加密算法)IDEA的安全性到目前為止尚未發(fā)現(xiàn)算法的明顯弱點(diǎn)減少密碼運(yùn)算的輪次，可導(dǎo)致算法被攻破存在一些弱密鑰需要避免AES為了替代DES和3DES，1997年4月美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究院(NationalInstituteofStandardsandTechnology，NIST)發(fā)布征集AES(AdvancedEncryptionStandard)的活動(dòng)1997年9月NIST公布AES要求的通告，要求AES比3DES快，至少同3DES一樣安全，分組長(zhǎng)度128位，密鑰長(zhǎng)度128/192/256位經(jīng)過(guò)反復(fù)的評(píng)選、論證最后兩個(gè)比利時(shí)密碼學(xué)家JoanDaemen和VincentRijmen提出的Rijndael密碼算法勝出，AES規(guī)范發(fā)布AES的安全性到目前為止，AES是安全的，尚未有有效的攻擊分組加密的工作模式電子編碼本(ElectronicCodeBook,ECB)密碼分組鏈接(CipherBlockChaining,CBC)密碼反饋(CipherFeedback,CFB)輸出反饋(OutputFeedback,OFB)電子編碼本(ECB)明文分組1加密密文分組1密文分組1解密明文分組1明文分組2加密密文分組2密文分組2解密明文分組2明文分組n加密密文分組n密文分組n解密明文分組n………………時(shí)間ECB的特點(diǎn)簡(jiǎn)單和有效可實(shí)現(xiàn)并行加密不能隱藏明文的模式信息，即相同明文對(duì)應(yīng)相同密文，同樣的信息多次出現(xiàn)造成泄露錯(cuò)誤傳遞?。杭用?、傳輸或解密時(shí)，一塊密文出錯(cuò)、修改、損壞僅對(duì)對(duì)應(yīng)的明文造成影響對(duì)明文的主動(dòng)攻擊是可能的：信息塊可被替換、重排、刪除、重放密碼分組鏈接(CBC)明文分組1加密密文分組1密文分組1解密明文分組1IV⊕⊕IV明文分組2加密密文分組2密文分組2解密明文分組2⊕⊕明文分組n加密密文分組n密文分組n解密明文分組n⊕⊕時(shí)間CBC的特點(diǎn)沒(méi)有已知的并行實(shí)現(xiàn)算法能隱藏明文的模式信息，相同明文對(duì)應(yīng)不同密文錯(cuò)誤傳遞較大：加密時(shí)一塊密文出錯(cuò)、損壞導(dǎo)致后續(xù)所有密文出錯(cuò)傳輸時(shí)一塊密文損壞、刪除、插入導(dǎo)致最多兩塊明文塊無(wú)法解密還原對(duì)明文的主動(dòng)攻擊是不易的：一塊密文被替換、重排、刪除、重放，解密會(huì)出現(xiàn)錯(cuò)誤安全性好于ECB密碼反饋(CFB)明文分組n密文分組iIV⊕明文分組2明文分組1移位寄存器加密選擇S位丟棄S明文分組1IV⊕明文分組2明文分組n移位寄存器加密選擇S位丟棄L－S

S……加密解密SSL－S

S

L

LCFB的特點(diǎn)適用于分組密碼和流密碼沒(méi)有已知的并行實(shí)現(xiàn)算法能夠隱藏明文模式，相同明文對(duì)應(yīng)不同密文需要共同的移位寄存器初始值誤差傳遞較大：加密時(shí)一塊密文出錯(cuò)、損壞使得所有后續(xù)密文出錯(cuò)傳遞時(shí)一塊密文修改、損壞、插入、刪除可能使得1+[(L+S-1)/S]塊明文塊無(wú)法解密還原輸出反饋(OFB)明文分組n密文分組iIV⊕明文分組2明文分組1移位寄存器加密選擇S位丟棄L－S

SS位明文分組1IV⊕明文分組2明文分組n移位寄存器加密選擇S位丟棄L－S

S……加密解密SS

L

LOFB的特點(diǎn)適用于分組密碼和流密碼沒(méi)有已知的并行實(shí)現(xiàn)算法能夠隱藏明文模式，相同明文對(duì)應(yīng)不同密文需要共同的移位寄存器初始值誤差傳遞小加密或傳輸時(shí)一個(gè)密文塊損壞只影響對(duì)應(yīng)的明文塊安全性較CFB差(偽隨機(jī)密鑰序列的周期短)分組加密的填充(padding)數(shù)據(jù)長(zhǎng)度不一定就是分組的倍數(shù)，在數(shù)據(jù)尾部填充適當(dāng)?shù)臄?shù)據(jù)使得最后一塊數(shù)據(jù)的長(zhǎng)度等于分組長(zhǎng)度要求：(1)滿足分組長(zhǎng)度要求；(2)解密者知道哪些是原始數(shù)據(jù)哪些是填充數(shù)據(jù)ANSIX.923尾部填充字節(jié)0，最后一個(gè)字節(jié)表示填充個(gè)數(shù)…|3AC34B78258BCD7D|3AC34B7800000004PKCS7填充的字節(jié)內(nèi)容就是填充的字節(jié)數(shù)…|3AC34B78258BCD7D|3AC34B7804040404ISO/IEC7816-4填充的第一個(gè)字節(jié)內(nèi)容是80，后面填充00…|3AC34B78258BCD7D|3AC34B7880000000對(duì)稱密鑰加密的特點(diǎn)算法實(shí)現(xiàn)簡(jiǎn)單速度快密鑰短密鑰分發(fā)難作業(yè)問(wèn)題1：將移位、乘數(shù)、仿射密碼用于英文26個(gè)字母的密碼變換時(shí)，n不是26行嗎？26個(gè)字母不按0~25連續(xù)編號(hào)行嗎？為什么？問(wèn)題2：如果被加密的數(shù)據(jù)的長(zhǎng)度正好是分組長(zhǎng)度的整數(shù)倍，是否還需要填充？如果不需要，說(shuō)明理由；如果需要，說(shuō)明如何填充。假設(shè)分組長(zhǎng)度是8字節(jié)，采用的填充方案是填充字節(jié)的內(nèi)容是填充字節(jié)數(shù)。公開(kāi)密鑰密碼體系PublicKeyCryptography也稱非對(duì)稱密鑰密碼體系，AsymmetricKeyCryptography公開(kāi)密鑰密碼算法思想的來(lái)源1976年WhitefieldDiffie和MartinHellman在其《密碼學(xué)新方向》中提出了公開(kāi)密鑰密碼算法的思想首次提出了單向陷門(trapdoor)函數(shù)的概念，并提出了Diffie-Hellman密鑰交換算法(加上使用密鑰進(jìn)行加密部分，它實(shí)質(zhì)上也是一個(gè)公開(kāi)密鑰加密算法！)單向陷門函數(shù)一個(gè)單向陷門函數(shù)f(x)滿足如下三個(gè)條件給定x，計(jì)算y=f(x)是容易的給定y，計(jì)算x使得y=f(x)是困難的存在δ，已知δ時(shí)對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使得y=f(x)是容易的Diffie-Hellman算法數(shù)學(xué)基礎(chǔ)素?cái)?shù)的原根(PrimitiveRoot)素?cái)?shù)p的一個(gè)原根是一個(gè)正整數(shù)g，gmodp、g2modp，…，gp-1modp不同，且包含了1到p-1的所有整數(shù)；若g是素?cái)?shù)p的一個(gè)原根，則（1）g，gmodp、g2modp，…，gp-1modp生成了{(lán)1,2,…,p-1}；（2）對(duì)應(yīng)任意整數(shù)1≤b≤p-1，存在一個(gè)唯一的1≤i≤p-1，使得b=gimodp定理.對(duì)于任意素?cái)?shù)p存在原根(一個(gè)或多個(gè))Diffie-Hellman算法數(shù)學(xué)基礎(chǔ)離散對(duì)數(shù)若n為大于1的正整數(shù)，m為整數(shù)，若b=mimodn，則b稱為m的模n下的i次冪，i稱為b的以m為基數(shù)的模n下的冪指數(shù)，即b的離散對(duì)數(shù)離散對(duì)數(shù)難題對(duì)于函數(shù)y=mxmodn，已知m、n、x計(jì)算y是容易的，反之，已知m、n、y計(jì)算x是困難的Diffie-Hellman密鑰交換算法描述Alice和Bob共享一個(gè)公開(kāi)的大素?cái)?shù)p和大整數(shù)g，1<g<p，g是p的原根Alice隨機(jī)選取大的隨機(jī)整數(shù)1<x<p，并計(jì)算W=gxmodpBob隨機(jī)選取大的隨機(jī)整數(shù)1<y<p，并計(jì)算Z=gymodpAlice將W發(fā)送給BobBob將Z發(fā)送給AliceAlice計(jì)算K1=Zxmodp=gxymodpBob計(jì)算K2=Wymodp=gxymodpK1=K2=KAlice和Bob用密鑰K進(jìn)行數(shù)據(jù)加密、解密ThisisasecretletterThisisasecretletterBobAlice(y,p,g)是Bob的私鑰，(Z,p,g)是Bob的公鑰(x,p,g)是Alice的私鑰，(W,p,g)是Alice的公鑰BobAlice易于遭受中間人攻擊BobAlice我是Bob我是AliceEveRSA公開(kāi)密鑰算法目前應(yīng)用最廣泛、也是最早能同時(shí)用于加密和簽名的公開(kāi)密鑰算法由美國(guó)的RonRivest、AdiShamir、LeonardAdleman三人于1978年提出數(shù)學(xué)基礎(chǔ)：數(shù)論中的歐拉(Euler)定理或費(fèi)馬小定理(Fermat’slittletheorem)和大整數(shù)的因子分解問(wèn)題RSA公開(kāi)密鑰算法的數(shù)學(xué)基礎(chǔ)1）Fermat’slittletheorem若p為素?cái)?shù)，則對(duì)于任意整數(shù)a，有apmodp=amodp若進(jìn)一步地，如p不能除a(即a≠kp)，則有ap-1modp=12）歐拉定理如果a和n是互素的正整數(shù)，則aφ(n)modn=1

φ(n)是Euler’stotientfunction

若n是素?cái)?shù)，則φ(n)=n-1若n=pq，p、q是互異的素?cái)?shù)，則φ(n)=(p-1)(q-1)RSA公開(kāi)密鑰算法的數(shù)學(xué)基礎(chǔ)3）若p、q是兩個(gè)互異的素?cái)?shù)，n=pq，0≤m<n，則對(duì)于任意正整數(shù)k，根據(jù)歐拉定理或Fermat’slittletheorem可導(dǎo)出如下結(jié)果：

mkφ(n)+1modn=m,其中,φ(n)=(p-1)(q-1)4）已知兩個(gè)互異的大素?cái)?shù)p、q，計(jì)算n=pq是容易的；反之，若已知n是兩個(gè)素?cái)?shù)p、q的乘積，分解出p、q卻是很困難的，目前無(wú)有效辦法RSA公開(kāi)密鑰算法描述1）選擇兩個(gè)互異的大素?cái)?shù)p和q，計(jì)算n=pq，計(jì)算φ(n)=(p-1)(q-1)2）選擇整數(shù)1<e<φ(n)使得gcd(e,φ(n))=1(互素)3）計(jì)算得到e的模φ(n)乘法逆元d，即e*dmodφ(n)=1，其中，1<d<φ(n)4）公開(kāi)密鑰是P=(e,n)，私鑰是S=(d,n,p,q)以上（1）到（4）由私鑰擁有者完成5）對(duì)于明文m加密運(yùn)算：c=memodn(使用公鑰)解密運(yùn)算：m=cdmodn(使用私鑰)RSA公開(kāi)密鑰算法描述算法有效性：d是e的模φ(n)乘法逆元，e*dmodφ(n)=1，故存在一個(gè)正整數(shù)k使得e*d=kφ(n)+1cdmodn=(memodn)dmodn=medmodn=mkφ(n)+1modn=m6）將使用e、d的順序換一下，結(jié)果同樣正確（用于數(shù)字簽名）加密運(yùn)算：c=mdmodn(使用私鑰d)解密運(yùn)算：m=cemodn(使用公鑰e)RSA公開(kāi)密鑰算法的應(yīng)用BobAlice公鑰私鑰ThisisasecretletterThisisasecretletter公鑰發(fā)布給BobAlice公鑰用Alice公鑰加密用私鑰解密RSA公開(kāi)密鑰算法的中間人攻擊BobAlice這是Bob公鑰這是Alice公鑰Eve需采用其他方案如PKI解決公鑰的發(fā)布問(wèn)題Eve的密鑰對(duì)RSA公開(kāi)密鑰密碼算法的安全性算法的安全性1）

加密函數(shù)c=memodn是單向門限函數(shù)：已知m求c是容易的，

反之已知c求m是困難的；若已知p、q(陷門信息)，則由c可計(jì)算出m2）安全性依賴大數(shù)n=pq的因子分解難題，及解密函數(shù)m=cdmodn的離散對(duì)數(shù)難題算法的安全性被認(rèn)為等同于大數(shù)分解的難度，但缺乏理論證明(也許除了分解之外，還有其他破解方案？)要保證安全，p和q必須是足夠大的素?cái)?shù)，目前n=pq是1024位的二進(jìn)制數(shù)已不很安全RSA公開(kāi)密鑰算法的特性首個(gè)既可以用于加密，又可以用于簽名的公開(kāi)密鑰密碼算法密鑰長(zhǎng)度(模n)要足夠長(zhǎng)RSA的加密、解密采用了大整數(shù)的指數(shù)運(yùn)算，故速度比采用移位、排列、代換、異或操作的對(duì)稱密鑰密碼算法要慢很多為了提高加密速度通常將整數(shù)e取為固定的小整數(shù)，如EDI國(guó)際標(biāo)準(zhǔn)中規(guī)定e=216+1，ISO/IEC9796中規(guī)定允許e=3，但d很大，故加密和驗(yàn)簽速度比解密和簽名速度快很多Rabin公開(kāi)密鑰密碼算法MichaelO.Rabin提出基于大數(shù)分解難題隨機(jī)選兩個(gè)大的素?cái)?shù)p和q，計(jì)算n=pq，n是公鑰，p和q是私鑰加密：c=m2modn,0≤m<n是明文解密：求c的{0,1,…,n-1}內(nèi)的模n平方根經(jīng)證明其安全性等同于大數(shù)分解難題ElGamal公開(kāi)密鑰密碼算法由TaherElGamal提出基于Diffie-Hellman密鑰交換算法和循環(huán)群上的離散對(duì)數(shù)難題包括加密算法和簽名算法ElGamal加密算法ElGamal加密算法，基于循環(huán)群(Cyclicgroup)，可用于任何循環(huán)群，包括橢圓曲線上的點(diǎn)構(gòu)成的循環(huán)群(ECC密碼算法)，故其方案被廣泛用于其他公開(kāi)密鑰加密算法群一個(gè)定義了乘法(或加法)，包含”1”(或”0”)元素的集合，集合中的任何一個(gè)元素都存在乘法(或加法)逆循環(huán)群，集合中的所有元素可由一個(gè)元素g按乘法冪gi生成(或加法倍乘i*g生成)例如：若Z*p={1,2,…,p-1}，p為素?cái)?shù)，定義模p乘法：任意a、b

∈

Z*p，a*b定義為abmodp，則Z*p就是一個(gè)循環(huán)群，它的一個(gè)原根g可生成Z*p的所有元素，即Z*p={g,g2,…,gp-1}ElGamal加密算法描述(Z*p群)設(shè)g是Z*p的一個(gè)大原根(Primitiveroot)，即gimodp，i=1,…,p-1，生成Z*p的所有元素密鑰生成Alice隨機(jī)生成一個(gè)整數(shù)x，1<x

<p-1Alice計(jì)算h=gxmodpAlice保存x作為其私鑰，將(h,g,p)作為公鑰發(fā)布數(shù)據(jù)加密Bob隨機(jī)生成一個(gè)整數(shù)y,1<y

<p-1并計(jì)算c1=gymodpBob計(jì)算共享秘密s=hymodp=gxymodp(D-H密鑰)Bob計(jì)算(加密)c2=m*smodpBob將(c1,c2)=(gymodp,m*smodp)發(fā)送給AliceElGamal加密算法描述(Z*p群)數(shù)據(jù)解密Alice計(jì)算共享秘密(c1)xmodp=gxymodp=s(D-H密鑰)Alice計(jì)算得到s模p乘法逆s-1Alice計(jì)算(解密)c2*s-1modp=(m*s*s-1modp)=(mmodp)*(s*s-1modp)modp=m對(duì)于Z*p群，ElGamal加密算法實(shí)際上是D-H密鑰交換算法+乘數(shù)密碼算法ElGamal加密算法的特點(diǎn)安全性依賴于離散對(duì)數(shù)難題要保證安全性，密鑰要很長(zhǎng)(p要很大)計(jì)算對(duì)稱密鑰采用了大整數(shù)的指數(shù)運(yùn)算，速度慢密文成倍增長(zhǎng)非對(duì)稱密鑰算法的特點(diǎn)算法實(shí)現(xiàn)復(fù)雜相對(duì)于對(duì)稱密鑰密碼算法，速度較慢，故通常采用非對(duì)稱密鑰密碼算法和對(duì)稱密鑰密碼算法相結(jié)合的方案：隨機(jī)對(duì)稱密鑰加密數(shù)據(jù)，非對(duì)稱密鑰加密隨機(jī)對(duì)稱密鑰有的算法密鑰長(zhǎng)度長(zhǎng)(如RSA,EIGamal算法)密鑰分發(fā)容易有些算法既可用于數(shù)據(jù)加密，又可用于抗抵賴數(shù)字簽名消息鑒別消息(Message)，即傳輸?shù)囊粠畔⒌臄?shù)據(jù)消息鑒別(MessageAuthentication)即判斷、確定消息的真實(shí)性和完整性，即是否由聲稱的發(fā)送者發(fā)送，不是偽造的，在傳輸過(guò)程中是否被篡改或出錯(cuò)，并兼顧抗抵賴常用的幾種方法消息加密消息編碼消息鑒別碼(MessageAuthenticationCode,MAC)數(shù)字簽名消息鑒別-消息加密對(duì)稱密鑰加密只有擁有同樣密鑰的人或?qū)嶓w才能正確對(duì)消息加密和解密：接收方能正確解密消息則說(shuō)明（1）消息發(fā)送方擁有密鑰；（2）傳輸中未修改（但有可能插入、刪除）ThisisasecretletterThisisasecretletterBobAlice消息鑒別-消息加密非對(duì)稱密鑰加密(數(shù)字簽名)私鑰擁有者用私鑰對(duì)發(fā)送的消息加密，接收者用發(fā)送者公鑰解密，成功解密說(shuō)明：（1）消息發(fā)送者擁有私鑰；（2）傳輸中未修改(但有可能插入、刪除)BobAlice公鑰私鑰ThisisasecretletterThisisasecretletter公鑰發(fā)布給BobAlice公鑰用Alice公鑰解密用私鑰加密消息編碼采用外界不知曉的特定編碼規(guī)則來(lái)保證消息的出處只能保證消息的源發(fā)性，不能保證消息的完整性很少采用消息鑒別-消息鑒別碼(MAC)散列函數(shù)(HASH)，也稱哈希、雜湊函數(shù)獲取消息的特征(信息指紋)將任意長(zhǎng)度的消息映射成一個(gè)固定長(zhǎng)度的數(shù)據(jù)，稱為散列值，也稱消息摘要(MessageDigest)散列函數(shù)的特性單向性，從散列值無(wú)法倒推出消息無(wú)碰撞性，任何兩個(gè)不同的消息的散列值不同(即不同的消息有不同的散列值)散列函數(shù)實(shí)質(zhì)是多到一的映射，因此，理想的無(wú)碰撞性是不存在的，只存在概率無(wú)碰撞性，即發(fā)生碰撞的概率極小，幾乎不能發(fā)生散列函數(shù)的無(wú)碰撞性弱無(wú)碰撞性散列函數(shù)h(x)的弱無(wú)碰撞性是指在消息特定的明文空間X，給定任一消息x∈X，在計(jì)算上幾乎找不到不同于x的xˊ∈X，使得h(x)=h(xˊ)強(qiáng)無(wú)碰撞性散列函數(shù)h(x)的強(qiáng)無(wú)碰撞性是指給定消息x∈X，X為x的所有可能明文數(shù)據(jù)空間，在計(jì)算上幾乎找不到不同于x的xˊ∈X，使得h(x)=h(xˊ)（x在更大的數(shù)據(jù)空間）散列函數(shù)的設(shè)計(jì)要考慮強(qiáng)無(wú)碰撞性，實(shí)際應(yīng)用中真正有