sky's blog

RSA之拒绝套路(1)

字数统计: 548阅读时长: 2 min
2018/08/24 Share


1
文章首发在合天智汇

前言

近期在复习数论和密码学的题目,于是先从RSA开始,做一些题目推导与证明
希望知其然,知其所以然,而不是一味的跟着套路走

RSA大众套路

在拒绝套路之前,先给出常见的套路
曾经这篇文章已经总结的很好了

1
https://www.anquanke.com/post/id/84632

这里简单的概述总结一下:

  • 1.e较大:Wiener攻击
  • 2.e较小:直接开方
  • 3.低加密指数广播攻击:相同低指数的e和多个相同的消息m
  • 4.Coppersmith定理攻击:只有部分高位的p或q
  • 5.共模攻击:相同n,相同m
    ……..
    话不多说,下面从非套路的题目开始

题干

例如题目

1
2
3
4
5
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

注意,其中dp的意思为:

公式推导

现在我们可以知道的是

由式5*e可以得到

因此可以得到

我们将式1带入式2可以得到

故此可以得到

变换一下

因为

可以得到

我们假设

可以得到x的范围为

因此有

那么我们可以遍历

求出p-1,求的方法也很简单,遍历65537种可能,其中肯定有一个p可以被n整除
那么求出p和q,即可利用

推出

注:这里的-1为逆元,不是倒数的那个-1

payload

写下如下脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
import libnum
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1,65538):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)/i)+1)==0:
p=((dp*e-1)/i)+1
q=n/(((dp*e-1)/i)+1)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)%phi
print libnum.n2s(pow(c,d,n))

即可得到flag

1
flag{wow_leaking_dp_breaks_rsa?_98924743502}

反思

现在不难得出结论,RSA中,如果dp或者dq任意一个泄露都可以导致密文被破解
因为上述的证明过程,没有用到任何特例情况。
但是如果e较大的话,可能会比较困难一些,但是如果e过大,那就可以使用维纳攻击了XD

点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. 前言
  2. 2. RSA大众套路
  3. 3. 题干
  4. 4. 公式推导
  5. 5. payload
  6. 6. 反思