RSA的常见攻击方法

发表于 | 分类于 | 作者：ESE

我不生产RAS,只是RAS的搬运工…..

前言

这里就不讨论数论的基础了，进行RSA的题目解答，至少要懂得基本的数论知识的，如果不了解数论的基本知识的话，网上相关内容还是挺多的。

RSA基于一个简单的数论事实，两个大素数相乘十分容易，将其进行因式分解确实困难的。在量子计算机还没有成熟的今天，RSA算法凭借其良好的抵抗各种攻击的能力，在公钥密码体制中发挥着中流砥柱的作用。然而即便RSA算法目前来说是安全可靠的，但是错误的应用场景，错误的环境配置，以及错误的使用方法，都会导致RSA的算法体系出现问题，从而也派生出针对各种特定场景下的RSA攻击方法。

本文针对一些在CTF中常见的RSA攻击方法，从如何识别应该应用那种方法以及如何去解题来介绍CTF中的RSA题目的常见解法。

RSA算法描述

RSA算法涉及三个参数，n，e，d，私钥为n，d，公钥为n，e。
其中n是两个大素数p，q的乘积。
c为密文，m为明文，则加解密过程如下：

1
2
c=m^e mod n 
m=c^d mod n

n，e是公开的情况下，想要知道d的值，必须要将n分解计算出n的欧拉函数值，而n是两个大素数p，q的乘积，将其分解是困难的。

RSA题目类型

在CTF竞赛中，RSA理所当然处在CRYPTO中居多。而且RSA作为典型的加密算法，其出镜率可谓相当高，基本上所有比赛都会有几道RSA的题目出现。

数据处理

在进行做题之前，我们要将数据处理成可以做题的模式。基本上来说，RSA的题目都是围绕着c，m，e，d，n，p，q这几个参数展开的，但是题目一般不会直接给这种样子的参数，而是通过别的方式给出，这里就需要我们使用一些工具或者自己手工将这些参数提取出来。

pem文件：

针对此类文件可以直接使用openssl提取(一般在kali)，大概使用过的方式有：

1
2
openssl   rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
openssl   rsa -pubin -text -modulus -in warmup -in public.pem

知道public.key

openssl rsa -pubin -text -modulus -in public.key
可求得n,e
然后用msieve分解，下载地址
使用
msieve153.exe 0xD99E952296A6D960DFC2504ABA545B9442D60A7B9E930AFF451C78EC55D555EB -v

知道q,p,求出d。
接着github上下载rsatool.py,
python rsatool.py -f PEM -o key.pem -n 13826123222358393307 -d 9793706120266356337
解密
openssl rsautl -decrypt -in encrypted.message -inkey key.pem -out flag.txt

pcap文件：

针对此类文件可以使用wireshark follow一下。这种问题一般都是写了一个交互的crypto系统，所以可能产生多轮交互。

PPC模式：

这种模式是上述pcap文件的交互版，会给一个端口进行一些crypto的交互，参数会在交互中给出。
第二个需要处理的就是明密文，这个方法多多，不多赘述。

RAS攻击方法

模数分解

说一说
解决RSA题目最简单，最暴力，最好使的方法就是分解模数n。如果能够将n分解成功，成功得到p，q的取值，那么可求n的欧拉函数的值。

求d与m代码

