256bit RSA公钥安全系数极低，只需要几分钟即可破解密文，本文综合其他文章记录了一次解密256bits RSA加密的密文的过程，仅作为备忘。
1.分解公钥，分解出n与e:
1.1使用openssl（红色标记是e与n）
qi@zhuandshao:~/download/iscc-ctf/RSA$ openssl rsa -pubin -text -modulus -in public.pem Public-Key: ( bit) Modulus: :a4:::de:fd::8b:::b4:e2:eb:1e:c9: bf::a6:1c:d9:c3:b5:a0:a7::::1e:eb:2f: b8::a7 13 Exponent: 65537 (0x10001) #e
14
15 Modulus=A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 #n writing RSA key -----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKQQBt79N4tzlbTi6x7Jv1amHNnDtaCn NShSHusvuBenAgMBAAE= -----END PUBLIC KEY----- qi@zhuandshao:~/download/iscc-ctf/RSA$
1.2使用脚本
from Crypto.PublicKey import RSA
pub = RSA.importKey(open('xxx\public.pem').read())
n = long(pub.n)
e = long(pub.e)
print n
print e2.使用msieve来对n来分解因式p、q:(红色标记部分)
qi@zhuandshao:~/download/iscc-ctf/RSA$ msieve 0XA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v Msieve v. 1.54 (SVN ) Wed May :: random seeds: 1225946d factoring ( digits) no P-/P+/ECM available, skipping commencing quadratic sieve (-digit input) using multiplier of using generic 32kb sieve core sieve interval: blocks of size processing polynomials in batches of using a sieve bound of ( primes) using large prime bound of ( bits) using trial factoring cutoff of bits polynomial 'A' values have factors restarting with full and partial relations relations ( full + combined from partial), need sieving complete, commencing postprocessing begin with relations reduce to relations in passes attempting to read relations recovered relations recovered polynomials attempting to build cycles found cycles in passes distribution of cycle lengths: length : length : largest cycle: relations matrix is x (5.3 MB) with weight (29.92/col) sparse part has weight (29.92/col) filtering completed in passes matrix is x (4.0 MB) with weight (33.55/col) sparse part has weight (33.55/col) saving the first matrix rows for later matrix includes packed rows matrix is x (2.6 MB) with weight (24.46/col) sparse part has weight (17.67/col) commencing Lanczos iteration memory use: 2.7 MB lanczos halted after iterations (dim = ) recovered nontrivial dependencies 87 p39 factor: 258631601377848992211685134376492365269------------------->p
88
89 p39 factor: 286924040788547268861394901519826758027------------------->q elapsed time :: qi@zhuandshao:~/download/iscc-ctf/RSA$
3.使用脚本来生成私钥文件(修改红色部分)
import math import sys from Crypto.PublicKey import RSA keypair = RSA.generate(1024) 11 keypair.p = 258631601377848992211685134376492365269 #msieve求解的ｐ
12
13 keypair.q = 286924040788547268861394901519826758027 #msieve求解的q
14
15 keypair.e = 65537 #分解出的e 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()
4.使用生成的privete.pem私钥文件对密文解密
openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag
附录：
1.linux下安装msieve
sourceforgot上下载软件源代码包：
https://sourceforge.net/projects/msieve/
解压后
$ cd msieve-code/ $make to build: make all add 'WIN=1 if building on windows add 'WIN64=1 if building on 64-bit windows add 'ECM=1' if GMP-ECM is available (enables ECM) add 'CUDA=1' for Nvidia graphics card support add 'MPI=1' for parallel processing using MPI add 'BOINC=1' to add BOINC wrapper add 'NO_ZLIB=1' if you don't have zlib $ make all ECM= #根据自己的配置进行选择
应该会报错ｇｍｐ.h不存在，安装高精度数学库就可以啦。
2.linux安装gmp(高精度数学库)
环境：ubuntu
17.04
下载gmp-5.0.1的源代码，解压至gmp-5.0.1目录。
#lzip -d gmp-6.1..tar.lz
#tar -xvf gmp-6.1..tar
su切换至超级用户权限。
./configure
--prefix=/usr --enable-cxx
提示：
checking
for suitable m4… configure: error:
No
usable m4 in $PATH or /usr/5bin (see config.log for
reasons).
根据提示查看config.log日志文件，发现文件太大，何处找原因呢？
没有办法，直接google搜索上面的英文提示。
居然马上就找到了资料解决这个问题，原来是缺少m4软件包。
查了一下m4是一个通用的宏处理器，由Brian
Kernighan 和Dennis
Ritchie设计。
apt-get
install build-essential
m4
安装完毕，其中的build-essential是ubuntu下用来解决安装g++/gcc编译环境依赖关系的软件包。
开始编译，安装gmp数学库。
./configure --prefix=/usr --enable-cxx
make
make check
make install
参考资料：
1.256-bitRSA破解-实验吧
2.[翻译]初学者向导―GGNFS和MSIEVE分解因数-『外文翻译』-看雪安全论坛：http://bbs.pediy.com/thread-156206.htm
3.ubuntu10.4下安装和使用GMP高精度数学库：http://blog.csdn.net/bingqingsuimeng/article/details/12748341