CTF中RSA加密的简单学习

2018年9月28日18:34:46 发表评论 13,905

摘要

本文讲述的是RSA加密的基本实现原理，以及其在CTF中基本题目的结题思路，附带解题脚本，可供新手学习入门，应付简单的RSA题目将不是难题。

0x01 RSA加密简介

RSA的简介百度百科上已经讲的很清楚了，这里就简单的陈述一下，只要记住RSA中的几个点就好了。RSA的名字来源于其三位作者的名字首字符；RSA是一种非对称加密;RSA是一种公认的非常安全的公钥加密方式，我们长见的SSL协议采用的加密方式就是RSA非对称加密；RSA加密使用公钥，解密使用私钥，所以是非对称加密，公钥可由私钥生成。

在CTF中RSA其实是一类非常简单的送分题，只要掌握简单的数学原理和基本工具的使用，一般很容易计算出结果，长见的攻击方式有n爆破攻击、共模攻击、低指数攻击。具体讲解请看下文。

0x02 RSA加密基本概念

下面是RSA的基本元素和加密解密公式，后面我们将围绕该表进行讲解。

公钥 KU	n：两素数p和q的乘积（p和q必须保密）。 e：与（p-1)(q-1)互质的数。
私钥 KR	d： e^-1 mod (p-1)(q-1) 的结果 n：同上
加密	c = m^e mod n
解密	m = c^d mod n

我们只要记住六个字母m、c、p、q、n、e，其中m代表我们要加密的文明，c代表我们加密后的密文，p和q是我们随机找的大素数，n代表p和q的乘积称为模数，e是我们找到的和(p-1)(q-1)互质的数称为加密指数，可能到这里我们需要补充一下数学上的几个概念。

什么是素数？

素数（质数）：一个数如果除了1和它本身外不能再被其他整数整除，那么这个数就是素数比如17。

什么是互质数？

互质数（互素数）：公约数只有1的两个整数称为互质数比如13和17.

公钥（KU）由(n,e)组成，有了公钥我们就可以进行数据的加密。

私钥（KR）由(n,d)组成，有了私钥我们可以对密文进行数据解密。

0x03 RSA加、解密基本流程

随机选择一对足够大的素数p和q。
根据n = p*q计算出n的值，一般n非常大，p和q需要保密。
根据f(n) = （p-1)(q-1)计算出f(n)的结果。
找到一个和f(n)互质的数e，一般用65537（0x10001)。
根据ed ≡ 1 mod n我们可以计算出d的值。注意≡代表数论中的同余，如：1 mod n的结果为1那ed mod n的结果也必须是1。
加密明文m时使用(n,e)公钥，使用公式c = m^e mod n，如果m比较长，我们可以分割成适当的组，注意加密的时都是数学计算，文本需要转化为数字。
解密密文c时使用(n,d)私钥，使用公式m = c^d mod n。

从上面的流程中我们可以总结如下，我们的加密解密的关键点在于p和q，以及他们的乘积n，因为我们的加密需要使用n和e，因为e是非常容易拿到的，所以只要能根据n分解出p和q那么我们就能计算出d，然后拿到私钥对密文解密。

0x04 CTF中RSA的基本思路

其实在CTF中RSA还是非常简单的，通常就是那么几种攻击方式。

直接求解
模数n分解
共享素数攻击
共模攻击

0x05 RSA直接求解

这种是最简单的，一般不会碰到，通常是给出参数p、q、e和密文c求解明文m,这种考法主要考察参赛选手对RSA加密解密公式的理解。直接使用工具解密即可，下面介绍一款工具：

RSA-tool

该工具为可视化工具，可以很方便的计算出RSA中的各项参数。

0x06 RSA模数n分解攻击

如果n不是特别大的情况下我们可以尝试使用工具暴力分解n拿到p和q，这里推荐几个工具:

msieve

该工具是一款命令行工具，包含32和64两个版本，可以将n直接输入到命令行中，也可以在文件中读取，使用参数-v可以看到运行的详细信息。但当n较长的时候还是不适用。

点击下载msieve

yafu

