作者EvilBrave (醒醒吧 阿宅!!)
看板Army-Sir
標題Re: [問題] 計概問題 RSA密碼機制
時間Thu Jan 25 01:19:19 2007
※ 引述《ultra2 ()》之銘言：
: 在RSA密碼機制中
: 令p=5 q=11
: 隨機公開金鑰為e=7
: 則其所對應的私密金鑰d=多少
: 答案是23
: 請問怎麼來的@@
: 感恩
: 祝各位順利上榜
Q:
RSA
n = p * q
n = 5 * 11 = 55
公開金鑰 e = 7
求 d ?
A:
d * e ≡ 1 ( mod ∮(n) ) // RSA 求 d 方法
又 ∮(n) = ( 5 - 1 ) ( 11 - 1 ) = 40 // ∮(n) = 小於 n 與 n 互質個數
∴ d * 7 ≡ 1 ( mod 40 ) // 求 d 的反元素 mod 40
反元素求法請查 Google
7 *
23 - 40 * 4 = 1
∴ d = 23 ＃
有錯請鞭 ＝ ＝
--
┤┤┴┼┬┤┐└E
├V
┬I
┼L
┘├┴┬┬┤┤┴┼┬┤┐└└┼┬┘├┴┬┬┤┤┴┤┼
┼├┬┤└
╔═══╮╔═══╮╭═══╮╔═╗╔╗╔═══╗ ┬┬┬
┬┼
┼├┬
┴┼ ║ ═ ║║ ☆║║ ═ ║║ ╰╯║║ ═╣
┤┼├
┬┴
┘┬├
┤┬ ║ ═ ║║ ╔╮╯║ ╔╗║║ ║║ ═╣ ┼┬┘┐
┬
├┬┼
┐┘┼ ╚═══╯╚═╝╚╝╚═╝╚╝╰═══╯╚═══╝
├┼┬┐
┼┐
┤┐┬┼┤┼┬┤┼┘┼┬├┬┤├┬┤┐┬┼┤┼┬┤┼┘┼┬├┬┤┬├┤┐┬┼┤
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.213.54
1F：推 ultra2:很詳盡 感謝感謝 01/25 01:24
2F：推 EvilBrave:反元素求法可參考 Euclidean Algorithm XDD 01/25 01:28
3F：→ Nafusica:其實預官沒考過這麼難的題目... 01/25 01:33
4F：→ EvilBrave:我也是剛好有修到 密碼學 這門課才知道解法的 XDD 01/25 01:37
5F：推 PanScott:這的確是預官的題目呀~~三樓@@ 01/25 01:47
6F：→ sephyth:直接猜質數 01/28 15:46
7F：推 eric10529:這是92計概第38題 01/15 20:46