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

1、RSA RSA 算法及平安性分析算法及平安性分析量子密碼研討室量子密碼研討室王濱王濱2019.4.13Euler 函數(shù)函數(shù) 一切模一切模m和和r同余的整數(shù)組成剩余類同余的整數(shù)組成剩余類r 剩余類剩余類r中的每一個數(shù)和中的每一個數(shù)和m互素的充要條件是互素的充要條件是r和和m互素互素 和和m互素的同余類數(shù)目用互素的同余類數(shù)目用(m)表示，稱表示，稱m的的Euler函數(shù)函數(shù) 當(dāng)當(dāng)m是素數(shù)時，小于是素數(shù)時，小于m的一切整數(shù)均與的一切整數(shù)均與m互素，因此互素，因此(m)=m-1對對n=pq, p和和q 是素數(shù)，是素數(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個模個模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算法的實現(xiàn)算法的實現(xiàn) 實現(xiàn)的步驟如下：實現(xiàn)的步驟如下：Bo

3、b為實現(xiàn)者為實現(xiàn)者 (1) Bob尋覓出兩個大素數(shù)尋覓出兩個大素數(shù)p和和q (2) Bob計算出計算出n=pq 和和(n)=(p-1)(q-1) (3) Bob選擇一個隨機數(shù)選擇一個隨機數(shù)e (0e (n)，滿足，滿足(e,(n)=1 (4) Bob運用輾轉(zhuǎn)相除法計算運用輾轉(zhuǎn)相除法計算d=e-1(mod(n) (5) Bob在目錄中公開在目錄中公開n和和e作為公鑰作為公鑰密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點在于如何分解體制的關(guā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)鍵點在于如何分解體制的關(guān)鍵點在于如何分解n假設(shè)分解勝利使假設(shè)分解勝利使n=pq，那么可以算出，那么可以算出(n)p-1)(q-1)，然后由公開的，然后由公開的e，解出的，解出的d假設(shè)使假設(shè)使RSA平安，平安，p與與q必為足夠大的素數(shù)，使分析必為足夠大的素數(shù)，使分析者沒有方法

5、在多項式時間內(nèi)將者沒有方法在多項式時間內(nèi)將n分解出來分解出來 n取取1024位或取位或取2048位，這樣位，這樣p、q就應(yīng)該取就應(yīng)該取512位和位和1024位。位。RSA算法的平安性分析算法的平安性分析建議選擇建議選擇p和和q大約是大約是100位的十進制素數(shù)位的十進制素數(shù)模模n的長度要求至少是的長度要求至少是512比特比特EDI攻擊規(guī)范運用的攻擊規(guī)范運用的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還有如下要求即是強素數(shù)：還有如下要求即是強素數(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)不要許多的用戶共用一個不要許多的用戶共用一個n。 定義 假設(shè) modemNm 那么稱那么稱 m m