第4講密碼學概論課程主要內(nèi)容密碼體制基本形式移位密碼替換密碼仿射密碼一次一密方案密碼分析2§1密碼體制基本形式Alice加密機解密機Bob安全信道密鑰源Oscarxyxk1密鑰源k2不安全信道密碼分析加密通信的模型密碼學的目的：Alice和Bob兩個人在不安全的信道上進行通信，而破譯者Oscar不能理解他們通信的內(nèi)容。3密碼系統(tǒng)的定義：密碼體制是這樣的一個5元組

{M，C，K，E，D}，且滿足如下的條件：1.M是所有可能明文(消息)的集合；（明文空間）2.C是所有可能的密文的集合；（密文空間）3.K是一個可能密鑰的有限集；（密鑰空間）4.滿足以下定義：§1密碼體制基本形式4密碼系統(tǒng)的定義：加密：解密：并且有：注意：所有算法的安全性基于密鑰的安全性，而不是基于算法細節(jié)的安全性，即算法可以公開！§1密碼體制基本形式5§1密碼體制基本形式1）Alice要將明文Ｘ在不安全信道上發(fā)給Bob，設(shè)X=x1x2…

xn，其中xi∈P,Alice用加密算法ek作yi=ek(xi)(1≤i≤n)，結(jié)果的密文是Y=y1y2…yn

在信道上發(fā)送，Bob收到后解密：xi=dk(yi)得到明文X=x1x2…

xn。2）加密函數(shù)ek必須是單射函數(shù)，就是一對一的函數(shù)。3）若P=C，則ek為一個置換。4）好的密鑰算法是唯密鑰而保密的。5）若Alice和Bob在一次通信中使用相同的密鑰，則這個加密體制為對稱的，否則稱為非對稱的。61、用于轉(zhuǎn)換純文本到密碼的類型

替代（substitution）移位（transposition）2、密鑰的種類對稱，單密鑰，秘密密鑰不對稱，雙密鑰,公開密鑰加密

3、以處理純文本文件的方法分組密碼（blockcipher）流密碼（streamcipher）密碼系統(tǒng)(CryptographySystem)的分類§1密碼體制基本形式7單鑰體制(對稱密碼)K1＝K2－－－根據(jù)密鑰的種類分類：明文abc加密器密文#@&解密器明文abc相同

雙鑰體制(非對稱密碼)K1≠K2明文abc加密器密文#@&解密器明文abc不同

8

密碼編碼學是密碼體制的設(shè)計學，而密碼分析學則是在未知密鑰的情況下從密文推演出明文或密鑰的技術(shù)。密碼編碼學與密碼分析學合起來即為密碼學密碼學及相關(guān)概念

如果不論截取者獲得了多少密文，但在密文中都沒有足夠的信息來惟一地確定出對應的明文，則這一密碼體制稱為無條件安全的，或稱為理論上是不可破的。但是在無任何限制的條件下，目前幾乎所有實用的密碼體制均是可破的。因此，人們關(guān)心的是要研制出在計算上(而不是在理論上)是不可破的密碼體制。如果一個密碼體制中的密碼不能被可以使用的計算資源破譯，則這一密碼體制稱為在計算上是安全的。9密碼體制的特征:對密文破譯攻擊極為困難；在有效地防破譯的前提下，密鑰長度應很小；加密、解密的操作流程簡便易行；錯碼率及錯碼的擴散程度低；加密后原信息的長度不受影響。§1密碼體制基本形式10數(shù)據(jù)加密標準DES（DataEncryptionStandard）公開密鑰密碼體制（publickeycrypto-system）成為近代密碼學發(fā)展史上的兩個重要里程碑。近代密碼學發(fā)展§1密碼體制基本形式一個密碼系統(tǒng)采用的基本工作方式稱為密碼體制。密碼體制從原理上可分為兩大類：

對稱密鑰密碼體制（單鑰、常規(guī)）非對稱密鑰密碼體制（雙鑰、公開）11在發(fā)端，明文X用加密算法E和加密密鑰K得到密文

