看雪CTF2017第十题简单解析

作    者：loudy

使用工具：IDA6.8（分析反汇编代码） python（大数运算） notepad（记录） vc6.0（解码） matlab（解方程组）

步    骤：

一、总体轮廓

正如作者“海风月影”所言，此题非常直接，就是RSA的基本原理应用，毫无取巧。见下图，图中配有注释。切记此题分解N就掉坑里了。

二、算法还原

（1）    输入注册码共70字节（实际只包含‘0’-‘9’、‘A’-‘F’）。

（2）    前6字节转化为RSA中的E（24位，当然说是D也可以，E、D地位均等）。

（3）    后64字节转化为RSA中的P（256位，当然说是Q也可以，P、Q地位均等）。

（4）    对E和P进行素性检测。

（5）    初始化RSA中的N（512位，无法直接分解，256位还可以）和D（与E互逆）。

                。。。。。。。。。。见附件

二、逆向过程

(1)由于E为素数且范围较小考虑对E进行枚举。

   1、用C语言，素数筛法求0xFFFFFF以内的素数，并存入文件。

#include <stdio.h>
char bb[0x1000000] = {0};
int main(){
      int xx = 0x1000;
      int i,j,sum;
      FILE *out;
      out = fopen("uu.txt", "wt");
      for(i=2;i<=xx;i++){
           if(bb[i]==0){
                 for(j=i+i;j<0x1000000;j=j+i){
                      bb[j]=1;
                 }
           }
      }
      sum = 0;
      for(i=2;i<0x1000000;i++){
           if(bb[i]==0) {fprintf(out,"%d\n",i);sum++;}
      }
      fclose(out);
      printf("\n%d\n",sum);
      return 0;
}

  2、用Python，读取第一步生成文件中的素数值，枚举正确E。

file = open("uu.txt")
n = 0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
d = 0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
while 1:
    line = file.readline()
    if not line:
        break
    e = int(line)
    x = e*d
    y = pow(2,x,n)
    if y==2:
        print str(e)

结果转化为16进制，得到E=0x F552B3

（2）RSA算法应用

公式太多，不便编辑，请见附件

得到P=0x8DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

key=（E，P）=“F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3”

熟悉RSA基本原理即可答题。

附件已经更新，调整了公式格式，不然太难看

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法