第20講--RSA算法及安全性分析 ppt課件

1、RSA RSA 算法及平安性分析算法及平安性分析量子密碼研討室量子密碼研討室王濱王濱2019.4.13Euler 函數(shù)函數(shù) 一切模一切模m和和r同余的整數(shù)組成剩余類同余的整數(shù)組成剩余類r 剩余類剩余類r中的每一個(gè)數(shù)和中的每一個(gè)數(shù)和m互素的充要條件是互素的充要條件是r和和m互素互素 和和m互素的同余類數(shù)目用互素的同余類數(shù)目用(m)表示，稱表示，稱m的的Euler函數(shù)函數(shù) 當(dāng)當(dāng)m是素?cái)?shù)時(shí)，小于是素?cái)?shù)時(shí)，小于m的一切整數(shù)均與的一切整數(shù)均與m互素，因此互素，因此(m)=m-1對對n=pq, p和和q 是素?cái)?shù)，是素?cái)?shù)，(n)=(p)(q)=(p-1)(q-1)Euler 函數(shù)舉例函數(shù)舉例 設(shè)設(shè)p=3,

2、q=5, p=3, q=5, 那么那么 1515= =3-13-1* *5-15-1=8=8 這這8 8個(gè)模個(gè)模1515的剩余類是：的剩余類是： 1 1，2 2，4 4，7 7，8 8，1111，1313，14 14 Euler定理、定理、Fermat定理定理oEuler定理：設(shè)定理：設(shè) x 和和 n 都是正整數(shù)，假設(shè)都是正整數(shù)，假設(shè)gcd(x，n)1，那么，那么 x (n)1 (mod n).oFermat定理定理:設(shè)設(shè) x 和和 p 都是正整數(shù)，假設(shè)都是正整數(shù)，假設(shè)gcd(x，p)1，那么，那么 x p-11 (mod p).RSA算法的實(shí)現(xiàn)算法的實(shí)現(xiàn) 實(shí)現(xiàn)的步驟如下：實(shí)現(xiàn)的步驟如下：Bo

3、b為實(shí)現(xiàn)者為實(shí)現(xiàn)者 (1) Bob尋覓出兩個(gè)大素?cái)?shù)尋覓出兩個(gè)大素?cái)?shù)p和和q (2) Bob計(jì)算出計(jì)算出n=pq 和和(n)=(p-1)(q-1) (3) Bob選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)e (0e (n)，滿足，滿足(e,(n)=1 (4) Bob運(yùn)用輾轉(zhuǎn)相除法計(jì)算運(yùn)用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod(n) (5) Bob在目錄中公開在目錄中公開n和和e作為公鑰作為公鑰密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解體制的關(guān)鍵點(diǎn)在于如何分解n。假設(shè)。假設(shè)分分解勝利使解勝利使n=pq，那么可以算出，那么可以算出(n)p-1)(q-1)，然后，然后由公由公開的開的e，解出的，解出的dR

4、SA算法編制算法編制 參數(shù)參數(shù)T=N；私鑰私鑰SK=D；公鑰公鑰PK=E； 設(shè)：明文設(shè)：明文M，密文，密文C，那么：，那么： 用公鑰作業(yè)：用公鑰作業(yè)：ME mod N = C 用私鑰作業(yè)：用私鑰作業(yè)：CD mod N = MRSA算法舉例算法舉例RSA算法的平安性分析算法的平安性分析密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解體制的關(guān)鍵點(diǎn)在于如何分解n假設(shè)分解勝利使假設(shè)分解勝利使n=pq，那么可以算出，那么可以算出(n)p-1)(q-1)，然后由公開的，然后由公開的e，解出的，解出的d假設(shè)使假設(shè)使RSA平安，平安，p與與q必為足夠大的素?cái)?shù)，使分析必為足夠大的素?cái)?shù)，使分析者沒有方法

5、在多項(xiàng)式時(shí)間內(nèi)將者沒有方法在多項(xiàng)式時(shí)間內(nèi)將n分解出來分解出來 n取取1024位或取位或取2048位，這樣位，這樣p、q就應(yīng)該取就應(yīng)該取512位和位和1024位。位。RSA算法的平安性分析算法的平安性分析建議選擇建議選擇p和和q大約是大約是100位的十進(jìn)制素?cái)?shù)位的十進(jìn)制素?cái)?shù)模模n的長度要求至少是的長度要求至少是512比特比特EDI攻擊規(guī)范運(yùn)用的攻擊規(guī)范運(yùn)用的RSA算法中規(guī)定算法中規(guī)定n的長度為的長度為512至至1024比特位之間，但必需是比特位之間，但必需是128的倍數(shù)的倍數(shù)國際數(shù)字簽名規(guī)范國際數(shù)字簽名規(guī)范ISO/IEC 9796中規(guī)定中規(guī)定n的長度位的長度位512比比特位特位密鑰大小 MIPS

6、年 512比特 768比特1024比特2048比特43 1082 10113 10203 10RSA算法的平安性分析算法的平安性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模模n的素因子的素因子p和和q還有如下要求即是強(qiáng)素?cái)?shù)：還有如下要求即是強(qiáng)素?cái)?shù)： (1) p-1 和和q-1分別含有大素因子分別含有大素因子p1和和q1 (2) P1-1和和q1-1分別含有大素因子分別含有大素因子p2和和q2 (3) p+1和和q+1分別含有大素因子分別含有大素因子p3和和q3RSA算法的平安性分析算法的平安性分析其它參數(shù)的選擇要求：其它參數(shù)的選擇要求：(1) |p-q|很大，通常很大，通常 p和和q的長度一樣；的長度一樣；(2)p-1和和q-1的最大公因子要??；的最大公因子要??；(3)e的選擇；的選擇；(4)d的選擇；的選擇；(5)不要許多的用戶共用一個(gè)不要許多的用戶共用一個(gè)n。 定義 假設(shè) modemNm 那么稱那么稱 m m