※ 引述《Dreamlgw (嗫嚅)》之铭言： : 我们都知道 先选两个质数 P Q : N=P*Q : Thta= (P-1)(Q-1) : 取 e*d=1 mod Thta [其中 gcd(e,Thta) =1 ] : e d 是选一个为公钥 一个为私钥 : ----------------------------------------------------- : 今天我看到一个RSA : P=79 Q= 113 : n=79*113=8927 : Thta= 78*112=8763 : e=2621 d=5 : 这组RSA是 可以 加解密的 。 : 可是 e*d= 2621*5=13105 : 13105 % 8763 != 1 : ------------------------------------------------ : 这个RSA 演算法中的金钥 是不是有其他的条件满足就可以加解密了?? : 有人有研究吗??? 我们其实是想要使 a^(e*d) = a mod N 对所有 a 都成立 取 e*d = 1 mod φ(N) 是一招 (另外这个函数叫 phi function 不是 theta...) 另一招是把 phi function 换成 Carmichael function λ(N) 它定义为 λ(p1^e1 * p2^e2 * ... * pn^en) = LCM(λ(p1^e1), λ(p2^e2), ..., λ(pn^en)) = LCM(p1^(e1-1) * (p1-1), p2^(e2-1) * (p2-1), ... pn^(en-1) * (pn-1)) (在质数和质数次方它和 phi function 的值相同 其他情形里 phi function 是乘起来 这里是取最小公倍数) 在这个例子里 λ(8927) = LCM(λ(79),λ(113)) = LCM(78,112) = 4368 而你的 2621*5 = 13105 ≡ 1 (mod 4368) 能这样换的理由是这个 Carmichael function 有个类似尤拉定理的定理: 若 a < N 且 a 和 N 互质 则 a^λ(N) ≡ 1 (mod N) 所以用和 phi function 几乎一样的推理就能导出这是对的了 这个函数的相关资料可以看这里: http://en.wikipedia.org/wiki/Carmichael_function 实务上虽然使用 Carmichael function 会有更多组 e/d 的选择 但我们得要计算两个很大的数的 LCM 即使运用辗转相除法都很累 还不如直接乘起来比较快 所以 RSA 通常会取用 phi function 的原因在这里 -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.230.62