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

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

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

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

a(2i)]modn =

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

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

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

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

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

①隨機(jī)選取大約用

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

②好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。

③確定素?cái)?shù)p和q以后，只需選取e,滿(mǎn)足gcd(