PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間13年前 (2011/06/21 23:59)推噓4(4推 0噓 4→)

留言8則, 3人參與討論串2/2 (看更多)

※ 引述《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

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

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