内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

浅析RSA Padding Attack

2018-09-08 10:53 出处:清屏网 人气: 评论(0

前言

近日在复盘一些Crypto的题目,做到了N1CTF的一道rsapadding,进行了一些拓展,于是进行了一些分析记录,有了这篇文章

题目分析

题目已开源在

https://github.com/Nu1LCTF/n1ctf-2018/tree/master/source/crypto/rsapadding

主要代码为

m = '*****************'
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
e = 3
welcom()
if cmd():
    f = open("/root/crypto/file.py")
    print(f.read())
    return
mm = bytes_to_long(m)
assert pow(mm, e) != pow(mm, e, n)
sys.stdout.write("Please give me a padding: ")
padding = input().strip()
padding = int(sha256(padding.encode()).hexdigest(),16)
c = pow(mm+padding, e, n)
print("Your Ciphertext is: %s"%c)

意思很简单

1.pow(mm, e) != pow(mm, e, n)

2.输入一个值

3.将输入的值sha256,记做padding

4.利用rsa加密m+padding

值得注意的是,e=3,padding可控

那么我们拥有的条件只有

n,e,c,padding

所以这里的攻击肯定是要从可控的padding入手了

初步推导

我们可以随便构造一对已知padding的密文,得到

此时,我们可以设

利用这两个式子,我们可以得到如下线性关系

即方程形式为

其中

我们有

我们知道

那么将其带入得到

我们将c1展开得到

我们将这个式子带入得到

于是便一筹莫展

可求证明

上述的推导我们漏了一个非常重要的信息

那么不难发现


同理,我们还可以构造方程

如此一来,我们可以得到

是下列方程组的一个解

那么一定可以有

可以被写成

如此一来,只要

我们由e=3可以得知

只有唯一解,所以k1和k2必互素,所以这里是M2一定是可求的

Related Message Attack

前面做了这么多证明铺垫,最后当然要祭出大招,即求解方法

这里的攻击是有方法名称的,即Related Message Attack

在e=3的情况下,我们可以利用rsa padding得到明文

根据之前第一步的推导,我们得到了

我们将式子变形为

移项得到

根据立方差公式,我们又有

联立

我们将式子1左右同乘 aM2-b ,将式子2左右同乘 3b

然后即可得到如下式子

我们再把c2带入得到

则最后可以有

即可求得M2

而我们知道

所以最后有

注意,这里的分式不是除法,是逆元

payload

既然推导出了公式,写脚本即可

def getM2(a,b,c1,c2,n):
    a3 = pow(a,3,n)
    b3 = pow(b,3,n)
    first = c1-a3*c2+2*b3
    first = first % n
    second = 3*b*(a3*c2-b3)
    second = second % n
    third = second*gmpy2.invert(first,n)
    third = third % n
    fourth = (third+b)*gmpy2.invert(a,n)
    return fourth % n
m = getM2(a,b,c1,c2,n)-padding2
print libnum.n2s(m)

Coppersmith’s short-pad attack

上述情况是e=3时候,我们可以根据

推导出m

那么当e不是3的时候怎么办呢?

这里稍作拓展,我们可以用Coppersmith’s short-pad attack,即padding过短引起的攻击

脚本如下

https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage

后记

根据这一次学习,不难发现在存在padding的情况下,rsa也存在各种风险:

1.若e=3,则可以利用Related Message Attack

2.若e不为3,但padding过短,则可以利用Coppersmith’s short-pad attack


分享给小伙伴们:
本文标签: RSA

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号