看雪.WiFi万能钥匙 CTF 2017第十题 点评及解题思路

看雪CTF 2017 比赛进行至第十题

截止至今天中午12点，第十题破解人数为 13 人！

防守方 hsadkhk 依然位居首位~，第十题作者位居第五位。

此题过后，风间仁依然处于第一位，lacoucou再次进入前十。

比赛进入倒计时，接下来还会有什么变化呢？

期待ing......

接下来我们来回顾一下第十题

看看 看雪评委和出题者是怎么说的ヾ(๑╹◡╹)ﾉ"。

看雪评委 netwind 点评

此题是一道算法为主的题目，需要攻方熟练掌握大数运算以及RSA算法。要解此题，首先要枚举e，然后再根据e、d、n求得p、q。

作者简介

看雪ID：海风月影

职业：老牌打酱油人员
联系方式：无
兴趣爱好：逛逛论坛，吹吹牛
特长：忽悠
研究方向：人工智能

看雪 CTF2017 第十题设计思路

参赛内容：Windows 64位系统 CrackMe

文件名：cm.exe

CRC32：13F73C04

MD5：31A4B4FF1ABFE9F0C9A11CF4E37C2B86

SHA-1：F38DE836BE531F436ACFD04100FFA52848FEFF15

设计思路

题目：RSA 密码学算法，穷举 e，快速分解 N

cm 运行流程：

1.  输入全大写 70 个字符，前 6 个，后 64 个，分别为两个 16 进制大数:e, p

2.  e、p 都是质数（Miller Rabin 测试算法）

3.  初始化 N、D 两个大数，N 为 512 位
   N=6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE94
   1C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
   D=2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D3
   81925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
   
4. p == 0 (mod N)，则设 q = N / p，p < q
5. 验证D = ( - 1)( - 1)
6. 上面全通过，完毕。
   

解题思路

1. N 是 512 位，分解 N = pq，e = D ( - 1)( - 1)，拼接 ep 完毕（如果是 768
   以上的，目前就不能用这种方法了，为了放水。。。所以 N 设计成 512 位）
   分解方法，使用 ggnfs 和 msieve 工具即可，这里不多说了。2 天内分解完，可能有点难度。

下面选取攻击者 lacoucou 的破解分析

1. PEID 扫描

又是大数运算，IDA打开：

F5，好直观：

查找字符串：

有 PEID 和上边的字符串信息可知，是用GMP实现的大数运算，接着就是猜每个函数的意义了。

由 MPN 的官方文档可知：

1. 所有对象使用前要初始化，通过调用函数 mpz_init来完成

2. 一般的函数，第一个参数为输出函数，后边的为输入参数

刚开始，使用的默认值来计算，进展缓慢，后来把mpn_set_str_140007990 处的大数改成0x10之后，进展飞快。

完整函数如上，流程如下：

1. 假设输入的字符串为szInput

2. 首先判断szInput的长度是否为70个字节

3. 接着判断这些字符是否由 0-9 和A-Z的字符组成：

4. 将输入字符串分成两段，第一段为原字符串的0-6自己，第二段为后64字节

5. 用这两个字符串来初始化两个mpz结构题：

结构体定义：

初始化前6个字符的例子：

内存中，rcx地址的值：

运行之后：

6. 判断是否为素数

这里花了点时间，后来通过连续测试0-0x10基本可以确定是判断素数。

跟官方文档似乎不太一样。

7. 初始化几个值

8. 用大数0x62..... 模上我们输入的64位然后与0比较：

9. 用大数0x62..... 除以我们输入的64位然后与商做比较，商大于我们输入的数：

10. 最后一段，p=input[6:64] 商q=big_1/p  v8=(p-1)(q-1)

有了以上信息，结合上一题的坑，基本猜到是RSA，不然还能有啥......

RSA 算法：

RSA密钥生成步骤：

根据以上信息，以及计算过程：

猜测：

在线分解N，达到P，Q：

可知：

把P转成十六进制作为后64位，果然可以直接运行到：

那么肯定是要根据以下公式求解E

根据以上条件,写python，计算：

完整注册码：

F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

最后感谢 WiFi 万能钥匙安全应急响应中心的赞助支持，

接下来的比赛大家一定要使出洪荒之力哦！↖(^ω^)↗

比心 ❤

赞助商

上海连尚网络科技有限公司成立于 2013 年，是一家专注于提供免费上网和内容服务的移动互联网企业。连尚网络自主研发的核心产品 WiFi 万能钥匙，以分享经济的模式，通过云计算和大数据技术，利用热点主人分享的闲置WiFi资源，为用户提供免费、稳定、安全的上网服务，以帮助更多的人上网，找到属于他们的机会，改变自己的命运。

往期热门内容推荐

---

更多比赛详情，长按下方二维码，“关注看雪学院公众号”查看！

看雪论坛：http://bbs.pediy.com/

微信公众号 ID：ikanxue

微博：看雪安全

商务合作：[e-mail]

点