Re: [考題] 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
至於後續加解密的動作我就不寫了。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.49.12
※ 文章網址: http://www.ptt.cc/bbs/Examination/M.1400231665.A.D7F.html
※ 編輯: loveann (140.122.49.12), 05/16/2014 17:18:02
討論串 (同標題文章)