• 欢迎访问惜文个人博客
  • 本博客最新公告:本站已经支持使用QQ和GitHub帐号快捷登录啦!
  • 访问本站建议使用火狐和谷歌浏览器哦!
  • 不知道要写什么哈哈
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏惜文博客吧
  • 源码模板插件免费下载,传送门:点我去看看传说中的安全之家!

CTF中RSA加密的简单学习

胡乱捣腾 惜 文 1年前 (2018-10-28) 1230次浏览 0个评论 扫描二维码

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较长的时候还是不适用。下载Msieve

yafu

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

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

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

 

{920139713,19}
 
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
......
......

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

#coding:utf-8

def crackN(n):
i = 2
while i < n :
if n % i == 0:
break
i = i+1
return i

n = 920139713
e = 19

p = crackN(n)
q = n / p

fn = (p-1)*(q-1)

i = 1
d = 0
while (True):
if (fn * i +1) % e == 0 :
d = (fn * i +1) / e
break
i = i+1

print "d:%s" % d

c = open("c.txt")
m = ''
for line  in c:
line = line.replace('\n','')
m += chr(pow(int(line), d , n))
print m

运行结果如下:

CTF中RSA加密的简单学习

 

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

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

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

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

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

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

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

import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 0xD7DB8F68BCEC6D7684B37201385D298B
keypair.q = 0xC292A272E8339B145D9DF674B9A875D5
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
    x = (Qn * i ) + 1
    if (x % keypair.e == 0):
        keypair.d = x / keypair.e
        break
    i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

请自行修改脚本中的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,基本的数学原理这里不做赘述,可自行百度研究,下面直接给出解密脚本。

#coding=utf-8
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def main():
n = int(raw_input("input n:"))
c1 = int(raw_input("input c1:"))
c2 = int(raw_input("input c2:"))
e1 = int(raw_input("input e1:"))
e2 = int(raw_input("input e2:"))
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m = (c1**s1)*(c2**s2)%n
print m
if __name__ == '__main__':
main()

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

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加密的简单学习


惜文博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:CTF中RSA加密的简单学习
喜欢 (0)
[白白]
分享 (0)
惜 文
关于作者:
感觉自己萌萌哒,啦啦啦,个人说明也没啥可写
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址