信息安全原理與技術(shù)第2章密碼學(xué)基礎(chǔ)課件

本章主要內(nèi)容密碼學(xué)基本概念對稱密碼體制公鑰密碼體制散列函數(shù)數(shù)字簽名信息隱藏與數(shù)字水印12/16/20221信息安全原理與技術(shù)本章主要內(nèi)容12/11/20221信息安全原理與技術(shù)2.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

單表置換密碼，凱撒密碼，

多表置換密碼，Vigenere密碼等等近代密碼：DES數(shù)據(jù)加密標(biāo)準(zhǔn)，70年代Diffie,Hellman

的開創(chuàng)性工作——公鑰體制的提出密碼應(yīng)用：電子數(shù)據(jù)，軍事目的，經(jīng)濟目的。應(yīng)用形式：數(shù)據(jù)的保密性、真實性、完整性。主要內(nèi)容：數(shù)據(jù)加密，密碼分析，數(shù)字簽名，信息

鑒別，零泄密認(rèn)證，秘密共享等等。信息攻擊：主動攻擊——對數(shù)據(jù)的惡意刪除、篡改等

被動攻擊——從信道上截取、偷竊、拷貝

信息。

無意攻擊——錯誤操作、機器故障等。12/16/20222信息安全原理與技術(shù)2.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

2.2密碼學(xué)基本概念現(xiàn)代密碼系統(tǒng)的組成

現(xiàn)代密碼系統(tǒng)(通常簡稱為密碼體制)一般由五個部分組成：明文空間M

密文空間C

密鑰空間K

加密算法E

解密算法D

則五元組（M，C，K，E，D）稱為一個密碼體制。12/16/20223信息安全原理與技術(shù)2.2密碼學(xué)基本概念現(xiàn)代密碼系統(tǒng)的組成現(xiàn)密碼體制

對稱密鑰體制

非對稱密鑰體制

12/16/20224信息安全原理與技術(shù)密碼體制12/11/20224信息安全原理與技術(shù)根據(jù)密碼算法對明文信息的加密方式，對稱密碼體制常分為兩類：分組密碼(Blockcipher，也叫塊密碼)DES、IDEA、BLOWFISH序列密碼(Streamcipher，也叫流密碼)。

A5、FISH、PIKE

12/16/20225信息安全原理與技術(shù)根據(jù)密碼算法對明文信息的加密方式，對稱密碼體制常分為兩密碼分析學(xué)窮舉攻擊：又稱作蠻力攻擊，是指密碼分析者用試遍所有密鑰的方法來破譯密碼對可能的密鑰或明文的窮舉統(tǒng)計分析攻擊：指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。

數(shù)學(xué)分析攻擊：指密碼分析者針對加密算法的數(shù)學(xué)依據(jù)，通過數(shù)學(xué)求解的方法來破譯密碼。

12/16/20226信息安全原理與技術(shù)密碼分析學(xué)12/11/20226信息安全原理與技術(shù)1、唯密文攻擊：僅根據(jù)密文進行的密碼攻擊；2、已知明文攻擊：根據(jù)一些相應(yīng)的明、密文對進行的密碼攻擊。3、選擇明文攻擊：可以選擇一些明文，并獲取相應(yīng)的密文，這是密碼分析者最理想的情形。例如，在公鑰體制中。4、選擇密文攻擊：密碼分析者能選擇不同的被加密的密文，并可得到對應(yīng)的解密的明文，密碼分析者的任務(wù)是推出密鑰。5、選擇密鑰攻擊：這種攻擊并不表示密碼分析者能夠選擇密鑰，它只表示密碼分析者具有不同密鑰之間關(guān)系的有關(guān)知識。6、軟磨硬泡攻擊：密碼分析者威脅、勒索，或者折磨某人，直到他給出密鑰為止。

根據(jù)密碼分析者掌握明、密文的程度密碼分析可分類為：12/16/20227信息安全原理與技術(shù)1、唯密文攻擊：僅根據(jù)密文進行的密碼攻擊；根據(jù)密碼分析者掌握密碼算法的安全性：

理論上，除一文一密外，沒有絕對安全的密碼體制，通常，稱一個密碼體制是安全的是指計算上安全的，即：密碼分析者為了破譯密碼，窮盡其時間、存儲資源仍不可得，或破譯所耗資材已超出因破譯而獲得的獲益。12/16/20228信息安全原理與技術(shù)密碼算法的安全性：12/11/20228信息安全原理與技術(shù)2.3對稱密碼體制經(jīng)典的密碼體制中，加密密鑰與解密密鑰是相同的，或者可以簡單相互推導(dǎo)，也就是說：知道了加密密鑰，也就知道了解密密鑰；知道了解密密鑰，也就知道了加密密鑰。所以，加、解密密鑰必須同時保密。這種密碼體制稱為對稱（也稱單鑰）密碼體制。最典型的是DES數(shù)據(jù)加密標(biāo)準(zhǔn)，應(yīng)該說數(shù)據(jù)加密標(biāo)準(zhǔn)DES是單鑰體制的最成功的例子。

12/16/20229信息安全原理與技術(shù)2.3對稱密碼體制經(jīng)典的密碼體制中，加密密鑰與解密密鑰是1973.5.15：美國國家標(biāo)準(zhǔn)局（NSA）公開征求密碼體制的聯(lián)邦注冊；1975.3.17：DES首次在《聯(lián)邦記事》公開，它由IBM開發(fā)，它是LUCIFER的改進；1977.2.15：DES被采用作為非國家機關(guān)使用的數(shù)據(jù)加密標(biāo)準(zhǔn)，此后，大約每五年對DES進行依次審查，1992年是最后一次審查，美國政府已聲明，1998年后對DES不再審查了；1977.2.15：《聯(lián)邦信息處理》標(biāo)準(zhǔn)版46（FIPSPUB46）給出了DES的完整描述。12/16/202210信息安全原理與技術(shù)1973.5.15：美國國家標(biāo)準(zhǔn)局（NSA）公開征求密碼體2.3.1DES分組密碼系統(tǒng)DES密碼體制：它是應(yīng)用56位密鑰，加密64比特明文分組的分組秘鑰密碼體制DES加密算法：

（一）初始置換：x0=L0R0=IP(x)；

（二）16次迭代：xi-1=Li-1Ri-1，

Li=Ri，Ri=Li

f(Ri-1,ki)

i=1,2,…,16；

（三）逆置換：x16=L16R16，y=IP-1(x16)。密鑰生成器：密鑰ki是由56位系統(tǒng)密鑰k生成的32位子密鑰。函數(shù)f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)ki))12/16/202211信息安全原理與技術(shù)2.3.1DES分組密碼系統(tǒng)DES密碼體制：它是應(yīng)用

其中E，P是兩個置換，表示比特的“異或”，S是一組八個變換S1，S2，S3，…，S8，稱為S盒，每個盒以6位輸入，4位輸出，S盒構(gòu)成了DES安全的核心。DES算法流程圖12/16/202212信息安全原理與技術(shù)其中E，P是兩個置換，表示比特的“異或”，S是一組函數(shù)f及S盒的示意圖DES解密：DES的解密過程與加密過程相同，只不過

子密鑰的使用相反，即，首先使用k16，再使用k15，