这个就是神器了，就算n较长也是可以分解的（相对于msieve）而言个人感觉比较强大，非常推荐。

点击下载yafu

下面讲解一个简单的例子：

题目链接：http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

{920139713,19}
 
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
......
......

{920139713,19}

704796792

752211152

274704164

18414022

368270835

483295235

263072905

459788476

483295235

459788476

663551792

......

大括号中应该对应的是n和e，因为n不大，所以我们只需要分解出p和q即可求出密钥d。然后下面的每一行应该是一个密文，等我们拿到密钥，然后按行解密即可，下面是解题脚本。

#coding:utf-8

def crackN(n):
	i = 2
	while i < n :
		if n % i == 0:
			break
		i = i+1
	return i

n = 920139713
e = 19

p = crackN(n)
q = n / p

fn = (p-1)*(q-1)

i = 1
d = 0
while (True):
	if (fn * i +1) % e == 0 :
		d = (fn * i +1) / e
		break
	i = i+1

print "d:%s" % d

c = open("c.txt")
m = ''
for line  in c:
	line = line.replace('\n','')
	m += chr(pow(int(line), d , n))
	print m

#coding:utf-8

def crackN(n):

i = 2

while i < n :

if n % i == 0:

break

i = i+1

return i

n = 920139713

e = 19

p = crackN(n)

q = n / p

fn = (p-1)*(q-1)

i = 1

d = 0

while (True):

if (fn * i +1) % e == 0 :

d = (fn * i +1) / e

break

i = i+1

print "d:%s" % d

c = open("c.txt")

m = ''

for line in c:

line = line.replace('\n','')

m += chr(pow(int(line), d , n))

print m

运行结果如下：

这道题目算是常规题了，题目中的n非常小，但是我们通常遇到的n因该是比较大的，普通的脚本跑出来是非常慢的，需要借助工具，但是本题就直接写了个小函数分解n了。

还有一类题目也是类似分解n的，只不过是采用了文件的形式，公钥和私钥都是文件，通常是key和pem为扩展名的文件。这类题目需要借助openssl工具分析出公钥中的n和e，然后套路就和上面差不多了，分解n，然后计算出私钥，但是要使写脚本自己生产私钥，并且解密密文文件也需要openssl命令来执行，下面介绍一下这个流程的命令和脚本。

假如有一个公钥文件public.pem，密文文件flag.enc

使用下面的命令分析公钥：

openssl rsa -pubin -text -modulus -in public.pem

1	openssl rsa -pubin -text -modulus -in public.pem

运行结果中将拿到n值和加密指数e

如果n不大，我们可以使用工具yafu分解n，命令如下

yafu-x64.exe "factor(@)" -batchfile 文件名

1	yafu-x64.exe "factor(@)" -batchfile 文件名

我们到这里已经拿到了p和q的值，下面我们来生产私钥文件，脚本如下：

import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 0xD7DB8F68BCEC6D7684B37201385D298B
keypair.q = 0xC292A272E8339B145D9DF674B9A875D5
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
    x = (Qn * i ) + 1
    if (x % keypair.e == 0):
        keypair.d = x / keypair.e
        break
    i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

import math

import sys

from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 0xD7DB8F68BCEC6D7684B37201385D298B

keypair.q = 0xC292A272E8339B145D9DF674B9A875D5

keypair.e = 65537

keypair.n = keypair.p * keypair.q

Qn = long((keypair.p-1) * (keypair.q-1))

i = 1

while (True):

x = (Qn * i ) + 1

if (x % keypair.e == 0):

keypair.d = x / keypair.e

break

i += 1

private = open('private.pem','w')

private.write(keypair.exportKey())

private.close()

请自行修改脚本中的p、q、e的值，我们将拿到私钥文件private.pem，下一步将进行解密，命令如下：

RSA openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.txt

1	RSA openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.txt

此命令的含义是采用私钥文件private.pem来解密文件flag.enc，结果保存到flag.txt中，到此位置，我们就完整的解出了这道题目。如需要题目文件请留言。

0x07 RSA共享素数攻击

