信息安全概論課件-lecture-資料下載頁
2025-08-04 14:09本頁面
【正文】 對數(shù)的困難性問題之上：設(shè) F為有限域 ， g∈ F是 F的乘法群 F*=F\{0}=g， 并且對任意正整數(shù) x， 計(jì)算 gx是容易的；但是已知 g和 y求 x使 y= gx， 是計(jì)算上幾乎不可能的 ? 這個(gè)問題稱為有限域 F上的離散對數(shù)問題 。 公鑰密碼學(xué)中使用最廣泛的有限域?yàn)樗赜?FP DiffieHellman密鑰交換協(xié)議描述 ? Alice和 Bob協(xié)商好一個(gè)大素?cái)?shù) p， 和大的整數(shù) g， 1gp， g最好是 FP中的本原元 ， 即 FP*＝ g ? p和 g無須保密 ， 可為網(wǎng)絡(luò)上的所有用戶共享 DiffieHellman密鑰交換協(xié)議描述 ? 當(dāng) Alice和 Bob要進(jìn)行保密通信時(shí) ， 他們可以按如下步驟來做： (1) Alice選取大的隨機(jī)數(shù) x，并計(jì)算 X = gx(mod P) (2) Bob選取大的隨機(jī)數(shù) x?，并計(jì)算 X ? = gx ?(mod P) (3) Alice將 X傳送給 Bob； Bob將 X ?傳送給 Alice (4) Alice計(jì)算 K= (X ?)X(mod P)。 Bob計(jì)算 K ? =（ X) X ?(mod P), 易見， K = K ? =g xx ?(mod P) ? 由 (4)知， Alice和 Bob已獲得了相同的秘密值 K ? 雙方以 K作為加解密鑰以傳統(tǒng)對稱密鑰算法進(jìn)行保密通信 RSA 算法 Euler 函數(shù) ? 所有模 m和 r同余的整數(shù)組成剩余類 [r] ? 剩余類 [r]中的每一個(gè)數(shù)和 m互素的充要條件是 r和 m互素 ? 和 m互素的同余類數(shù)目用 φ(m)表示 ， 稱 m的 Euler函數(shù) ? 當(dāng) m是素?cái)?shù)時(shí) ， 小于 m的所有整數(shù)均與 m互素 ， 因此φ(m)=m1 ? 對 n=pq, p和 q 是素?cái)?shù) ， φ(n)=φ(p)φ(q)=(p1)(q1) Euler 函數(shù) 舉例 設(shè) p=3, q=5, 那么 φ （ 15） =（ 31） *（ 51） =8 這 8個(gè)模 15的剩余類是 ： {1， 2， 4， 7， 8， 11， 13， 14} RSA算法的實(shí)現(xiàn) ? 實(shí)現(xiàn)的步驟如下： Bob為實(shí)現(xiàn)者 (1) Bob尋找出兩個(gè)大素?cái)?shù) p和 q (2) Bob計(jì)算出 n=pq 和 φ (n)=(p1)(q1) (3) Bob選擇一個(gè)隨機(jī)數(shù) e (0e φ (n))，滿足 (e,φ (n))=1 (4) Bob使用輾轉(zhuǎn)相除法計(jì)算 d=e1(modφ (n)) (5) Bob在目錄中公開 n和 e作為公鑰 ? 密碼分析者攻擊 RSA體制的關(guān)鍵點(diǎn)在于如何分解 n。 若分 解成功使 n=pq，則可以算出 φ(n)＝（ p1)(q1)，然后由公 開的 e，解出秘密的 d RSA算法編制 ? 參數(shù) T={N}； ? 私鑰 SK=D； ? 公鑰 PK=E； 設(shè)：明文 M， 密文 C， 那么： 用公鑰作業(yè)： ME mod N = C 用私鑰作業(yè)： MD mod N = M RSA算法舉例 ? 設(shè) p=7, q=17, n=7*17=119。 參數(shù) T={n=119}。 ? φ(n)=(71)(171)=96。 ? 選擇 e=5, gcd(5,96)=1。 公鑰 pk=5。 ? 計(jì)算 d, ( d*e) mod 96=1。 d=77。 私鑰 sk=77。 設(shè) :明文 m=19 加密： （ 19） 5 mod 119 = 66 脫密： （ 66） 77 mod 119 = 19 RSA算法的安全性分析 ? 密碼分析者攻擊 RSA體制的關(guān)鍵點(diǎn)在于如何分解 n ? 若分解成功使 n=pq， 則可以算出 φ(n)＝ （ p1)(q1)， 然后由公開的 e， 解出秘密的 d ? 若使 RSA安全 ， p與 q必為足夠大的素?cái)?shù) ， 使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將 n分解出來 RSA算法的安全性分析 ? 建議選擇 p和 q大約是 100位的十進(jìn)制素?cái)?shù) ? 模 n的長度要求至少是 512比特 ? EDI攻擊標(biāo)準(zhǔn)使用的 RSA算法中規(guī)定 n的長度為 512至 1024比特位之間 ， 但必須是 128的倍數(shù) ? 國際數(shù)字簽名標(biāo)準(zhǔn) ISO/IEC 9796中規(guī)定 n的長度位 512比特位 RSA算法的安全性分析 為了抵抗現(xiàn)有的整數(shù)分解算法 ， 對 RSA模 n的素因子 p和 q還有如下要求： (1) |pq|很大 ， 通常 p和 q的長度相同； (2) p1 和 q1分別含有大素因子 p1和 q1 (3) P11和 q11分別含有大素因子 p2和 q2 (4) p+1和 q+1分別含有大素因子 p3和 q3 RSA算法的安全性分析 ? 為了提高加密速度 ， 通常取 e為特定的小整數(shù) ? 如 EDI國際標(biāo)準(zhǔn)中規(guī)定 e＝ 216＋ 1 ? ISO/IEC9796中甚至允許取 e＝ 3 ? 這時(shí)加密速度一般比解密速度快 10倍以上
試題試卷相關(guān)推薦
鄂ICP備17016276號-1