【正文】 RSA密碼體制描述 ? 若 Bob選擇了 p=7和 q＝ 17 ? 則 n=119, ? (n)=6 16＝ 96＝ 25 3，一個(gè)正整數(shù) e能用作加密指數(shù)，當(dāng)且僅當(dāng) e不能被 2， 3所整除 ? 假設(shè) Bob選擇 e=5，那么用輾轉(zhuǎn)相除法將求得： d=e 1 ? 77(mod 96) ? Bob的解密密鑰 d={77,119}，公開｛ 5,119｝ ? 現(xiàn)假設(shè) Alice想發(fā)送明文 19給 Bob 注 ： RSA的安全性基于：加密函數(shù) ek(x)=xe(mod n)是一個(gè)單向函數(shù)，所以對(duì)敵人來說求逆計(jì)算不可行。 公鑰密碼系統(tǒng)的應(yīng)用類型 ?加密 /解密 ?數(shù)字簽名 ?會(huì)話密鑰交換 ? 一個(gè)素?cái)?shù) q和一個(gè)整數(shù) a（均公開）， a是 q的一個(gè) 原根 ? 用戶 A選擇一個(gè)隨機(jī)數(shù) XAq，并計(jì)算 ? 類似地，用戶 B選擇一個(gè)隨機(jī)數(shù) XBq,并計(jì)算 ? 每一方都對(duì) X的值保密存放而使得 Y的值對(duì)于另一方可以公開得到 ? 用戶 A計(jì)算密鑰： ? 用戶 B計(jì)算密鑰： ? 雙方以 K作為加、解密密鑰，以對(duì)稱密鑰算法進(jìn)行保密通信 qaY AXA m o d?qaY BXB m o d?qYK AXB m o d)(?qYK BXA m o d)(?167。 ?公開密鑰算法本身可能被攻破。 3*.單向陷門函數(shù)的第 (2)條性質(zhì)表明竊聽者由截獲的密文 y=f(x)推測(cè) x是不可行的。 f函數(shù)的設(shè)計(jì)者將 δ 保密，用作解密密鑰，此時(shí) δ 稱為秘密密鑰，記為 Sk。 2*. 當(dāng)用陷門函數(shù) f作為加密函數(shù)時(shí)，可將 f公開，這相當(dāng)于公開加密密鑰。 （ 5） 敵對(duì)方即使知道公開密鑰 KUb和密文 C， 要想恢復(fù)原來的報(bào)文 M在計(jì)算上也是不可行的 。如 : – n= 100 時(shí) C( 100,2)= 4,995 – n= 5000 時(shí) C( 5000,2)= 12,497,500 ? 陌生人間的保密通信問題 ? 數(shù)字簽名的問題 – 傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求 公鑰密碼體制 ? 公鑰密碼又稱為雙鑰密碼、非對(duì)稱密碼 ? 公鑰密碼體制提出的標(biāo)志性文獻(xiàn)： – and , New Directions in Cryptography, IEEE Transaction on Information Theory, , Nov 1976, 對(duì)公鑰密碼體制的要求 （ 1） 參與方 B容易通過計(jì)算產(chǎn)生一對(duì)密鑰 （ 公開密鑰 KUb和私有密鑰KRb） 。第 6章 非對(duì)稱密碼體制 ?學(xué)習(xí)要點(diǎn)： – 了解非對(duì)稱密碼體制的提出背景、基本思想 – 了解非對(duì)稱密碼體制的基本應(yīng)用方向 – 了解三種典型的公鑰密碼體制 ? DH密鑰交換算法 ? RSA ? ECC 167。 6－ 1 概 述 ? 問題的提出： ? 密鑰管理困難 – 傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則 n 個(gè)用戶需要 C( n, 2)= n( n 1)/ 2 個(gè)密鑰，當(dāng)用戶量增大時(shí) 密鑰空間急劇增大 。 （ 2） 在知道公開密鑰和待加密報(bào)文 M的情況下 ， 對(duì)于發(fā)送方 A， 很容易通過計(jì)算產(chǎn)生對(duì)應(yīng)的密文： C＝ EKUb（ M） （ 3） 接收方 B使用私有密鑰容易通過計(jì)算解密所得的密文以便恢復(fù)原來的報(bào)文： M＝ DKRb（ C） ＝ DKRb（ EKUb（ M）） （ 4） 敵對(duì)方即使知道公開密鑰 KUb， 要確定私有密鑰 KRb在計(jì)算上是不可行的 。 （ 6） 加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來使用 : M＝ DKRb（ EKUb（ M）） M=EKUb(DKRb(M)) 注 ： 1*. 僅滿足 (1)、 (2)兩條的稱為單向函數(shù)；第 (3)條稱為陷門性， δ 稱為陷門信息。此時(shí)加密密鑰便稱為公開密鑰，記為 Pk。由于加密函數(shù)是公開的，任何人都可以將信息 x加密成 y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過不安全信道傳送）；由于設(shè)計(jì)者擁有 Sk，他自然可以解出 x=f1(y)。 是滿足下列條件的函數(shù) f： (1)給定 x，計(jì)算 y=f(x)是容易的 (2)給定 y, 計(jì)算 x使 y=f(x)是困難的 (3)存在 δ，已知 δ 時(shí) ,對(duì)給定的任何 y，若相應(yīng)的 x存在，則計(jì)算 x使 y=f(x)是容易的 陷門單向函數(shù) 公開密鑰密碼系統(tǒng)的分析方法 ?強(qiáng)行攻擊 (對(duì)密鑰 )。 ?可能報(bào)文攻擊 (對(duì)報(bào)文本身的強(qiáng)行攻擊 )。 6－ 2 DiffieHellman密鑰交換算法 DH例子 ? 素?cái)?shù) q=97,它的一個(gè)本原元 a=5 ? A和 B分別選擇隨機(jī)數(shù) Xa=36和 Xb=58 ? A計(jì)算公開密鑰： Ya=536mod97=50mod97 ? B計(jì)算公開密鑰： Yb=558mod97=44mod97 ? A計(jì)算會(huì)話密鑰： K= 4436mod97=75mod97 ? B計(jì)算會(huì)話密鑰： K= 5058mod97=75mod97 167。而 Bob能解密的陷門是分解n=pq，知 ? (n)=(p1)(q1)，從而解出解密私鑰 d RSA的例子 步驟 ： Bob為實(shí)現(xiàn)者 ? Bob尋找出兩個(gè)大素?cái)?shù) p和 q ? Bob計(jì)算出 n=pq和 ? (n)=(p1)(q1). ? Bob選擇一個(gè)隨機(jī)數(shù) e(0e ? (n))，滿足（ e， ? (n)）＝ 1 ? Bob使用輾轉(zhuǎn)相除法計(jì)算 d=e1(mod ? (n)) ? Bob在目錄中公開 n和 e作為她的公開鑰 密碼分析者攻擊 RSA體制的關(guān)鍵點(diǎn)在于如何分解 n。 RSA密碼體制描述 要求：若使 RSA安全， p與 q必為足夠大的素?cái)?shù)，使 分析者沒有辦法在有效時(shí)間內(nèi)將 n分解出來。 模 n的長(zhǎng)度要求至少是 512比特。 為了提高加密速度，通常取 e為特定的小整數(shù)，如EDI國(guó)際標(biāo)準(zhǔn)中規(guī)定 e＝ 216＋ 1， ISO/IEC9796中甚至允許取 e＝ 3。 RSA密鑰的生成 例： p=47, q=61, ?(n)=(471)(611)=2760時(shí)， SK=167是否為 秘密密 鑰的候選者？ 用歐氏算法計(jì)算： gcd(2760,167)=1即可證明。 1819128 18194 18191(mod 2867) =2756 2756 2022 0542 0669 2347 0408 1815 選擇兩個(gè)大素?cái)?shù) p和 q，通常要求每個(gè)均大于 10100。 ?選擇一與 z互素的數(shù)、令其為 d 。 選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度 m滿足 0mn。由于模運(yùn)算的對(duì)稱性，可以證明， 在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。 RSA算法歸納 如何計(jì)算 ab mod n？ 如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？ 如何找到足夠大的素?cái)?shù) p和 q ? 問題 …… 要點(diǎn) 1： (a x b) mod n = [(a mod n) x (b mod n)] mod n] 要點(diǎn) 2： a16=aaaaaaaaaaaaaaaa =a2, a4,a8, a16 更一般性的問題： am m的二進(jìn)制表示為 bkbk1…b 0, 則 計(jì)算 am mod n am mod n = [? a(2i)] mod n = ?[ a(2i) mod n] bi?0 bi?0 ikiibm 20???如何計(jì)算 ab mod n？ 快速取模指數(shù)算法計(jì)算 abmodn c 0。 說明：① 隨機(jī)選取大約用 ln(N)/2的次數(shù)，如 ln(2200)/2=70 ② 好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受?？捎晌逶P(guān)系組（ M,A,K,S,V）來描述： (1)M是由一切可能 消息 所構(gòu)成的有限集合； (2)A是一切可能的簽名的有限集合； (3)K為有限密鑰空間，是一些可能密鑰的有限集合； (4)任意 k ∈ K，有簽