（2）：n = p * q 然后隨機選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互質。
檢查兩數是否互質的方法：檢查兩數的公約數以gcd是否為l，若是，則兩數互素。根據歐幾里德算法，如果a為n+c，則a和b的gCd等于b和C的gcd，即gcd(a，b)=gcdb(，c)，因此，gdc(a，b)可用每次運算的余數去除該運
算的除數來計算，這樣可以逐漸減少參加運算的操作數的數值，最后的非零余數即為公約。
如對40，31是否互素進行判斷，即計算gcd(40，31)。
第一次運算:40=31*l+9，即40/31的余數為9;
第二次運算:31=9*3+4，即31/9的余數為4;
第三次運算:9一*42+1，即9/4的余數為1。
因此，gcd(40，31)=1，40與31互素。
上述算法即使對根大的整數，也只需要不多的步驟即可得到結果。
（3）：利用歐幾里德定理計算解密密鑰d, 滿足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) ，即ed的相乘值與( p - 1 ) * ( q - 1 ) 互質。
其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，與私鑰不同的是不僅需要保密，而且應該丟棄，不要讓任何人知道。
編碼過程是,若資料為a,化為二進制數表示,首先把m分成等長數據塊 m1 ,m2,..., mi ，塊長s，其中 2^s = n, s 盡可能的大。對應的密文是：
ci = mi^e ( mod n ) －－－－－－－－－－－－－( a )
解密時作如下計算：
mi = ci^d ( mod n ) －－－－－－－－－－－－－( b )
RSA 可用于數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運算。
二、RSA 的安全性
RSA的安全性依賴于大數分解，但是否等同于大數分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數分解。假設存在一種無須分解大數的算法，那它肯定可以修改成為大數分解算法。目前， RSA 的一些變種算法已被證明等價于大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解多個十進制位的大素數。因此，模數n 必須選大一些，因具體適用情況而定。
三、RSA的速度
由于進行的都是大數計算，使得RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現。速度一直是RSA的缺陷。一般來說只用于少量數據加密。
加入技術交流群
評論