作者LPH66 (-858993460)
看板Prob_Solve
標題Re: [問題] RSA 的 金鑰條件
時間Tue Jun 21 23:59:04 2011
※ 引述《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
1F：→ LPH66:順帶一提, 這個 Carmichael 正是數論裡 Carmichael number 06/22 00:01
2F：→ LPH66:的那個 Robert D. Carmichael 06/22 00:02
3F：推 Favonia:應該說他的定義是「最小正整數 m 使得 a^m=1 (mod n) 吧」 06/22 00:36
4F：→ Favonia:嗯我的意思是說遞迴式比較像是推導出來的 xD 06/22 00:37
5F：推 Favonia:對了我突然想到，大數相乘也要 nlgn 呀 xDDDDDD 06/22 02:38
6F：→ LPH66:做一次乘和做O(log n)次除還是有差吧 XD 06/22 03:02
7F：推 Favonia:喔是沒錯啦... // 乘法位元複雜度O(nlgnlglgn) 06/22 08:01
8F：推 suhorng:推 06/22 08:30