Crypto:RSA2解题分析

今天终于将RSA第二题解决，一路走来踩了不少坑。先是yafu的安装与配置，然后大部分时间都用来安装rsatool工具，但在安装过程中出现了好多问题，解决了一个问题，还是存在下一步问题，最后依然没有解决，于是我选择用python脚本来输出私钥，但在安装Crypto库的时候也出现了问题，解决后虽然成功输出私钥，最后一步用openssl解密的时候，还是报错，查阅资料才发现原来是python生成的私钥是无填充的。

yafu的安装与使用

yafu用于自动整数因式分解，在RSA中，当p、q的取值差异过大或过于相近的时候，使用yafu可以快速的把n值分解出p、q值，原理是使用Fermat方法与Pollard rho方法等。

1.windows下的安装

yafu下载

下载后解压即可。解压会有yafu-Win32.exe和yafu-x64.exe。

可以通过CMD命令行进入文件夹进行使用。

但为了方便下次使用可采用添加环境变量的方式。

(1)新建一个cmd的快捷方式。
(2)点击查看属性，将起始位置修改为所解压的yafu-1.34文件夹所在的位置。

2.使用

主要用来分解N，命令为factor(N)

打开已创建的cmd快捷方式输入 yafu-x64.exe打开。

执行factor(N)即可分解。

大数十六进制如何转换十进制

只需一条简单的python代码即可完成。

shell下执行，

eval('0xc2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd')

eval可实现将十六进制转换为十进制

解题过程：

1.根据所给公钥提取模数n，与指数e。

有两种办法：①通过openssl ②在线RSA网站

这里我采用的是在线解密的方式，方便快捷。

推荐：在线Rsa 公私钥分解

得到模数n为c2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd,指数e=65537，如下图：

2.将得到的n转为十进制。

3.使用yafu工具，拆解n

factor(87924348264132406875276140514499937145050893665602592992418171647042491658461) 如下图：

得到p=275127860351348928173285174381581152299，q=319576316814478949870590164193048041239。

4.使用python生成私钥

生成私钥代码：

import math

import sys

from Crypto. PublicKey import RSA


keypair = RSA.generate(1024)

keypair.p = 275127860351348928173285174381581152299
keypair.q = 319576316814478949870590164193048041239
keypair.e = 65537

keypair.n = keypair.p * keypair.q

Qn = long( (keypair.p-1) * (keypair.q-1))

i = 1

while(True):

  x =(Qn*i)+1

  if (x % keypair.e == 0):

     keypair.d = x / keypair.e
     break

  i+=1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

5.使用openssl进行解密

 openssl rsautl -decrypt -in flag.encrypt -inkey private.pem -out flag.txt  --raw

所遇问题：

1. Windows下pip安装库出错：Microsoft Visual C++ 9.0 is required < Unable to find vcvarsall.bat

解决办法：

下载并安装Microsoft Visual C++ Compiler for Python 2.7

2.Windows下安装Crypto库老是失败。报错：（ImportError: No module named Crypto.Cipher）

解决办法：

pip uninstall crypto
pip uninstall pycrypto

pip install Crypto
pip install pycrypto

此时如果还不行,找到c:/python27/Lib/site-packages/crypto 把crypto改成Crypto就可以了。

3.使用openssl解密时报错：RSA operation error

解决办法：

因为python生成的私钥是无填充的，后面加上参数 --raw.

虽然此题很简单，一路走来经历了许多坎坷，但安装rsatool工具仍未成功，最终放弃了这种方式，以后再仔细检查一下是啥原因。最终收获还是挺多的!

参考链接：

从小白变RSA大神

在线RSA分解模数、指数

在线Rsa 公私钥分解

从数盲到口算 ——带你玩转RSA加密算法（一）

Python各进制间的转换方法

yafu安装使用方法以及mismatched parens解决方法

RSA工具集-openssl,rsatool,RsaCtfTool,RSAtool