第一章信息安全概述-RSA算法實現(xiàn)的幾個問題計算機系統(tǒng)與網(wǎng)絡(luò)安全技術(shù)實現(xiàn)要求若使RSA安全，p與q必為足夠大的素數(shù)建議選擇p和q大約是100位的十進制素數(shù)。模n的長度要求至少是512比特。電子數(shù)據(jù)交換(EDI)標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特之間，但必須是128的倍數(shù)。國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC9796中規(guī)定n的長度位512比特。問題1：RSA實現(xiàn)對大素數(shù)p和q的要求RSA算法實現(xiàn)的幾個問題信息安全概述用戶密鑰生成問題：使用RSA算法的用戶必須決定以下數(shù)據(jù):隨機選擇兩個大素數(shù)p,q選擇e并計算d素數(shù)p,q必須不易通過模數(shù)

N=p.q計算得到必須足夠大采用概率猜測測試方法來生成指數(shù)e,d是互逆，因此可以通過互逆算法來計算問題2：對RSA的實現(xiàn)要求-密鑰要求RSA算法實現(xiàn)的幾個問題信息安全概述為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長度相同；(2)p-1和q-1分別含有大素因子p1和q1(3)P1-1和q1-1分別含有大素因子p2和q2(4)p+1和q+1分別含有大素因子p3和q3問題3：對RSA的實現(xiàn)要求-模數(shù)n的要求RSA算法實現(xiàn)的幾個問題信息安全概述為了提高加密速度，通常取e為特定的小整數(shù)如EDI國際標(biāo)準(zhǔn)中規(guī)定e＝216＋1ISO/IEC9796中甚至允許取e＝3e＝216＋1優(yōu)于e＝3之處在于它能夠抵抗對RSA的小加密指數(shù)攻擊問題4：對RSA的實現(xiàn)要求-e的選擇要求RSA算法實現(xiàn)的幾個問題信息安全概述

要點1：(axb)modn=[(amodn)x(bmodn)]modn]要點2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的問題：am m的二進制表示為bkbk-1…b0,

則m=2ic0;d1forikdownto0 doc2xc d(dd)modn ifbi=1 thencc+1 d(da)modnreturnd計算ammodnammodn=[

a(2i)]modn =

[a(2i)modn]問題5：如何計算abmodnRSA算法實現(xiàn)的幾個問題信息安全概述問題6：如何判定一個給定的整數(shù)是素數(shù)？目前還沒有一個高效的辦法，實際中應(yīng)用最多MillerandRabin算法1.令bkbk-1…b0

為(n-1)的二進制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素數(shù)FALSE:n可能是素數(shù)應(yīng)用：隨機選擇a<n,計算s次，如果每次都返回FALSE，則這時n是素數(shù)的概率為

(1-1/2s)WITNESS(a,n)判定n是否為素數(shù)，a是某些小于n的整數(shù)RSA算法實現(xiàn)的幾個問題信息安全概述

通常的辦法是隨機選取一個大的奇數(shù)，然后進行素性檢驗1.隨機選一個奇數(shù)n(如:可使用偽隨機數(shù)發(fā)生器)2.隨機選擇一個整數(shù)a<n3.執(zhí)行概率素數(shù)判定測試(如:用WITNESS(a,n)),如果n未測試通過,則拒絕數(shù)值n,轉(zhuǎn)向步驟14.如果n已通過足夠的測試,則接受n,否則轉(zhuǎn)向步驟2;說明：

①隨機選取大約用

ln(N)/2的次數(shù)，如ln(2200)/2=70

②好在生成密鑰對時才用到，慢一點還可忍受。

③確定素數(shù)p和q以后，只需選取e,滿足gcd(