转载请注明出处：http://www.jianshu.com/p/64dcc0133394
题目：
You are given an oracle-access to a function dec(c) that inverts the RSA N,d function: on input c it computes m = c^d mod N for all but one ciphertext. We call this ciphertext a challenge-ciphertext c∗. The parameters (N, e, d, c∗ ) are fixed. You’ll find all public parameters in the file ‘params.txt‘. Your task is to decrypt the challenge c∗ .
To accomplish the task you should follow the instruction below (Important! You will need to have the GMP library installed on your machine (www.gmplib.org):
Instructions (for Linux):
- Download the two files ‘dec.o’ and ‘dec.h’ from the web-page.
It provides the function
char∗ dec ( const char ∗ c_inp )
that returns the decryption of a ciphertext c_inp given as a string for fixed (N, d). You
can also provide a ciphertext of the GMP long int type by calling
char∗ dec ( mpz t ∗ c_inp )
- To use the above function, either create your own .cpp file and include ‘dec.h’ as a
header or download the template file ‘hw1.cpp’ from the web-site. To compile this .cpp
file with the ‘dec.o’ run in terminal
g++ hw1 . cpp dec . o −lgmp
Don’t forget to link it with the GMP library!
- As the result, you should get a .out file which you can then execute.
As this is an attack on a public key cryptosystem and you are given e, you should implement the corresponding encryption function by yourself. You should submit both the resulting
m = dec(c∗ ) and your code.
Instructions (for Windows):
Find a machine with Linux.
Follow the instructions above.
看了上面的题目，我们再来分析一下RSA破解的过程：
思路
基本的RSA算法容易受到选择密文攻击，选择密文攻击攻击RSA利用了RSA如下的性质：
E(PU,M1) × E(PU,M2) = E(PU,[M1 × M2)
利用选择密文攻击（CCA），可以用如下方式解密C=Memod n。
- 计算X = (C × 2e)mod n
- 将X作为选择明文提交，并收到Y = Xdmod n。
因此：
X = (C mod n) × (2e mod n) = (Me mod n) × (2 e mod n) = (2M)e mod n
因此：
Y = (2M) mod n
就这样，我们获得了M。
代码过程
#include <stdio.h>
#include <stdlib.h>
#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()
{
char *char_M;
mpz_t n,e,C,C_temp,c1,c2,M,m1,m2;
// n = N_str, e = e_str
mpz_init_set_str(n,N_str,10);
mpz_init_set_str(e,e_str,10);
mpz_init(C);
mpz_init(C_temp);
// c1 = c_str_s
mpz_init_set_str(c1,c_star_s,10);
mpz_init(c2);
mpz_init(M);
mpz_init(m1);
// m2 = m_text_s
mpz_init_set_str(m2,m_text_s,10);
/*The key arithmetic of program is CCA: E(PU,M1)*E(PU,M2)=E(PU,[M1*M2]) [See on the P208 of Textbook]*/
mpz_powm(c2,m2,e,n);// c2 = m2^e mod n, m2 = "2"
mpz_mul(C_temp,c1,c2);// C_temp = (c1 * c2)
mpz_mod(C,C_temp,n); // C = (C_temp)mod n = (c1 * c2)mod n = (c1 * 2^e)mod n
/*Access the dec(c_cipher) oracle providing by dec.h*/
char_M = dec(C);// char_M = dec(C) = (C^d)mod n
mpz_init_set_str(M,char_M,10);// M = char_M
mpz_divexact(m1,M,m2); // M = (m1 * m2)mod n ---> m1 is the result
// m1 is the result
gmp_printf ("The m of c_star_s is %Zd\n\n",m1);
// clean and exit
mpz_clear(n);
mpz_clear(e);
mpz_clear(C);
mpz_clear(C_temp);
mpz_clear(c1);
mpz_clear(c2);
mpz_clear(M);
mpz_clear(m1);
mpz_clear(m2);
return 0;
}
源代码及文件
链接: https://pan.baidu.com/s/1boWr3wr 密码: c7f4
