作者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