yafu

yafu
FB招聘站
分类阅读
专栏
公开课
FIT 2019
企业服务
用户服务
搜索
投稿
登录
注册
RSA史上最强剖析，从小白变大神，附常用工具使用方法及CTF中RSA典型例题婷儿小跟班✧2018-03-06现金奖励共421405人围观，发现 9 个不明物体工具
*本文作者：婷儿小跟班✧，本文属 FreeBuf 原创奖励计划，未经许可禁止转载。

前言
RSA加解密类题型是ctf题中常见题型，考点比较广泛，涉及各种攻击手法，以前在这栽了不少跟头，这里好好总结一下。包括RSA加密原理，RSA常用工具使用方法及下载地址，RSA典型例题。

RSA加密基本原理
加密过程
选择两个大素数p和q，计算出模数N = p * q

计算φ = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1msieve.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v

Msieve v. 1.52 (SVN 939)
Tue Feb 27 14:16:37 2018
random seeds: 4700eb70 a74b9797
factoring 74207624142945242263057035287110983967646020057307828709587969646701361764263 (77 digits)
searching for 15-digit factors
commencing quadratic sieve (77-digit input)
using multiplier of 7
using VC8 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 921409 (36471 primes)
using large prime bound of 92140900 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors
restarting with 19759 full and 186804 partial relations