C

EK(P)在傳送過程中可能出現(xiàn)密文截取者。截取者又稱為攻擊者或入侵者。P’或K’在收端，利用解密算法D和解密密鑰K，解出明文為

DK(C)

DK(EK(P))

P對稱（常規(guī)）密碼體制12

k

k明文

密文

解密后的明文

加密Ｅ解密Ｄ密鑰產(chǎn)生器加密和解密表示為：ＥＫ(Ｍ)＝ＣＤＫ(Ｃ)＝Ｍ解密算法是加密算法的逆運算；加密密鑰和解密密鑰相同；加密算法強度高；密鑰傳遞需專用通道；對稱密鑰密碼體制13

由對稱算法可分為兩類：

序列算法（streamalgorithm）或序列密碼(streamcipher)：明文中的單個位（有時對字節(jié)）運算的算法。

分組算法（blockalgorithm）或分組密碼（blockcipher）：把明文信息分割成塊結(jié)構(gòu)，逐塊予以加密和解密；塊的長度由算法設(shè)計者預先確定。對稱密鑰密碼體制14基本思想加密密鑰（即公開密鑰）PK公開解密密鑰（即私有密鑰）SK保密加密算法E和解密算法D也都是公開私有密鑰SK由公開密鑰PK決定，但卻不能根據(jù)PK計算出SK每個用戶產(chǎn)生一對密鑰PK和SK公開密鑰密碼體制15收方破譯者發(fā)方解密算法P’K’公開密鑰體制模型加密算法密鑰通道密鑰源公開密鑰密碼體制16公

開

密

鑰

算

法

描

述EPK（DSK（X））＝X，不能用PK解密在計算機上可以容易地產(chǎn)生成對的PK和SK從已知的PK不可能推導出SK，即從PK到SK是“計算上不可能的”。加密和解密算法都是公開的。DSK（EPK（X））＝XEPK（DSK（X））＝X公開密鑰密碼體制17

單鑰密碼體制中，收發(fā)雙方使用同一密鑰，系統(tǒng)的保密性主要取決于密鑰的安全性。系統(tǒng)的密鑰管理、傳輸和分配是一個重要且十分復雜的問題。體制的優(yōu)點是：保密強度高，運算速度快；缺點是密鑰數(shù)目大，密鑰分配困難，無法實現(xiàn)不可否認服務。