…，最后使用k1。12/16/202213信息安全原理與技術(shù)函數(shù)f及S盒的示意圖DES解密：DES的解密過程與加密過程相2.3.2關(guān)于DES的討論S盒是唯一非線性組件：有人認(rèn)為其中可能含有某種“陷門”，國家安全機關(guān)可以解密。DES的密鑰量太小：密鑰量為2561977年：Diffie.Hellman提出制造一個每秒測試106的VLSI芯片，則一天就可以搜索完整個密鑰空間，當(dāng)時造價2千萬美圓。CRYPTO’93：R.Session，M.Wiener提出并行密鑰搜索芯片，每秒測試5x107個密鑰，5760片這種芯片，造價10萬美圓，平均一天即可找到密鑰。12/16/202214信息安全原理與技術(shù)2.3.2關(guān)于DES的討論S盒是唯一非線性組件：有人Internet的超級計算能力：1997年1月28日，美國RSA數(shù)據(jù)安全公司在Internet上開展了一項“秘密密鑰挑戰(zhàn)”的競賽，懸賞一萬美圓，破解一段DES密文。計劃公布后，得到了許多網(wǎng)絡(luò)用戶的強力相應(yīng)。科羅拉州的程序員R.Verser設(shè)計了一個可以通過互聯(lián)網(wǎng)分段運行的密鑰搜索程序，組織了一個稱為DESCHALL的搜索行動，成千上萬的的志愿者加入到計劃中。12/16/202215信息安全原理與技術(shù)Internet的超級計算能力：1997年1月28日，美國R第96天，即競賽公布后的第140天，1997年6月17日晚上10點39分，美國鹽湖城Inetz公司職員M.Sanders成功地找到了密鑰，解密出明文：TheunknownMessageis：“Strongecryptographymakesthewordasaferplace”(高強度密碼技術(shù)使世界更安全)。Internet僅僅利用閑散資源，毫無代價就破譯了DES密碼，這是對密碼方法的挑戰(zhàn)，是Internet超級計算能力的顯示.12/16/202216信息安全原理與技術(shù)第96天，即競賽公布后的第140天，1997年6月17日晚上差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著名的有Biham，Shamir的差分分析法。這是一個選擇明文攻擊方法。雖然對16輪DES沒有攻破，但是，如果迭代的輪數(shù)降低，則它可成功地被攻破。例如，8輪DES在一個個人計算機上只需要2分鐘即可被攻破。12/16/202217信息安全原理與技術(shù)差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著2.3.3DES擴展形式多重DESS盒可選擇的DES具有獨立子密鑰的DESG-DES

12/16/202218信息安全原理與技術(shù)2.3.3DES擴展形式多重DES12/11/202212.4公鑰密碼體制

一個安全的對稱密鑰密碼系統(tǒng)，可以達到下列功能：保護信息機密

認(rèn)證發(fā)送方之身份

確保信息完整性對稱密鑰密碼系統(tǒng)具有下列缺點：

收發(fā)雙方如何獲得其加密密鑰及解密密鑰？

密鑰的數(shù)目太大

無法達到不可否認(rèn)服務(wù)

2.4.1傳統(tǒng)密碼體制的缺陷與公鑰密碼體制的產(chǎn)生

12/16/202219信息安全原理與技術(shù)2.4公鑰密碼體制一個安全的對稱密鑰密碼系統(tǒng)，可以達到下現(xiàn)代密碼學(xué)修正了密鑰的對稱性，1976年，Diffie，Hellmann提出了公開密鑰密碼體制（簡稱公鑰體制），它的加密、解密密鑰是不同的，也是不能（在有效的時間內(nèi)）相互推導(dǎo)。所以，它可稱為雙鑰密碼體制。它的產(chǎn)生，是密碼學(xué)革命性的發(fā)展，它一方面，為數(shù)據(jù)的保密性、完整性、真實性提供了有效方便的技術(shù)。另一方面，科學(xué)地解決了密碼技術(shù)的瓶頸──密鑰的分配問題。12/16/202220信息安全原理與技術(shù)現(xiàn)代密碼學(xué)修正了密鑰的對稱性，1976年，Diffie，He第一個公鑰體制是1977年由Rivest，Shamir，Adleman提出的，稱為RSA公鑰體制，其安全性是基于整數(shù)的因子分解的困難性。RSA公鑰體制已得到了廣泛的應(yīng)用。其后，諸如基于背包問題的Merkle-Hellman背包公鑰體制，基于有限域上離散對數(shù)問題的EIGamal公鑰體制，基于橢圓曲線的密碼體制等等公鑰體制不斷出現(xiàn)，使密碼學(xué)得到了蓬勃的發(fā)展，12/16/202221信息安全原理與技術(shù)第一個公鑰體制是1977年由Rivest，Shamir，Ad2.4.2公鑰密碼體制介紹

公鑰密碼體制加解密過程主要有以下幾步：

12/16/202222信息安全原理與技術(shù)2.4.2公鑰密碼體制介紹公鑰密碼體制加解密過程主要安全的公開密鑰密碼可以達到下列功能：（1）簡化密鑰分配及管理問題

公鑰體制用于數(shù)據(jù)加密時：用戶將自己的公開（加密）密鑰登記在一個公開密鑰庫或?qū)崟r公開，秘密密鑰則被嚴(yán)格保密。信源為了向信宿發(fā)送信息，去公開密鑰庫查找對方的公開密鑰，或臨時向?qū)Ψ剿魅」€，將要發(fā)送的信息用這個公鑰加密后在公開信道上發(fā)送給對方，對方收到信息（密文）后，則用自己的秘密（解密）密鑰解密密文，從而，讀取信息?？梢?，這里省去了從秘密信道傳遞密鑰的過程。這是公鑰體制的一大優(yōu)點。

12/16/202223信息安全原理與技術(shù)安全的公開密鑰密碼可以達到下列功能：12/11/202223（2）保護信息機密

任何人均可將明文加密成密文，此后只有擁有解密密鑰的人才能解密。

12/16/202224信息安全原理與技術(shù)（2）保護信息機密12/11/202224信息安全原理與技（3）實現(xiàn)不可否認(rèn)功能

公鑰體制用于數(shù)字簽名時：信源為了他人能夠驗證自己發(fā)送的消息確實來自本人，他將自己的秘密（解密）密鑰公布，而將公開（加密）密鑰嚴(yán)格保密。與別人通信時，則用自己的加密密鑰對消息加密──稱為簽名，將原消息與簽名后的消息一起發(fā)送.對方收到消息后，為了確定信源的真實性，用對方的解密密鑰解密簽名消息──稱為（簽名）驗證，如果解密后的消息與原消息一致，則說明信源是真實的，可以接受，否則，拒絕接受。

12/16/202225信息安全原理與技術(shù)（3）實現(xiàn)不可否認(rèn)功能12/11/202225信息安全原理2.4.3基本數(shù)學(xué)概念群模逆元費爾馬小定理

Euler函數(shù)

生成元

12/16/202226信息安全原理與技術(shù)2.4.3基本數(shù)學(xué)概念群12/11/202226信息安2.4.4RSA算法1976年：Diffie，Hellman在“NewDirectioninCryptography”(密碼學(xué)新方向)一文中首次提出公開密鑰密碼體制的思想。1977年：Rivest,Shamir,Adleman第一次實現(xiàn)了公開密鑰密碼體制，現(xiàn)稱為RSA公鑰體制。12/16/202227信息安全原理與技術(shù)2.4.4RSA算法1976年：Diffie，Hell基本算法：①生成兩個大素數(shù)p和q（保密）；

②計算這兩個素數(shù)的乘積n=pq（公開）；

③計算小于n并且與n互素的整數(shù)的個數(shù)，即歐拉函數(shù)(n)=(p–1)(q–1)（保密）；

④選取一個隨機整數(shù)e滿足1<e<(n)，并且e和(n)互素，即gcd(e,(n))=1（公開）；

⑤計算d，滿足de=1mod(n)（保密）；12/16/202228信息安全原理與技術(shù)12/11/202228信息安全原理與技術(shù)E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解密過程公開信道12/16/202229信息安全原理與技術(shù)E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解一個利用RSA算法的加密實例

設(shè)p=101，q=113，n=pq=11413，

(n)=(p-1)(q-1)=100×112=11200，a=6597，b=3533，x=9726。

加密：y=xb=97263533=5761mod11413；解密：x=ya=57616597=9726mod11413。12/16/202230信息安全原理與技術(shù)一個利用RSA算法的加密實例設(shè)p=101，q=113，n=算法分析：該體制的數(shù)學(xué)依據(jù)是Euler定理及大數(shù)分解的困難性，體制中使用的是Zn中的計算。設(shè)是兩個不同奇素數(shù)p,q的乘積，對于這樣的正整數(shù)，其Euler函數(shù)值是容易計算的，它是(n)=(p-1)(q-1)。對于給定的明文x<n，選定一個正整數(shù)b，稱為加密密鑰。12/16/202231信息安全原理與技術(shù)算法分析：12/11/202231信息安全原理與技術(shù)作Zn中的指數(shù)運算，將明文以指數(shù)形式xb表示出來，即以指數(shù)形式將明文隱藏起來。即使知道一個明、密文對(x,y)，y=xbmodn,要得到密鑰b，必須求解離散對數(shù)問題：b=logxy，在Zn中這也是一個困難問題。可見這種加密思想是簡單、明確的。

12/16/202232信息安全原理與技術(shù)作Zn中的指數(shù)運算，將明文以指數(shù)形式xb表示出來，即以指數(shù)形RSA安全性分析

加密密鑰b是公開的，從而，要求從b不能有效地推導(dǎo)出a，解已知b，求解ab≡1mod(n)是計算上不可能的。(n)是n的Euler函數(shù)，如果已知(n)，則可以應(yīng)用展轉(zhuǎn)相除法求得b的逆元a，從而(n)的保密是安全的關(guān)鍵，而(n)的有效計算則依賴于n的素因子分解，從而，RSA的安全性與n的素因子分解等價。體制的安全性機理是大數(shù)分解的困難性。

12/16/202233信息安全原理與技術(shù)RSA安全性分析12/11/202233信息安全原理與技術(shù)大數(shù)分解是一個NP問題，目前已知的最好的算法需要進行ex次算術(shù)運算。假設(shè)我們用一臺每秒運算（即：一億）次的計算機來分解一個200位十進制的數(shù)

要分解一個200位十進制的數(shù)，需要3.8×107年，類似地，可算出要分解一個300位的十進制整數(shù)，則需要年4.86×1013。可見，增加的位數(shù)，將大大地提高體制的安全性。由以上分析可見，從直接分解大數(shù)來破譯RSA是計算上不可能的，那么是否存在一種破譯方法不依賴于的分解呢？雖然現(xiàn)在還沒有發(fā)現(xiàn)，但是也沒有嚴(yán)格的論證。

12/16/202234信息安全原理與技術(shù)大數(shù)分解是一個NP問題，目前已知的最好的算法需要進行ex次算直接分解一個大素數(shù)的強力攻擊的一個實例是：1994年4月分解的RSA密鑰RSA-129，即分解了一個129位十進制，425比特的大素數(shù)。分解時啟用了1600臺計算機，耗時8個月，處理了4600MIPS年的數(shù)據(jù)。1MIPS年是1MIPS的機器一年所能處理數(shù)據(jù)量。Pentium100大約是125MIPS，它分解RSA-129需要37年。100臺Pentium100需要4個月。

12/16/202235信息安全原理與技術(shù)直接分解一個大素數(shù)的強力攻擊的一個實例是：1994年4月分解硬件實現(xiàn)時，RSA比DES要慢大約1000倍，軟件實現(xiàn)時，RSA比DES要慢大約100倍?？梢?，用RSA直接加密信息有諸多不便，所以，很多實際系統(tǒng)中，只用RSA來交換DES的密鑰，而用DES來加密主體信息。

12/16/202236信息安全原理與技術(shù)硬件實現(xiàn)時，RSA比DES要慢大約1000倍，軟件實現(xiàn)時，R2.5散列函數(shù)2.5.1散列函數(shù)的概念

散列函數(shù)又可稱為壓縮函數(shù)、雜湊函數(shù)、消息摘要、指紋、密碼校驗和、信息完整性檢驗(DIC)、操作檢驗碼(MDC)。散列函數(shù)有4個主要特點：①它能處理任意大小的信息②它是不可預(yù)見的。③它是完全不可逆的，即散列函數(shù)是單向的④它是抗碰撞的12/16/202237信息安全原理與技術(shù)2.5散列函數(shù)2.5.1散列函數(shù)的概念12/11/單向散列函數(shù)的工作原理

常用的消息摘要算法有：（1）MD2算法（2）MD4和MD5算法（3）SHA算法12/16/202238信息安全原理與技術(shù)單向散列函數(shù)的工作原理12/11/202238信息安全原理2.5.2MD5算法

算法MD5首先填充消息成512比特的整數(shù)倍，但最后64比特是由文件長度填充的；其次，將個512比特分割成16個32比特子塊；取4個初始向量，從其及第一個子塊出發(fā)，作4輪（MD4只有3輪）16次迭代。得128比特輸出；以此作為初始向量，對下一個512比特執(zhí)行同樣的操作；

