RSA加密演算法(20點)－jpjzhf9的部落格

標題:

RSA加密演算法(20點)

發問:

我們老師給我們出了一道超級課外補充題~~就是這個RSA老師上課有講過,可是我不認真聽......= =(最近迷上魔方)可不可以請你們幫我找出這題的私鑰?「公開兩質數29、31，及一數11與(29-1)(31-1)互質」還有,可不可以用很小的數字幫我舉個例子來解釋?直接用數字帶進去公式就好......也請詳細解釋!!!因為我只是升國一而已......最後......假如某數是三位數,那他的次方如果也是三位數,要怎麼用Excel算?我在A1打了"437"(舉例),在A2打"=A1^333"他都會跑出"#NUM!"要怎麼做~~20點唷~ 顯示更多我們老師給我們出了一道超級課外補充題~~就是這個RSA 老師上課有講過,可是我不認真聽......= =(最近迷上魔方) 可不可以請你們幫我找出這題的私鑰? 「公開兩質數29、31，及一數11與(29-1)(31-1)互質」還有,可不可以用很小的數字幫我舉個例子來解釋? 直接用數字帶進去公式就好......也請詳細解釋!!! 因為我只是升國一而已...... 最後......假如某數是三位數,那他的次方如果也是三位數,要怎麼用Excel算? 我在A1打了"437"(舉例),在A2打"=A1^333"他都會跑出"#NUM!" 要怎麼做~~ 20點唷~

最佳解答:

此文章來自奇摩知識+如有不便請留言告知

Q1: 原理:(1) a,φ(n)互質, 則 a^[φ(n)]≡1 (mod n) [Euler's thm.] (2) φ(29*31)=28*30=840 (3) 11*611≡1 (mod 840) (4) 若(C, 29*31)=1, 且C^11≡D (mod 29*31), 則D^611φ≡C (mod 29*31) 因D^611≡C^(11*611)≡C^[8φ(29*31)+1]≡C (mod 29*31) 註:國一生不必作這種問題 Q2: A1=437, A1^333數值大大,Excel顯示不出來 A1^333 mod 899的求法: 將333改為2進位數得101001101, 故可用Excel,遞迴式,求A1 mod 899, A1^4 mod 899, A1^8 mod 899, A1^64 mod 899, A1^256 mod 899,將這5數相乘,再mod 899即得註:A1=437, B1=mod(A1^2, 899), C1=mod(B1^2, 899), D1=mod(C1^2,899) E1=mod(D1^2, 899), F1=mod(E1^2, 899), G1=mod(F1^2, 899), I1=mod(G1^2,899), 則A1^333 mod 899 = mod(A1*C1*D1*G1*I1, 899) 2010-08-27 01:06:34 補充： 11x+840y=1, 則840y≡1 (mod 11) 4y≡1 (mod 11) 12y≡3 (mod 11), 則y≡3 (mod 11) 取y=3,代入11x+840y=1得x=-229 -229+ 840= 611 故11*611≡1 (mod 840)

其他解答:

真是謝謝Lotus囉~~ 我們老師有特別講過這個東西~~|||||候選編號 001 ...我覺得國一生還沒學mod.φ耶428DFA428D9FA6F8