RSA加密原理

大整數(shù)因數(shù)分解困難問題

RSA算法就是利用大整數(shù)分解困難問題而設(shè)計 限門單向函數(shù)實(shí)現(xiàn)公鑰密碼算法

預(yù)備知識

質(zhì)數(shù)

互質(zhì)是公約數(shù)只有1的兩個整數(shù)，叫做互質(zhì)整數(shù)。

質(zhì)數(shù)是指在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)

歐拉函數(shù)

就是對于一個正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)的個數(shù)，記作φ(n)。

如果n=1，則 φ(1) = 1 。因?yàn)?與任何數(shù)（包括自身）都構(gòu)成互質(zhì)關(guān)系。

如果n是質(zhì)數(shù)，則 φ(n)=n-1 。因?yàn)橘|(zhì)數(shù)與小于它的每一個數(shù)，都構(gòu)成互質(zhì)關(guān)系。比如5與1、2、3、4都構(gòu)成互質(zhì)關(guān)系。

如果n=p*q，則φ(n)=φ(p)*φ(q)。更進(jìn)一步如果p與q都為素數(shù)，則φ(n)=（p-1）*(q-1)。

模反元素

如果兩個正整數(shù)e和φ(n)互質(zhì)，那么一定可以找到整數(shù)d，使得 ed-1 被φ(n)整除，或者說ed被φ(n)除的余數(shù)是1。這時，d就叫做e的“模反元素”。

edmodφ(n)=1

正式的算法加密步驟

① 選兩個安全的大素數(shù)p和q。

② 計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。

③ 選一整數(shù)e，滿足1<e<φ(n)，且gcd(φ(n),e)=1。

④ 計算d，滿足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運(yùn)算可知，它的乘法逆元一定存在。(一般公鑰取值為65537（216+1））

⑤ 以{e,n}為公開密鑰（PK）,{d,n}為秘密密鑰（SK）。

?

注意由e計算d需要使用p和q，但是密碼破譯者并不知道p和q，因此不可能通過和生成密鑰對時相同的計算方法來求出d。

對于RSA來說，有一點(diǎn)很重要，那就是質(zhì)數(shù)p和q不能被密碼破譯者知道。把p和q交給密碼破譯者與把私鑰交給密碼破譯者是等價的。

總結(jié)

以上是生活随笔為你收集整理的RSA算法加密流程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。