36609 relations (19759 full + 16850 combined from 186804 partial), need 36567
sieving complete, commencing postprocessing
begin with 206563 relations
reduce to 51387 relations in 2 passes
attempting to read 51387 relations
recovered 51387 relations
recovered 38239 polynomials
attempting to build 36609 cycles
found 36609 cycles in 1 passes
distribution of cycle lengths:
length 1 : 19759
length 2 : 16850
largest cycle: 2 relations
matrix is 36471 x 36609 (5.3 MB) with weight 1094350 (29.89/col)
sparse part has weight 1094350 (29.89/col)
filtering completed in 4 passes
matrix is 24957 x 25021 (4.0 MB) with weight 837221 (33.46/col)
sparse part has weight 837221 (33.46/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 24909 x 25021 (2.6 MB) with weight 614783 (24.57/col)
sparse part has weight 438151 (17.51/col)
commencing Lanczos iteration
memory use: 2.6 MB
lanczos halted after 395 iterations (dim = 24905)
recovered 16 nontrivial dependencies
prp39 factor: 258631601377848992211685134376492365269
prp39 factor: 286924040788547268861394901519826758027
elapsed time 00:00:05

E:\ctf工具\ctf工具\加解密工具\RSA专用工具\msieve152_svn939_win64_i7>msieve.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -q

0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7
prp39: 258631601377848992211685134376492365269
prp39: 286924040788547268861394901519826758027
注：prp39 即是分解出来的p,q

注意前面加上相应进制。八进制0 十六进制0x 十进制什么也不加。

openssl

生成私钥，并导出公钥生成2048 bit的PEM格式的RSA Key：Key.pem

徐超@yoona MINGW64 ~/Desktop/test
$ openssl genrsa -out key.pem -f4 2048
Generating RSA private key, 2048 bit long modulus
................+++
..............................+++
e is 65537 (0x10001)
从私钥导出公钥：Key_public.pem

徐超@yoona MINGW64 ~/Desktop/test
$ openssl rsa -in key.pem -pubout -out key_public.pem
writing RSA key
准备测试数据

为了简便起见，这里将字符串”hello rsa”存放到文件msg.txt作为测试数据：

徐超@yoona MINGW64 ~/Desktop/test
$ echo "hello rsa" > msg.txt
公钥加密

使用公钥key_public.pem对测试数据msg.txt进行加密生成msg.txt.enc，并查看加密后的数据：

徐超@yoona MINGW64 ~/Desktop/test
$ openssl rsautl -in msg.txt -out msg.txt.enc -inkey key_public.pem -pubin -encrypt -pkcs

徐超@yoona MINGW64 ~/Desktop/test
$ cat msg.txt.enc
Ff▒▒li▒Yn▒HA▒cǴ▒Ԋ7▒V4▒
KS콳h)▒▒w)▒▒{kv▒+ ▒h▒▒qi?Ǭ▒▒f▒▒T.▒▒▒▒ߍ▒.▒▒▒&▒;Z▒▒▒▒▒▒$y▒▒)n_▒8▒0▒")[▒w▒▒]~)r▒▒'▒▒u▒▒6g▒*F▒F▒'ٲ▒▒] +G▒m▒j%k*▒▒s&
▒▒JQ~n▒▒▒.هsi▒▒}~▒▒f ▒Eӝ▒}▒7C▒▒▒Z▒Z|>▒]A▒▒▒ǐ▒
▒▒▒▒e▒Uc▒▒B▒▒▒(dh▒üj▒՗▒vĊ
这里使用：

-in 选项指定原始数据文件msg.bin -out 选项指定加密后的输出文件msg.bin.enc -inkey 选项指定用于加密的公钥Key_pub.pem，由于输入是公钥，所以需要使用选项-pubin来指出 -encrypt 选项表明这里是进行加密操作 -pkcs 选项指定加密处理过程中数据的填充方式，对于填充，可选项有：-pkcs, -oaep, -ssl, -raw，默认是-pkcs，即按照PKCS#1 v1.5规范进行填充

私钥解密

使用私钥key.pem对加密后的数据msg.txt.enc进行解密，并将结果存放到msg.txt.dec文件中：

徐超@yoona MINGW64 ~/Desktop/test
$ openssl rsautl -in msg.txt.enc -out msg.txt.dec -inkey key.pem -decrypt -pkcs

徐超@yoona MINGW64 ~/Desktop/test
$ cat msg.txt.dec
hello rsa
这里使用：

-in 选项指定待解密的数据文件msg.bin.enc -out 选项指定解密后的输出文件msg.bin.dec -inkey 选项指定用于解密的私钥Key.pem，由于输入是私钥，所以不再需要使用选项-pubin -decrypt 选项表明这里是进行解密操作 -pkcs 选项指定解密处理过程中数据的填充方式，对于填充，可选项有：-pkcs, -oaep, -ssl, -raw，默认是-pkcs，即按照PKCS#1 v1.5规范进行填充

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

先运行文件夹下的yafu-x64.exe进入命令行

执行factor(N)

执行过程：（也可以像下面这样后面直接加上factor(N)）

E:\ctf工具\ctf工具\加解密工具\RSA专用工具\yafu>yafu-x64.exe factor(920139713)

fac: factoring 920139713
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.0080 seconds

***factors found***

P5 = 49891
P5 = 18443

ans = 1
mismatched parens报错

这是因为N的位数过长，命令行不支持。

把N值保存到文件中，如rsa.txt ，然后执行

yafu-x64.exe "factor(@)" -batchfile rsa.txt
执行后rsa.txt就会被自动删除。

执行过程如下：

E:\ctf工具\ctf工具\加解密工具\RSA专用工具\yafu>yafu-x64.exe "factor(@)" -batchfile rsa.txt

=== Starting work on batchfile expression ===
factor(966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533)
=============================================
fac: factoring 966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.4415 seconds

***factors found***

PRP617 = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221
PRP617 = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473

ans = 1
eof; done processing batchfile报错

rsa.txt用notepad++打开，最后加上换行即可。

RSA题型分析
实验吧RSA
题目链接：http://www.shiyanbar.com/ctf/1772

openssl分析公钥，得到N,E

openssl rsa -pubin -text -modulus -in public.pem
运行结果

徐超@yoona MINGW64 ~/Desktop/RSA
$ openssl rsa -pubin -text -modulus -in public.pem
Public-Key: (256 bit)
Modulus:
00:a4:10:06:de:fd:37:8b:73:95:b4:e2:eb:1e:c9:
bf:56:a6:1c:d9:c3:b5:a0:a7:35:28:52:1e:eb:2f:
b8:17:a7
Exponent: 65537 (0x10001)
Modulus=A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKQQBt79N4tzlbTi6x7Jv1amHNnDtaCn
NShSHusvuBenAgMBAAE=
-----END PUBLIC KEY-----
writing RSA key
Modulus 是n的值，Exponent是E的值。

msieve分解N的值

msieve.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v
运行结果

E:\ctf工具\ctf工具\加解密工具\RSA专用工具\msieve153>msieve153.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v

Msieve v. 1.53 (SVN 1005)
Wed Feb 28 23:00:33 2018
random seeds: f922db80 d61d4d18
factoring 74207624142945242263057035287110983967646020057307828709587969646701361764263 (77 digits)
searching for 15-digit factors
commencing quadratic sieve (77-digit input)
using multiplier of 7
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 921409 (36471 primes)
using large prime bound of 92140900 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors
restarting with 19771 full and 188452 partial relations

36803 relations (19771 full + 17032 combined from 188452 partial), need 36567
sieving complete, commencing postprocessing
begin with 208223 relations
reduce to 51729 relations in 2 passes
attempting to read 51729 relations
recovered 51729 relations
recovered 38607 polynomials
attempting to build 36803 cycles
found 36803 cycles in 1 passes
distribution of cycle lengths:
length 1 : 19771
length 2 : 17032
largest cycle: 2 relations
matrix is 36471 x 36803 (5.3 MB) with weight 1102159 (29.95/col)
sparse part has weight 1102159 (29.95/col)
filtering completed in 3 passes
matrix is 24858 x 24922 (4.0 MB) with weight 836197 (33.55/col)
sparse part has weight 836197 (33.55/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 24810 x 24922 (2.6 MB) with weight 611256 (24.53/col)
sparse part has weight 439905 (17.65/col)
commencing Lanczos iteration
memory use: 2.7 MB
lanczos halted after 394 iterations (dim = 24805)
recovered 14 nontrivial dependencies
p39 factor: 258631601377848992211685134376492365269
p39 factor: 286924040788547268861394901519826758027
elapsed time 00:00:06
知道p，q，e的值，python脚本生成私钥

import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 0xD7DB8F68BCEC6D7684B37201385D298B
keypair.q = 0xC292A272E8339B145D9DF674B9A875D5
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()
注：生成的私钥会默认base64加密。

密钥解密密文

➜ RSA openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.txt
➜ RSA cat flag.txt
ISG{256bit_is_weak}
RSA roll
题目给出一个txt文件，内容如下：

{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148
可知 N = 920139713 E = 19

方法一 RSA-tool 2

分解N得到p,q 选对进制，生成D(私钥) 点击test用私钥解密密文

方法二 python脚本

分解N得到p,q

n = 2
while (n<920139713): if (920139713%n == 0): print n,920139713/n n = n + 1 解出私钥d p = int(input("p:")) q = int(input("q:")) e = int(input("e:")) #print(type(e)) L = (p-1)*(q-1) i = 0 while True: if (1+L*i)%e == 0: break i+=1 #print(i) print("d is %s"%((1+L*i)/e)) 私钥 d 解密密文(密文保存为rsa.txt并去掉开头两行) n = 920139713 d = 96849619 result = [] with open("rsa.txt") as f: for i in f: result.append(chr(pow(int(i),d,n))) print(result) 运行结果 C:\Python27\python.exe F:/code/learning/ctf/rsa_py/rsa_1.py ['f', 'l', 'a', 'g', '{', '1', '3', '2', '1', '2', 'j', 'e', '2', 'u', 'e', '2', '8', 'f', 'y', '7', '1', 'w', '8', 'u', '8', '7', 'y', '3', '1', 'r', '7', '8', 'e', 'u', '1', 'e', '2', '}'] 进程已结束,退出代码0 得到flag为flag{13212je2ue28fy71w8u87y31r78eu1e2} 常用工具下载地址 RSA-tool 2 http://www.skycn.net/soft/appid/39911.html msieve https://sourceforge.net/projects/msieve/ yafu https://sourceforge.net/projects/yafu/ 后续遇到相应题型还会在我的博客补充www.ixuchao.cn 联系方式： qq：755563428 email：755563428@qq.com phone:15615833854 *本文作者：婷儿小跟班✧，本文属 FreeBuf 原创奖励计划，未经许可禁止转载。婷儿小跟班✧ 婷儿小跟班✧ 7 篇文章等级： 3级 || 上一篇：代码分享|使用Python和Tesseract来识别图形验证码下一篇：LSB-Steganography：教你如何使用最低有效位将文件隐写到图像中发表评论已有 9 条评论 monsterL (1级) 2018-03-06回复 1楼不错的学习了亮了(0) 幕刃 2018-03-06回复 2楼徐超是谁？亮了(3) 婷儿小跟班✧ (3级) 2018-03-06回复 @ 幕刃我的艺名∑(ﾟДﾟ) 亮了(0) 陆仁甲 (2级) echo exp(www.baidu.com,timeout... 2018-03-06回复 3楼 msieve153.exe 这个工具对电脑的 CPU 和内存有要求吗 ? 亮了(2) 婷儿小跟班✧ (3级) 2018-03-06回复 4楼对于那些一般长度的n，一般电脑都能分解出来，只是时间上稍微有点差别，但是对于很长的n,那就需要一些攻击方法了@ 陆仁甲亮了(0) Enchantedor (1级) 这家伙太懒了，还未填写个人描述！ 2018-03-07回复 5楼 :razz: 很好的一篇文章，简直太棒了！！亮了(0) 徐超他爸爸1 (1级) 2018-03-09回复 6楼厉害亮了(2) jamzy (1级) 2018-03-09回复 7楼厉害亮了(0) 小白兔 2018-03-26回复 8楼 nb 亮了(0) 昵称请输入昵称必须您当前尚未登录。登陆？注册邮箱请输入邮箱地址必须（保密）表情插图有人回复时邮件通知我婷儿小跟班✧ 婷儿小跟班✧ 这家伙太懒，还未填写个人描述！ 7 文章数 8 评论数最近文章 PentesterLab新手教程（四）：文件包含 2018.05.11 PentesterLab 新手教程（三）：LDAP攻击 2018.05.04 PentesterLab新手教程（二）：XML注入 2018.04.26 浏览更多相关阅读 2014信息安全技能竞赛（ISG）火热报名中非对称算法之RSA的签名剖析SQL注入之骚姿势小记第二届XCTF联赛：ZCTF-writeupBSidesTLV 2018 CTF WriteUp（附CTF环境）特别推荐关注我们分享每日精选文章活动预告 11月 FreeBuf精品公开课·双11学习狂欢节 | 给努力的你打打气已结束 10月【16课时-连载中】挖掘CVE不是梦（系列课程2）已结束 10月【首节课仅需1元】挖掘CVE不是梦已结束 9月【已结束】自炼神兵之自动化批量刷SRC 已结束 FREEBUF免责声明协议条款关于我们加入我们广告及服务寻求报道广告合作联系我们友情链接关注我们官方微信新浪微博腾讯微博Twitter赞助商 Copyright © 2018 WWW.FREEBUF.COM All Rights Reserved 沪ICP备13033796号 css.php 正在加载中...0daybank

文章评论