【正文】 的公鑰體制中， RSA倍受推崇，已被 ISO/TC97的數(shù)據(jù)加密技術(shù)分委員會 SC20推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。 ?此外 ， 還有蒙特卡羅算法 、 連分式算法 、試除法等因子分解算法 。 該算法最快的版本叫多重多項式二次篩選的雙重大素數(shù)算法 。 當(dāng)它最初被提出時 ， 還不算實用 ， 但隨著后來的一系列改進(jìn) ， 成為新的一種因子分解實用算法 。分解一個數(shù)很簡單 ， 但其過程很費時 。 96 (6) 因子分解 ?對于一個數(shù)進(jìn)行因子分解 ， 就是找出其各個素數(shù)因子 ， 如： 15=3?5， 80=2? 2?2?2?5， 252601=41?61?101等 。 ? 如果 gcd(a,n)≠1，也并非一切都無用。 7是素數(shù)， ? (7)=71=6。因此，可以利用 b=aф(n)1 (mod n)來計算 a模 n。 ? 如果 n是一個素數(shù)，且 a不是 n的倍數(shù)，則有： ? an1≡1 (mod n)。 ? 歐拉函數(shù)（記為 ф(n)），表示模 n的余數(shù)化簡集中元素的數(shù)目，即 ф(n)表示與 n互素的小于 n的正整數(shù)的數(shù)目 (n1)。例如：模 12的余數(shù)化簡集是 {1， 5， 7， 11}，如果 n是素數(shù)，那么模 n的余數(shù)化簡集是從 1到 n1的所有整數(shù)集合。在公開密鑰密碼體制的 RSA算法中，就是用歐幾里德算法求逆元的。 ? 一般，如果 a和 n是互素的，那么 a1≡b (mod n)有惟一解，即存在惟一的逆元；如果 a和 n不是互素的，那么 a1≡b (mod n)沒有解，即沒有逆元；如果 n是一個素數(shù)，則從 1到 n1的每一個數(shù)與 n都是互素的，且在這個范圍內(nèi)各有一個逆元。 ? 解決逆元的問題很復(fù)雜，有時有結(jié)果，有時沒有結(jié)果。 ? 在模運算領(lǐng)域，該問題更復(fù)雜。 gcd(a,n)=1 a和 n互素 ? 15與 28互素 ， 13與 500互素 ， 而 15與 27不是互素 ?一個素數(shù)與它的倍數(shù)以外的任何其它數(shù)都是互素的 94 (4) 求模逆元 ? 什么是逆元呢？對于算術(shù)加法來說， 5和 5互為逆元，因為 5+(5)=0；對于乘法來說， 4的逆元是 1/4，因為 4?1/4=1。如以下各數(shù)為素數(shù)： 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47，53,59,61,67,71,73,79,83,89,97,101,103,107,109,113, …,2521,2365347734339,27568391等都是素數(shù)。 88 公鑰體制加 /解密模型 加密(E) 解密(D) 發(fā)送 M 接收 M Ke Kd 密文 C=E(M,Ke) 89 2. 公鑰體制的特點 ?用 Ke對明文加密后，再用 Kd解密，即可恢復(fù)出明文，即 M=D Kd{E Ke(M)} ? 加密和解密運算可以對調(diào)，即 M=D Kd{E Ke(M)} = E Ke {D Kd (M)} 90 ? 但加密密鑰不能用來解密，即 M≠D Ke{E Kd(M)} ? 在計算上很容易產(chǎn)生密鑰對 Ke和 Kd ? 已知 Ke是不能推導(dǎo)出 Kd的，或者說從Ke得到 Kd是“計算上不可能的”。 87 ?在公開密鑰密碼體制中 ， 加密密鑰是公開的 ， 解密密鑰是保密的 ， 加 /解密算法都是公開的 。因此，相應(yīng)的密碼體制叫公開密鑰密碼體制。 85 5． 4 公開密鑰密碼體制 公鑰體制概述 1．公鑰體制的概念 ? 加密密鑰與解密密鑰不同，且由其中一 個不容易得到另一個，則這種密碼系統(tǒng)是非對稱密鑰系統(tǒng)。 ? IDEA中使用的運算有： ? 異或 ? 模 216加法 ? 模 216+1乘法 ? 這三種運算彼此混合可產(chǎn)生很好的效果。 ? IDEA的密鑰比 DES的多一倍，增加了破譯難度，被認(rèn)為是多年后都有效的算法。 82 K1 E M K2 D K3 E K3 D C K2 E K1 D M C 三重 DES的加密解密過程 83 (2) 國際數(shù)據(jù)加密算法 (IDEA) ? IDEA是分組密碼算法，分組長度為 64位，但密鑰長度 128位。一般三重 DES算法使用兩個 DES密鑰。 78 (8) DES加密過程的數(shù)學(xué)模型 ? L0R0=IP(M64) (M64為 64位輸入明文 ) ? Ki=ks(i,key) i=1,2,…,16 (ks表示密鑰運算函數(shù) ,產(chǎn)生 48位的子密鑰 ) ? Li=Ri1/Ri=Li1?f (Ri1,Ki) ? (Ri1,Ki)中涉及到 E變換、 S盒代替、 P盒變換和異或運算等步驟 ? C64=IP1(L16,R16) 79 (9) DES解密過程的數(shù)學(xué)模型 ? L16R16=IP(C64) ? Ki=ks(i,key) i=16,15,…,1 ? Ri1 = Li ? Li1 = Ri ?? (Ri,Ki) ? M64=IP1(L0,R0) 80 (10) DES的特點及應(yīng)用 ? DES算法具有算法容易實現(xiàn)、速度快、通用性強等優(yōu)點，但也存在密鑰位數(shù)少，保密強度較差和密鑰管理復(fù)雜的缺點。只是解密時逆向取用加密時用的密鑰順序。該組密文與其它各組明文加密得到的密文合在一起，即為原報文的加密結(jié)果。 76 (6) 末置換 ?末置換是 DES算法的最后一步，是一次簡單的數(shù)碼移位，也與密鑰無關(guān)。 S1盒的第 2行第10列的數(shù)是 9，其二進(jìn)制數(shù)為 1001(行和列的計數(shù)均從 0開始而非從 1開始 )。 75 ? 如 6位輸入的第 1和第 6位組合構(gòu)成了 2位二進(jìn)制數(shù)，可表示十進(jìn)制數(shù) 0~3，它對應(yīng)著表中的一行； 6位輸入的第 2到第 5位組合構(gòu)成了 4位二進(jìn)制數(shù)，可表示十進(jìn)制數(shù) 0~15，它對應(yīng)著表中的一列。見表 S盒是一個 4行 16列的表，盒中的每一項都是一個 4位二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)。盡管輸出分組大于輸入分組，但每個輸入分組產(chǎn)生唯一的輸出分組。在擴(kuò)展置換中，對于每個輸入的 4位分組，第 1和第 4位分別表示輸出分組中的 2位，第 2和第 3位分別表示輸出分組中的 1位。該過程通過多次重復(fù)的替代和置換方法，打亂原輸入數(shù)據(jù)組，加大非規(guī)律性，增加系統(tǒng)分析的難度。該過程包括線性變換和非線性變換。 具體步驟如下： 66 ? 第一步： 56位密鑰通過置換選擇 PC1(見 表 )置換，然后分為左右各 28位； ? 第二步：兩個 28位按其輪數(shù)進(jìn)行不同位數(shù)的左移 (見 表 ) ； ? 第三步：將左右兩部分合成 56位后，再經(jīng)過置換選擇 PC2 (見 表 )置換(壓縮置換 )為 48位的子密鑰。 63 (2) DES算法的主要過程 ① 初始置換： ② 子密鑰生成： ③ 乘積變換： ④ 末置換： 初始置換 (IP) 乘積變換 子密鑰生成 輸入 64位明文 (密文 ) 64位密鑰組 末置換 (IP1) 輸出 64位密文 (明文 ) 64 (3) 初始置換 IP ?初始置換 (permutation)按照固定的矩陣進(jìn)行 (移位 )，此部分與密鑰無關(guān)，如下表。 ? DES最先用于軍事系統(tǒng)，后又推廣到民用，應(yīng)用最多的是在銀行和商業(yè)系統(tǒng)。 64位密鑰中有 8位作為校驗位 (第 1 2 3 4 56和 64位 )，因此真正成為密鑰的只有 56位。 ? 傳統(tǒng)密鑰密碼算法有： DES、 IDEA、TDEA(3DES)、 MD RC5等，典型的算法是 DES算法。 59 5 . 3 對稱密鑰密碼體制 1. 對稱密鑰密碼的概念 ? 也叫傳統(tǒng)密鑰密碼體制，其基本思想就是“加密密鑰和解密密鑰相同或相近”，由其中一個可推導(dǎo)出另一個。 美國與前蘇聯(lián)之間的熱線電話據(jù)說就是用一次一密密鑰本加密的 ， 許多前蘇聯(lián)間諜傳遞的信息也是用 一次 一密鑰密碼加密的 。 如果采用真隨機序列發(fā)生器產(chǎn)生密鑰 ， 這種方案就是安全的 。對這種方案的攻擊實際上是依賴于產(chǎn)生密鑰序列的方法 。 接收者在解密信息后也銷毀密鑰本中用過的一頁密鑰 。 55 ?發(fā)送者使用密鑰本中每個密鑰字母串去加密一條明文字母串 ， 加密過程就是將明文字母串和密鑰本中的密鑰字母串進(jìn)行模 26加法運算 。 用二進(jìn)制數(shù)據(jù)組成一次密碼本 ，用異或代替加法 ， 對二進(jìn)制密碼和明文進(jìn)行操作；解密時用同樣的密碼和密文進(jìn)行異或 ， 得到明文 。 類似日歷的使用過程 ， 每使用一個密碼加密一條信息后 ， 就將該頁撕掉作廢 ， 下次加密時再使用下一頁的密碼 。 53 3 . 一次 一密鑰密碼 ?一次 一密鑰密碼 是一種理想的加密方案 。 52 ?按照該密鑰加密可得到一個不可理解的新句子（密文） “ 密密位碼移加對字只明時文新字重排母序置但位變母化沒藏們被它隱 ” 。如用“ china”為密鑰，對“ this is a bookmark”排列成矩陣如下： t h i s i s a b o o k m a r k 按“ china”各字母排序“ 23451”順序，輸出得到密文 ioktskhamibasor 51 ?再如：對于句子 “ 移位密碼加密時只對明文字母重新排序字母位置變化但它們沒被隱藏 ” ，可選擇密鑰 “ 362415”，并循環(huán)使用該密鑰對上句進(jìn)行移位加密。 ?把明文按行寫出，讀出時按列進(jìn)行，得到的即為密文。 48 2 . 移位密碼 ?移位密碼變換：只對明文字母重新排序，位置變化了，而不隱藏它們。 Vigenere密碼就是把 26個字母循環(huán)移位，排列在一起，形成 26 26的方陣表。 47 (3) 多表替代密碼 ?一種常用的多表替代密碼叫 Vigenere密碼。 45 A B C D … … … … … … … … … … W X Y Z E F G H … … … … … … … … … … A B C D (a) A B C D … … … … … … … … … … W X Y Z Z Y X W … … … … … … … … … … B C B A (b) A B C D … … … … … … … … … … W X Y Z C F I L … … … … … … … … … … Q T W Z (c) 圖 替代加密 (a) 移位映射 (b) 倒映射 (c) 步長映射 (步長為 3) 46 (2)多字母替代密碼 ?多字母替代密碼的加密和解密都是將字母以塊為單位進(jìn)行的，比如， ABA對應(yīng)于 OST， ABB對應(yīng)于 STL，等等。如果明文是“ about”，則變?yōu)槊芪摹?efsyx”，其密鑰k=+4。其加密方法就是將明文中的每個字母都用其右邊固定步長的字母代替，構(gòu)成密文。規(guī)律是根據(jù)密鑰形成一個新的字母表，與原明文字母表有相應(yīng)的對應(yīng)關(guān)系。 ?在經(jīng)典密碼學(xué)中 ， 有簡單替代 、 多名碼替代 、 多字母替代和多表替代加密法 。 41 5． 2 傳統(tǒng)密碼技術(shù) 1. 替代密碼 2. 移位密碼 42 1 . 替代密碼 ?替代也叫置換 。 ?相應(yīng)地，這兩種密碼體制各有一些典型算法。 如果加密密鑰和解密密鑰相同或相近 ， 由其中一個很容易地得出另一個 ， 這樣的系統(tǒng)稱為 對稱密鑰系統(tǒng) ， 加密和解密密鑰都是保密的；如果加密密鑰與解密密鑰不同 ， 且由其中一個不容易得到另一個 ， 則這種密碼系統(tǒng)是 非對稱密鑰系統(tǒng) ， 往往其中一個密鑰是公開的 ， 另一個是保密的 。 ? 序列密碼的安全性主要依賴于隨機密鑰序列。 37 ? 序列密碼加 /解密的密鑰，是采用一個比特流發(fā)生器隨機產(chǎn)生二進(jìn)制比特流而得到的。 35 加密 /解密 輸出塊 輸入塊 加 /解密鑰塊 發(fā) /收信端 分組密碼 36 ?序列密碼 ? 序列密碼加密過程是：把報文、語音、圖像等原始信息轉(zhuǎn)換為明文數(shù)據(jù)序列，再將其與密鑰序列進(jìn)行“異或”運算，生成密文序列發(fā)送給接收者。 34 ? 打亂：就是改變數(shù)據(jù)塊，使輸出位與輸入位之間沒有明顯的統(tǒng)計關(guān)系 (替代 )； ? 擴(kuò)散：就是通過密鑰位轉(zhuǎn)移到密文的其它位上 (移位 )。 3．分組密碼和序列密碼 33 ? 分組密碼的加 /解密運算是