RSA所含的數學方法

172542

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

87447

厲害了

138101

感謝分享