这类题目其实还不是很常见，但也简单的介绍一下。当我们生成p和q的时候，难免有重复的，比如我们使用了p、q1和p、q2生成了n1和n2，就可以说我们的q被n1和n2共享了，如果我们能拿到这两个n，那么我们很容易就可以得到q1和q2，为什么呢？因为我们可以使用最大公约数gcd算法很快的计算出q，那么q1和q2也就很容易计算出来了，后面就不用再说了，直接计算d然后用私钥解密即可。

0x08 RSA共模攻击

这种攻击方式还是很常见了，该攻击的基本条件如下：

同一份明文m使用不同的秘钥加密了两次
两次生成秘钥时模数n相同但加密指数e不相同
我们能拿到两个不同的密文c1、c2和模数n、加密指数n1、n2

在满足上面条件的情况下我们可以在不用获得秘钥d的情况下解密出明文m，基本的数学原理这里不做赘述，可自行百度研究，下面直接给出解密脚本。

#coding=utf-8
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
def main():
	n = int(raw_input("input n:"))
	c1 = int(raw_input("input c1:"))
	c2 = int(raw_input("input c2:"))
	e1 = int(raw_input("input e1:"))
	e2 = int(raw_input("input e2:"))
	s = egcd(e1, e2)
	s1 = s[1]
	s2 = s[2]
	# 求模反元素
	if s1<0:
		s1 = - s1
		c1 = modinv(c1, n)
	elif s2<0:
		s2 = - s2
		c2 = modinv(c2, n)
	m = (c1**s1)*(c2**s2)%n
	print m
if __name__ == '__main__':
	main()

#coding=utf-8

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

def main():

n = int(raw_input("input n:"))

c1 = int(raw_input("input c1:"))

c2 = int(raw_input("input c2:"))

e1 = int(raw_input("input e1:"))

e2 = int(raw_input("input e2:"))

s = egcd(e1, e2)

s1 = s[1]

s2 = s[2]

# 求模反元素

if s1<0:

s1 = - s1

c1 = modinv(c1, n)

elif s2<0:

s2 = - s2

c2 = modinv(c2, n)

m = (c1**s1)*(c2**s2)%n

print m

if __name__ == '__main__':

main()

脚本来自互联网，非原创并未测试，若有问题还请留言。

0x09 RSA低加密指数攻击

所谓低加密指数指的就是e非常小的情况下，通常为3，再CTF中也是有可能出现着用题目的，这种题目通常有两种类型，一种直接爆破，另外一种是低指数广播攻击。

首先介绍比较简单的情况，比如我们的e为3，n很淡，但是明文缺很小。这种情况下回出现什么呢？我们先看一下加密公式：c = m^e mod n , 当我们的 m^e < n 的情况下 c将等于m^e ，又因为e很小，所以我们可以直接对c开方求得明文m。

上面说的是m^e < n 的情况，那如果m^e > n 呢? 注意 m^e不能太大，否则将很难爆破。我们可以尝试进行爆破，假设我们 m^e / n 商 k 余数为c ,这里的k就是我们的商了，c就是模值，所已m^e =n*k+c , 我们可以对k进行爆破然，只要n*k+c的结果可以开方就可以求得明文m。

0x0A RSA低加密指数广播攻击

首先介绍什么是广播，加入我们需要将一份明文进行多份加密，但是每份使用不同的密钥，密钥中的模数n不同但指数e相同且很小，我们只要拿到多份密文和对应的n就可以利用中国剩余定理进行解密。关于中国剩余定理请参考文章：点击查看。

只要满足一下情况，我们便可以考虑使用低加密指数广播攻击：

加密指数e非常小
一份明文使用不同的模数n，相同的加密指数e进行多次加密
可以拿到每一份加密后的密文和对应的模数n、加密指数e

攻击脚本如下：

# coding:utf8

from struct import pack,unpack
import zlib
import gmpy
def my_parse_number(number):
    string = "%x" % number
    #if len(string) != 64:
    #    return ""
    erg = []
    while string != '':
        erg = erg + [chr(int(string[:2], 16))]
        string = string[2:]
    return ''.join(erg)