依次下去，直到所有的512比特都處理完畢，輸出128比特，此即MD5的輸出。12/16/202239信息安全原理與技術(shù)2.5.2MD5算法12/11/202239信息安全原2.6數(shù)字簽名數(shù)字簽名最早被建議用來對禁止核試驗條律的驗證。禁止核試驗條律的締約國為了檢測對方的核試驗，需要把地震測試儀放在對方的地下，而把測試的數(shù)據(jù)送回，自然這里有一個矛盾：東道主需要檢查發(fā)送的數(shù)據(jù)是否僅為所需測試的數(shù)據(jù)；檢測方需要送回的數(shù)據(jù)是真實的檢測數(shù)據(jù)，東道主沒有篡改。12/16/202240信息安全原理與技術(shù)2.6數(shù)字簽名數(shù)字簽名最早被建議用來對禁止核試驗條律的基本要求：簽名不能偽造：簽名是簽名者對文件內(nèi)容合法性的認(rèn)同、證明、和標(biāo)記，其他人的簽名無效；簽名不可抵賴：這是對簽名者的約束，簽名者的認(rèn)同、證明、標(biāo)記是不可否認(rèn)的；簽名不可改變：文件簽名后是不可改變的，這保證了簽名的真實性、可靠性；簽名不可重復(fù)使用：簽名需要時間標(biāo)記，這樣可以保證簽名不可重復(fù)使用。簽名容易驗證：對于簽名的文件，一旦發(fā)生糾紛，任何第三方都可以準(zhǔn)確、有效地進行驗證。12/16/202241信息安全原理與技術(shù)基本要求：12/11/202241信息安全原理與技術(shù)數(shù)字簽名的基本原理：應(yīng)用一對不可互相推導(dǎo)的密鑰，一個用于簽名（加密），一個用于驗證（解密），顛倒使用加解密過程。公鑰簽名原理：這種簽名就是加密過程的簡單顛倒使用，簽名者用加密密鑰（保密）簽名（加密）文件，驗證者用（公開的）解密密鑰解密文件，確定文件的真?zhèn)巍?2/16/202242信息安全原理與技術(shù)數(shù)字簽名的基本原理：應(yīng)用一對不可互相推導(dǎo)的密鑰，一個用于簽散列函數(shù)：散列函數(shù)是數(shù)字簽名的一個重要輔助工具，應(yīng)用散列函數(shù)可以生成一個文件的，具有固定長度的文件摘要，從而使數(shù)字簽名可以迅速有效地簽名一個任意長度的文件。一般地，對文件的任意小改動，都會改變文件的散列值，從而，秘密的散列函數(shù)可以用來檢測病毒等對文件的破壞。對簽名的攻擊：對數(shù)字簽名有各種各樣的欺騙存在，重復(fù)使用是一個典型欺騙，如電子支票，重復(fù)的使用具有可怕后果，阻止這種欺騙的有效方法是簽名中包含時間日期標(biāo)志。12/16/202243信息安全原理與技術(shù)散列函數(shù)：散列函數(shù)是數(shù)字簽名的一個重要輔助工具，應(yīng)用散列函常用算法介紹1、Elgamal算法：ElGamal簽名方案基于離散對數(shù)問題離散對數(shù)問題：設(shè)p是一個素數(shù)，bZ*p，尋找整數(shù)d，0<d<p，滿足：ad≡bmodp。這樣的問題稱為離散對數(shù)問題。選取p至少150位十進制數(shù)，p-1至少有一個“大”素因子，則離散對數(shù)問題稱為困難問題，困難問題不存在多項式時間算法12/16/202244信息安全原理與技術(shù)常用算法介紹12/11/202244信息安全原理與技術(shù)ElGamal簽名方案于1985年提出，改進后，被美國國家標(biāo)準(zhǔn)和技術(shù)研究所（NIST）采納為數(shù)字簽名標(biāo)準(zhǔn)。ElGamal簽名方案是一個非確定性的方案，也就是說，驗證算法可以接受的合法簽名不止一個。

12/16/202245信息安全原理與技術(shù)ElGamal簽名方案于1985年提出，改進后，被美國國家標(biāo)ElGamal簽名方案的定義：

設(shè)p是一個素數(shù)，Zp中的離散對數(shù)是困難問題，

aZ*p是一個生成元，b≡admodp，則定義：

簽名算法：Sigk(x,t)=(,)，≡atmodp，

≡(x-a)t-1modp-1，t是一保密的隨機數(shù)。

驗證算法：對給定的消息及簽名(x,(,))，x,Z*p,

Zp-1，驗證算法為12/16/202246信息安全原理與技術(shù)ElGamal簽名方案的定義：

設(shè)p是一個素數(shù)，Zp中的2、DSA算法：DSA是Schnorr和ElGamal簽名算法的變種，被美國NIST作為DSS。

數(shù)字簽名標(biāo)準(zhǔn)DSS：

設(shè)p是一個512比特的素數(shù)，Zp中的離散對數(shù)是困難

問題，q是一個60比特的素數(shù)，q|p-1，aZ*p是p模

q的單位根。則定義：

簽名算法：Sigk(x,t)=(,)，≡(atmodp)modq，

≡(x+a)t-1modq；

驗證算法：

Ver(x,(,))=true(albmmodp)modq≡，

其中：l≡x-1modq，m≡-1modq。12/16/202247信息安全原理與技術(shù)2、DSA算法：DSA是Schnorr和ElGamal簽名算DSS與ElGamal簽名方案的差別：

ElGamal簽名方案中模p至少有512比特，但這樣會產(chǎn)生1024比特的簽名。這樣的膨脹率對于象靈巧卡之類的應(yīng)用是一個難題。而DSS使用512比特模素數(shù)，簽名一個160比特的消息，產(chǎn)生320比特的簽名，即：模素數(shù)不變，但簽名消息的比特數(shù)減少了，而離散對數(shù)是基于Z*p的每個階為2160的子群，從而，安全性是可以保證的。

12/16/202248信息安全原理與技術(shù)DSS與ElGamal簽名方案的差別：

ElGam2.7信息隱藏與數(shù)字水印

信息隱藏不同于傳統(tǒng)的密碼學(xué)技術(shù)。密碼技術(shù)主要是研究如何將機密信息進行特殊的編碼，以形成不可識別的密碼形式(密文)進行傳遞；而信息隱藏則主要研究如何將某一機密信息秘密隱藏于另一公開的信息中，然后通過公開信息的傳輸來傳遞機密信息。

12/16/202249信息安全原理與技術(shù)2.7信息隱藏與數(shù)字水印信息隱藏不同于傳統(tǒng)的密碼學(xué)技術(shù)2.7.1信息隱藏信息隱藏模型

12/16/202250信息安全原理與技術(shù)2.7.1信息隱藏12/11/202250信息安全原理與信息隱藏特點

魯棒性(robustness)

不可檢測性(undetectability)透明性(invisibility)安全性(security)自恢復(fù)性

12/16/202251信息安全原理與技術(shù)信息隱藏特點12/11/202251信息安全原理與技術(shù)2.7.2數(shù)字水印典型的數(shù)字水印系統(tǒng)模型12/16/202252信息安全原理與技術(shù)2.7.2數(shù)字水印12/11/202252信息安全原理與數(shù)字水印的分類

（1）按水印的可見性劃分：可將水印分為可見水印和不可見水?。?）按水印的所附載體劃分：可以把水印劃分為圖像水印、音頻水印、視頻水印、文本水印以及用于三維網(wǎng)絡(luò)模型的網(wǎng)格水印等。（3）按水印的檢測過程劃分：可以將水印劃分非盲水印(NonblidWatermark)，半盲水印(SeminonblindWatermark)和盲水印(BindWatermark)。12/16/202253信息安全原理與技術(shù)數(shù)字水印的分類12/11/202253信息安全原理與技術(shù)（4）按水印的內(nèi)容劃分：可以將水印分為有意義水印和無意義水印。（5）按水印的用途劃分：可以將數(shù)字水印劃分為票據(jù)防偽水印、版權(quán)標(biāo)識水印、篡改提示水印和隱蔽標(biāo)識水印等。（6）按水印的隱藏位置劃分：可以將其劃分為時(空)域數(shù)字水印、變換域數(shù)字水印。

12/16/202254信息安全原理與技術(shù)（4）按水印的內(nèi)容劃分：可以將水印分為有意義水印和無意義水印數(shù)字水印的基本特性（1）隱藏信息的魯棒性

