CTF中的RSA套路_rsa ctf

CTF中的RSA套路

前言

RSA是在CTF中经常出现的一类题目。一般难度不高，并且有一定的套路。
在RSA里面的几个基本参数。

N：大整数N，我们称之为模数（modulus）
p 和 q ：大整数N的两个因子（factor）
e 和 d：互为模反数的两个指数（exponent）
c 和 m：分别是密文和明文
1
2
3
4

而{N,e}称为公钥,{N,d}称为私钥。总的来说,明文m(一般为flag)就像是一个锁,而私钥就是打开这个锁的钥匙。我们要做的就是根 据公钥来生成这把钥匙来打开锁。而私钥中的N又是可以从公钥中获得的，所以关键就是在d的获取，d的值和p,q,e有关。p,q又是N的 两个因子，所以RSA题目关键便是对N的分解，分解出N的两个因子题目便解决了。这便是RSA题目的思路。

具体类型

已知p,q,e，获取d

这种题目一般不难，是RSA里面的入门题目。通常可以使用python脚本解题。

import gmpy2
p =gmpy2.mpz(336771668019607304680919844592337860739)
q =gmpy2.mpz(296173636181072725338746212384476813557)
e =gmpy2.mpz(65537)
phi_n= (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
print("d is:")
print (d)
1
2
3
4
5
6
7
8

也可以通过RSA-Tool解出d.

已知e,d,N,求p,q

python代码如下:

import libnum
d = 79636639378326691339908122673730404813380296570362148297604910660437221154417
e = 65537
n = 99742889480132178464693625265991467727088330702125690789109469022100733238623
k = e * d - 1
r = k
t = 0
while True:
    r = r / 2
    t += 1
    if r % 2 == 1:
        break
success = False
for i in range(1, 101):
    g = random.randint(0, n)
    y = pow(g, r, n)
    if y == 1 or y == n - 1:
        continue
    for j in range(1, t):
        x = pow(y, 2, n)
        if x == 1:
            success = True
            break
        elif x == n - 1:
            continue
        else:
            y = x
    if success:
        break
    else:
        continue
if success:
    p = libnum.gcd(y - 1, n)
    q = n / p
    print 'P: ' + '%s' % p
    print 'Q: ' + '%s' % q
else:
    print 'Cannot compute P and Q'
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
35
36
37
38

已知N,e,c，求m

这种题目要先分解出p,q。之后的python代码如下:

#!/usr/bin/env python # -*- coding: utf-8 -*- import gmpy2
p = 336771668019607304680919844592337860739
q = 296173636181072725338746212384476813557
e = 65537
c = 55907434463693004339309251502084272273011794908408891123020287672115136392494
n = p * q
fn = (p - 1) * (q - 1)
d = gmpy2.invert(e, fn)
h = hex(gmpy2.powmod(c, d, n))[2:]
if len(h) % 2 == 1:
    h = '0' + h
s = h.decode('hex')
print s
1
2
3
4
5
6
7
8
9
10
11
12
13

给出公钥文件和密文文件获取明文

出题人会给你一个公钥文件（通常是以.pem或.pub结尾的文件）和密文（通常叫做flag.enc之类的），你需要分析公钥，提取出（N，e），通过各种攻击手段恢复私钥，然后去解密密文得到flag。 EG:一般先用openssl提取公钥文件中的N和e。

root@kali:~/桌面/RSA# openssl rsa -pubin -text -modulus -in public.pem
RSA Public-Key: (256 bit)
Modulus:
    00:dc:84:79:8f:78:6d:6d:ab:33:14:46:3e:2c:5f:
    27:cd:0d:c4:8a:0f:97:13:da:fc:f9:18:02:eb:bc:
    b7:1d:5f
Exponent
1
2
3
4
5
6