def extended_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0
    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y
    return (lastx, lasty, a)
def chinese_remainder_theorem(items):
  N = 1
  for a, n in items:
    N *= n
  result = 0
  for a, n in items:
    m = N/n
    r, s, d = extended_gcd(n, m)
    if d != 1:
      N=N/n
      continue
      #raise "Input not pairwise co-prime"
    result += a*s*m
  return result % N, N
sessions=[
{"c": 18547562724906720577486693684739489152547099593770967227662477478402201412715, "e": 7, "n": 53005661126534868602318707133611899019730819612971397126467405275805291247593},
{"c": 38080214796844206733759849504393184114911570888290711280913147447511559455673, "e": 7, "n": 84080528857266683438885394596690106809484104855460348347690627904896317465537},
{"c": 64341186257788012263409881160841287235929197643049077877015427200375821245501, "e": 7, "n": 84173503532728082763432007316428245924416536365662064681543769793438063575441}
]

data = []
for session in sessions:
    e=session['e']
    n=session['n']
    msg=session['c']
    data = data + [(msg, n)]
print "Please wait, performing CRT"
x, n = chinese_remainder_theorem(data)
e=session['e']
realnum = gmpy.mpz(x).root(e)[0].digits()
print my_parse_number(int(realnum))

# coding:utf8

from struct import pack,unpack

import zlib

import gmpy

def my_parse_number(number):

string = "%x" % number

#if len(string) != 64:

# return ""

erg = []

while string != '':

erg = erg + [chr(int(string[:2], 16))]

string = string[2:]

return ''.join(erg)

def extended_gcd(a, b):

x,y = 0, 1

lastx, lasty = 1, 0

while b:

a, (q, b) = b, divmod(a,b)

x, lastx = lastx-q*x, x

y, lasty = lasty-q*y, y

return (lastx, lasty, a)

def chinese_remainder_theorem(items):

N = 1

for a, n in items:

N *= n

result = 0

for a, n in items:

m = N/n

r, s, d = extended_gcd(n, m)

if d != 1:

N=N/n

continue

#raise "Input not pairwise co-prime"

result += a*s*m

return result % N, N

sessions=[

{"c": 18547562724906720577486693684739489152547099593770967227662477478402201412715, "e": 7, "n": 53005661126534868602318707133611899019730819612971397126467405275805291247593},

{"c": 38080214796844206733759849504393184114911570888290711280913147447511559455673, "e": 7, "n": 84080528857266683438885394596690106809484104855460348347690627904896317465537},

{"c": 64341186257788012263409881160841287235929197643049077877015427200375821245501, "e": 7, "n": 84173503532728082763432007316428245924416536365662064681543769793438063575441}

]

data = []

for session in sessions:

e=session['e']

n=session['n']

msg=session['c']

data = data + [(msg, n)]

print "Please wait, performing CRT"

x, n = chinese_remainder_theorem(data)

e=session['e']

realnum = gmpy.mpz(x).root(e)[0].digits()

print my_parse_number(int(realnum))

ps：以上脚本来自互联网，使用时请自行修改脚本中的参数。

运行结果如下图：

文件下载

下载RSA-tool

CTF中RSA加密的简单学习

0x01 RSA加密简介

0x02 RSA加密基本概念

0x03 RSA加、解密基本流程

0x04 CTF中RSA的基本思路

0x05 RSA直接求解

0x06 RSA模数n分解攻击

0x07 RSA共享素数攻击

0x08 RSA共模攻击

0x09 RSA低加密指数攻击

0x0A RSA低加密指数广播攻击

文件下载

发表评论取消回复

微信

0x01 RSA加密简介

0x02 RSA加密基本概念

0x03 RSA加、解密基本流程

0x04 CTF中RSA的基本思路

0x05 RSA直接求解

0x06 RSA模数n分解攻击

0x07 RSA共享素数攻击

0x08 RSA共模攻击

0x09 RSA低加密指数攻击

0x0A RSA低加密指数广播攻击

文件下载

发表评论取消回复

登录 找回密码

微信

登录找回密码