SCERush's Blog
0%

CTF中RSA的常见套路

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

当时学习RSA的时候感觉挺简单的，但一到做题时，就发现还有很多地方没有理解透，这里记录一下CTF中RSA的常见套路，参考来源：https://wiki.x10sec.org/crypto/introduction/
https://err0rzz.github.io/2017/11/14/CTF中RSA套路/index.html
这里仅记录一些代码，具体解法还请参考：https://www.anquanke.com/post/id/84632
需要注意：关于gmpy2库的使用，可以参考https://www.cnblogs.com/pcat/p/5746821.html

数据提取

一般来说，RSA都围绕着c,m,d,n,p,q这几个参数展开，但不会给出全部，给出其中几个来求解。数据的给出也有以下几种方式：

  • txt文件：直接给出已知数据，分析求解
  • 源文件：直接将加密的源文件给出，通过分析源代码，编写程序求解
  • pem文件：针对这类文件需要使用openssl来提取数据
    1
    2
    openssl rsa -pubin -text -modulus -in warmup -in public.pem
    openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
  • pcap文件：针对这类文件可以使用wireshake follow一下。这种问题一般都是写了一个交互式crypto系统，可能产生多轮交互
  • ppc模式：这种模式是上述pcap文件的交互版，会给一个端口进行一些crypto的交互，参数会在交互中给出

模数分解

先说一说RSA中最简单最暴力的，直接分解n，一般给出的n不会太大

已知n求p，q

  • 在线分解：http://www.factordb.com/
    通过在此类网站上查询n，如果可以分解或者之前分解成功过，那么可以直接得到p和q。此类问题一般是分值较小的题目，提取出n之后可以发现n的长度小于等于512bit，可以直接取分解n。如果大于512bit，建议在使用每个题目都用后面所说的方法去解题。
  • yafu分解：https://sourceforge.net/projects/yafu/
    下载解压后直接打开程序，输入factor(n)，n为要分解的数，即可
  • 公约数分解n：一般这种是用于题目给出了两个及以上的n，可以使用这种方法来得到p和q，然后n1与n2的最大公因数就是p，再用n1或n2除以p就能得到q1或q2 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def gcd(a, b):
        if a < b:
          a, b = b, a
        while b != 0:
          temp = a % b
          a = b
          b = temp
        return a

    p = gcd(n1, n2)
    q1 = n1/p
    q2 = n2/p
    或者直接使用gmpy2库
    1
    2
    3
    4
    5
    import gmpy2

    p = gmpy2.gcd(n1, n2)
    q1 = n1/p
    q2 = n2/p

已知e，p，q求d

一般e都是直接给出的，然后得到p和q之后，便可以求d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

d = modinv(e,(p-1)*(q-1))

#或者使用gmpy2
import gmpy2

d = gmpy2.invert(e,(p-1)*(q-1))

已知c，d，n求m

1
pow(c, d, n)

低加密指数攻击

e = 3时的小明文攻击

识别：e=3时
如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。
如果明文的三次方虽然比n大，但是大不了多少，则可以爆破。

1
2
3
4
5
6
i = 0
while 1:
  if(gmpy2.iroot(c+i*n, 3)[1]==1):
    print gmpy2.iroot(c+i*n, 3)
    break
  i = i + 1

低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。
这个识别起来比较简单，一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且e都取了一个较小的数字。
（个人还没做到过）

低解密指数攻击

识别：简单来说，就是e非常大
GitHub上的开源攻击代码：https://github.com/pablocelayes/rsa-wiener-attack
这里注意一个细节问题，如果在运行脚本的时候报错，请在脚本前加上：

1
2
import   sys
sys.setrecursionlimit(10000000)

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
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

d = hack_RSA(e,n)

共模攻击

识别：若干次加密，e不同，n相同，m相同。就可以在不分解n和求d的前提下，解出明文m。
给出了c1，c2，e1，e2，n

1
2
3
4
5
6
7
8
9
10
11
import gmpy2

gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
	s = -s
	c1 = gmpy2.invert(c1, n)
if t < 0:
	t = -t
	c2 = gmpy2.invert(c2, n)

m = gmpy2.powmod(c1,s,n) * gmpy2.powmod(c2,t,n) % n

已知dp，dq

最开始看到dp和dq时还查了好久，不知道啥意思，推导参考：https://beiyuouo.github.io/beiyuouo.github.io/blog/ctf-buuctf/

已知dp，dq，p，q，c

其中

使用中国剩余定理即可，但p-1与q-1不互质，推导如下：

最后

1
2
3
4
5
6
import gmpy2

n = p*q
phi = (p-1)*(q-1)
dd = gmpy2.gcd(p-1, q-1)
d=(dp-dq)//dd * gmyp2.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq

已知e，n，dp，c

dp同上

然后枚举x就可以计算出p-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2

for x in range(1,e):
	if(e*dp%x==1):
        	p=(e*dp-1)//x+1
        	if(n%p!=0):
        	    continue
        	q=n//p
        	phin=(p-1)*(q-1)
        	d=gmpy2.invert(e, phin)
        	m=gmpy2.powmod(c, d, n)
        	if(len(hex(m)[2:])%2==1):
        	    continue

            print m

已知e，d，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
import gmpy2
import sympy
# n = p * q
n =
# e_d = e * d
e_d = 
f, s, tem = e_d-1, 0, 1
while f % 2 == 0:
    f = f // 2
    s += 1
i, a, t = s, 2, f
b = pow(a, t, n)
while b == 1:
    a = sympy.nextprime(a)
    b = pow(a, t, n)
while i != 1:
    c = pow(b, 2, n)
    if c != 1:
        b = c
        i -= 1
    else:
        break
if b == n-1:
    a = sympy.nextprime(a)
    b = pow(a, t, n)
    while b == 1:
        a = sympy.nextprime(a)
        b = pow(a, t, n)
p = gmpy2.gcd(b-1, n)
q = n//p

已知n(pq)，(p-1)(q-1)

利用二分法求p，q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# n = p * q
n =
# phi = (p- 1 ) * (q - 1)
phi =

c=n-phi+1 # p + q
l=c/2
r=c

while l<r:
    p=(l+r)/2
    y=p*(c-p)
        if y==n:
            print p
            break
        if y>n:
            l=p
        else:
            r=p
q=c-p
print q

中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
ms=[]
cs=[]
def CRT(bs,ms):
    m = reduce(lambda x,y: x*y, ms)
    re = 0
    for i in range(len(ms)):
        M = m / ms[i]
        gcd, n1, M1 = gmpy2.gcdext(ms[i], M)# ms[i]*n1 + M*M1 = 1
        re += bs[i] * M * M1
    return re % m
m = CRT(cs,ms)