文章轉自新浪博客@任家

正文：

RSA是第一個也是使用的最廣泛的公鑰加密算法，在1978年由R.Rivest、AdiShamir和Adleman三人發明，

并以他們的名字命名。RSA算法的安全性基于大數因子分解的困難性，下面介紹一下它的基本原理：

1、生成公鑰和私鑰

(1)選取兩個大素數：p和q；

(2)計算n=p*q；

(3)計算小于n并且與n互質的整數的個數，即歐拉函數?(n)=(p-1)*(q-1)；

(4)隨機選擇加密密鑰e，使1

(5)最后，利用Euclid(歐幾里得)算法計算解密密鑰d，使其滿足ed=1(mod ?(n))。

然后將(e，n)公開，即為公鑰PK，私人保存好d，即為私鑰SK；

2、加密

將明文m分解成等長數據塊m1，m2，……，mi。加密時，按如下公式進行計算即可：

ci=(mi)?e(mod n)，密文c則由c1，c2，……ci組成。

3、解密

與加密一樣，按如下公式進行計算：

mi=(ci)?d(mod n)，明文m則由m1，m2，……，mi組成。

以上就是RSA算法的公私鑰產生、加密和解密的過程。整個過程中，最難理解的部分應是1.5中的求私鑰d，

很多課本提到的都是用歐幾里得算法，但并未給出具體的計算過程

下面本人就通過一個實例向大家介紹歐幾里得算法在RSA中的應用。

例：令p=47，q=71，求用RSA算法加密的公鑰和私鑰。

計算如下：

(1)n=pq=47*71=3337；

(2)?(n)=(p-1)*(q-1)=46*70=3220；

(3)隨機選取e=79(滿足與3220互質的條件)；

(4)則私鑰d應該滿足：79*d mod 3220 = 1；

那么這個式子(4)如何解呢？這里就要用到歐幾里得算法(又稱輾轉相除法)，解法如下：

(a)式子(4)可以表示成79*d-3220*k=1(其中k為正整數)；

(b)將3220對79取模得到的余數60代替3220，則變為79*d-60*k=1；

(c)同理，將79對60取模得到的余數19代替79，則變為19*d-60*k=1；

(d)同理，將60對19取模得到的余數3代替60，則變為19*d-3*k=1；

(e)同理，將19對3取模得到的余數1代替19，則變為d-3*k=1；

當d的系數最后化為1時，(注：當k的系數先化為1時，令d=1，再帶入)

令k=0，代入(e)式中，得d=1；

將d=1代入(d)式，得k=6；

將k=6代入(c)式，得d=19；

將d=19代入(b)式，得k=25；

將k=25代入(a)式，得d=1019，這個值即我們要求的私鑰d的最終值。

此時，我們即可得到公鑰PK=(e，n)={79，3337}，私鑰SK={1019，3337}

后面的加密和解密直接套相應公式即可。

總結

以上是生活随笔為你收集整理的java实现rsa欧几里得算法求d_RSA算法中利用欧几里得算法求d详细过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。