【正文】 10， X3=10111。版權(quán)所有 ,引用請注明出處 舉例 1 （ 1）選擇一個 超遞增背包作為私鑰 ，例如A=(2,3,6,13,27)。 求解超遞增背包問題，將密文變?yōu)槊魑?X=D(S’)=∑aixi。 xi （ i=1,2,...,n） ? 解密 計算 w在模 m下的乘法逆元 w1，即滿足 ww1≡1mod m。版權(quán)所有 ,引用請注明出處 55 背包算法的加密 /解密過程 ? 加密 – 將明文分為長度為 n的塊 X=(x1,…,x n) – 然后用轉(zhuǎn)換背包 —公鑰 A 39。 ◆選擇一個與 m互素的整數(shù) w，并計算 ai’ =wai(mod m)（ i=1,2,...,n）。 設(shè)：背包序列為 {2,3,6,13,27,52}，求解 密文 S=70的 明文 X。 ? 超遞增序列時滿足下列特征的序列： 其中的每個元素都大于前面所有元素之和，即 ：ai ∑aj(j=1,2,...,i1)。 ◆ 難解的背包作為公鑰 ，可以實現(xiàn)加密。因為 85 1+13 1+9 0+7 0+47 1+27 1+99 0+86 0=172 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。對于每個 ai∈ {0,1},能否找到一組系數(shù) a1,a2,……,a n,使得 S = a1W1+a2W2 +...+ anWn成立，即為背包問題。 ? 背包算法只能用于加密 /解密。 ? 第一種情況 O只是簡單地偷聽 A與 B之間的通信 ? 第二種情況 O想篡改 A發(fā)送給 B的消息。版權(quán)所有 ,引用請注明出處 44 DiffieHellman密鑰交換的攻擊 ? 舉例 – A和 B選擇素數(shù) p以及 p的一個本原根 a(假定 O知道 ) – A選擇 Xap,計算 Ya=aXa mod p, A?B: Ya – O截獲 Ya,選 Xo,計算 Yo=aXo mod p,冒充 A?B:Yo – B選擇 Xbp,計算 Yb=aXb mod p, B?A: Yb – O截獲 Yb,冒充 B?A:Yo – A計算 : (Yo)Xa?(aXo)Xa?aXoXa mod p – B計算 : (Yo)Xb?(aXo)Xb?aXoXb mod p – O計算 : (Ya)Xo?aXaXo mod p, (Yb)Xo?aXbXo mod p ? 在這種攻擊方式中， O無法計算出 A和 B期望獲得的會話密鑰 K=aXaXb mod p，但 O與 A和 B分別建立了共享密鑰aXaXo mod p和 aXbXo mod p。 ? 密鑰交換協(xié)議完成后， A實際上和 O建立了一個共享密鑰， B實際上和 O也建立了一個共享密鑰。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ⑤因為 k=k’ =160,所以 160即為 A和 B共享的“會話密鑰” 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 計算過程如下： ① A計算 X=ax mod p=397 mod 353＝ 40，并發(fā)送給 B。 ? 接下來，雙方以共享密鑰 K=aXaXb mod p作為加 /解密密鑰，以傳統(tǒng)的 對稱密鑰密碼算法 進(jìn)行保密通信。版權(quán)所有 ,引用請注明出處 39 DiffieHellman密鑰交換 ? 算法描述： – 假定 A,B雙方共同選擇素數(shù) p以及 p的一個本原根 a（ p和 a可以公開 ） – 用戶 A選擇一個隨機(jī)數(shù) Xa p，計算 Ya=aXa mod p – 用戶 B選擇一個隨機(jī)數(shù) Xb p，計算 Yb=aXb mod p – 每一方保密 X值，而將 Y值通過公開信道交換給對方（ Ya和 Yb無需保密 ） – 用戶 A計算出 K=YbXa mod p=(aXb)Xa mod p =aXbXa mod p – 用戶 B計算出 K39。該秘密信息僅為兩個參與者知道。版權(quán)所有 ,引用請注明出處 36 內(nèi)容提要 ? 公鑰密碼算法概述 ? 公鑰密碼體制的基本原理 ? 公鑰密碼算法的數(shù)學(xué)基礎(chǔ) ? 一些經(jīng)典算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 離散對數(shù)難題 ? 舉例 取 p=13，有限域 GF(13)={0， 1， 2， ...,12}上的 乘法群 Z13*={1， 2， ...,12}。 即：求解離散對數(shù)相當(dāng)于求解一個 單向陷門函數(shù)。這些數(shù)構(gòu)成 1～ p1的全體數(shù)的一個排列 {g mod p， g2 mod p， ...， gp1 mod p}={1,2， ...，p1}=Zp*， 即構(gòu)成了有限域 GF(p)上的乘法群。 ●有限域 GF(p)上的乘法群： 是由 Zp上的非 0元 構(gòu)成的集合，記為 Zp*，即 Zp*={1,2， ...， p1}。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。當(dāng) n=1時， GF(p)稱為階數(shù)為 p的素域，它屬于模 p的最小非負(fù)完全剩余系 Zp={0,1,...p1}。 ◆有限域中的元素個數(shù)稱為 階數(shù)或者基數(shù) 。比如，全體有理數(shù)的集 合 Q是一個域。 ⑶ {F\{0}， }構(gòu)成乘法交換群（乘法阿貝爾群。 ? 特別的，若對任意的 a,b∈ G有 a*b=b*a，則稱群 G,*為 交換群或阿貝爾（ Abel）群，簡記a*b=ab。 ⑵ 結(jié)合律： a,b,c∈ G，恒有 (a*b)*c=a*(b*c)。 23 這 8個數(shù)構(gòu)成的集 合就是 20的既約 剩余系 Z20* 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 Euler定理 ? 歐拉函數(shù) ?(n)定義為： 小于 n且與 n互素的正整數(shù)個數(shù)。版權(quán)所有 ,引用請注明出處 21 內(nèi)容提要 ? 公鑰密碼算法概述 ? 公鑰密碼體制的基本原理 ? 公鑰密碼算法的數(shù)學(xué)基礎(chǔ) ? 一些經(jīng)典算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 (2)任何人均可將明文 X經(jīng)過函數(shù) F加密得到密文 Y=F(X)。對于公鑰密碼體制來說， “陷門”就是“私鑰” 。 k稱之為“陷門”。 ●加密密鑰是公開的，不能用它來解密，即 DKUb(EKUb(X))≠X。 ●接收方 B利用其私鑰 KRb來解密密文 Y在計算上是可行的。 ◆ 密鑰交換： 通信雙方交換會話密鑰。每次 邏輯連接使用一把新的會話密鑰，用完就丟 棄。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 KRb X Kub 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。DKRa(Y)=DKRa(EKUa(X))=X。 (2)每一個用戶把公鑰 KU公開，私鑰 KR保密。X=DKR(EKU(X))=EKU(DKR(X)) 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。KR是保密的，稱為“私鑰”（ private key）。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 ? 公鑰密碼的產(chǎn)生過程 1976年，由 Diffie和 Hellman在其論文 《 密碼 學(xué)新方向 》 中首次提出了“不對稱密鑰密碼” 的思想，首次證明在發(fā)送端和接收端之間進(jìn) 行無密鑰傳輸?shù)谋Ｃ芡ㄐ攀强赡艿?，但他們 并沒有提出一個具體的公鑰密碼算法。同時，由于加密密鑰公開，因此任何人均可使用加密密鑰來加密消息，但只有擁有解密密鑰的人才能解密消息。由于密鑰數(shù)目和參與通信人數(shù)的平方成正比，故隨著通信人數(shù) n的增加，密鑰空間將會急劇增大，從而造成對密鑰的分配和管理極為困難。 使用兩個密鑰在消息的保密性、密鑰分配和認(rèn)證領(lǐng)域有著重要的意義 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 2 內(nèi)容提要 ? 公鑰密碼算法概述 ? 公鑰密碼體制的基本原理 ? 公鑰密碼算法的數(shù)學(xué)基礎(chǔ) ? 一些經(jīng)典算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 1 信息安全原理與應(yīng)用 第四章 公鑰密碼 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。首先， 公鑰算法是基于數(shù)學(xué)函數(shù)而不是基于代替和置換， 更重要的是，與只使用一個密鑰的對稱密鑰密碼不同， 公鑰密碼是非對稱的，它使用兩個獨立的密鑰。 假設(shè)有 n方參與保密通信，若兩兩之間分別采用不同的對稱密鑰，則最少需要 C(n,2)=n(n1)/2個密鑰（不包括兩兩之間多次通信或反復(fù)傳送同一信息）。版權(quán)所有 ,引用請注明出處 概述 ? 公鑰密碼算法的出現(xiàn)是現(xiàn)代密碼學(xué)誕生的標(biāo)志之一 ，其加密和解密過程使用不同的密鑰，而且，由解密密鑰很容易計算出加密密鑰（但 解密密鑰是保密 的），但由加密密鑰卻很難甚至無法計算出解密密鑰（ 加密密鑰是公開 的）。版權(quán)所有 ,引用請注明出處 6 內(nèi)容提要 ? 公鑰密碼算法概述 ? 公鑰密碼體制的基本原理 ? 公鑰密碼算法的數(shù)學(xué)基礎(chǔ) ? 一些經(jīng)典算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。其中， KU是公開的，稱為“公鑰”（ public key） 。 (4)加密和解密的順序可以調(diào)換。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 應(yīng)用一：加 /解密 其主要步驟如下： (1)每一個用戶都擁有自己的密鑰對 (KU， KR)。 (4)當(dāng) A收到密文 Y后，用自己的私鑰 KRa解密。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 應(yīng)用二：數(shù)字簽名 用公鑰密碼算法實現(xiàn)身份鑒別（數(shù)字簽名）的過程 如圖 42所示。這樣， 可以防止消息被擅自篡改和偽造 。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 應(yīng)用四：密鑰交換 通信雙方交換 會話密鑰， 用以加密通信 雙方后續(xù)進(jìn)行連接通信所傳輸?shù)男畔ⅰ? ◆ 數(shù)字簽名： 發(fā)送方用自己的私鑰對消息加密—簽名，接收方用發(fā)送方的公鑰解密 —驗證簽名。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的思想和要求 公鑰密碼算法的基本要求包括 安全性 和 計算可行 性 兩方面： ●用戶 B產(chǎn)生一對密鑰（公鑰 KUb，私鑰 KRb）在計算上是可行的 ●已知 B的公鑰 KUb和明文 X，發(fā)送方 A產(chǎn)生密文 Y在計算上是可行的。 ●加密和解密的順序可以交換。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的思想和要求 單向函數(shù)： 單向函數(shù)是滿足下列條件的函數(shù)：每個函數(shù)值 y都存在唯一的逆 x，并且計算函數(shù)值 y是容易的，但求逆 x卻是不可