（2）不易察覺性（3）安全可靠性（4）抗攻擊性（5）水印調(diào)整和多重水印（6）可證明性12/16/202255信息安全原理與技術(shù)數(shù)字水印的基本特性12/11/202255信息安全原理與技數(shù)字水印的主要用途（1）數(shù)字媒體的版權(quán)保護和跟蹤（2）圖像認(rèn)證（3）篡改提示（4）數(shù)字廣播電視分級控制（5）標(biāo)題與注釋12/16/202256信息安全原理與技術(shù)數(shù)字水印的主要用途12/11/202256信息安全原理與技數(shù)字水印的制作方法（1）空間域水印算法（2）變換域算法（3）壓縮域算法（4）NEC算法（5）生理模型算法12/16/202257信息安全原理與技術(shù)數(shù)字水印的制作方法12/11/202257信息安全原理與技小結(jié)密碼學(xué)盡管在信息安全中具有舉足輕重的地位，但密碼學(xué)絕不是確保信息安全的唯一工具，它也不能解決所有的安全問題。同時，密碼編碼和密碼分析是一對矛和盾的關(guān)系，它們在發(fā)展中始終處于一種動態(tài)平衡。在后面的章節(jié)中還將介紹計算機系統(tǒng)安全的其他技術(shù)。

12/16/202258信息安全原理與技術(shù)小結(jié)密碼學(xué)盡管在信息安全中具有舉足輕重的地位，但密碼學(xué)絕不思考與練習(xí)

2.1什么是密碼學(xué)？什么是密碼編碼學(xué)和密碼分析學(xué)？2.2現(xiàn)代密碼系統(tǒng)的五個組成部分是什么？2.3密碼分析主要有哪些形式？各有何特點？2.4對稱密碼體制和非對稱密碼體制各有何優(yōu)缺點？2.5簡述用RSA及DES算法保護的機密性、完整性和抗否認(rèn)性的原理。12/16/202259信息安全原理與技術(shù)思考與練習(xí)2.1什么是密碼學(xué)？什么是密碼編碼學(xué)和密碼分析2.6在使用RSA公鑰中如果截取了發(fā)送給其他用戶的密文C＝10，若此用戶的公鑰為e＝5，n＝35，請問明文的內(nèi)容是什么?2.7已知有明文publickeyencryptions，先將明文以2個字母為組分成10塊，如果利用英文字母表的順序，即a＝00，b＝01…，將明文數(shù)據(jù)化?，F(xiàn)在令p＝53，q＝58，請計算得出RSA的加密密文。2.8請簡要比較DES算法和RSA算法的優(yōu)缺點。12/16/202260信息安全原理與技術(shù)2.6在使用RSA公鑰中如果截取了發(fā)送給其他用戶的密文C＝2.9查找資料，了解MD5算法還有哪些應(yīng)用。2.10什么是數(shù)字簽名？常用的算法有哪些？2.11進一部閱讀數(shù)字水印有關(guān)文獻(見本書參考文獻)，了解數(shù)字水印的攻擊方法和對抗策略。12/16/202261信息安全原理與技術(shù)2.9查找資料，了解MD5算法還有哪些應(yīng)用。12/11/2精品課件！12/16/202262信息安全原理與技術(shù)精品課件！12/11/202262信息安全原理與技術(shù)精品課件！12/16/202263信息安全原理與技術(shù)精品課件！12/11/202263信息安全原理與技術(shù)2.12編程：實現(xiàn)利用MD5算法進行文件完整性驗證的程序。2.13編程：實現(xiàn)基于LSB算法的在BMP圖片中進行信息隱藏的程序。2.14實驗：數(shù)字證書的應(yīng)用。實驗主要內(nèi)容：獲取數(shù)字證書、查看數(shù)字證書、對電子郵件進行數(shù)字簽名等應(yīng)用。12/16/202264信息安全原理與技術(shù)2.12編程：實現(xiàn)利用MD5算法進行文件完整性驗證的程序。本章主要內(nèi)容密碼學(xué)基本概念對稱密碼體制公鑰密碼體制散列函數(shù)數(shù)字簽名信息隱藏與數(shù)字水印12/16/202265信息安全原理與技術(shù)本章主要內(nèi)容12/11/20221信息安全原理與技術(shù)2.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

單表置換密碼，凱撒密碼，

多表置換密碼，Vigenere密碼等等近代密碼：DES數(shù)據(jù)加密標(biāo)準(zhǔn)，70年代Diffie,Hellman

的開創(chuàng)性工作——公鑰體制的提出密碼應(yīng)用：電子數(shù)據(jù)，軍事目的，經(jīng)濟目的。應(yīng)用形式：數(shù)據(jù)的保密性、真實性、完整性。主要內(nèi)容：數(shù)據(jù)加密，密碼分析，數(shù)字簽名，信息

鑒別，零泄密認(rèn)證，秘密共享等等。信息攻擊：主動攻擊——對數(shù)據(jù)的惡意刪除、篡改等

被動攻擊——從信道上截取、偷竊、拷貝

信息。

無意攻擊——錯誤操作、機器故障等。12/16/202266信息安全原理與技術(shù)2.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

2.2密碼學(xué)基本概念現(xiàn)代密碼系統(tǒng)的組成

現(xiàn)代密碼系統(tǒng)(通常簡稱為密碼體制)一般由五個部分組成：明文空間M

密文空間C

密鑰空間K

加密算法E

解密算法D

則五元組（M，C，K，E，D）稱為一個密碼體制。12/16/202267信息安全原理與技術(shù)2.2密碼學(xué)基本概念現(xiàn)代密碼系統(tǒng)的組成現(xiàn)密碼體制

對稱密鑰體制

非對稱密鑰體制

12/16/202268信息安全原理與技術(shù)密碼體制12/11/20224信息安全原理與技術(shù)根據(jù)密碼算法對明文信息的加密方式，對稱密碼體制常分為兩類：分組密碼(Blockcipher，也叫塊密碼)DES、IDEA、BLOWFISH序列密碼(Streamcipher，也叫流密碼)。

A5、FISH、PIKE

12/16/202269信息安全原理與技術(shù)根據(jù)密碼算法對明文信息的加密方式，對稱密碼體制常分為兩密碼分析學(xué)窮舉攻擊：又稱作蠻力攻擊，是指密碼分析者用試遍所有密鑰的方法來破譯密碼對可能的密鑰或明文的窮舉統(tǒng)計分析攻擊：指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。

數(shù)學(xué)分析攻擊：指密碼分析者針對加密算法的數(shù)學(xué)依據(jù)，通過數(shù)學(xué)求解的方法來破譯密碼。

12/16/202270信息安全原理與技術(shù)密碼分析學(xué)12/11/20226信息安全原理與技術(shù)1、唯密文攻擊：僅根據(jù)密文進行的密碼攻擊；2、已知明文攻擊：根據(jù)一些相應(yīng)的明、密文對進行的密碼攻擊。3、選擇明文攻擊：可以選擇一些明文，并獲取相應(yīng)的密文，這是密碼分析者最理想的情形。例如，在公鑰體制中。4、選擇密文攻擊：密碼分析者能選擇不同的被加密的密文，并可得到對應(yīng)的解密的明文，密碼分析者的任務(wù)是推出密鑰。5、選擇密鑰攻擊：這種攻擊并不表示密碼分析者能夠選擇密鑰，它只表示密碼分析者具有不同密鑰之間關(guān)系的有關(guān)知識。6、軟磨硬泡攻擊：密碼分析者威脅、勒索，或者折磨某人，直到他給出密鑰為止。

根據(jù)密碼分析者掌握明、密文的程度密碼分析可分類為：12/16/202271信息安全原理與技術(shù)1、唯密文攻擊：僅根據(jù)密文進行的密碼攻擊；根據(jù)密碼分析者掌握密碼算法的安全性：

