*RSA是非對稱加密體系,也就是說加密用壹個公鑰,解密用壹個私鑰,這2個密鑰不同,這點非常非常重要。
其實RSA非常簡潔,但很美
流程
1,尋找2個大的素數p,q n=p*q=33 N=(p-1)*(q-1)=20
公鑰e壹般是3 私鑰d要通過公鑰e去算出來
e*d=1(mod N) 就是說e和d的乘積模N得1 也就是e和d關於模N互為逆元
3*7=1(mod 20) 可知d=7
加密的明文設為M 加密後的密文設為c
加密過程:C=M^e(mod n)
解密過程:M=C^d(mod n)
舉個具體的例子 假如M=2
加密過程:C=2^3(mod 33)=8(mod 33)
解密過程:M=8^7(mod 33)=2097152(mod 33)=2(mod 33) 可以看出和和本來的明文是相同的。
原理可以理解為 M=M^(ed) (mod n)
本例中 e*d=21 也就是是M^21次方等於M
RSA這個特性是數論中的費馬定理推出的
在講講細節 比如樓主加密的是26的字母 就當明文的值是從1到26
就拿n=33說吧 加密後的密文的值是1到33 這很正常
但是解密後 壹定和明文的值相同 也就是1到26
實際情況中 公鑰e是公開的 私鑰d是保密的
比如甲要給乙發個東西 乙的公鑰由於是公開的 所以甲知道 但甲不知道乙的私鑰
甲先用乙的公鑰加密 之後 這個密文只能用乙的私鑰 由於乙的私鑰是保密的 只有他自己知道 所以保證了安全
RSA最大的安全問題是 n的分解 只要把n分解為p*q 則N=(p-1)(q-1)
根據 e*d=1(mod N) 就可以通過e算出d 那麽私鑰都被人算出來了 也就沒安全性而言了
不過可惜的是 大數分解是壹個單向的函數 妳算知道p,q算n很容易,但是知道n算出p,q相當難
強調壹句 n是加密解密用的 N是知道e算d的
樓主也沒說妳要幹嘛 想看懂就這麽多
如果要實現這個算法:
必須知道2點:
1.p,q這個兩個大素數的生成,這牽扯到素性檢驗,數論中是壹章的內容,沒法和妳展開
2.取模運算,由於加密解密過程可能取壹個數的幾十次方的模數,所以這個必須用簡便的算法來化解復雜度,也就是模重復平方算法。
如果要編程中使用,太容易了
去下個dll
在java中 直接有可用於RSA的類 相當容易
如果樓主想研究的更深 可以把郵箱 發我 RSA我以前做過壹個ppt