通过公钥解密密文思路（256bits RSA）

256bit RSA公钥安全系数极低，只需要几分钟即可破解密文，本文综合其他文章记录了一次解密256bits RSA加密的密文的过程，仅作为备忘。

1.分解公钥，分解出n与e:

1.1使用openssl（红色标记是e与n）

1 qi@zhuandshao:~/download/iscc-ctf/RSA$ openssl rsa -pubin -text -modulus -in public.pem
2
3 Public-Key: (256 bit)
4
5 Modulus:
6
7 00:a4:10:06:de:fd:37:8b:73:95:b4:e2:eb:1e:c9:
8
9 bf:56:a6:1c:d9:c3:b5:a0:a7:35:28:52:1e:eb:2f:
10
11 b8:17:a7
12
13 Exponent: 65537 (0x10001)　　　　　　　　　　　　　　　 #e
14
15 Modulus=A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 #n
16
17 writing RSA key
18
19 —–BEGIN PUBLIC KEY—–
20
21 MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKQQBt79N4tzlbTi6x7Jv1amHNnDtaCn
22
23 NShSHusvuBenAgMBAAE=
24
25 —–END PUBLIC KEY—–
26
27 qi@zhuandshao:~/download/iscc-ctf/RSA$

 

1.2使用脚本

1 from Crypto.PublicKey import RSA
2
3 pub = RSA.importKey(open(‘xxx\public.pem’).read())
4
5 n = long(pub.n)
6
7 e = long(pub.e)
8
9 print n
10
11 print e

 

2.使用msieve来对n来分解因式p、q:(红色标记部分)

1 qi@zhuandshao:~/download/iscc-ctf/RSA$ msieve 0XA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v
2
3
4 Msieve v. 1.54 (SVN 1009)
5
6 Wed May 31 17:02:38 2017
7
8 random seeds: 31130210 1225946d
9
10 factoring 74207624142945242263057035287110983967646020057307828709587969646701361764263 (77 digits)
11
12 no P-1/P+1/ECM available, skipping
13
14 commencing quadratic sieve (77-digit input)
15
16 using multiplier of 7
17
18 using generic 32kb sieve core
19
20 sieve interval: 12 blocks of size 32768
21
22 processing polynomials in batches of 17
23
24 using a sieve bound of 921409 (36471 primes)
25
26 using large prime bound of 92140900 (26 bits)
27
28 using trial factoring cutoff of 26 bits
29
30 polynomial ‘A’ values have 10 factors
31
32 restarting with 19759 full and 186503 partial relations
33
34
35 36750 relations (19759 full + 16991 combined from 186503 partial), need 36567
36
37 sieving complete, commencing postprocessing
38
39 begin with 206262 relations
40
41 reduce to 51619 relations in 2 passes
42
43 attempting to read 51619 relations
44
45 recovered 51619 relations
46
47 recovered 38442 polynomials
48
49 attempting to build 36750 cycles
50
51 found 36750 cycles in 1 passes
52
53 distribution of cycle lengths:
54
55 length 1 : 19759
56
57 length 2 : 16991
58
59 largest cycle: 2 relations
60
61 matrix is 36471 x 36750 (5.3 MB) with weight 1099597 (29.92/col)
62
63 sparse part has weight 1099597 (29.92/col)
64
65 filtering completed in 4 passes
66
67 matrix is 24901 x 24965 (4.0 MB) with weight 837672 (33.55/col)
68
69 sparse part has weight 837672 (33.55/col)
70
71 saving the first 48 matrix rows for later
72
73 matrix includes 64 packed rows
74
75 matrix is 24853 x 24965 (2.6 MB) with weight 610638 (24.46/col)
76
77 sparse part has weight 441218 (17.67/col)
78
79 commencing Lanczos iteration
80
81 memory use: 2.7 MB
82
83 lanczos halted after 394 iterations (dim = 24853)
84
85 recovered 18 nontrivial dependencies
86
87 p39 factor: 258631601377848992211685134376492365269——————->p
88
89 p39 factor: 286924040788547268861394901519826758027——————->q
90
91 elapsed time 00:00:10
92
93 qi@zhuandshao:~/download/iscc-ctf/RSA$

3.使用脚本来生成私钥文件(修改红色部分)

 

1 import math
2
3 import sys
4
5 from Crypto.PublicKey import RSA
6
7
8 keypair = RSA.generate(1024)
9
10
11 keypair.p = 258631601377848992211685134376492365269 #msieve求解的ｐ
12
13 keypair.q = 286924040788547268861394901519826758027　　　 #msieve求解的q
14
15 keypair.e = 65537 #分解出的e
16
17
18 keypair.n = keypair.p * keypair.q
19
20 Qn = long((keypair.p-1) * (keypair.q-1))
21
22
23 i = 1
24
25 while (True):
26
27 x = (Qn * i ) + 1
28
29 if (x % keypair.e == 0):
30
31 keypair.d = x / keypair.e
32
33 break
34
35 i += 1
36
37
38 private = open(‘private.pem’,’w’)
39
40 private.write(keypair.exportKey())
41
42 private.close()

4.使用生成的privete.pem私钥文件对密文解密

 

1 　openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag

 

 

 

附录：

1.linux下安装msieve

sourceforgot上下载软件源代码包：

https://sourceforge.net/projects/msieve/

解压后

1 $ cd msieve-code/
2
3 $make
4
5 to build:
6
7 make all
8
9 add ‘WIN=1 if building on windows
10
11 add ‘WIN64=1 if building on 64-bit windows
12
13 add ‘ECM=1’ if GMP-ECM is available (enables ECM)
14
15 add ‘CUDA=1’ for Nvidia graphics card support
16
17 add ‘MPI=1’ for parallel processing using MPI
18
19 add ‘BOINC=1’ to add BOINC wrapper
20
21 add ‘NO_ZLIB=1’ if you don’t have zlib
22
23 $ make all ECM=1 #根据自己的配置进行选择

应该会报错ｇｍｐ.h不存在，安装高精度数学库就可以啦。

2.linux安装gmp(高精度数学库)

环境：ubuntu 17.04

源代码：https://gmplib.org/

下载gmp-5.0.1的源代码，解压至gmp-5.0.1目录。

 

#lzip -d gmp-6.1.2.tar.lz
#tar -xvf gmp-6.1.2.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数学库。

1 ./configure –prefix=/usr –enable-cxx
2 make
3 make check
4 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