第一次運算:40=31*l+9，即40/31的余數(shù)為9;

第二次運算:31=9*3+4，即31/9的余數(shù)為4;

第三次運算:9一*42+1，即9/4的余數(shù)為1。

因此，gcd(40，31)=1，40與31互素。

上述算法即使對根大的整數(shù)，也只需要不多的步驟即可得到結(jié)果。

(3)：利用歐幾里德定理計算解密密鑰d, 滿足

e * d = 1 ( mod ( p – 1 ) * ( q – 1 ) ) ，即ed的相乘值與( p – 1 ) * ( q – 1 ) 互質(zhì)。

其中n和d也要互質(zhì)。數(shù)e和n是公鑰，d是私鑰。兩個素數(shù)p和q不再需要，與私鑰不同的是不僅需要保密，而且應(yīng)該丟棄，不要讓任何人知道。

編碼過程是, 若資料為 a, 化為二進(jìn)制數(shù)表示, 首先把m分成等長數(shù)據(jù)塊 m1 ,m2,…, mi ，塊長s，其中 2^s <= n, s 盡可能的大。對應(yīng)的密文是：

ci = mi^e ( mod n ) ————-( a )

解密時作如下計算：

mi = ci^d ( mod n ) ————-( b )

RSA 可用于數(shù)字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運算。

二、RSA 的安全性

RSA 的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前， RSA 的一些變種算法已被證明等價于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在，人們已能分解多個十進(jìn)制位的大素數(shù)。因此，模數(shù)n 必須選大一些，因具體適用情況而定。

三、RSA的速度

由于進(jìn)行的都是大數(shù)計算，使得RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。

huanghui