算法思想：
加密過程：c=M^e mod N。解密過程：M=c^d mod N觅丰。取c1=2^e mod N盖腕，將c和c1作為dec(*c)的參數，此時(c*c1)^d mod N=(2M)^(e*d) mod N并巍，又M^(e*d) mod n=M目木，那么(c*c1)^d mod N=2M。最后得到的2M還要判斷是否大于N懊渡。
代碼使用了大數gmp庫刽射。其中，所有大數都用mpz類型存儲剃执，用mpz_init_set_str(N,N_str,10)將字符串轉為mpz類型誓禁。此外，2^e mod N可用mpz_powm(c1,M,e,N)肾档；(c*c1)mod N可先用mpz_mul(ans,c,c1),后用mpz_mod(ans,ans,N)摹恰；判斷是2M否大于N可用mpz_cmp(x,N)。
主要代碼：
#include
#include
#include "dec.h"
using namespace std;
const char* N_str = "10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531469002933770824382865926730400902798743137187335810705309884635534159797732259520594337385186897629868362414475309001507719259272508669419676508606630823351242964205044695669333236417591";
const char* e_str = "10335071977839588495324343307012721241868030345867699233451500809021555989403028103743221782417440900848403102247012012875905268518785845678756696925714007988778268752026049276281025329038071087021446834856566687537729918372863729292015978809506607411711073716898691660211835403800810547133032654209857";
const char *c_star_s = "775789568255447714013247918834475198679653917741675336925599335265205597974556878796619688391490153400553690715156825186410083467239441867930362368759072824742512821423959166270736914130604102452801162684877374802075310241079026986641176079329871431448404341153307957496668749957011118721172866996397";
const char *m_text_s = "2";
mpz_t ans;
/*
//用于(a*b)mod c怒见，后來發(fā)現可以直接用gmp庫的乘法和取模函數得到結果俗慈。
void q_mul(mpz_t a,mpz_t b, mpz_t c){
mpz_init(ans);//初始化為0
mpz_t k;
mpz_init(k);
while(mpz_cmp_ui(b,0)){//判斷b是否大于0
mpz_mod_ui(k,b,2);
if(mpz_cmp_ui(k,0)){//判斷b&1是否大于0
mpz_sub_ui(b,b,1);//b減1
mpz_add(ans,ans,a);//ans=ans+a
mpz_mod(ans,ans,c);//ans=ans%c
}
mpz_cdiv_q_ui(b,b,2);//b=b/2
mpz_add(a,a,a);//a=a+a
mpz_mod(a,a,c);//a=a%c
}
}
*/
//g++ dec_rsa.cpp -o dec_rsa dec.o -lgmp
int main()
{
mpz_t N;
mpz_init_set_str(N,N_str,10);//將字符串N_str以十進制存儲到N
mpz_t e;
mpz_init_set_str(e,e_str,10);//將字符串e_str以十進制存儲到e
mpz_t c;
mpz_init_set_str(c,c_star_s,10);//將字符串c_star_s以十進制存儲到c
mpz_t M;
mpz_init_set_str(M,m_text_s,10);//將字符串m_text_s以十進制存儲到M
mpz_t c1;
mpz_init(c1);
mpz_powm(c1,M,e,N);//將c1賦值為(2^e)modN
mpz_mul(ans,c,c1);//ans=c*c1
mpz_mod(ans,ans,N);//ans=ans%N
mpz_t x;
mpz_init(x);
char *m = dec(ans); //access the dec oracle
mpz_init_set_str(x,m,10);//m為ans的解密結果,將字符串m以十進制存儲到x
if(mpz_cmp(x,N)==1)
cout<<"error!"<
else{
mpz_cdiv_q_ui(x,x,2);//x=x/2
gmp_printf("%Zd\n",x);//輸出x
}
return 0;
}
運行結果：