公鑰密碼體制中，加密密鑰KU是公開的，解密密鑰KP必須保密。公鑰體制的密鑰產(chǎn)生、分配和管理相對簡單，尤適用于計算機網(wǎng)絡(luò)系統(tǒng)中。公鑰體制的特點：實現(xiàn)信息公開加密，實現(xiàn)不可否認服務，但缺點是加解密運算復雜其速度較慢。兩種密碼體制的對比18密碼學應用用加密來保護信息采用數(shù)字證書來進行身份鑒別數(shù)字指紋采用密碼技術(shù)對發(fā)送信息進行驗證利用數(shù)字簽名來完成最終協(xié)議信息加密信息認證數(shù)字簽名密鑰管理19----密碼學數(shù)據(jù)加密我需要轉(zhuǎn)帳，這是我的帳號和密碼。業(yè)務服務器田景成38ighwejb.。成景田這是什么？！我們用相關(guān)的密碼協(xié)議建立一個安全的加密信道，這個加密信道的密鑰只有你我知道。20----密碼學數(shù)據(jù)加密加密解密明文明文密文KK加密解密KKK的密文B公鑰B私鑰21----密碼學身份認證我是田景成，你是網(wǎng)上銀行服務器嗎？嗨，我是網(wǎng)上銀行服務器。你真的是田景成嗎？你真的是網(wǎng)上銀行服務器嗎？業(yè)務服務器田景成使用對方公鑰驗證對方簽名確定對方身份。22----基于非對稱密鑰的挑戰(zhàn)應答方式田景成認證服務器1、獲得公鑰（數(shù)字證書）；5、DP(ED(r))=r’2、請求登錄3、隨機數(shù)r4、ED(r)＋證書P6、比較r和r’擁有正確私鑰，則認為其聲明身份與證書中的身份一致。23----密碼學數(shù)據(jù)完整性轉(zhuǎn)帳200萬到關(guān)曉陽的帳號。業(yè)務服務器田景成成景田轉(zhuǎn)帳100萬到關(guān)曉陽的帳號，轉(zhuǎn)帳100萬到成景田的帳號。篡改田景成，你傳送的數(shù)據(jù)在傳送過程中被修改過，請重新發(fā)送你的要求。有了簽名，改了可能會被人發(fā)現(xiàn)。24----密碼學數(shù)據(jù)完整性明文摘要數(shù)字摘要算法散列算法明文摘要◎相等？明文摘要A公鑰加密摘要的密文A私鑰明文解密25----密碼學不可否認性和審計我的錢呢？田景成什么也沒撈到！成景田銀行職員轉(zhuǎn)走了！轉(zhuǎn)哪去了？豈有此理，我要告你們！你們沒有我的簽名。您自己忘了！我們查看了系統(tǒng)審計庫，你的200萬轉(zhuǎn)到了關(guān)曉陽帳號。這是所有交易的數(shù)字簽名。261、機密性:提供只允許特定用戶訪問和閱讀信息，任何非授權(quán)用戶對信息都不可理解的服務[通過數(shù)據(jù)加密實現(xiàn)]密碼學的作用總結(jié)4、抗否認性:提供阻止用戶否認先前的言論或行為的服務。[通過對稱加密或非對稱加密，以及數(shù)字簽名等，并借助可信的注冊機構(gòu)或證書機構(gòu)的輔助，提供這種服務]3、數(shù)據(jù)完整性:提供確保數(shù)據(jù)在存儲和傳輸過程中不被未授權(quán)修改（竄改、刪除、插入和重放等）的服務。[通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實現(xiàn)]2、鑒別:提供與數(shù)據(jù)和身份識別有關(guān)的服務。[通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實現(xiàn)]27

移位密碼是采用移位法進行加密的。它把明文中的字母重新排列，本身不變，但位置變了，移位密碼是靠重新安排字母的次序，而不是隱藏他們。

常見的移位密碼主要有：倒置法列換位法矩陣換位法?！?移位密碼28（1）完全倒置法把明文中的字母按順序倒過來寫，然后以固定長度的字母組發(fā)送或記錄。 明文：computersystems 密文：smetsysretupmoc（2）分組倒置法把明文中的字母按固定長度分組后每組字母串倒過來寫。 明文：computersystems

分組：computersystems 密文：pmocretutsyssme§2移位密碼---倒置法29（1）列換位法將明文字符分割成為若干個（例如5個）一行的分組，并按一組后面跟著另一組的形式排好，形式如下： c1c2c3c4c5 c6c7c8c9c10……最后，不全的組可以用不常使用的字符或a,b,c…填滿。密文是取各列來產(chǎn)生的：

c1c6…c2c7…c3c8….c4c9….c5c10….§2移位密碼---換位法30例：明文：WHATYOUCANLEARNFROMTHISBOOK進行排列：

WHAT

Y

OUCAN

FRO

MT

H

I

SBO

OKXX

X則密文為：WOFHOHURIKACOSXTAMBXYNTOX

這里的密鑰是數(shù)字5?！?移位密碼---換位法31（2）矩陣換位法把明文中的字母按給定的順序安排在一矩陣中，然后用另一種順序選出矩陣的字母來產(chǎn)生密文。例：明文ENGINEERING按行排在3×4矩陣中，最后一行不全用ABC…填充，如下所示。給定置換1234ENGINEERINGA§2移位密碼---換位法32現(xiàn)在根據(jù)給定的置換，按第2列、第4列、第1列、第3列的次序排列，就得到密文：NIEGERNENAIG在這個加密方案中，密鑰就是矩陣的行數(shù)m和列數(shù)n，即m*n＝3*4，以及給定的置換矩陣:

