RSA所含的數(shù)學(xué)方法

172542

RSA的加密于解密數(shù)學(xué)過(guò)程描述：
1.        愛(ài)麗絲挑選了兩個(gè)巨大的質(zhì)數(shù)p和q。這兩個(gè)質(zhì)數(shù)要非常龐大（越大越好），不過(guò)，為了方便說(shuō)明，我們假設(shè)愛(ài)麗絲所挑選的是p=17，q=11.這兩個(gè)數(shù)字必須保存好，不讓任何人知道。
2.        愛(ài)麗絲讓這兩個(gè)質(zhì)數(shù)相乘，得到另一個(gè)數(shù)字N。本例中，N=187。她又再挑選一個(gè)數(shù)字e，假設(shè)e=7.[數(shù)字e和數(shù)字(p-1)和(q-1)必須互質(zhì)，也就是說(shuō)，它們不可以有共同的因數(shù)]
3.        愛(ài)麗絲把e和N公布在類(lèi)似電話(huà)簿的地方。這兩個(gè)數(shù)字是加密程序的要素，應(yīng)該讓任何想加密信息給愛(ài)麗絲的人都拿得到。這兩個(gè)數(shù)字一起，被稱(chēng)為公開(kāi)密鑰。(愛(ài)麗絲所選取的e值可以跟其他人的e值一樣，跟p和g有關(guān)的N值卻必須是獨(dú)一無(wú)二的。)
4.        加密信息時(shí)，必須先把信息轉(zhuǎn)換成一個(gè)數(shù)字M。例如，文字被轉(zhuǎn)成ASCII二進(jìn)制數(shù)(bits)時(shí)，我們可以把這些二進(jìn)制數(shù)字想成一個(gè)十進(jìn)制數(shù)字。根據(jù)以下公式，就可以把M加密成密碼文C：C=M^e(mod N)
5.        假設(shè)鮑勃想送給愛(ài)麗絲一個(gè)吻：就單單一個(gè)字母X。X的ASCII碼是1011000B換算成十，進(jìn)制就是88,。所以，M=88
6.        鮑勃查詢(xún)愛(ài)麗絲的公開(kāi)鑰匙，發(fā)現(xiàn)N=187,e7。這兩個(gè)數(shù)字等于提供了他加密信息給愛(ài)麗所需的公式。已知M=88，這個(gè)公式就變成
C=88^7(mod  187)
7.        用計(jì)算機(jī)算這個(gè)式子反而費(fèi)事，因?yàn)樗娘@示屏容不下這么大的數(shù)字。事實(shí)上，模算數(shù)的指數(shù)有一個(gè)計(jì)算技巧：88^7(mod 187)=[88^4(mod  187)x88^2(mod  187)x 88(mod 187)](mod 187)
鮑勃就把密碼文C=11寄送給愛(ài)麗絲。
8.        我們知道模算術(shù)里的指數(shù)函數(shù)是單向函數(shù)，要從C=11逆向求出原始信息M是非常困難的事情。所以，伊芙?jīng)]有方法破解這則信息。
9.        愛(ài)麗絲可以解譯這則信息，因?yàn)樗刑貏e的信息：她知道p和q的值。她會(huì)利用下面的公式計(jì)算出一個(gè)值d，它就是解密鑰匙，也就是她的私人鑰匙：
e x d=1(mod(p-1)x(q-1))
7 x d=1(mod 16x10)
7 x d=1(mod 160)
d=23 可以用歐幾里得演算求出
10.        愛(ài)麗絲利用以下公式解譯信息：
M=C^d(MOD 187)
M=11^23(MOD 187)
M=[11(MOD 187)X11^2(MOD 187)X11^4(NOD 187)X11^16(MOD 187)](MOD 187)
M=88=X(ASCII)

151308

看不懂，所以要收藏

154973

感謝分享

171120

感謝分享

118773

感謝分享

172220

看懂了 感謝分享

157094

謝謝

81845

也就是常說(shuō)的PKC公鑰密碼學(xué)最常用的方法。主要涉及到大數(shù)分解質(zhì)因數(shù)，快速冪取模算法，輾轉(zhuǎn)相除法。

87447

厲害了

138101

感謝分享