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

172542

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

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

87447

厲害了

138101

感謝分享