CTF| 你想要的RSA解题技巧(二)

上一期已经给大家分享了RSA的基本解题思路,总结如下,本期带来几种复杂的RSA题目解法。

以上都是基本解法,基于n能够分解的前提下进行的解法,但是当题目n的长度达到2048、4096bit以上的级别的时候,上述的方法就不适用了。

一、CTF题目实战

1.1 利用n的公约数

题目链接 : http://pan.baidu.com/s/1bo7maR1

密码:kd7o

题目:在一道CTF题中,已知n1和n2且长度很大,e都为65537。

解题思路:

求解n1,n2的最大公约数,用python脚本实现,脚本参考下篇文章。http://www.cnblogs.com/reborn-blog/p/7553528.html

此时求解出一个公约数,此即为n1,n2共有的共因素p,在借助公式n=p*q解出q。

1.2 共模攻击

我们知道RSA加密算法:

如果收到两份密文c1,c2,是一个明文m由相同的n和不同的2个e(e1,e2)进行加密的,此时无需求解出d即可破解出明文,具体的证明过程就不给出了,可自行查阅资料。

题目链接:http://pan.baidu.com/s/1bSmJHO

密码:0mzz

题目:

解题思路:这道题给出两个加密文件,flag.enc1和flag.enc2,verhardRSA.py给出了N的值和e1,e1。

打开加密文件会乱码,你可以使用winhex来提取十六进制。也可以使用python的libnum模块来进行进制和字符串的转换。

libnum模块的安装方法:

git clone https://github.com/hellman/libnum

cd libnum

python setup.py install

下面直接给出这种题型的解密脚本,脚本作者是ByStudent,非斗哥原创。

gmpy2模块可以参考pcat的文章安装,http://www.cnblogs.com/pcat/p/5746821.html

1.3 低加密指数攻击

加密指数指的是e,因为e是可以随机选取的,当e很小时就会被直接破解掉。

当e=3,而且明文也很小,导致明文的三次方仍然小于n,那么通过直接对密文3次开放,即可得到明文。

C=me mod n

如果e=3,且me<n,那么

me mod n= me ,即C=me

m=3√c

如果e=3,且me>n,那么设k,有:

c= me +kn

爆破k,如果c−kn能开三次根式,那么可以直接得到明文。

题目链接:http://pan.baidu.com/s/1nuIxdQ5

密码:avvw

解题思路:通过公钥pubkey.pem获取e和n的值:

发现n的长度为4098,难以直接分解得到p和q。

e=3,尝试使用低加密指数攻击,通过计算可知密文的3次方大于n。

利用脚本爆破n的值求出m。

将m转换字符串的形式。

二、总结

大致介绍了3种情形,RSA题目解密方法远不止这些,本文算是上一篇的延伸,所有脚本和题目,以及脑图和密码学相关的几本书籍都放在网盘。

链接:http://pan.baidu.com/s/1i55UoQh

密码:5l4s

小伙伴们根据需要进行下载吧。

原文发布于微信公众号 - 漏斗社区(newdooneSec)

原文发表时间:2017-09-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏漏斗社区

HASH函数烧脑大作战

本期讲解一下hash函数,由于之前在比赛中做到了一题hash有关的题目,引发了此次的深(烧)度(脑)研究,本来想讲讲原理,但是太难,看得很痛苦,所以此次通过结合...

1235
来自专栏数据结构与算法

洛谷P3857 [TJOI2008]彩灯(线性基)

Peter女朋友的生日快到了,他亲自设计了一组彩灯,想给女朋友一个惊喜。已知一组彩灯是由一排N个独立的灯泡构成的,并且有M个开关控制它们。从数学的角度看,这一排...

552
来自专栏龙首琴剑庐

Java基准测试利器OpenJDK-JMH

5509
来自专栏WOLFRAM

用 Wolfram 语言绘制电子轨道

1525
来自专栏大闲人柴毛毛

张全蛋和李小花的故事——“代理模式”

举个例子: 假设张全蛋喜欢上了李小花,张全蛋准备给李小花送一些礼物,但张全蛋又非常害羞,因此买了礼物之后让王尼玛代送。王尼玛跑到李小花把礼物送给她之后就走了。 ...

38512
来自专栏生信技能树

第2篇:原始数据的质控、比对和过滤

首先对拿到的原始测序数据(fastq或fastq.gz格式)进行质控检测,直接用fastqc软件,再加上multiqc将多个检测结果一起展示。 如:

4863
来自专栏温安适的blog

贪婪算法-单源最短路径

3755
来自专栏王亚昌的专栏

FFMPEG-如何对视频按时长切片与压缩

本文介绍如何用ffmpeg开源组件按时长进行切片,举一个例子,一个视频网站,拿到一个时长1.5小时的电影,用户点击播放时,常用的技术方案就是把一个完整的大文件,...

1381
来自专栏点滴积累

PhiloGL学习(2)——骚年,让我们荡起双桨

 前言 上一篇文章中简单介绍了PhiloGL框架如何上手、GLSL语言以及简单的绘制一个方块(见PhiloGL学习(1)——场景创建及二维方块加载)。本文很简单...

3537
来自专栏JMCui

策略模式.

    网上介绍设计模式的文章有很多,好文也不少。作为设计模式的初学者,实在不敢多加造次。就仅以此文作为我记忆的备忘录吧!

1103

扫码关注云+社区

领取腾讯云代金券