Re: [問題] RSA 的 金鑰條件
※ 引述《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
→
06/22 00:01, , 1F
06/22 00:01, 1F
→
06/22 00:02, , 2F
06/22 00:02, 2F
推
06/22 00:36, , 3F
06/22 00:36, 3F
→
06/22 00:37, , 4F
06/22 00:37, 4F
推
06/22 02:38, , 5F
06/22 02:38, 5F
→
06/22 03:02, , 6F
06/22 03:02, 6F
推
06/22 08:01, , 7F
06/22 08:01, 7F
推
06/22 08:30, , 8F
06/22 08:30, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：