作者BombCat (炸彈貓)
看板C_and_CPP
標題[問題] RSA加解密程式
時間Tue Sep 2 05:51:24 2014
各位版大好，原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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.6.249
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1409608287.A.E21.html
※ 編輯: BombCat (36.239.6.249), 09/02/2014 05:56:18
推 EdisonX: (P-1)*(Q-1) 這裡 OV 了, 改 (P-1LL)*(Q-1LL) 試試 09/02 07:14
→ EdisonX: @@ 忽視上樓，我誤會 P Q 了 09/02 07:15
推 StarRoad: ExtendedGCD的return值從int改成long long? 09/02 12:04
→ StarRoad: 不然 if (A%B==0)return B 時，可能會出錯 09/02 12:05
謝謝E大和S大，我再改改看。
※ 編輯: BombCat (36.239.6.249), 09/02/2014 19:55:13