【愚公系列】2022年04月 密码学攻击-RSA小公钥指数

举报
愚公搬代码 发表于 2022/04/30 23:32:48 2022/04/30
【摘要】 一、了解小公钥指数攻击的原理,获得flag我们得到了两个密文和两个公钥,公钥的e分别是3和2,你能把他转换成私钥解密获得flag么解密e=3的flag解密e=2的flag任务描述:了解小公钥指数攻击的原理,获得flag首先我们来了解小公钥指数的原理,假设用户使用的密钥e=3,考虑到加密关系满足:则我们就可以从小到大枚举K,依次开三次根,直到开出整数为止。那我们就可以根据原理来写我们的脚本这...

一、了解小公钥指数攻击的原理,获得flag

我们得到了两个密文和两个公钥,公钥的e分别是3和2,你能把他转换成私钥解密获得flag么

  1. 解密e=3的flag
  2. 解密e=2的flag

任务描述:了解小公钥指数攻击的原理,获得flag

首先我们来了解小公钥指数的原理,假设用户使用的密钥e=3,考虑到加密关系满足:
在这里插入图片描述

在这里插入图片描述
我们就可以从小到大枚举K,依次开三次根,直到开出整数为止。

那我们就可以根据原理来写我们的脚本

这里使用libnum库的s2n,n2s和gmpy2的iroot算根

首先我们打开题目3->小e,输入N,e,和获取flag的C,flag文件要和脚本文件在同一个目录
在这里插入图片描述
首先我们先枚举K,这里的一个算法逻辑是先求m,然后使用while循环求k,如果求出来的m等于整数,则退出循环,这里会跑很久,建议大家直接定义数值,
在这里插入图片描述
跑出来的

k = 118719488

m= 440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186

m已经是跑出来10进制的flag了,所以直接用n2s做转换就可以了
在这里插入图片描述

了解Rabin攻击的原理,获得flag

Rabin是RSA衍生出来的一种算法。这种算法的特点在于e=2,加密方法是
在这里插入图片描述
解密也不同,首先得计算出mq和mp
在这里插入图片描述
然后用扩展欧几里得计算出yq和yp
在这里插入图片描述
接着用获得的yq和yp解密四个密文
在这里插入图片描述
注意,如果q = p =3(mod 4)的话则
在这里插入图片描述
一般情况的话q = p =3(mod 4)是满足的,要是不满足的话可以找下其他的算法解决。接下来我们来看例题,拿到了一个公钥和flag.enc,同样的使用openssl去查看

openssl rsa -pubin -in pubkey.pem -modulus -text
在这里插入图片描述
发现e=2,满足rabin算法条件,首先先来分解q和p,这里同样也是通过在线网站进行分解,

http://www.factordb.com/index.php?query=87924348264132406875276140514499937145050893665602592992418171647042491658461

在这里插入图片描述
分解出来的

p=275127860351348928173285174381581152299

q=319576316814478949870590164193048041239

现在我们可以通过我们前面的知识点写python的脚本进行解密,首先输入q,p,然后读取公钥和密文参数
在这里插入图片描述
然后根据前面的知识点接着求yp和yq,这里可以用gmpy2.invert来对其进行运算
在这里插入图片描述
然后我们需要再算出mp和mq,
在这里插入图片描述
算出了mp和mq后我们就可以去解四个密文了,根据前面算法我们得知

A = (yppmq+yqqmp) mod n,

C同理,B是N-A,D是N-C,所以这里可以用python这样写
在这里插入图片描述
最后写个for循环,让他验证然后输出出来
在这里插入图片描述
在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。