理論上，除一文一密外，沒有絕對安全的密碼體制，通常，稱一個密碼體制是安全的是指計算上安全的，即：密碼分析者為了破譯密碼，窮盡其時間、存儲資源仍不可得，或破譯所耗資材已超出因破譯而獲得的獲益。12/16/202272信息安全原理與技術(shù)密碼算法的安全性：12/11/20228信息安全原理與技術(shù)2.3對稱密碼體制經(jīng)典的密碼體制中，加密密鑰與解密密鑰是相同的，或者可以簡單相互推導(dǎo)，也就是說：知道了加密密鑰，也就知道了解密密鑰；知道了解密密鑰，也就知道了加密密鑰。所以，加、解密密鑰必須同時保密。這種密碼體制稱為對稱（也稱單鑰）密碼體制。最典型的是DES數(shù)據(jù)加密標(biāo)準(zhǔn)，應(yīng)該說數(shù)據(jù)加密標(biāo)準(zhǔn)DES是單鑰體制的最成功的例子。

12/16/202273信息安全原理與技術(shù)2.3對稱密碼體制經(jīng)典的密碼體制中，加密密鑰與解密密鑰是1973.5.15：美國國家標(biāo)準(zhǔn)局（NSA）公開征求密碼體制的聯(lián)邦注冊；1975.3.17：DES首次在《聯(lián)邦記事》公開，它由IBM開發(fā)，它是LUCIFER的改進；1977.2.15：DES被采用作為非國家機關(guān)使用的數(shù)據(jù)加密標(biāo)準(zhǔn)，此后，大約每五年對DES進行依次審查，1992年是最后一次審查，美國政府已聲明，1998年后對DES不再審查了；1977.2.15：《聯(lián)邦信息處理》標(biāo)準(zhǔn)版46（FIPSPUB46）給出了DES的完整描述。12/16/202274信息安全原理與技術(shù)1973.5.15：美國國家標(biāo)準(zhǔn)局（NSA）公開征求密碼體2.3.1DES分組密碼系統(tǒng)DES密碼體制：它是應(yīng)用56位密鑰，加密64比特明文分組的分組秘鑰密碼體制DES加密算法：

（一）初始置換：x0=L0R0=IP(x)；

（二）16次迭代：xi-1=Li-1Ri-1，

Li=Ri，Ri=Li

f(Ri-1,ki)

i=1,2,…,16；

（三）逆置換：x16=L16R16，y=IP-1(x16)。密鑰生成器：密鑰ki是由56位系統(tǒng)密鑰k生成的32位子密鑰。函數(shù)f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)ki))12/16/202275信息安全原理與技術(shù)2.3.1DES分組密碼系統(tǒng)DES密碼體制：它是應(yīng)用

其中E，P是兩個置換，表示比特的“異或”，S是一組八個變換S1，S2，S3，…，S8，稱為S盒，每個盒以6位輸入，4位輸出，S盒構(gòu)成了DES安全的核心。DES算法流程圖12/16/202276信息安全原理與技術(shù)其中E，P是兩個置換，表示比特的“異或”，S是一組函數(shù)f及S盒的示意圖DES解密：DES的解密過程與加密過程相同，只不過

子密鑰的使用相反，即，首先使用k16，再使用k15，

…，最后使用k1。12/16/202277信息安全原理與技術(shù)函數(shù)f及S盒的示意圖DES解密：DES的解密過程與加密過程相2.3.2關(guān)于DES的討論S盒是唯一非線性組件：有人認(rèn)為其中可能含有某種“陷門”，國家安全機關(guān)可以解密。DES的密鑰量太?。好荑€量為2561977年：Diffie.Hellman提出制造一個每秒測試106的VLSI芯片，則一天就可以搜索完整個密鑰空間，當(dāng)時造價2千萬美圓。CRYPTO’93：R.Session，M.Wiener提出并行密鑰搜索芯片，每秒測試5x107個密鑰，5760片這種芯片，造價10萬美圓，平均一天即可找到密鑰。12/16/202278信息安全原理與技術(shù)2.3.2關(guān)于DES的討論S盒是唯一非線性組件：有人Internet的超級計算能力：1997年1月28日，美國RSA數(shù)據(jù)安全公司在Internet上開展了一項“秘密密鑰挑戰(zhàn)”的競賽，懸賞一萬美圓，破解一段DES密文。計劃公布后，得到了許多網(wǎng)絡(luò)用戶的強力相應(yīng)。科羅拉州的程序員R.Verser設(shè)計了一個可以通過互聯(lián)網(wǎng)分段運行的密鑰搜索程序，組織了一個稱為DESCHALL的搜索行動，成千上萬的的志愿者加入到計劃中。12/16/202279信息安全原理與技術(shù)Internet的超級計算能力：1997年1月28日，美國R第96天，即競賽公布后的第140天，1997年6月17日晚上10點39分，美國鹽湖城Inetz公司職員M.Sanders成功地找到了密鑰，解密出明文：TheunknownMessageis：“Strongecryptographymakesthewordasaferplace”(高強度密碼技術(shù)使世界更安全)。Internet僅僅利用閑散資源，毫無代價就破譯了DES密碼，這是對密碼方法的挑戰(zhàn)，是Internet超級計算能力的顯示.12/16/202280信息安全原理與技術(shù)第96天，即競賽公布后的第140天，1997年6月17日晚上差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著名的有Biham，Shamir的差分分析法。這是一個選擇明文攻擊方法。雖然對16輪DES沒有攻破，但是，如果迭代的輪數(shù)降低，則它可成功地被攻破。例如，8輪DES在一個個人計算機上只需要2分鐘即可被攻破。12/16/202281信息安全原理與技術(shù)差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著2.3.3DES擴展形式多重DESS盒可選擇的DES具有獨立子密鑰的DESG-DES

12/16/202282信息安全原理與技術(shù)2.3.3DES擴展形式多重DES12/11/202212.4公鑰密碼體制

一個安全的對稱密鑰密碼系統(tǒng)，可以達到下列功能：保護信息機密

認(rèn)證發(fā)送方之身份

確保信息完整性對稱密鑰密碼系統(tǒng)具有下列缺點：

收發(fā)雙方如何獲得其加密密鑰及解密密鑰？

密鑰的數(shù)目太大

無法達到不可否認(rèn)服務(wù)

2.4.1傳統(tǒng)密碼體制的缺陷與公鑰密碼體制的產(chǎn)生

12/16/202283信息安全原理與技術(shù)2.4公鑰密碼體制一個安全的對稱密鑰密碼系統(tǒng)，可以達到下現(xiàn)代密碼學(xué)修正了密鑰的對稱性，1976年，Diffie，Hellmann提出了公開密鑰密碼體制（簡稱公鑰體制），它的加密、解密密鑰是不同的，也是不能（在有效的時間內(nèi)）相互推導(dǎo)。所以，它可稱為雙鑰密碼體制。它的產(chǎn)生，是密碼學(xué)革命性的發(fā)展，它一方面，為數(shù)據(jù)的保密性、完整性、真實性提供了有效方便的技術(shù)。另一方面，科學(xué)地解決了密碼技術(shù)的瓶頸──密鑰的分配問題。12/16/202284信息安全原理與技術(shù)現(xiàn)代密碼學(xué)修正了密鑰的對稱性，1976年，Diffie，He第一個公鑰體制是1977年由Rivest，Shamir，Adleman提出的，稱為RSA公鑰體制，其安全性是基于整數(shù)的因子分解的困難性。RSA公鑰體制已得到了廣泛的應(yīng)用。其后，諸如基于背包問題的Merkle-Hellman背包公鑰體制，基于有限域上離散對數(shù)問題的EIGamal公鑰體制，基于橢圓曲線的密碼體制等等公鑰體制不斷出現(xiàn)，使密碼學(xué)得到了蓬勃的發(fā)展，12/16/202285信息安全原理與技術(shù)第一個公鑰體制是1977年由Rivest，Shamir，Ad2.4.2公鑰密碼體制介紹

