101專技網路 - 考試

※ 引述《pthread (QQ)》之銘言：
: 六、(一)簡述說明何謂 RSA？（5分）
: (二)假設兩質數 p=7 與 q = 11，請詳細說明如何利用 p、q 以 RSA 加密演算法對訊息
: 進行加密與解密動作，並舉例說明。（15分）
: n=7*11=77
: z=6*10=60
: 找到d與z互質
: 又找 (e*d) mod z =1
: 從(e*d) mod 60 =1 反推
: (e*d) = 61 or 121 or 181 or ....
: 根本很難求出 e跟d
: 考試如果遇到很難算
: 有人有別的求解方法嗎?
我的筆記 http://gotonsb-numbertheory.blogspot.tw/2014/04/rsa.html

我用跟你一樣的符號。

步驟一、取兩質數 p=7，q=11

步驟二、計算p與q的乘積n。n=pxq=7x11=77

步驟三、計算n的euler phi function值。z=φ(n)=φ(pq)=φ(p)φ(q)=6x10=60

步驟四、在1~60中選一數e，其中gcd(e,60)=1。假設取11好了，所以e=11

步驟五、計算11對於60的模反元素d。 寫成式子就是 11d≡1 (mod 60)

我們可以用歐基里德原理(輾轉相除法)求出d

首先，先把式子改寫成 11d+60f=1，其中f是整數。

利用輾轉相除法，得到 60=11x5+5、11=5x2+1 兩式 (礙於版面關係我寫成橫式)

兩式整理合併後，得到 11x11+60x(-2)=1。 所以d就是11


至於後續加解密的動作我就不寫了。

--