sa算法及安全性分析

1、rsa rsa 算法及安全性分析算法及安全性分析 euler 函數(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 對(duì)對(duì)n=pq, p和和q 是素?cái)?shù)，是素?cái)?shù)，(n)=(p)(q)=(p-1)(q-1) euler 函數(shù)函數(shù)舉例舉例 設(shè)設(shè)p=3, q=5, 那么那么 （15）=（3-1）* *

2、（5-1）=8 這這8個(gè)模個(gè)模15的剩余類是的剩余類是： 1，2，4，7，8，11，13，14 euler定理、定理、fermat定理定理 oeuler定理：定理：設(shè)設(shè) x 和和 n 都是正整數(shù)，如果都是正整數(shù)，如果 gcd(x，n)1，則，則 x (n)1 (mod n). ofermat定理定理:設(shè)設(shè) x 和和 p 都是正整數(shù)，如果都是正整數(shù)，如果 gcd(x，p)1，則，則 x p-11 (mod p). rsa算法的實(shí)現(xiàn)算法的實(shí)現(xiàn) 實(shí)現(xiàn)的步驟如下：實(shí)現(xiàn)的步驟如下：bob為實(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

3、)=(p-1)(q-1) (3) bob選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)e (0e (n)，滿足，滿足(e,(n)=1 (4) bob使用輾轉(zhuǎn)相除法計(jì)算使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod(n) (5) bob在目錄中公開(kāi)在目錄中公開(kāi)n和和e作為公鑰作為公鑰 密碼分析者攻擊密碼分析者攻擊rsa體制的關(guān)鍵點(diǎn)在于如何分解體制的關(guān)鍵點(diǎn)在于如何分解n。若分。若分 解成功使解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后由公，然后由公 開(kāi)的開(kāi)的e，解出秘密的，解出秘密的d rsa算法編制算法編制 參數(shù)參數(shù)t=nt=n； 私鑰私鑰sk=dsk=d； 公鑰公鑰pk=epk=e； 設(shè)：明文

4、設(shè)：明文m m，密文，密文c c，那么：，那么： 用公鑰作業(yè)：用公鑰作業(yè)：m me e mod n = c mod n = c 用私鑰作業(yè)：用私鑰作業(yè)：c cd d mod n = m mod n = m rsa算法舉例算法舉例 rsa算法的安全性分析算法的安全性分析 密碼分析者攻擊密碼分析者攻擊rsa體制的關(guān)鍵點(diǎn)在于如何分解體制的關(guān)鍵點(diǎn)在于如何分解n 若分解成功使若分解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)， 然后由公開(kāi)的然后由公開(kāi)的e，解出秘密的，解出秘密的d 若使若使rsa安全，安全，p與與q必為足夠大的素?cái)?shù)，使分析者必為足夠大的素?cái)?shù)，使分析者 沒(méi)有辦法在多項(xiàng)式

5、時(shí)間內(nèi)將沒(méi)有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來(lái)分解出來(lái) 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的長(zhǎng)度要求至少是的長(zhǎng)度要求至少是512比特比特 edi攻擊標(biāo)準(zhǔn)使用的攻擊標(biāo)準(zhǔn)使用的rsa算法中規(guī)定算法中規(guī)定n的長(zhǎng)度為的長(zhǎng)度為512至至 1024比特位之間，但必須是比特位之間，但必須是128的倍數(shù)的倍數(shù) 國(guó)際數(shù)字簽名標(biāo)準(zhǔn)國(guó)際數(shù)字簽名標(biāo)準(zhǔn)iso/iec 9796中規(guī)定中規(guī)定n的長(zhǎng)度位的長(zhǎng)度位512比比 特位特位 如果用如果

6、用mips年表示每秒鐘執(zhí)行一百萬(wàn)條指令年表示每秒鐘執(zhí)行一百萬(wàn)條指令 的計(jì)算機(jī)計(jì)算一年時(shí)間的計(jì)算量，下表給出了不同的計(jì)算機(jī)計(jì)算一年時(shí)間的計(jì)算量，下表給出了不同 比特的整數(shù)的因子分解所需的時(shí)間。比特的整數(shù)的因子分解所需的時(shí)間。 密鑰大小 mips年 512比特 768比特 1024比特 2048比特 4 3 10 8 2 10 11 3 10 20 3 10 rsa算法的安全性分析算法的安全性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)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和和q3 rsa算法的安全性分析算法的安全性分析 其它參數(shù)的選擇要求：其它參數(shù)的選擇要求： (1) |p-q|很大，通常很大，通常 p和和q的長(zhǎng)度相同；的長(zhǎng)度相同； (2)p-1和和q-1的最大公因子要?。坏淖畲蠊蜃右。?(3)e的選擇；的選擇； (4)d的選擇；的選擇； (5)不要許多的用戶共用一個(gè)不要許多的用戶共用一個(gè)n。 定義定義 如果如果 mod e mnm 則稱則稱 m