公鑰密碼體制加解密過程主要有以下幾步：

12/16/202286信息安全原理與技術(shù)2.4.2公鑰密碼體制介紹公鑰密碼體制加解密過程主要安全的公開密鑰密碼可以達到下列功能：（1）簡化密鑰分配及管理問題

公鑰體制用于數(shù)據(jù)加密時：用戶將自己的公開（加密）密鑰登記在一個公開密鑰庫或?qū)崟r公開，秘密密鑰則被嚴(yán)格保密。信源為了向信宿發(fā)送信息，去公開密鑰庫查找對方的公開密鑰，或臨時向?qū)Ψ剿魅」€，將要發(fā)送的信息用這個公鑰加密后在公開信道上發(fā)送給對方，對方收到信息（密文）后，則用自己的秘密（解密）密鑰解密密文，從而，讀取信息?？梢?，這里省去了從秘密信道傳遞密鑰的過程。這是公鑰體制的一大優(yōu)點。

12/16/202287信息安全原理與技術(shù)安全的公開密鑰密碼可以達到下列功能：12/11/202223（2）保護信息機密

任何人均可將明文加密成密文，此后只有擁有解密密鑰的人才能解密。

12/16/202288信息安全原理與技術(shù)（2）保護信息機密12/11/202224信息安全原理與技（3）實現(xiàn)不可否認(rèn)功能

公鑰體制用于數(shù)字簽名時：信源為了他人能夠驗證自己發(fā)送的消息確實來自本人，他將自己的秘密（解密）密鑰公布，而將公開（加密）密鑰嚴(yán)格保密。與別人通信時，則用自己的加密密鑰對消息加密──稱為簽名，將原消息與簽名后的消息一起發(fā)送.對方收到消息后，為了確定信源的真實性，用對方的解密密鑰解密簽名消息──稱為（簽名）驗證，如果解密后的消息與原消息一致，則說明信源是真實的，可以接受，否則，拒絕接受。

12/16/202289信息安全原理與技術(shù)（3）實現(xiàn)不可否認(rèn)功能12/11/202225信息安全原理2.4.3基本數(shù)學(xué)概念群模逆元費爾馬小定理

Euler函數(shù)

生成元

12/16/202290信息安全原理與技術(shù)2.4.3基本數(shù)學(xué)概念群12/11/202226信息安2.4.4RSA算法1976年：Diffie，Hellman在“NewDirectioninCryptography”(密碼學(xué)新方向)一文中首次提出公開密鑰密碼體制的思想。1977年：Rivest,Shamir,Adleman第一次實現(xiàn)了公開密鑰密碼體制，現(xiàn)稱為RSA公鑰體制。12/16/202291信息安全原理與技術(shù)2.4.4RSA算法1976年：Diffie，Hell基本算法：①生成兩個大素數(shù)p和q（保密）；

②計算這兩個素數(shù)的乘積n=pq（公開）；

③計算小于n并且與n互素的整數(shù)的個數(shù)，即歐拉函數(shù)(n)=(p–1)(q–1)（保密）；

④選取一個隨機整數(shù)e滿足1<e<(n)，并且e和(n)互素，即gcd(e,(n))=1（公開）；

⑤計算d，滿足de=1mod(n)（保密）；12/16/202292信息安全原理與技術(shù)12/11/202228信息安全原理與技術(shù)E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解密過程公開信道12/16/202293信息安全原理與技術(shù)E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解一個利用RSA算法的加密實例

設(shè)p=101，q=113，n=pq=11413，

(n)=(p-1)(q-1)=100×112=11200，a=6597，b=3533，x=9726。

加密：y=xb=97263533=5761mod11413；解密：x=ya=57616597=9726mod11413。12/16/202294信息安全原理與技術(shù)一個利用RSA算法的加密實例設(shè)p=101，q=113，n=算法分析：該體制的數(shù)學(xué)依據(jù)是Euler定理及大數(shù)分解的困難性，體制中使用的是Zn中的計算。設(shè)是兩個不同奇素數(shù)p,q的乘積，對于這樣的正整數(shù)，其Euler函數(shù)值是容易計算的，它是(n)=(p-1)(q-1)。對于給定的明文x<n，選定一個正整數(shù)b，稱為加密密鑰。12/16/202295信息安全原理與技術(shù)算法分析：12/11/202231信息安全原理與技術(shù)作Zn中的指數(shù)運算，將明文以指數(shù)形式xb表示出來，即以指數(shù)形式將明文隱藏起來。即使知道一個明、密文對(x,y)，y=xbmodn,要得到密鑰b，必須求解離散對數(shù)問題：b=logxy，在Zn中這也是一個困難問題?？梢娺@種加密思想是簡單、明確的。

12/16/202296信息安全原理與技術(shù)作Zn中的指數(shù)運算，將明文以指數(shù)形式xb表示出來，即以指數(shù)形RSA安全性分析

加密密鑰b是公開的，從而，要求從b不能有效地推導(dǎo)出a，解已知b，求解ab≡1mod(n)是計算上不可能的。(n)是n的Euler函數(shù)，如果已知(n)，則可以應(yīng)用展轉(zhuǎn)相除法求得b的逆元a，從而(n)的保密是安全的關(guān)鍵，而(n)的有效計算則依賴于n的素因子分解，從而，RSA的安全性與n的素因子分解等價。體制的安全性機理是大數(shù)分解的困難性。

12/16/202297信息安全原理與技術(shù)RSA安全性分析12/11/202233信息安全原理與技術(shù)大數(shù)分解是一個NP問題，目前已知的最好的算法需要進行ex次算術(shù)運算。假設(shè)我們用一臺每秒運算（即：一億）次的計算機來分解一個200位十進制的數(shù)

要分解一個200位十進制的數(shù)，需要3.8×107年，類似地，可算出要分解一個300位的十進制整數(shù)，則需要年4.86×1013?？梢?，增加的位數(shù)，將大大地提高體制的安全性。由以上分析可見，從直接分解大數(shù)來破譯RSA是計算上不可能的，那么是否存在一種破譯方法不依賴于的分解呢？雖然現(xiàn)在還沒有發(fā)現(xiàn)，但是也沒有嚴(yán)格的論證。

12/16/202298信息安全原理與技術(shù)大數(shù)分解是一個NP問題，目前已知的最好的算法需要進行ex次算直接分解一個大素數(shù)的強力攻擊的一個實例是：1994年4月分解的RSA密鑰RSA-129，即分解了一個129位十進制，425比特的大素數(shù)。分解時啟用了1600臺計算機，耗時8個月，處理了4600MIPS年的數(shù)據(jù)。1MIPS年是1MIPS的機器一年所能處理數(shù)據(jù)量。Pentium100大約是125MIPS，它分解RSA-129需要37年。100臺Pentium100需要4個月。

12/16/202299信息安全原理與技術(shù)直接分解一個大素數(shù)的強力攻擊的一個實例是：1994年4月分解硬件實現(xiàn)時，RSA比DES要慢大約1000倍，軟件實現(xiàn)時，RSA比DES要慢大約100倍。可見，用RSA直接加密信息有諸多不便，所以，很多實際系統(tǒng)中，只用RSA來交換DES的密鑰，而用DES來加密主體信息。

12/16/2022100信息安全原理與技術(shù)硬件實現(xiàn)時，RSA比DES要慢大約1000倍，軟件實現(xiàn)時，R2.5散列函數(shù)2.5.1散列函數(shù)的概念

散列函數(shù)又可稱為壓縮函數(shù)、雜湊函數(shù)、消息摘要、指紋、密碼校驗和、信息完整性檢驗(DIC)、操作檢驗碼(MDC)。散列函數(shù)有4個主要特點：①它能處理任意大小的信息②它是不可預(yù)見的。③它是完全不可逆的，即散列函數(shù)是單向的④它是抗碰撞的12/16/2022101信息安全原理與技術(shù)2.5散列函數(shù)2.5.1散列函數(shù)的概念12/11/單向散列函數(shù)的工作原理

常用的消息摘要算法有：（1）MD2算法（2）MD4和MD5算法（3）SHA算法12/16/2022102信息安全原理與技術(shù)單向散列函數(shù)的工作原理12/11/202238信息安全原理2.5.2MD5算法

算法MD5首先填充消息成512比特的整數(shù)倍，但最后64比特是由文件長度填充的；其次，將個512比特分割成16個32比特子塊；取4個初始向量，從其及第一個子塊出發(fā)，作4輪（MD4只有3輪）16次迭代。得128比特輸出；以此作為初始向量，對下一個512比特執(zhí)行同樣的操作；

依次下去，直到所有的512比特都處理完畢，輸出128比特，此即MD5的輸出。12/16/2022103信息安全原理與技術(shù)2.5.2MD5算法12/11/202239信息安全原2.6數(shù)字簽名數(shù)字簽名最早被建議用來對禁止核試驗條律的驗證。禁止核試驗條律的締約國為了檢測對方的核試驗，需要把地震測試儀放在對方的地下，而把測試的數(shù)據(jù)送回，自然這里有一個矛盾：東道主需要檢查發(fā)送的數(shù)據(jù)是否僅為所需測試的數(shù)據(jù)；檢測方需要送回的數(shù)據(jù)是真實的檢測數(shù)據(jù)，東道主沒有篡改。12/16/2022104信息安全原理與技術(shù)2.6數(shù)字簽名數(shù)字簽名最早被建議用來對禁止核試驗條律的基本要求：簽名不能偽造：簽名是簽名者對文件內(nèi)容合法性的認(rèn)同、證明、和標(biāo)記，其他人的簽名無效；簽名不可抵賴：這是對簽名者的約束，簽名者的認(rèn)同、證明、標(biāo)記是不可否認(rèn)的；簽名不可改變：文件簽名后是不可改變的，這保證了簽名的真實性、可靠性；簽名不可重復(fù)使用：簽名需要時間標(biāo)記，這樣可以保證簽名不可重復(fù)使用。簽名容易驗證：對于簽名的文件，一旦發(fā)生糾紛，任何第三方都可以準(zhǔn)確、有效地進行驗證。12/16/2022105信息安全原理與技術(shù)基本要求：12/11/202241信息安全原理與技術(shù)數(shù)字簽名的基本原理：應(yīng)用一對不可互相推導(dǎo)的密鑰，一個用于簽名（加密），一個用于驗證（解密），顛倒使用加解密過程。公鑰簽名原理：這種簽名就是加密過程的簡單顛倒使用，簽名者用加密密鑰（保密）簽名（加密）文件，驗證者用（公開的）解密密鑰解密文件，確定文件的真?zhèn)巍?2/16/2022106信息安全原理與技術(shù)數(shù)字簽名的基本原理：應(yīng)用一對不可互相推導(dǎo)的密鑰，一個用于簽散列函數(shù)：散列函數(shù)是數(shù)字簽名的一個重要輔助工具，應(yīng)用散列函數(shù)可以生成一個文件的，具有固定長度的文件摘要，從而使數(shù)字簽名可以迅速有效地簽名一個任意長度的文件。一般地，對文件的任意小改動，都會改變文件的散列值，從而，秘密的散列函數(shù)可以用來檢測病毒等對文件的破壞。對簽名的攻擊：對數(shù)字簽名有各種各樣的欺騙存在，重復(fù)使用是一個典型欺騙，如電子支票，重復(fù)的使用具有可怕后果，阻止這種欺騙的有效方法是簽名中包含時間日期標(biāo)志。12/16/2022107信息安全原理與技術(shù)散列函數(shù)：散列函數(shù)是數(shù)字簽名的一個重要輔助工具，應(yīng)用散列函常用算法介紹1、Elgamal算法：ElGamal簽名方案基于離散對數(shù)問題離散對數(shù)問題：設(shè)p是一個素數(shù)，bZ*p，尋找整數(shù)d，0<d<p，滿足：ad≡bmodp。這樣的問題稱為離散對數(shù)問題。選取p至少150位十進制數(shù)，p-1至少有一個“大”素因子，則離散對數(shù)問題稱為困難問題，困難問題不存在多項式時間算法12/16/2022108信息安全原理與技術(shù)常用算法介紹12/11/202244信息安全原理與技術(shù)ElGamal簽名方案于1985年提出，改進后，被美國國家標(biāo)準(zhǔn)和技術(shù)研究所（NIST）采納為數(shù)字簽名標(biāo)準(zhǔn)。ElGamal簽名方案是一個非確定性的方案，也就是說，驗證算法可以接受的合法簽名不止一個。

12/16/2022109信息安全原理與技術(shù)ElGamal簽名方案于1985年提出，改進后，被美國國家標(biāo)ElGamal簽名方案的定義：

設(shè)p是一個素數(shù)，Zp中的離散對數(shù)是困難問題，

aZ*p是一個生成元，b≡admodp，則定義：

簽名算法：Sigk(x,t)=(,)，≡atmodp，

≡(x-a)t-1modp-1，t是一保密的隨機數(shù)。

驗證算法：對給定的消息及簽名(x,(,))，x,Z*p,

Zp-1，驗證算法為12/16/2022110信息安全原理與技術(shù)ElGamal簽名方案的定義：

設(shè)p是一個素數(shù)，Zp中的2、DSA算法：DSA是Schnorr和ElGamal簽名算法的變種，被美國NIST作為DSS。

數(shù)字簽名標(biāo)準(zhǔn)DSS：

設(shè)p是一個512比特的素數(shù)，Zp中的離散對數(shù)是困難

問題，q是一個60比特的素數(shù)，q|p-1，aZ*p是p模

q的單位根。則定義：

簽名算法：Sigk(x,t)=(,)，≡(atmodp)modq，

≡(x+a)t-1modq；

驗證算法：

Ver(x,(,))=true(albmmodp)modq≡，

其中：l≡x-1modq，m≡-1modq。12/16/2022111信息安全原理與技術(shù)2、DSA算法：DSA是Schnorr和ElGamal簽名算DSS與ElGamal簽名方案的差別：

ElGamal簽名方案中模p至少有512比特，但這樣會產(chǎn)生1024比特的簽名。這樣的膨脹率對于象靈巧卡之類的應(yīng)用是一個難題。而