通过欧几里得算法可以通过e与n的欧拉函数的值轻易求出d，从而计算出解密密钥。
即在知道e，p，q的情况下，modinv函数即为求模拟的函数,可以解出d,接着即可求出解密密钥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import libnum
def egcd(a, b):
    if a == 0:
      return (b, 0, 1)
    else:
      g, y, x = egcd(b % a, a)
      return (g, x - (b // a) * y, y)
def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
p = 13574881
q = 23781539
n = p * q
e = 23
c = 0xdc2eeeb2782c
d=modinv(e,(p-1)*(q-1))
m=pow(c,d,n)
s= libnum.n2s(m)
print s

当然可以用gmpy2会更方便

1
2
3
4
5
6
7
8
9
import libnum
import gmpy2
p = 13574881
q = 23781539
e = 23
d =gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
s= libnum.n2s(m)
print s

直接分解n

分解网站:
http://factordb.com
也可以用yafu

识别

n的长度小于等于512bit，如果大于512bit，则一般分解不出来

例题：

比如在某次竞赛中，发现：
n=87924348264132406875276140514499937145050893665602592992418171647042491658461
利用factordb分解

利用公约数

识别

通常会发现题目给了若干个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。

例题：

在一个题目中，你拿到了两个n，e都为65537，两个n分别为：

1
2
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

通过直接分解，上factordb都分解失败。通过尝试发现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
代码
```C
def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a
print gcd(n1,n2)
打印出：
```C
1564859779720039565508870182569324208117555667917997801104862601098933699462849007879184203051278194180664616470669559575370868384820368930104560074538872199213236203822337186927275879139590248731148622362880471439310489228147093224418374555428793546002109

则此致即为两个n共有的素因子p，然后进一步求出q，求解完毕。

Fermat方法与Pollard rho方法

此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。

识别

在直接分解n无望，不能利用公约数分解n之后，都应该使用yafu去试一下。

低加密指数攻击

在RSA中e也称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是选取不当的话，就会造成安全问题。

介绍

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

例题:

关键代码如下：通过不断给明文+n开三次方即可求得：

1
2
3
4
5
6
i=0
   while 1:
   if(gmpy.root(c+i*N, 3)[1]==1):
     print gmpy.root(c+i*N, 3)
     break
   i=i+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum
e = 0x3
n = 0x7438b43e2186d818bce041be5d0101d2891a34015a9549f61d7df5dfdb10949c6937723de93e405bea791334d51f1d0585e006b9e400ae8be29347e39fa6ac156e24d8ca5fdc54204a2cc96bf29176858ea1d1dd3578ba14716eb3db0f60aef0e561f5ef6905e16f10025a2d7ff3f673deeae607d539eca169f3ef829fffb1b5
c = 0xb3b496b9eb7ae0d251191442f5a6fb1f3e6f87f8529bc41d3c6b075c11ae141861e1469a88c6baa9fa8a29e5f3b92e3ab4900057b435329178b0a5fdc78756d2d119ca1a97e6214dce1b5569930741eacb4640214c607c25c8565a6b6d3dcc770d8fc718c0a330d142f2e702e02c401d095efcebf3aa906a3d238b97465
i=0
while 1:
   m = gmpy2.iroot(c+n*i,e)[0]
   s= libnum.n2s(m)
   if 'flag{' in s:
    print s
   if 'FLAG{' in s:
    print s
   if 'ctf{' in s:
    print s
   if 'CTF{' in s:
    print s
   i=i+1

若有字符串

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
import libnum
import base64
c1 = "FATe12RvmXf/xIGAvNprfAQUpt1RBFw1m/zXkDKGr/vNjy9mTyT/2khYY5zcRB68fiuaehpa5HqhYprATPNty1ui+3KhW4iUBZC0J7/6zCPwocHPouHrNq3NAXhLgxYKrZkr+elHcCaP9Qz8Y6V9fH6THuWRNNVqxnaima5HdVaxxzFUYkM53fvqmsaNZEpWuFDz"
c2 = "FATe12RvmXf/xIGAvNprfAQUpt1RBFw1m/zXkDKGr/vNjy9mTyT/2khYY5zcRB68j7m+E97aqeoObnxAe3oAKXY3RgH2FyW3oKuVYTx5VxGjCksbPd5cK2mqY/yc8qSgQ/v3JREuSAPNc1muPCv9A+FcnU6m9BHERDOxyUuZosK66GTyirqVTaC2YnviYVnoyVJT"
n = 27262030738190162906068533309218248319312037416856794814532459866130196673561833084739048171769479893806671499522643803412108279907223895517897969906253626028270289028646596897429641138913001561947557784840311014399973312098056896539904624036584153785225626096007313018814076860235378686567457599895712604364100507424939342862464483596795761725357279364545154915110900098124905389351969357103586063992040096368146580315262263546850581515833590884397726108478477798668261762306189036525841356592859315437201733146083995028221597538824801113980100295046731791678895520928441645173205511865657977068061078456941189550383
e = 3
b=base64.b64decode(c2)
c=libnum.s2n(b)
m = gmpy2.iroot(c,e)[0]
s= libnum.n2s(m)
print s

低解密指数攻击

介绍：

与低加密指数相同，低解密指数可以加快解密的过程，但是者也带来了安全问题。Wiener表示如果满足：

1
$ d<frac{1}{3}gn^frac{1}{4}$      >

那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害RSA的安全。此时需要满足：

1
$q<$$p$$<2q$

如果满足上述条件，通过Wiener Attack可以在多项式时间中分解n。
rsa-wiener-attack的攻击源码开源在了github中，采取python编写，可以很容易使用。

识别

非常简单，e看起来很大就行了。如果密文用不同的ei加密几次,并且用同一个n，那么e=e1e2e3*..,这时e变得很大。就可以攻击啦

例题：

直接github用工具就行。
链接：https://pan.baidu.com/s/194Tqa20WK-F-KZyAElj3pQ 密码：5fyu
https://github.com/pablocelayes/rsa-wiener-attack
这里注意一个细节问题，如果在运行脚本的时候报错，请在脚本前加上：

1
2
import   sys
sys.setrecursionlimit(10000000)

共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。
即：

1
2
3
$ c_1equiv m^{e_1}$ $mod$ $n$
$ c_2equiv m^{e_2}$ $mod$ $n$

此时不需要分解n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。
过程如下，首先两个加密指数互质，则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 $ (e_1,e_2)=1 $
即存在$ s_2 $，$ s_2 $使得：
$ s_1e_1+s_2e_2=1 $
又因为：
$ c_1equiv m^{e_1}$ $mod$ $n$
$ c_2equiv m^{e_2}$ $mod$ $n$
通过代入化简可以得出：
$c_1^{s_1}c_2^{s_2}equiv m$ $mod$ $n$

明文解出。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# -*- coding: utf-8 -*-
from libnum import n2s,s2n
from gmpy2 import invert
# 欧几里得算法
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
def main():
  n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211
  c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853
  c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
  e1 = 1804229351
  e2 = 17249876309
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
  # 求模反元素
  if s1<0:
    s1 = - s1
    c1 = invert(c1, n)
  elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)
  m = pow(c1,s1,n)*pow(c2,s2,n) % n
  print n2s(m)
if __name__ == '__main__':
  main()

识别：

非常简单，若干次加密，每次n都一样，明文根据题意也一样即可。

例题：

https://www.jarvisoj.com
(very hard RSA)如果已知：n1，n2，c1，c2，e1，e2，并且其中n1=n2的话：

1
2
3
4
5
6
7
8
9
10
11
12
s = egcd(e1, e2)
 s1 = s[1]
 s2 = s[2]
   print s
 n=n1
   if s1<0:
     s1 = - s1
     c1 = modinv(c1, n)
   elif s2<0:
     s2 = - s2
     c2 = modinv(c2, n)
 m=(pow(c1,s1,n)*pow(c2,s2,n)) % n

e是偶数时，即当e与(p-1)*(q-1)不互数

例:
e=200这时e=258，我们把e=25，25与(p-1)(q-1)互数,解出来的密文在开8次方。

1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
c=7797067792814175554801975939092864905908878472965854967525218347636721153564161093453344819975650594936628697646242713415817737235328825333281389820202851500260665233910426103904874575463134970160306453553794787674331367563821223358610113031883172742577264334021835304931484604571485957116313097395143177603380107508691261081725629713443494783479897404175199621026515502716868988672289887933681890547568860707175288422275073767747544353536862473367590288531216644146154729962448906402712219657000812226637887827912541098992158458173920228864293993030475885461755767069329678218760943185942331149777258713727459739405
p=111052706592359766492182549474994387389169491981939276489132990221393430874991652628482505832745103981784837665110819809096264457329836670397000634684595709283710756727662219358743235400779394350023790569023369287367240988429777113514012101219956479046699448481988253039282406274512111898037689623723478951613
q=146182161315365079136034892629243958871460254472263352847680359868694597466935352294806409849433942550149005978761759458977642785950171998444382137410141550212657953776734166481126376675282041461924529145282451064083351825934453414726557476469773468589060088164379979035597652907191236468744400214917268039573
e=25
n=p*q
d =gmpy2.invert(e,(p-1)*(q-1))
flag8 = pow(c,d,n)
m=gmpy2.iroot(flag8,8)[0]
s= libnum.n2s(m)
print s

c1,c2只有一个bit不同

例题:
描述
在Alice用帐户名和密码登录一个用RSA加密通信的网站的过程中，不小心将密码的最后一位字符的大小写弄错了，于是重新输入，这一过程恰好被攻击者K监听到，并截获了这两条密文。那么攻击者就能很容易破解出Alice的密码，求出这个密码，提交FLAG。
参考:
https://github.com/ZoEplA/Team233/blob/0bb364f2aef8775230c9552d75465ef6a6aa1fb5/2018/wp/redhet/Team233%20writeup.md

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from hashlib import sha256
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
n = 27262030738190162906068533309218248319312037416856794814532459866130196673561833084739048171769479893806671499522643803412108279907223895517897969906253626028270289028646596897429641138913001561947557784840311014399973312098056896539904624036584153785225626096007313018814076860235378686567457599895712604364100507424939342862464483596795761725357279364545154915110900098124905389351969357103586063992040096368146580315262263546850581515833590884397726108478477798668261762306189036525841356592859315437201733146083995028221597538824801113980100295046731791678895520928441645173205511865657977068061078456941189550383
e = 3
c2 = 80256065280425989347153660555632253204654757632704797390559450985825600409910703812294413750536361555897348650491697548574007864446117693097103136799284683292648287334023253488891301144881769557674366138889636475162525325855368132832237345279798028008137655682278413635753791609965810603989005785747744993045461207072415730041608172272077090225741385971
c1 = 80256065280425989347153660555632253204654757632704797390559450985825600409910703812294413750536361555897348650491699334745453065435184774282609871793525447798655880850590288431173204818294305809864531293135689257716648980215360552397800418527073621708108066406898267720300730094465977262440649283179655484278496374936325875186126245693549228697550672467
diff = 32
m = related_message_attack(c2, c1, diff, e, n)
flag = ('%x' % m).decode('hex')
print flag

Donate
-------------本文结束感谢您的阅读-------------