RSA 算法及安全性分析课件

RSA演算法及安全性分析

Euler

函數

所有模m和r同餘的整數組成剩餘類[r]

剩餘類[r]中的每一個數和m互素的充要條件是r和m互素和m互素的同餘類數目用φ(m)表示，稱m的Euler函數當m是素數時，小於m的所有整數均與m互素，因此φ(m)=m-1對n=pq,p和q是素數，φ(n)=φ(p)φ(q)=(p-1)(q-1)Euler

函數舉例

設p=3,q=5,那麼

φ（15）=（3-1）*（5-1）=8

這8個模15的剩餘類是：

{1，2，4，7，8，11，13，14}Euler定理、Fermat定理Euler定理：設x和n都是正整數，如果gcd(x，n)＝1，則xφ(n)≡1(modn).Fermat定理:設x和p都是正整數，如果gcd(x，p)＝1，則xp-1≡1(modp).RSA演算法的實現

實現的步驟如下：Bob為實現者

(1)Bob尋找出兩個大素數p和q(2)Bob計算出n=pq

和φ(n)=(p-1)(q-1)(3)Bob選擇一個亂數e(0<e<φ(n))，滿足(e,φ(n))=1(4)Bob使用輾轉相除法計算d=e-1(modφ(n))(5)Bob在目錄中公開n和e作為公鑰密碼分析者攻擊RSA體制的關鍵點在於如何分解n。若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然後由公開的e，解出秘密的dRSA演算法編制

參數T={N}；私鑰SK=D；公鑰PK=E；設：明文M，密文C，那麼：用公鑰作業：MEmodN=C

用私鑰作業：CDmodN=MRSA演算法舉例設p=7,q=17,n=7*17=119;參數T={n=119};φ(n)=(7-1)(17-1)=96;選擇e=5,gcd(5,96)=1;公鑰pk=5;計算d,(d*e)mod96=1;d=77;私鑰sk=77;設:明文m=19

加密：（19）5mod119=66

脫密：（66）77mod119=19RSA演算法的安全性分析密碼分析者攻擊RSA體制的關鍵點在於如何分解n若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然後由公開的e，解出秘密的d若使RSA安全，p與q必為足夠大的素數，使分析者沒有辦法在多項式時間內將n分解出來

n取1024位或取2048位，這樣p、q就應該取512位和1024位。RSA演算法的安全性分析建議選擇p和q大約是100位的十進位素數模n的長度要求至少是512比特EDI攻擊標準使用的RSA演算法中規定n的長度為512至1024比特位之間，但必須是128的倍數國際數字簽名標準ISO/IEC9796中規定n的長度位512比特位

如果用MIPS年表示每秒鐘執行一百萬條指令的電腦計算一年時間的計算量，下表給出了不同比特的整數的因數分解所需的時間。

密鑰大小MIPS年512比特768比特1024比特2048比特RSA演算法的安全性分析

為了抵抗現有的整數分解演算法，對RSA模n的素因數p和q還有如下要求（即是強素數）：

(1)p-1和q-1分別含有大素因數p1和q1(2)P1-1和q1-1分別含有大素因數p2和q2(3)p+1和q+1分別含有大素因數p3和q3RSA演算法的安全性分析其他參數的選擇要求：(1)|p-q|很大，通常p和q的長度相同；(2)p-1和q-1的最大公因數要小；(3)e的選擇；(4)d的選擇；(5)不要許多的用戶共用一個n。不動點分析

定義如果

則稱m為RSA的一個不動點。