RSA系列——實踐測試

01-29

本文將把筆者對RSA演算法簡單測試的過程進行敘述。

由於只是簡單測試，因此所有運算均在C++的long long範圍內，都不涉及高精度（python大佬請回吧）。

C++中long long的絕對值的範圍是 $2^{63}-1$ （約 $9times 10^{18}$ ），因此我只打了一個小質數表，隨便選了601和787兩個質數，他們的乘積 $n=472987$ ，生成的密鑰為 $(e=134743,n)$ ，公鑰為 $(d=7,n)$ 。

以下所有代碼中均有

typedef long long LL;nconst LL n=472987,e=134743,d=7;n

生成公鑰和密鑰的代碼很簡單，就不貼了。

以下是快速冪的代碼（只是為了說明我的代碼中這個函數的參數是什麼意思）。

LL fpow(LL a,LL b,LL p){ntLL c=1;ntwhile(b){nttif(b&1)c=c*a%p;ntta=a*a%p;nttb>>=1;nt}ntreturn c;n}n

以下是加密的代碼。其中的 $d$ 是公鑰的一部分。加密過程是將原文分為若干個長度為 $a$ 的字元串，再將字元串化為128進位的數（這是因為char只有1byte，並且還有符號）。這裡 $a=2$ 。加密之後的內容以若干個數呈現。注意：當最後一段長度不足 $a$ 時，用空格代替。

gets(s);nint len=strlen(s);nint a=2;n//freopen("codes.txt","w",stdout);nfor(int i=0;i<len;i+=a){ntLL cur=0;ntfor(int j=i+a-1;j>=i;j--)cur=(cur*128+(j>=len? :s[j]))%n;ntcout<<fpow(cur,d,n)<<endl;n}n

以下是解密的代碼。其中的 $e$ 是密鑰的一部分。

LL a;nwhile(cin>>a){nta=fpow(a,e,n);ntwhile(a)putchar(a%128),a/=128;n} nsystem("pause");n

測試：輸入"To be or not to be,that is a question."（不含引號），加密之後得到的數為：365681 1063 84079 30630 10377 74610 53833 67913 462632 38996 184533 73918 384841 51679 379868 83595 190323 338991 359932

再將這些數作為解密程序的輸入，再次得到了"To be or not to be,that is a question."，測試成功。