
0x01 RSA加密简介
RSA的简介百度百科上已经讲的很清楚了,这里就简单的陈述一下,只要记住RSA中的几个点就好了。RSA的名字来源于其三位作者的名字首字符;RSA是一种非对称加密;RSA是一种公认的非常安全的公钥加密方式,我们长见的SSL协议采用的加密方式就是RSA非对称加密;RSA加密使用公钥,解密使用私钥,所以是非对称加密,公钥可由私钥生成。
在CTF中RSA其实是一类非常简单的送分题,只要掌握简单的数学原理和基本工具的使用,一般很容易计算出结果,长见的攻击方式有n爆破攻击、共模攻击、低指数攻击。具体讲解请看下文。
0x02 RSA加密基本概念
下面是RSA的基本元素和加密解密公式,后面我们将围绕该表进行讲解。
公钥 KU |
n:两素数p和q的乘积(p和q必须保密)。
e:与(p-1)(q-1)互质的数。 |
私钥 KR |
d: e^-1 mod (p-1)(q-1) 的结果
n:同上 |
加密 |
c = m^e mod n |
解密 |
m = c^d mod n |
我们只要记住六个字母m、c、p、q、n、e,其中m代表我们要加密的文明,c代表我们加密后的密文,p和q是我们随机找的大素数,n代表p和q的乘积称为模数,e是我们找到的和(p-1)(q-1)互质的数称为加密指数,可能到这里我们需要补充一下数学上的几个概念。
公钥(KU)由(n,e)组成,有了公钥我们就可以进行数据的加密。
私钥(KR)由(n,d)组成,有了私钥我们可以对密文进行数据解密。
0x03 RSA加、解密基本流程
- 随机选择一对足够大的素数p和q。
- 根据n = p*q计算出n的值,一般n非常大,p和q需要保密。
- 根据f(n) = (p-1)(q-1)计算出f(n)的结果。
- 找到一个和f(n)互质的数e,一般用65537(0x10001)。
- 根据ed ≡ 1 mod n我们可以计算出d的值。注意≡代表数论中的同余,如:1 mod n的结果为1那ed mod n的结果也必须是1。
- 加密明文m时使用(n,e)公钥,使用公式c = m^e mod n,如果c比较长,我们可以分割成适当的组,注意加密的时都是数学计算,文本需要转化为数字。
- 解密密文c时使用(n,d)私钥,使用公式m = c^d mod n。
从上面的流程中我们可以总结如下,我们的加密解密的关键点在于p和q,以及他们的乘积n,因为我们的加密需要使用n和e,因为e是非常容易拿到的,所以只要能根据n分解出p和q那么我们就能计算出d,然后拿到私钥对密文解密。
0x04 CTF中RSA的基本思路
其实在CTF中RSA还是非常简单的,通常就是那么几种攻击方式。
0x05 RSA直接求解
这种是最简单的,一般不会碰到,通常是给出参数p、q、e和密文c求解明文m,这种考法主要考察参赛选手对RSA加密解密公式的理解。直接使用工具解密即可,下面介绍一款工具:
RSA-tool
该工具为可视化工具,可以很方便的计算出RSA中的各项参数。[fanctdl filename=’RSA-Tool 2′ filesize=’57.5k’ href=’http://www.skycn.net/soft/appid/39911.html’ filedown=’RSA算法辅助工具’]http://www.skycn.net/soft/appid/39911.html[/fanctdl]
0x06 RSA模数n分解攻击
如果n不是特别大的情况下我们可以尝试使用工具暴力分解n拿到p和q,这里推荐几个工具: