RSA

2016/10/09 网络

RSA是目前最有影响力的公钥加密算法,良好的RSA参数能够抵抗绝大多数的密码攻击。下面谈一谈RSA的工作原理以及如何用写代码实现RSA的过程。

RSA算法分别输出公钥(e,n),私钥(d,n),其中公钥是公开,而私钥是保密的。通信的过程理解为:

  1. A同学向B同学询问公钥。
  2. A同学得到了公钥,并且使用它加密得到密文C。
  3. A同学将密文C传送给B同学。
  4. B同学利用私钥解开密文得到明文M。

可以这么理解这个过程:

  1. A同学向B同学要了一把锁。
  2. A同学得到了锁,并且使用它将盒子锁起来。
  3. A同学将盒子传送给B同学。
  4. B同学用钥匙解开盒子。

RSA算法

  1. 找到两个大素数p、q。
  2. 计算n=p*q,f(n)=(p-1)(q-1)。
  3. 找到小于f(n)的e,满足gcd(e,f(n))=1。
  4. 计算d=e^-1 mod f(n)。

加密过程

C=M^e mod n

解密过程

M=C^d mod n

破解RSA的暴力方法

注意到上面的算法,要想破解RSA可以简单的对n进行因式分解。但是当n非常巨大的时候(1024bit以上),这个过程将变得十分困难,换言之RSA的安全性是建立在目前没有很好的方法可以快速分解长度足够长的模数n。

在一些CTF竞赛里面总是会出现1~2道RSA相关的题目,如果n小于256bit,可以本地直接破解,如果n小于768bit,可以尝试到factordb这个数据库里面查询有没有已经被分解过的结果,如果n的长度是2048bit,那么就需要从别的思路来进行破解了。

利用GMP库来实现RSA的过程

GMP库的好处是可以进行大整数的数学操作,参见下面的代码:

#include <gmp.h>
#include <time.h>
#include <iostream>

int main(){
    mpz_t p,q;
    mpz_t n;
    time_t seed;
    gmp_randstate_t state;

    time(&seed);
    mpz_init(p);
    mpz_init(q);
    mpz_init(n);
    gmp_randinit_default(state);
    //Initialize state with a default algorithm.
    //This will be a compromise between speed and randomness
    //and is recommended for applications with no special requirements.
    gmp_randseed_ui(state,long(seed));
    //set an initial seed value into state.

    mpz_urandomb(p,state,1024);
    mpz_urandomb(q,state,1024);
    if(mpz_even_p(p))
        mpz_add_ui(p,p,1);
    if(mpz_even_p(q))
        mpz_add_ui(q,q,1);

    while(mpz_probab_prime_p(p,30)==0)
        mpz_add_ui(p,p,2);
    while(mpz_probab_prime_p(q,30)==0)
        mpz_add_ui(q,q,2);

    mpz_mul(n,p,q);
    gmp_printf("n:%Zd\n",n);
    
    mpz_t e,f,d;
    mpz_init_set_ui(e,65537);
    mpz_init(f);
    mpz_init(d);

    mpz_sub_ui(p,p,1);
    mpz_sub_ui(q,q,1);
    mpz_mul(f,p,q);
    
    mpz_invert(d,e,f);
    gmp_printf("d:%Zd\n",d);

    return 0;
}

将代码保存为rsa.cpp,在终端执行

g++ rsa.cpp -o rsa -lgmp
./rsa

利用sageMath工具来进行大整数分解

下载sageMath工具,执行下面的代码

time print factor(数据)

time用于计算分解的时间。在我的Macbook Pro 2015上,分解280bit长度的模数n大约需要1小时。

题目

简单RSA 选择明文攻击 HCTF RSA签到题

Search

    Table of Contents