RSA常见解题思路及技巧

RSA算法介绍

1977年，麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密算法，用他们三人的姓氏缩写命名为 RSA。RSA 既不是惟一，也不是最早的非对称加密算法。但它是使用最广泛，因而也是最重要的非对称加密算法。

RSA算法的可靠性由极大整数因数分解的难度决定。也就是说，对一个极大整数做因数分解越困难，RSA算法越可靠。如果有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极大降低。然而找到这样的算法的可能性是非常低的，如今只有短的RSA密钥才可能被强力方式破解，到2018年为止，还未有任何可靠的攻击RSA算法的方式。

RSA加密算法原理

在开始前可以根据这篇文章复习一下数论基础：

https://blog.sengxian.com/algorithms/mod-world

1、RSA加密解密涉及元素

· N：大整数N，我们称之为模数（modulus）

· p 和 q ：大整数N的两个因子（factor）

· e 和 d：互为模反数的两个指数（exponent）

· c 和 m：分别是密文和明文

· phi：N的欧拉函数值，在求解d的时候常用

2、RSA算法密钥的产生

· 选取两个较大的互不相等的质数p和q，计算n = p * q 。

· 计算phi = (p-1) * (q-1) 。

· 选取任意e，使得e满足 1<e<phi 且 gcd(e , phi) = 1 。

· 计算e关于phi的模逆元d， 即d满足

。

· 加解密：

，

。其中m为明文，c为密文，{n,e}为公钥对，d为私钥，要求 0 <= m < n 。

3、RSA加密解密原理图

模拟场景：

假设A是秘密消息的发送者，B是秘密消息的接收者，则只有B知道私钥{d,n}，所有人都可以知道公钥{e,n}。

加密操作：

如果A要发送需要保密的明文m给B，首先，要用B的公钥{e,n}计算，得到密文c，然后把c发送给B。

解密操作：

B收到密文c之后，根据自己的私钥{d,n}计算,得到的结果就是明文m。

常见解题思路

CTF中的RSA题目一般是将flag进行加密，给出密文c以及其他一些解题需要的信息，需要克服重重难关解密密文c，得到flag（即明文m），一般有下列题型：

1已知p、q、e，求d

求d脚本：get-d.py//rsatool.py(需gmpy模块)

例：

在一次RSA密钥对生成中，假设p=473398607161，q=4511911，e=17，求解d。

代码：

import gmpy2

p = gmpy2.mpz(473398607161)

q = gmpy2.mpz(4511491)

e = gmpy2.mpz(17)

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

d = gmpy2.invert(e, phi)

print d

2已知p、q、e、密文c，求明文m

（1）求d脚本

（2）m=pow(c,d,n)

3已知n、e、密文c，求明文m

（1）分解n

a)yafu.com(https://sourceforge.net/projects/yafu/)

命令行运行 ./yafu-x64.exe，输入：factor(920139713) ，回车即可：

b) http://factordb.com

c) http://www.atool.org/quality_factor.php

（2）求d脚本

（3）m=pow(c,d,n)

例：http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

题目给出了RSA加密之后的密文c、以及加密所用到的e、n的值，求解明文m。

分解n，得到p,q分别为18443,49891，后续脚本如下：

4已知public key，密文c，求明文m

（1）分解public key:

a) public.pem/public.pub文件

i. getn-e.py(RSA模块）

from Crypto.PublicKey import RSA

public = RSA.importKey(open('normal.pub').read())

n = long(public.n)

e = long(public.e)

print n

print e

ii. openssl：

pem/pub文件可以直接使用openssl提取，主要方法如

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

或：

openssl rsa -inform PEM -in normal.pub -noout -modulus -text -pubin

n可以通过factorDB 或者yafu.exe分解得到p

b)public.pcap/public.ppc文件

i. pcap文件：

需要用wireshark等工具分析，根据流量包的通信信息，提取出所有解题需要用到的参数，然后进行解密；

ii. PPC文件：

这种模式是上述pcap文件的交互版，通常会给一个端口进行一些crypto的交互，参数会在交互中给出。

（2）github

a) https://github.com/pablocelayes/rsa-wiener-attack

b) https://github.com/D001UM3/CTF-RSA-tool