用大数实现RSA选择密文攻击

选择密文攻击（CCA）：攻击者选择一些密文，并获得相应的明文，这些明文是利用目标对象的私钥解密获得的。
利用RSA的性质：E（PU,M1）* E（PU,M2）=E（PU,[M1M2]）
利用CCA攻击，可以用如下方式解密C=M^e mod n。
（1）计算X=（C2^e）mod n
（2）将X作为选择明文提交，并收到Y=X^d mod n

注意到：X=(C mod n)(2^e mod n)=(M^e mod n)(2^e mod n)=(2M)^e mod n
因此，Y=（2M） mod n，由此得到M。

//dec.h
#ifndef DEC_H_INCLUDED 
#define DEC_H_INCLUDED 
#include <gmp.h> 
char* dec(mpz_t c); 
char* dec(const char *c_inp); 
#endif // DEC_H_INCLUDED 

#include<iostream>
#include"dec.h"
#include<gmp.h>
#include<gmpxx.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_class fun(const mpz_class exponent,const mpz_class base,const mpz_class n)//base^exponent%n
{
    mpz_class e,b,temp=1,remainder=0;
    e=exponent;b=base; 
   while(e>=1)
  {
        if(e==1)
       {
              remainder=(temp*b)%n;
              return remainder;//返回结果
       }
       else if(e%2==0)
      {
             e=e/2;
             b=(b*b)%n;
      }
      else if(e%2==1)
     {
            temp=(b*temp)%n;
            e=e-1;
     }
  }
}

当然可以不用这么麻烦自己写快速幂取模运算。可以用gmp库本身的函数。因为用的mpz_class，mpz_class所包装的函数较少（？在官方文档上找了c++ interface）,所以需要转换为mpz_t所包装的函数。

例：mpz_powm(ret.get_mpz_t()，m.get_mpz_t()，e.get_mpz_t()，n.get_mpz_t())

int main()
{
    mpz_class n(N_str,10);//10进制
    mpz_class e(e_str,10);
    mpz_class c_star(c_star_s,10);
    mpz_class m_text(m_text_s,10);
    mpz_class x,y,c_cipher;
    x=c_star%n;//x=c_star mod n
    y=fun(e,m_text,n);//y=2^e mod n
    c_cipher=(x*y)%n;//c_cipher=x*y mod n
    char *m = dec(c_cipher.get_str().data()); //access the dec oracle
    mpz_class mm(m,10);
    if(mm>n)//需要判断！
      cout<<"error"<<endl;
    else
    {
     mm=mm/2;
     cout<<"c*="<<c_star<<endl;
     cout<<"m="<<mm<<endl;
    }
    return 0;
}

在终端输入命令

g++ main.cpp dec.o -lgmpxx -lgmp -o main

./main