前言

在CTF中分别得到了N和C，请问你能解密他吗

我们的任务分为3个部分：

1．了解什么情况可分解N，可用什么工具来分解N。
2．完成题目

一、分析N的大小，并对其进行分解

学习了预备知识后我们开始今天的课程

我们知道了Q,P是组成N的因素，Q和P越大，产生的N也越大，那反之，N很小的时候，组成的Q,P也很小，所有我们可以通过暴力分解的方法对其进行分解取得Q,P。以下是例子

首先我们先打开pentestbox，通过ssh生成一个私钥来分析

openssl.exe genrsa -out rsa_private_key.pem 100 //生成一个100bit的私钥

通过私钥去生成公钥，私钥负责解密，公钥负责加密，所以基本CTF比赛中提供的都是公钥，要求我们做出私钥进行解密。公钥是(N,e)，私钥是（N，d），有了Q,P后才可以去生成d，这也是我们目的

openssl.exe rsa -in rsa_private_key.pem -pubout -out rsa_public_key.pem //把私钥转换成公钥

接下来我们来分析下他的N（modulus）和e

openssl rsa -pubin -in rsa_public_key.pem -modulus -text

我们可以看到，N特别的小，N= 0xd5e62464c99662a9b38f231c9

目前已知N是Q和P两个素数相乘，所以我们只需找到什么两个数相乘即可

接下来我们就可以通过离线的运算给他破解，这里使用的是yafu工具

首先先让cmd的目录切换过来，然后输入

yafu-x64.exe factor(0xd5e62464c99662a9b38f231c9)

我们可以看到。P15等于q，p16等于p，可以进行验证

N的十进制是1059176510317624978494004015561

由于数字较大这里使用python进行运算

算出来的结果等于1059176510317624978494004015561L，L可以忽略，结果和N匹配

得知了Q,P后，我们现在可以来算私钥D，使用RSA tools来进行运算，

Numer base代表当前的进制，由于我们转换后是10进制，所有这里输入10，然后输入Q,P值，最后点击计算D


得出D =867129354175225290070399065057

利用D我们即可生成私钥去解密我们的数据了，这里可以用python实现

二、解密出FLAG

首先我们来看题目提供了公钥和一个flag.enc的密文，我们可以先查看公钥中的N和E

openssl rsa -pubin -in public.pem -text -modulus


我们可以得知

N=A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7

且N是256bit，我们可以通过爆破的方式解密,但是软件的算力不够，所以这里使用在线工具进行破解，该网站默认是10进制的数据，所以这里要把数据转为10进制。

http://www.factordb.com/index.php

十进制：

74207624142945242263057035287110983967646020057307828709587969646701361764263

现在打开网站在框里输入我们的N，然后点击按钮即可出结果

258631601377848992211685134376492365269<39> · 286924040788547268861394901519826758027<39>

即为我们的Q,P，那现在我们来整理下我们的数据

N=74207624142945242263057035287110983967646020057307828709587969646701361764263

Q=258631601377848992211685134376492365269

P=286924040788547268861394901519826758027

有了这些同样的方法求D

现在我们就有了这些数据

N=74207624142945242263057035287110983967646020057307828709587969646701361764263

Q=258631601377848992211685134376492365269

P=286924040788547268861394901519826758027

D=23071769375111040425287244625328797615295772814180109366784249976498215494337

我们可以通过这个数据生成个私钥来对密文进行解密，先查看密文的16进制

xxd -ps flag.enc

获得密文C=49b96edbe3961f58d529074bd893d6e036ceaf2b6d214b470fdc0d48723d

6a40

然后再通过我们之前的脚本进行解密

这里稍微改两句代码

c=binascii.a2b_hex(‘49b96edbe3961f58d529074bd893d6e036ceaf2b6d214b470fdc0d48723d6a40’)

t = rsa.decrypt(c, prikey)

然后执行该脚本

即可得到flag