【正文】 ii112x 0 1 1 , 2 , .. ., ,a, , .. ., bniininxba a a????求 ＝ 或 ， 使 其 滿 足 ：其 中 和 都 是 整 數(shù)96 背包問題求解 N P N P背 包 問 題 屬 于 完 備 類 （ 問 題 中 難 度 最 大 的 一 類 ）對(duì) 這 一 問 題 沒 有 有 效 算 法11( 2 , 3 , . . . , )ijja i n?????1 2 ni但 是 ， 如 果 序 列 a , a , . . . , a 是 超 遞 增 序 列 ：a背 包 問 題 有 多 項(xiàng) 式 解 法97 超遞增序列背包問題求解方法 1 2 3 4 5 62 4 8 16 32 43x x x x x x? ? ? ? ? ?n1 2 n例 :已 知 序 列 a ,a ,...,a 是 超 遞 增 序 列 ： 1,2,4,8,...,2求 背 包 問 題 的 解思路： xi取值只可能為 0或者 1；如果為 0，表示不能裝入對(duì)應(yīng)的物體，否則可以裝入。 93 公鑰密碼基于的數(shù)學(xué)難題 ? 背包問題 ? 大 整 數(shù) 分 解 問 題 （ The Integer Factorization Problem,RSA體制 ） ? 有限域的乘法群上的離散對(duì)數(shù)問題 (The Discrete Logarithm Problem, ElGamal體制 ） ? 橢圓曲線上的離散對(duì)數(shù)問題 （ The Elliptic Curve Discrete Logarithm Problem, 類比的 ElGamal體制 ） 94 一、背包問題 ? 背包問題： ? 已知一長度為 B的背包，及長度分別為a1,a2,...,an的 n個(gè)物品。kkkkkkk k k kk)kkA l i c e B ob c E D mB ob DDD E D mm?用 戶 擁 有 密 鑰 對(duì) （ k,公 鑰 公 開 ， 私 鑰 保 密： ＝ （ （ ） ）： （ E (c) ） ＝ （ E (c) ） ＝ （ E( （ （ ） ） ) ） ＝89 公鑰密鑰的應(yīng)用范圍 ?加密 /解密 ?數(shù)字簽名 (身份鑒別 ) ?密鑰交換 算法 加 /解密 數(shù)字簽名 密鑰交換 RSA 是 是 是 DieffieHellman 否 否 是 DSS 否 是 否 90 3. 公鑰密碼算法 91 基本思想和要求 ? 涉及到各方：發(fā)送方、接收方、攻擊者 ? 涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文 ? 公鑰算法的條件： ? 產(chǎn)生一對(duì)密鑰是計(jì)算可行的 ? 已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的 ? 接收方利用私鑰來解密密文是計(jì)算可行的 ? 對(duì)于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的 ? 已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的 ? (可選 )加密和解密的順序可交換 92 陷門單向函數(shù) 單向陷門函數(shù)是滿足下列條件的函數(shù) f： (1)給定 x，計(jì)算 y=fk(x)是容易的； (2)給定 y, 計(jì)算 x使 x=fk1(y)是不可行的。A B B A39。BAABAB39。39。A39。39。39。如 : n=100 時(shí)， C(100,2)=4,995 n=5000時(shí)， C(5000,2)=12,497,500 （ 2）數(shù)字簽名的問題 傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求。 ? 公開密鑰算法主要用于加密 /解密 、 數(shù)字簽名 、 密鑰交換 。 ? 線性密碼分析 比差分密碼分析更有效 73 公鑰密碼 ? 公開密鑰算法中用作加密的密鑰不同于用作解密的密鑰 ， 而且解密密鑰不能根據(jù)加密密鑰計(jì)算出來（ 至少在合理假定的長時(shí)間內(nèi) ） ， 所以加密密鑰能夠公開 ， 每個(gè)人都能用加密密鑰加密信息 ， 但只有解密密鑰的擁有者才能解密信息 。 71 針對(duì) DES的攻擊方法 攻擊 DES的方法主要有： ? 密鑰窮搜索攻擊， DES算法總的密鑰量為 ， 1998年使用高級(jí)計(jì)算機(jī)的情況下，破譯 DES只需 56小時(shí)； ? 差分攻擊； ? 線性攻擊，較有效的方法； ? 相關(guān)密鑰攻擊等。 ? DES至少有 12個(gè)半弱密鑰。 ? DES至少有 4個(gè)弱密鑰 ： ? 0101010101010101 ? 1f1f1f1f0e0e0e0e ? e0e0e0e0f1f1f1f1 ? fefefefefefefefe )()( 1 ??? ? kk DE SDE S69 半弱密鑰 ? 半弱密鑰：對(duì)于密鑰 k ，存在一個(gè)不同的密鑰 ，滿足 。 68 弱密鑰 ? 弱密鑰： 由密鑰 k 確定的加密函數(shù)與解密函數(shù)相同 ，即 。 63 Permutation ? 16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25 子密鑰的產(chǎn)生 k 1 （ 56 位） (48 位 ) k i （ 56 位） （ 48 位） 64 位密鑰 置換選擇 1 C 0 （ 28 位） D 0 （ 28 位） 循環(huán)左移 循環(huán)左移 C 1 （ 28 位） D 1 （ 28 位） 循環(huán)左移 循環(huán)左移 C i （ 28 位） D i （ 28 位） 置換選擇 2 置換選擇 2 密鑰表的計(jì)算邏輯 循環(huán)左移： 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1 65 置換選擇 1(PC1)和置換選擇2(PC2) 總結(jié)－ DES示意圖 67 DES的安全性分析 ? DES的安全性完全依賴于密鑰，與算法本身沒有關(guān)系。相應(yīng)行、列位置的十進(jìn)制數(shù)的 4位二進(jìn)制數(shù)表示作為輸出。 DES 的歷史 52 ? 爭論： ? 56位夠長嗎？ ? 內(nèi)部結(jié)構(gòu)公開，設(shè)計(jì)原理沒公開？ DES 的歷史 53 DES的應(yīng)用 ? 1979年，美國銀行協(xié)會(huì)批準(zhǔn)使用 ? 1980年，美國國家標(biāo)準(zhǔn)局（ ANSI）贊同 DES作為私人使用的標(biāo)準(zhǔn) ,稱之為 DEA（ ANSI ） 1983年，國際化標(biāo)準(zhǔn)組織 ISO贊同 DES作為國際標(biāo)準(zhǔn)，稱之為 DEA1 ? 該標(biāo)準(zhǔn)規(guī)定每五年審查一次，計(jì)劃十年后采用新標(biāo)準(zhǔn) ? 最近的一次評(píng)估是在 1994年 1月，已決定 1998年 12月以后， DES將不再作為聯(lián)邦加密標(biāo)準(zhǔn)。 ? 1975年 3月 17日， NBS公布了 IBM公司提供的密碼算法，以標(biāo)準(zhǔn)建議的形式在全國范圍內(nèi)征求意見。 49 雙密鑰的三重 DES （ Triple DES with Two Keys) ? C=EK1(DK2(EK1(P))) ? P=DK1(EK2( DK1(C))) 50 三密鑰的三重 DES （ Triple DES with Three Keys) ? C=EK3(DK2(EK1(P))) ? =DK3(EK2( DK1(C))) 51 ? 1973年，美國國家標(biāo)準(zhǔn)局 (NBS) 開始征集聯(lián)邦數(shù)據(jù)加密標(biāo)準(zhǔn)的方案。 45 現(xiàn)代常規(guī)分組加密算法 ? 1. Triple DES ? 2. IDEA ? 3. RC5 ? 4. RC6 ? 5. AES ? 其他一些較實(shí)用的算法，如 Blowfish，CAST，以及 RC2。 39 分組密碼的操作模式 ? 電子密碼本 ECB (electronic codebook mode) ? 密碼分組鏈接 CBC (cipher block chaining) ? 密碼反饋 CFB (cipher feedback) ? 輸出反饋 OFB (output feedback) ? 計(jì)數(shù)器模式 CTR） ? 美國 NSB在 [FIPS PUB 74和 81]中規(guī)定 ? ANSI 在 [ANSI ]中規(guī)定 ? ISO和 ISO/IEC在 [ISO 9732 ISO/IEC 10116]中規(guī)定 分組密碼的操作模式 模式 描述 典型應(yīng)用 電子密碼本 ECB 用相同的密鑰分別對(duì)明文分組加密 單個(gè)數(shù)據(jù)的安全傳輸 密碼分組鏈接 CBC 加密算法的輸入是上一個(gè)密文分組和下一個(gè)明文分組的異或 普通目的的面向分組的傳輸 密碼反饋CFB 一次處理 J位，上一個(gè)分組密文作為產(chǎn)生一個(gè)偽隨機(jī)數(shù)輸出的加密算法的輸入，該輸出與明文分組異或，作為下一個(gè)分組的輸入 普通目的的面向分組的傳輸認(rèn)證 輸出反饋OFB 與 CFB相同，只是加密算法的輸入是上一次DES的輸出 噪聲信道上數(shù)據(jù)流的傳輸（如衛(wèi)星傳輸） 計(jì)數(shù)器模式 CTR） 每個(gè)明文分組是加密的計(jì)數(shù)器的異或，對(duì)每個(gè)后續(xù)的分組，計(jì)數(shù)器是累加的。 seed (short) PRBS (long) 01101 1010010110.... 38 分組密碼 ? 分組密碼是將明文按一定的位長分組，明文組和密鑰組的全部經(jīng)過加密運(yùn)算得到密文組。偽隨機(jī)序列發(fā)生器指使用短的真隨機(jī)序列（稱為種子）x擴(kuò)展成較長的偽隨機(jī)序列 y。如自然界中的拋幣。 密鑰流產(chǎn)生器 密鑰 k 明文 m 密文 c 異或運(yùn)算 37 序列密碼 ? 偽隨機(jī)序列發(fā)生器是指輸入真隨機(jī)的較短的密鑰（種子）通過某種復(fù)雜的運(yùn)算產(chǎn)生大量的偽隨機(jī)位流。 36 序列密碼（流密碼） ? 序列密碼主要應(yīng)用于軍事和外交場合。 ? 對(duì)稱算法可分為兩類。在大多數(shù)對(duì)稱算法中，加 /解密密鑰是相同的。 33 加密與解密 ? 使用兩個(gè)密鑰的加 /解密。 K可以是很多數(shù)值里的任意值。 ? 使用一個(gè)密鑰的加 /解密。 ? 2022年 11月美國國家標(biāo)準(zhǔn)技術(shù)研究所發(fā)布高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn) AES代表著密碼學(xué)的最新發(fā)展。 1949年，信息論之父 《 保密系統(tǒng)的通信理論 》 ，密碼學(xué)走上科學(xué)和理性之路。 ? 這四句詩寫出后，被官府拿到了證據(jù)，大興問罪之師，到處捉拿盧俊義，終于把他逼上梁山。 ? 盧花灘上有扁舟，俊杰黃昏獨(dú)自游。 30 密碼學(xué)起源 ? 第六十回 吳用智賺玉麒麟 梁山泊義軍頭領(lǐng)宋江久慕盧俊義的威名，一心想招取盧俊義上山坐第一把交椅，共圖大業(yè)，替天行道。張小花獨(dú)自在家只有紡車做伴。李石匠靠手藝賺錢，張小花在家紡紗織布。 1940年，經(jīng)過盟軍密碼分析學(xué)家的不懈努力， ? 恩尼格瑪 ? 密碼機(jī)被動(dòng)攻破，盟軍掌握了德軍的許多機(jī)密，而德國軍方卻對(duì)此一無所知。 1933年，納粹最高統(tǒng)帥部通信部決定將 ? ENIGMA”作為德國國防軍新式閃擊部隊(duì)的通信裝置。后來德國人將其改裝為軍用型，使之更為復(fù)雜可靠?？坪盏暮商m