破解rsa

密码学

简述

　　一开始，直接将密文丢入dec()中，运行得到如下截图：
　　
　　
　
　　果然斌头的作业不会这么简单，于是构造一个新的密文: C = $c \times2^e = (2\times m)^e$。对$C$进行解密，得到$2m$。最终除以$2$得到明文$m = 101$。
　　
　　

源代码

#include <iostream> 
#include <gmp.h> 
#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"; 
int main() 
{ 
    mpz_t e, n, c, tmp, M;
    mpz_init_set_str(e, e_str, 10);  //初始化
    mpz_init_set_str(n, N_str, 10);
    mpz_init_set_str(c, c_star_s, 10);
    mpz_init_set_str(tmp, "2", 10);
    mpz_powm(tmp, tmp, e, n);  //tmp = 2^e
    mpz_mul(c, c, tmp);  //c = c*2^e mod n
    mpz_mod(c, c, n);
    char *m2 = dec(c);  //对c*2^e = (2*m)^e解密 
    mpz_init_set_str(M, m2, 10); //M = 2*m = m2
    //求2的逆元
    mpz_set_str(tmp, "2", 10);
    mpz_t g,s,t;
    mpz_init(g);
    mpz_init(s);
    mpz_init(t);
    mpz_gcdext(g,s,t,tmp,n);  //tmp*s+ n*t = g = gcd(tmp,n)
    mpz_add(s,s,n);  //s = 2^(-1)               
    mpz_mod(s,s,n);
    //2m/2 = 2m*2^(-1)
    mpz_mul(M,M,s);
    mpz_mod(M,M,n);
    gmp_printf("m is %Zd\n", M);
    //清除变量
    mpz_clear(t);
    mpz_clear(g);
    mpz_clear(s);
    mpz_clear(e);
    mpz_clear(n);
    mpz_clear(c);
    mpz_clear(tmp);
    mpz_clear(M);
    return 0; 
}