某CTF比赛题解析分享--RSA Roll

FoodieOnTheWay

看到论坛2016安全挑战赛的帖子，不由得觉得几分可惜。如果我早来半个月，这奖金不知道会不会有我一份呢  

话说回来，在前几天看到了另外一个CTF竞赛的加密题目，就试着分析了一下，结果竟然做出来了。在此，就跟着论坛上的帖子一块贴出来，供大家开阔一下思路。高手或者CTF常客可以飞过啦。


Ⅰ. 题目内容



附件里的数据如下：

[Visual Basic] 纯文本查看 复制代码

{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

看这情况，肯定是用RSA相关的算法解题了。


Ⅱ. 解题过程
第一步，我先假设19为私人密钥，直接用它来解密每个数据。（电视剧看了那么多，大家肯定能猜得到这个不奏效的，对吧{:1_912:}所以如果对RSA基础知识有了解的，可以跳过）
这里需要祭出一个加密解密常用的小工具：大整数计算器。我想信安专业的童鞋们大多都用过它，或者类似的吧。
此工具虽然体积不大，但是功能强大，信息行业常用的几种运算都被它集成在一起了，并且界面整洁，各种进制的切换也很方便。
如果大家参加CTF比赛，带上它绝对没错。因为只要不是说出题全部都是WEB的，经常都能用得到它。再说了，就那么100多k，比东京热什么之类的MV省地方多了，对吧？


我这里根据题目，在X这里输入数值，然后Y这里输入19（密钥），Z这里输入模数（920139713）。
然后如你们所料，得出的结果都是什么嘛，全是无规律的垃圾数据

这里再简单说下RSA，这个在学校时觉得巨复杂，巨烦的算法，在没工作前就一直没真正懂过，其实现在应用过后再看，也不算太复杂。
就好比电影中的天机锁，主人让手底下的人去取武林秘籍，给他一把公的钥匙（居然也真可以简称公钥），他把东西放好，然后用公钥锁到天机锁的箱子里，这时候锁芯结构发生变化，公的钥匙就没用了，而他带回去之后，主人就能用手中的母钥（类似私钥）把锁打开，取出秘籍。
RSA的公钥和私钥就是这样一对钥匙（都是解密人提前准备好的）。也就是说一般情况下，即便是公钥和信息都泄露了，信息还是安全的（跟我现在遇到的情况一样）。


第二步，找弱点攻破
上面说到了，一般情况下，公钥和信息都泄露了，信息还是安全的。那二版情况下，是不是就可以还原信息了呢？
上面还说了，公钥和母钥，哦，是私钥，他们是存在相关性的，所以才能实现公钥加密，私钥解密。
那么，我们就从“RSA的安全性依赖于大整数分解”这句话入手吧。
正常来说，一般生产环境中的RSA加密都是1024位（指密钥位数）或者更多位。而我们的这个模数只有几十位，那就意味着，两个质数的值其实不太大，而密钥长度也不长了。


那就分解这个模数吧。python代码如下：

[Python] 纯文本查看 复制代码

n = 2
while (n<920139713): 
    if (920139713%n == 0):
       print n,920139713/n
    n = n + 1

但是准备运行时，我发现这个数是能被3除掉的，那么稍微改下，提升一下运行效率（强迫症啊，强迫症 计算机性能这么好，说不定改一下的时间都不用，结果都出来了）

[Python] 纯文本查看 复制代码

n = 3
while (n<306713237): # 306713237 = 920139713/3
    if (920139713%n == 0):
        print n,920139713/n
    n = n + 1

这样会得到一对质数。
==================== RESTART: D:\Python27\MyPy\GetNum.py ====================
18443 49891
49891 18443


有了他们俩，那就可以得到模数的欧拉函数了，φ(n) = (p-1)(q-1)  值是(49891-1)*(18443-1) = 920071380。
一旦有了这个数，就可以根据 920071380x + 19y = 1 通过现成的代码得出私钥了。

[Python] 纯文本查看 复制代码

# 19x + 920071380y = 1
--------------------------------------------------------
def ext_euclid ( a , b ):
    if (b == 0):
        return 1, 0, a
    else:
        x , y , q = ext_euclid( b , a % b )
        x , y = y, ( x - (a // b) * y )
        return x, y, q
print ext_euclid(19, 920071380);

运行完，我们可以得到一组数，其中的96849619就是我们亲爱的私钥了。
==================== RESTART: D:\Python27\MyPy\GetPrivateKey.py ====================
(96849619, -2, 1)
>>>


好了，接下来就是奇迹到来的时刻了，我跑了前几个字符，分别是‘f’,'l','a','g'，我知道，这就是正解了。


解出来的数值如下：
-----------------------------
704796792        102
752211152        108
274704164    97
18414022      103
368270835    123
483295235 49
263072905 51
459788476 50
483295235 49
459788476 50
663551792 106
475206804 101
459788476 50
428313374 117
475206804 101
459788476 50
425392137 56
704796792 102
458265677 121
341524652 55
483295235 49
534149509 119
425392137 56
428313374 117
425392137 56
341524652 55
458265677 121
263072905 51
483295235 49
828509797 114
341524652 55
425392137 56
475206804 101
428313374 117
483295235 49
475206804 101
459788476 50
306220148 125

-------------------------
用Python解一下，就能看到flag了。

[Python] 纯文本查看 复制代码

chars = [102,108,97,103,123,49,51,50,49,50,106,101,50,117,101,50,56,102,121,55,49,119,56,117,56,55,121,51,49,114,55,56,101,117,49,101,50,125]
for char in chars:
    print chr(char)

也就是“flag{13212je2ue28fy71w8u87y31r78eu1e2}”

顺便安利一下UltraEdit和010Editor，对于我这样搞二进制的菜鸟，一般时候Notepad++就挺够用了，但是做加密解密时，如果有Ultra了Edit和010Editor，那简直是如鸟添翼啊，那16进制模式，不要太叼哟。
而且我的上一个帖子 [调试逆向] 修改ProcessMonitor过TMD壳反监测（1） 里就有用到它记录一些东西，并且还用了它的兄弟产品UltraCompare（简称UC）做了那个修改前后对比图呢，有些时候分析打了补丁前后对比也是行的。


Ⅲ. 知识梳理
刚刚我们成功的破解了一个27位RSA密钥加密的数据，叼炸天吧{:1_902:}。
虽然我们平时用的都是1024++位的RSA加密，但是这毕竟也算是破解了吧…………


说到1024位，其实理论上是能找到解的，但是“大整数”分解目前为止还是一个大难题，如果目前正在用的1024位加密直接通过计算机求解，不知道超级计算机得运行多少年才能拿到密钥？
不过目前已经有人破解了768位的加密（比起我，不知道高到哪里去了）。
或许100年之后，个人电脑都能解我们现在的密钥？？？想想还有点小担心自己的隐私呢

通过这次破解呢，我们应该能对RSA有点客观的认识了吧。
加密及解密的步骤大概如下：
1. 如果我要发条消息给心爱的姑娘，那么我就要提前跟她说好，让她找两个足够大的质数，这样才能保证私钥足够大，满足安全需求；
我们举一个不安全的例子，比如就11和13吧。那模数就是143。然后欧拉函数就是（11-1）*（13-1）= 120。

2. 她在1-120中随便挑一个数（一定的随机性，而且不是哪个都行的），当作公钥（实际情况中，需要保证私钥的长度，不能真的就任性的选一个哦）

[Python] 纯文本查看 复制代码

def ext_euclid ( a , b ):
    if (b == 0):
        return 1, 0, a
    else:
        x , y , q = ext_euclid( b , a % b )
        x , y = y, ( x - (a // b) * y )
    return x, y, q

def printvalue(a, b):
    print a, ext_euclid(a, b)

for p in range(2,119):
    printvalue(p, 120);

================= RESTART: D:\Python27\MyPy\OutPutprivateKeys.py =================
2 (1, 0, 2)
3 (1, 0, 3)
4 (1, 0, 4)
5 (1, 0, 5)
6 (1, 0, 6)
7 (-17, 1, 1)
8 (1, 0, 8)
9 (-13, 1, 3)
10 (1, 0, 10)
11 (11, -1, 1)
12 (1, 0, 12)
13 (37, -4, 1)
14 (-17, 2, 2)
15 (1, 0, 15)
16 (-7, 1, 8)
17 (-7, 1, 1)
18 (7, -1, 6)
19 (19, -3, 1)
20 (1, 0, 20)
…… 省略若干 ……
113 (17, -16, 1)
…… 省略若干 ……
118 (-1, 1, 2)
>>>

比如说她就选13吧（实际应用中通常是65537），那么根据“扩展欧几里得算法”，对应的私钥应该是37了。
3. 那么接下来她就可以把公钥给我，让我给她发加密消息了
比如我想给她发5，2，1，加密后的值应该是70,41,1。
4. 她收到后，就能用大整数计算器结合私钥和模数就能算出来（因为自定义的加密算法，哈哈）这个过程就是利用公钥和私钥的关联性，得到原数据。这三个数分别是5,2,1 。

===============================================
更多相关的文章，敬请参考：
【CFCA】用实例给新手讲解RSA加密算法 http://www.cfca.com.cn/zhishi/wz-012.htm
【CSDN】跨越千年的RSA算法  http://www.matrix67.com/blog/archives/5100
【故事】RSA 算法是如何诞生的 http://localhost-8080.com/2013/12/history-of-rsa/
【道客巴巴】RSA的小故事-真实性我不确定 http://www.doc88.com/p-3837768868063.html
增加一条修正链接时看到的，数论基础讲得很好，例子也挺好：RSA算法原理1 http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html  和 RSA算法原理2 http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

本篇文章中所用到的主要工具如下，能在网上找得到，有的爱盘就有，超级赞爱盘！！！
1. UltraEdit  (爱盘有)
2. 大整数计算器（看雪论坛上也有很多其他的，我刚才搜索到了不少） BigIntCalc.rar (61.58 KB, 下载次数: 166)

2016-4-21 01:19 上传

点击文件名下载附件
大整数计算器

3. Python2.7 （3.x其实也挺好的，一般的工作没啥问题，但是部分库不太兼容）
===============================================
其实开头说的在奖金里分一份羹纯粹是吹吹牛，大家不要戳破


还有就是，写东西真累，尤其是想让它稍微风趣一点，美观一点，1点了，去睡觉啦（逃

hancool

其实这道题还有一种更简单的思路。这题是4.29首都安全日预赛的一题，我只用了十几分钟。我的思路是这样的：
一、根据给的data.txt第一行数据：{920139713,19}，基本上可以猜测出来这是RSA的公钥，只要能成功分解素数，基本上可以“秒破”。现在问题来了：如何快速进行素数分解？
二、最快捷的方式是在在http://factordb.com， 直接得到结果：920139713 = 18443 * 49891
三、现在有了n、p、q、e，直接用RSA算法跑结果吧，得到flag{13212je2ue28fy71w8u87y31r78eu1e2}。代码如下：

[Asm] 纯文本查看 复制代码

#!/usr/bin/env python
#-*- coding: utf-8 -*-
from Crypto.Util.number import bytes_to_long, long_to_bytes

def egcd(a, b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
    return u


def get_d(p, n, e):
    q = n / p
    phi = (p - 1) * (q - 1)
    d = egcd(e, phi)
    if d < 0:
        d += phi
    return d

def main():
    n = 920139713
    p = 18443
    q = 49891
    e = 19

    data = []
    line_index = 1
    with open('data.txt') as f:
        while True :
            line = f.readline()
            if not line:
                break
            if line_index >2:  
                data.append(line.strip('\n'))
            line_index += 1
        print data
    flag = []
    for c in data:
        ct = int(c)
        d = get_d(p, n, e)
        pt = pow(ct, d, n)
        flag.append(long_to_bytes(pt))
    print ''.join(flag)

if __name__ == '__main__':
    main()

UNCLE

既然你们都说了 ，我就来凑凑热闹吧，当时我还是第一个做出来的诶
RSA Roll 原意是利用循环攻击解题，但是一般这种攻击都可以直接利用分解素数解出来。
循环攻击的方法就不说了，writeup上都有。
大家多多使用这个rsatools这个神器吧，非常给力。

为了方便不用修改进制，将右上角Number Base修改为10，修改E为13（这里必须为16进制）。
在倒数第二个框（N）输入N，这里输入920139713，点击Factor N，这个时候就开始了求质因数的过程。如果数字比较大，求的时间就会很长甚至一直都求不出来。
当求出来之后，再点击Calc D，就会计算出D来，这时破解已经完成，如果不确定就可以尝试点击test测试，Rsatool有个不太好的设计，必须要点击加密后才能使用解密。
首先任意加密一下，再将需要解密的内容输入进去点击解密，如图所示，
第一个数字解出来就是正确的f

RSA-Tool.rar (68.97 KB, 下载次数: 44)

2016-5-13 21:48 上传

点击文件名下载附件

Hmily

图片有个百度盗链了，上传到本地吧。

Sound

可以把那个盗链 上传到本地? 修改后 请@Sound 再进行主题 加亮 置顶 精华操作
@FoodieOnTheWay

www52pojiecn

写的挺好的，现在CTF竞赛好多，多参加才有新视野，谢谢分享

FoodieOnTheWay

Hmily 发表于 2016-4-21 11:30
图片有个百度盗链了，上传到本地吧。

是个表情图，我这边看着好好的 不过不重要，就删了吧

FoodieOnTheWay

Sound 发表于 2016-4-21 23:32
可以把那个盗链 上传到本地? 修改后 请@Sound 再进行主题 加亮 置顶 精华操作
@FoodieOnTheWay

Thanks, 那是个表情图，已删。顺手把几个链接修复了

FoodieOnTheWay

Sound 发表于 2016-4-21 23:32
可以把那个盗链 上传到本地? 修改后 请@Sound 再进行主题 加亮 置顶 精华操作
@FoodieOnTheWay

好吧，链接不知道怎么回事儿，编辑时ok，发出来就没了，只剩文字空余恨，是链接不支持中文么？

苏紫方璇

膜拜大牛  算法原理完全不懂

GodIand

膜拜大牛+1 ，对于算法原理真是看的头痛。。

s1986q

谢谢楼主的分享。