也就是：k=（m*n，f）1234NIEGERNENAIG§2移位密碼---換位法33其解密過程是將密文根據(jù)3*4矩陣，按行、列的順序?qū)懗觯俑鶕?jù)給定置換產(chǎn)生新的矩陣，恢復明文為：ENGINEERING1234ENGINEERINGA1234NIEGERNENAIG§2移位密碼---換位法34

替換密碼是使用替換法進行加密所產(chǎn)生的密碼。替換密碼就是明文中每一個字符被替換成密文中的另外一個字符，代替后的各字母保持原來位置。接收者對密文進行逆替換就恢復出明文來。在替換法加密體制中，使用了密鑰字母表。它可以由明文字母表構(gòu)成，也可以由多個字母表構(gòu)成。在傳統(tǒng)密碼學中，有四種類型的代替密碼：（1）單表（簡單）替換密碼

就是明文的一個字符用相應的一個密文字符替換。加密過程中是從明文字母表到密文字母表的一一映射。

例：愷撒（Caesar)密碼。§3替換密碼35（2）同音（多名碼）替換密碼與簡單替換密碼系統(tǒng)相似，唯一的不同是單個字符明文可以映射成密文的幾個字符之一，同音替換的密文并不唯一。（3）多字母組替換密碼字符塊被成組加密，例如“ABA”可能對應“RTQ”，ABB可能對應“SLL”等。例：Playfair密碼。（4）多表替換密碼

由多個單字母密碼構(gòu)成，每個密鑰加密對應位置的明文。

例：維吉尼亞密碼?！?替換密碼361、愷撒（Caesar)密碼又叫循環(huán)移位密碼。它的加密方法就是把明文中所有字母都用它右邊的第k個字母替代，并認為Z后邊又是A。這種映射關(guān)系表示為如下函數(shù)：

F(a)=(a+k)mod26

其中：a表示明文字母；k為密鑰。§3.1單表替換密碼37設(shè)k＝3；則有明文：abcdefghijklmnopqrstuvwxyz密文：defghijklmnopqrstuvwxyzabc

對于明文P＝computer

systems

有密文C＝frpsxwhuv

bvwhpv顯然，由密文C恢復明文非常容易，只要知道密鑰K，就可構(gòu)造一張映射表。其加密和解密均可根據(jù)此映射表進行。凱撤密碼的優(yōu)點是密鑰簡單易記。但它的密碼文與明碼文的對應關(guān)系過于簡單，密鑰空間為26，故安全性很差?！?.1單表替換密碼382、密鑰短語密碼選擇一組有助于記憶的英文字符串作為密鑰，從中篩選無重復的字符按原順序記下字符串，寫在明文字母表下，然后將未出現(xiàn)在字符串的字母按順序依次寫在密鑰短語后。如選擇密鑰短語networksecurity，則有：明文：abcdefghijklmnopqrstuvwxyz密文：networkscuiyabdfghjlmpqvxz若明文為dataaccess則密文為wnln

nttojj§3.1單表替換密碼39

多表替換密碼是一種用多組替換表依次對明文消息的字母進行替換的加密方法。

維吉尼亞（Vigenere）密碼是一種常用的多表替換密碼。這種替代法是循環(huán)地使用有限個字母來實現(xiàn)替代的一種方法。這種加密的加密表是以字母表移位為基礎(chǔ)把26個英文字母進行循環(huán)移位，排列在一起，形成26×26的方陣。該方陣被稱為維吉尼亞表。采用的算法為 F(a)=(a+Bi)mod26（其中i=(1，2，…，26)）

