【問題】RSA在C的寫法

[PichuChen 10]

老實說...我只是為了學大數運算而已

我先講一下RSA的演算法好了

1.確認密鑰長度

2.取p,q兩長度為密鑰長度一半的質數

3.設N=p*q,E=(p-1)(q-1)

4.取r,r>2,(r,E)=1 //(r和E互質)

5.取m r*m=1 (mod N) //(r*m除N餘1)

之後,私鑰為(r,N)

公鑰為(m,N)

加密方法

-----

(原始資料)^m mod N =加密資料

解密方法

-----

(加密資料)^r mod N =原始資料

-----------------------

以上....

用說的都很簡單

用做的.........

很刺激= ="

[TerryW 10]

就是大數運算的問題吧

先把+-*/做出來吧

[john0312 10]

用GMP又快又省事: http://gmplib.org/

不過說真的,大數運算真的是用組合語言(Assembly)寫快很多. 例如說,在做加法時,直接用ADD 指令,在檢查CF/OF,也不用檢查兩者之和是否大於2^32.

在做 (A^B) mod C 時,不要硬乘出來. 參考:http://en.wikipedia.org/wiki/Modular_exponentiation