首页
社区
课程
招聘
[原创]看雪.Wifi万能钥匙 CTF 2017 第10题Writeup
发表于: 2017-6-20 21:38 3606

[原创]看雪.Wifi万能钥匙 CTF 2017 第10题Writeup

2017-6-20 21:38
3606

程序是静态编译的,全是黑函数。看了下入口call,jmp应该是VC写的,但是多了个push pop的过程。

查看字符串,发现了ctf2017,附近还有注册成功之类的,定位到关键算法所在,在字符串中还发现了GNU MP: Cannot allocate memory之类,经查为gmp计算库。

 其实本来由于前面精力用太多,感觉很累,想放了这题的,看了个开头就没看了。准备试试ida的符号加载,去掉一些黑函数,下载编译了个gmp,试了一晚上也没有成功。 

后来又想看题了,就对照gmp的源码,把部分函数比对了下,如下

先检查输入长度为70,再检查大于`Z``的字符为70。

然后把输入分别6byte和64byte两部分,按16进制字符转成数字,并检查其为素数,再进行一些算术运算,最近与常量数字比较。 

从整体看是RSA的密钥生成过程。计输入的两部分分别为e,p,记代码中的常量分别为n,d。则计算过得是这样的:

其中的invert是求模反元素的函数调用。

看完到这,直接将n去数据库里查,没有结果。又拿出yafu分解了两个小时没有结果。果断停了,开始想办法爆破,试了几次都不理想。又整理下公式及思路。

那么,

上面两条/为带小数的除法

由于p,q很大,1-1/p-1/q+1/(pq)无限接近于1,kN/n无限接近于k,那么,

(ed-1)/n = k1 此处为整除

则k1 = k-1 ,所以

再结合pq=n,就可以由这个二元一次方程求出p,q。所以解题思路就出来了,爆破e,如果(ed-1)%(k1+1)==0,则e为可能解,再由于n为512bit,p和q应该比较接近(p为256bit,q也应该为256bit左右),限制p+q 为264bit以下,代码如下:

不到一分钟出了一个结果:


[峰会]看雪.第八届安全开发者峰会10月23日上海龙之梦大酒店举办!

收藏
免费 1
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回
//