Re: [問題] RSA 的 金鑰條件

[LPH66 (-858993460)]

※ 引述《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
→ LPH66:順帶一提, 這個 Carmichael 正是數論裡 Carmichael number
→ LPH66:的那個 Robert D. Carmichael
推 Favonia:應該說他的定義是「最小正整數 m 使得 a^m=1 (mod n) 吧」
→ Favonia:嗯我的意思是說遞迴式比較像是推導出來的 xD
推 Favonia:對了我突然想到，大數相乘也要 nlgn 呀 xDDDDDD
→ LPH66:做一次乘和做O(log n)次除還是有差吧 XD
推 Favonia:喔是沒錯啦...            // 乘法位元複雜度O(nlgnlglgn)
推 suhorng:推