Re: [問題] RSA加解密程式
※ 引述《BombCat (炸彈貓)》之銘言：
: 各位版大好，原PO最近在書上看到RSA的介紹並參考網路資料
: C, M, D, E 為正整數, P和Q為質數
: M為要加密的數字, C則是加密後的數字
: RSA加密公式: C = M^E % (P*Q)
: RSA解密公式: M = C^D % (P*Q)
: 並且 D*E % ((P-1)*(Q-1)) = 1
: 寫了一個RSA加解密程式，在P與Q都不大時，可以加解密運作正常。
: http://ideone.com/AM70Ot
: 但是，當P和Q都是六位數左右時，就沒辦法運作正常了
: 感覺是overflow，但是後來全部用 unsigned long long 還是一樣的結果
: 看了一兩天還是不知道問題在哪
: 不知道有沒有版大有寫過或是有類似經驗可以提點，感謝!
: 目前沒有打算要用大數運算來寫，只是希望做個64bit的RSA
編輯：
剛想了一下，假設算式是對的。
I = (I * I) % (P * Q)
return I % (P * Q);
在P有6位，Q有6位的情況下，餘可以為11位
11位乘以11位最高到22位
long long頂多20位，怎麼看都不太夠。
---------------------------------------------
可以上網查詢bigmod的寫法。
簡單地說，
I = (I * I) % (P * Q)
^^^^^^^^^
可以寫成I =(Ｉ%(P*Q)) * (I % (P * Q)) % (P * Q)
long long結果可以容納P 5位, Q 5位
http://ideone.com/DpRAIU
供參考
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1409613113.A.710.html
※ 編輯: bleed1979 (220.135.203.156), 09/02/2014 07:32:27
→
09/02 11:47, , 1F
09/02 11:47, 1F
→
09/02 11:49, , 2F
09/02 11:49, 2F
→
09/02 11:53, , 3F
09/02 11:53, 3F
→
09/02 11:54, , 4F
09/02 11:54, 4F
→
09/02 19:53, , 5F
09/02 19:53, 5F
推
09/02 19:56, , 6F
09/02 19:56, 6F
→
09/02 20:15, , 7F
09/02 20:15, 7F
→
09/02 20:16, , 8F
09/02 20:16, 8F
推
09/03 08:02, , 9F
09/03 08:02, 9F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章