“再论RSA加密算法”

优美的数，自然的码

侦破数的逻辑

看透码的奥秘

RSA加密算法的算法结构是非常严谨的，具有良好的保密性和完整性。正确使用RSA加密算法，可以确保信息传输的安全性。但是根据现代密码学的研究和发现，RSA加密算法已经被攻破了。中国的王小云通过密码分析学的方法，破解了RSA加密算法。

而RSA加密算法在CTF比赛中的地位仍然是不容小视的，在CTF比赛中的密码学部分是经常出没。CTF的密码学题目往往是在考察参赛者对于密码学算法的理解，往往采用的是密码分析学的知识进行密码学破解。密码学经常使用的三个角色是Alice、Bob和Eva，这三个人往往是Alice和Bob在不安全的信道上进行传输信息，而Eva是在窃听不安全信道上面信息的窃听者。而CTF比赛中，参赛者往往就需要扮演Eva的角色，根据题目给到的信息进行密码破译，来获取到Flag。

说来说去，RSA加密算法，RSA加密算法其实就挺简单的，至少算法逻辑是比较简单的。但是在计算机的实际应用中，往往会有编码和其他各种加密的使用，进行综合性的安全性应用。RSA加密算法虽然是比较简单的算法过程，但是随着现代密码学的不断发展和进步，越来越多针对RSA加密算法的攻击方式，因而CTF也根据密码学研究是文献进行革新，演变出来了各种各样针对RSA攻击方法的破译算法。

CTF中RSA题目类型

CTF中常见的RSA题目类型有如下几类：^1^

公钥加密文

这是CTF中最常见最基础的题型，出题人会给你一个公钥文件（通常是以.pem或.pub结尾的文件）和密文（通常叫做flag.enc之类的），你需要分析公钥，提取出（N，e），通过各种攻击手段恢复私钥，然后去解密密文得到flag。

文本文档

对于第一种题型，耿直点的出题人直接给你一个txt文本文档，里面直接写出了（N，e，c）所对应的十进制数值，然后你直接拿去用就行了。当然也不都是给出（N，e，c）的值，有时还会给出其他一些参数，这时就需要思考，这题具体考察的什么攻击方法

pcap文件

有时出题人会给你一个流量包，你需要用wireshark等工具分析，然后根据流量包的通信信息，分析题目考察的攻击方法，你可以提取出所有你解题需要用到的参数，然后进行解密

本地脚本分析

题目会给你一个脚本和一段密文，一般为python编写，你需要逆向文件流程，分析脚本的加密过程，写出对应的解密脚本进行解密

远程脚本利用

这种题型一般难度较大。题目会给你一个运行在远程服务器上的python脚本和服务器地址，你需要分析脚本存在的漏洞，确定攻击算法，然后编写脚本与服务器交互，得到flag

密码学的题目类型也大致就是这些类型了，这些题目类型也展现出了密码学并不是孤立的存在，密码学与网络安全的各个方面都有着较大的联系，并彼此互联。

数据处理

CTF比赛中的CRYPTO题目类型往往会给到一些需要进行数据处理的文件格式：

基本上来说，RSA的题目都是围绕着c，m，e，d，n，p，q这几个参数展开的，但是题目一般不会直接给这种样子的参数，而是通过别的方式给出，这里就需要我们使用一些工具或者自己手工将这些参数提取出来。^2^

pem文件**：**针对此类文件可以直接使用openssl提取，大概使用过的方式有：

openssl   rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
openssl   rsa -pubin -text -modulus -in warmup -in public.pem

pcap文件：针对此类文件可以使用wireshark follow一下。这种问题一般都是写了一个交互的crypto系统，所以可能产生多轮交互。

PPC模式：这种模式是上述pcap文件的交互版，会给一个端口进行一些crypto的交互，参数会在交互中给出。

第二个需要处理的就是明密文，这个方法多多，不多赘述。

RSA加密算法的攻击类型

RSA加密算法题目的攻击类型是各种各样的，常见的攻击方法：

模数分解

解决RSA题目最简单，最暴力，最好使的方法就是分解模数n。如果能够将n分解成功，成功得到p，q的取值，那么可求n的欧拉函数的值。

模数分解往往可以使用多种方式进行分解，素数分解向来就是数学研究领域比较难以攻克的内容。而RSA算法的保密性也是由于素数分解的困难。但是有些简单的RSA题目可以使用素数分解的方法来解决，常用的工具有：foctordb，sagemath

低加密指数攻击

在RSA中e也称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是选取不当的话，就会造成安全问题。

e=3时的小明文攻击

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

即： $$ c\equiv; m^e ;mod; n $$

如果e=3，且 $ m^e<{n} $，那么：

$$ c= m^e,;e=3 $$

$$ m=sqrt[3]{c} $$

如果明文的三次方比n大，但是不是足够大，那么设k，有：

$$ c= m^e+kn $$

爆破k，如果$ c-kn $能开三次根式，那么可以直接得到明文。

低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。

即，选取了相同的加密指数e（这里取e=3），对相同的明文m进行了加密并进行了消息的传递，那么有：

$$ c_1\equiv m^e;mod ; n_1 $ $$ $$ c_2\equiv m^e;mod ; n_2 $ $$ $$ c_3\equiv m^e;mod;n_3 $$

对上述等式运用中国剩余定理，在e=3时，可以得到：

$$ c_x\equiv m^3;mod;n_1n_2n_3 $$

通过对 $ c_x $ 进行三次开方可以求得明文。

低解密指数攻击

与低加密指数相同，低解密指数可以加快解密的过程，但是者也带来了安全问题。Wiener表示如果满足：

$$ d<\frac{1}{3}g n^\frac{1}{4} $$

那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害RSA的安全。此时需要满足：

$$ q;<;p;<;2q $$

如果满足上述条件，通过Wiener Attack可以在多项式时间中分解n。

rsa-wiener-attack的攻击源码开源在了github中，采取python编写，可以很容易使用。

共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。

即：

$$ c_1\equiv m^{e_1};mod;n $$ $$ c_2\equiv m^{e_2};mod;n $$

此时不需要分解n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。

过程如下，首先两个加密指数互质，则：

$$ (e_1,e_2)=1 $$

即存在$ s_2 $，$ s_2 $使得：

$$ s_1e_1+s_2e_2=1 $$

又因为： $$ c_1 \equiv m^{e_1};mod;n $$ $$ c_2\equiv m^{e_2};mod;n $$

通过代入化简可以得出： $$ c_1^{s_1}c_2^{s_2}\equiv;m;mod;n $$

明文解出。

RSA的攻击方法肯定不止这五种，随着时代的发展和科技的进步，RSA加密算法被各种各样的破译算法进行攻破。而掌握这几种攻击算法，可以解决RSA题目中的大部分中等题目类型。比较难的题目，也就只能去多看看paper了。

参考

  1. CTF中RSA题型解题思路及技巧，附小白福利-FREEBUF
  2. 【技术分享】CTF中RSA的常见攻击方法-安全客

闲聊到此为止，来喝杯茶可好？