CTF中RSA加密的简单学习

2018年9月28日18:34:46 发表评论 2,169
摘要

本文讲述的是RSA加密的基本实现原理,以及其在CTF中基本题目的结题思路,附带解题脚本,可供新手学习入门,应付简单的RSA题目将不是难题。

CTF中RSA加密的简单学习

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)互质的数称为加密指数,可能到这里我们需要补充一下数学上的几个概念。

什么是素数?

素数(质数):一个数如果除了1和它本身外不能再被其他整数整除,那么这个数就是素数比如17。

什么是互质数?

互质数(互素数):公约数只有1的两个整数称为互质数比如13和17.

公钥(KU)由(n,e)组成,有了公钥我们就可以进行数据的加密。

私钥(KR)由(n,d)组成,有了私钥我们可以对密文进行数据解密。

0x03 RSA加、解密基本流程

  1. 随机选择一对足够大的素数p和q。
  2. 根据n = p*q计算出n的值,一般n非常大,p和q需要保密。
  3. 根据f(n) = (p-1)(q-1)计算出f(n)的结果。
  4. 找到一个和f(n)互质的数e,一般用65537(0x10001)。
  5. 根据ed ≡  1 mod n我们可以计算出d的值。注意≡代表数论中的同余,如:1 mod n的结果为1那ed mod n的结果也必须是1。
  6. 加密明文m时使用(n,e)公钥,使用公式c = m^e mod n,如果c比较长,我们可以分割成适当的组,注意加密的时都是数学计算,文本需要转化为数字。
  7. 解密密文c时使用(n,d)私钥,使用公式m = c^d mod n。

从上面的流程中我们可以总结如下,我们的加密解密的关键点在于p和q,以及他们的乘积n,因为我们的加密需要使用n和e,因为e是非常容易拿到的,所以只要能根据n分解出p和q那么我们就能计算出d,然后拿到私钥对密文解密。

0x04 CTF中RSA的基本思路

其实在CTF中RSA还是非常简单的,通常就是那么几种攻击方式。

  • 直接求解
  • 模数n分解
  • 共享素数攻击
  • 共模攻击

0x05 RSA直接求解

这种是最简单的,一般不会碰到,通常是给出参数p、q、e和密文c求解明文m,这种考法主要考察参赛选手对RSA加密解密公式的理解。直接使用工具解密即可,下面介绍一款工具:

CTF中RSA加密的简单学习

RSA-tool

该工具为可视化工具,可以很方便的计算出RSA中的各项参数。

0x06 RSA模数n分解攻击

如果n不是特别大的情况下我们可以尝试使用工具暴力分解n拿到p和q,这里推荐几个工具:

msieve

该工具是一款命令行工具,包含32和64两个版本,可以将n直接输入到命令行中,也可以在文件中读取,使用参数-v可以看到运行的详细信息。但当n较长的时候还是不适用。

yafu

这个就是神器了,就算n较长也是可以分解的(相对于msieve)而言个人感觉比较强大,非常推荐。

下面讲解一个简单的例子:

题目链接:http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

大括号中应该对应的是n和e,因为n不大,所以我们只需要分解出p和q即可求出密钥d。然后下面的每一行应该是一个密文,等我们拿到密钥,然后按行解密即可,下面是解题脚本。

运行结果如下:

CTF中RSA加密的简单学习

这道题目算是常规题了,题目中的n非常小,但是我们通常遇到的n因该是比较大的,普通的脚本跑出来是非常慢的,需要借助工具,但是本题就直接写了个小函数分解n了。

还有一类题目也是类似分解n的,只不过是采用了文件的形式,公钥和私钥都是文件,通常是key和pem为扩展名的文件。这类题目需要借助openssl工具分析出公钥中的n和e,然后套路就和上面差不多了,分解n,然后计算出私钥,但是要使写脚本自己生产私钥,并且解密密文文件也需要openssl命令来执行,下面介绍一下这个流程的命令和脚本。

假如有一个公钥文件public.pem,密文文件flag.enc

使用下面的命令分析公钥:

运行结果中将拿到n值和加密指数e

如果n不大,我们可以使用工具yafu分解n,命令如下

我们到这里已经拿到了p和q的值,下面我们来生产私钥文件,脚本如下:

请自行修改脚本中的p、q、e的值,我们将拿到私钥文件private.pem,下一步将进行解密,命令如下:

此命令的含义是采用私钥文件private.pem来解密文件flag.enc,结果保存到flag.txt中,到此位置,我们就完整的解出了这道题目。如需要题目文件请留言。

0x07 RSA共享素数攻击

这类题目其实还不是很常见,但也简单的介绍一下。当我们生成p和q的时候,难免有重复的,比如我们使用了p、q1和p、q2生成了n1和n2,就可以说我们的q被n1和n2共享了,如果我们能拿到这两个n,那么我们很容易就可以得到q1和q2,为什么呢?因为我们可以使用最大公约数gcd算法很快的计算出q,那么q1和q2也就很容易计算出来了,后面就不用再说了,直接计算d然后用私钥解密即可。

0x08 RSA共模攻击

这种攻击方式还是很常见了,该攻击的基本条件如下:

  • 同一份明文m使用不同的秘钥加密了两次
  • 两次生成秘钥时模数n相同但加密指数e不相同
  • 我们能拿到两个不同的密文c1、c2和模数n、加密指数n1、n2

在满足上面条件的情况下我们可以在不用获得秘钥d的情况下解密出明文m,基本的数学原理这里不做赘述,可自行百度研究,下面直接给出解密脚本。

脚本来自互联网,非原创并未测试,若有问题还请留言。

0x09 RSA低加密指数攻击

所谓低加密指数指的就是e非常小的情况下,通常为3,再CTF中也是有可能出现着用题目的,这种题目通常有两种类型,一种直接爆破,另外一种是低指数广播攻击。

首先介绍比较简单的情况,比如我们的e为3,n很淡,但是明文缺很小。这种情况下回出现什么呢?我们先看一下加密公式:c = m^e mod n , 当我们的 m^e < n 的情况下 c将等于m^e ,又因为e很小,所以我们可以直接对c开方求得明文m。

上面说的是m^e < n 的情况,那如果m^e > n 呢? 注意 m^e不能太大,否则将很难爆破。我们可以尝试进行爆破,假设我们 m^e / n 商 k 余数为c ,这里的k就是我们的商了,c就是模值,所已m^e =n*k+c , 我们可以对k进行爆破然,只要n*k+c的结果可以开方就可以求得明文m。

0x0A RSA低加密指数广播攻击

首先介绍什么是广播,加入我们需要将一份明文进行多份加密,但是每份使用不同的密钥,密钥中的模数n不同但指数e相同且很小,我们只要拿到多份密文和对应的n就可以利用中国剩余定理进行解密。关于中国剩余定理请参考文章:点击查看

只要满足一下情况,我们便可以考虑使用低加密指数广播攻击:

  • 加密指数e非常小
  • 一份明文使用不同的模数n,相同的加密指数e进行多次加密
  • 可以拿到每一份加密后的密文和对应的模数n、加密指数e

攻击脚本如下:

ps:以上脚本来自互联网,使用时请自行修改脚本中的参数。

运行结果如下图:

CTF中RSA加密的简单学习

文件下载

  • A+
所属分类:CTF

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: