【信息系統(tǒng)】lecture06_公鑰密碼體制(已修改)
2025-08-13 16:17 本頁面
【正文】 第 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í) 密鑰空間急劇增大 。如 : – 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） 。 （ 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ì)算上是不可行的 。 （ 5） 敵對(duì)方即使知道公開密鑰 KUb和密文 C， 要想恢復(fù)原來的報(bào)文 M在計(jì)算上也是不可行的 。 （ 6） 加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來使用 : M＝ DKRb（ EKUb（ M）） M=EKUb(DKRb(M)) 注 ： 1*. 僅滿足 (1)、 (2)兩條的稱為單向函數(shù)；第 (3)條稱為陷門性， δ 稱為陷門信息。 2*. 當(dāng)用陷門函數(shù) f作為加密函數(shù)時(shí)，可將 f公開，這相當(dāng)于公開加密密鑰。此時(shí)加密密鑰便稱為公開密鑰，記為 Pk。 f函數(shù)的設(shè)計(jì)者將 δ 保密，用作解密密鑰，此時(shí) δ 稱為秘密密鑰，記為 Sk。由于加密函數(shù)是公開的，任何人都可以將信息 x加密成 y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過不安全信道傳送）；由于設(shè)計(jì)者擁有 Sk，他自然可以解出 x=f1(y)。 3*.單向陷門函數(shù)的第 (2)條性質(zhì)表明竊聽者由截獲的密文 y=f(x)推測 x是不可行的。 是滿足下列條件的函數(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)行攻擊 )。 公鑰密碼系統(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。 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。 6－ 3 RSA 由 Rivest,Shamir和 Adleman在 1978年提出來的 數(shù)學(xué)基礎(chǔ) :Euler定理，并建立在大整數(shù)因子分解的困難性之上 ? 明文空間 P＝密文空間 C=Zn ? 密鑰的生成 – 選擇互異素?cái)?shù) p,q，計(jì)算 n=p*q, ? (n)=(p1)(q1), 選擇整數(shù) e使 (? (n),e)=1,1e? (n),計(jì)算 d,使 d=e1mod ? (n) – 公鑰 Pk={e,n} – 私鑰 Sk={d,n} ? 加密 (用 e,n) – 明文： Mn 密文： C=Me(mod n) ? 解密 (用 d,n) 密文： C 明文： M=Cd（ mod n) 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ì)算不可行。而 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。若分解成功使 n=pq，則可以算出 φ(n)＝（ p1)(q1)，然后由公開的 e，解出秘密的 d。 RSA密碼體制描述 要求：若使 RSA安全， p與 q必為足夠大的素?cái)?shù)，使 分析者沒有辦法在有效時(shí)間內(nèi)將 n分解出來。建議選擇 p和 q大約是 100位的十進(jìn)制素?cái)?shù)。 模 n的長度要求至少是 512比特。 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì) RSA模 n的素因子 p和 q還有如下要求： (1)|pq|很大，通常 p和 q的長度相同； (2)p1 和 q1分別含有大素因子 p1和 q1 (3)gcd(p11,q11)應(yīng)該很小。 為了提高加密速度，通常取 e為特定的小整數(shù)，如EDI國際標(biāo)準(zhǔn)中規(guī)定 e＝ 216＋ 1， ISO/IEC9796中甚至允許取 e＝ 3。這時(shí)加密速度一般比解密速度快 10倍以上。 RSA密鑰的生成 例： p=47, q=61, ?(n)=(471)(611)=2760時(shí)， SK=167是否為 秘密密 鑰的候選者？ 用歐氏算法計(jì)算： gcd(2760,167)=1即可證明。 Q X1 X2 X3 Y1 Y2 Y3 － 1 0 2760 0 1 167 16 0 1 167 1 － 16 88 1 1 － 16 88 － 1 17 79 1 － 1 17 79 2 － 33 9 8 2 － 33 9 － 17 281 7 1 － 17 281 7 19 － 314 2 3 19 － 314 2 － 74 1223 1 用 RSA算法加密與解密的過程： 例：明文 =“RSA ALGORITHM” (1) 明文用數(shù)字表示 空白 =00， A=01, B=02
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1