優(yōu)點：能抵抗簡單的字母頻率分析攻擊。§3.2多表替換密碼40§3.2多表替換密碼---Vigenere密碼表41加密過程：以明文字母選擇列，以密鑰字母選擇行，兩者的交點就是加密生成的密文。解密過程：以密鑰字母選擇行，從中找到密文字母，密文字母所在列的列名即為明文字母。例：以your為密鑰，加密明文howareyou 明文P=howareyou 密鑰K=youryoury 密文C=fcqrpssfs§3.2多表替換密碼---Vigenere密碼42

多字母替換密碼每次加密一組（兩個以上）字母串。Playfair密碼為此類密碼，其密鑰是由25個英文字母（j與i相同）組成的5階方陣。密鑰方陣P導出取決于給定密鑰，重復不寫，余下按字母順序填充。明文劃分如下：將明文字母串按兩個字母一組進行分組，每組中的兩個字母不同。每一對明文字母m1和m2，對應的密文為c1和c2。每一對明文字母m1和m2，按下面的規(guī)則進行加密:§3.3多字母替換密碼43（1）若m1和m2在P的同一行，則密文c1和c2分別是m1和m2右邊的字母。第一列看作最后一列的右邊。（2）若m1和m2在P的同一列，則密文c1和c2分別是m1和m2下邊的字母。第一行看作最后一行的下邊。（3）若m1和m2在P的不同行、不同列，則密文c1和c2是m1和m2確定的長方形的另兩個頂點的字母。其中c1與m1同行，c2與m2同行。（4）若m1＝m2，則在m1和m2之間加一個無效字母(如x)。（5）若明文字母為奇數(shù)個，則在末尾加一個無效字母?！?.3多字母替換密碼44例：以firewallsecurity為密鑰，加密明文howareyou。由密鑰導出密鑰矩陣為明文分組處理howareyoux則密文khfuewgkcz§3.3多字母替換密碼45仿射密碼亦稱為線性替換密碼，是由移位替換密碼（加法密碼）和乘法密碼組合而成。(1)加法密碼：加密c＝Ek(m)=m+k(modq)解密m=Dk(c)=c-k(modq)(2)乘法密碼：加密c＝Ek(m)=km(modq)解密m=Dk(c)=k-1c(modq)其中密鑰k必須與q互素。§4仿射密碼46例：密鑰k=7，則乘法密碼的明文字母到密文字母的替換表若明文howareyou則密文xuyapcmuk(3)仿射密碼

加密c＝Ek(m)=k1+k2m(modq)

解密m=Dk(c)=k2-1(c-k1)(modq)§4仿射密碼47例：密鑰k=(3,7)，則加密函數(shù)Ek(m)=3+7m(mod26)，相應的解密函數(shù)是Dk(c)=7-1(c-3)(mod26)=15(c-3)(mod26)=15c-19(mod26)

若加密明文為hot，則：§4仿射密碼解密：加密：48(4)置換密碼加密c＝Ek(m)=π(m)解密m=Dk(c)=π-1(c)置換π的表示：π＝密鑰空間很大，|π|=26!≈4×1026

移位密碼體制是置換密碼體制的一個特例，它僅含26個置換做為密鑰空間。(0123..2324250'1'2'3'..23'24'25')§4仿射密碼49例：設(shè)m=6，取密鑰而若明文為cryptography首先分成6個字母長的明文組：crypto|graphyπ(crypto)＝(ytcopr)π(graphy)＝(ahgypr)求得的密文是：ytcoprahgypr§4仿射密碼50一次一密方案是一種理想的加密方案，由AT&T公司的GilbertVernam在1917年提出。它使用的密鑰是一個大的不重復的真隨機密鑰字母集，這個密鑰字母集被寫在幾張紙上，并被粘成一個密碼本。它最初的形式是用于電傳打字機。

1）發(fā)送者用密碼本中的每一密鑰字母準確地加密一個明文字符。加密是明文字符和一次密碼本密鑰字符的模26加法。每個密鑰僅對一個消息使用一次。發(fā)送者對所發(fā)送的消息加密，然后銷毀密碼本中用過的一頁或