Crypto—RSA常见题型总结

Record my learning process of RSA.

CTF

字数统计: 2.6k阅读时长: 10 min

 2020/01/31   Share

前言：

做了很多有关RSA的题，有必要总结一下，题永远做不完的，但是大致的规律都是不变的！

0x01 基本工具的使用

经常使用的RSA工具有openssl、分解整数工具等

openssl

这里也有必要说一下Openssl，OpenSSL 是一个强大的安全套接字层密码库，囊括主要的密码算法、常用的密钥和证书封装管理功能及SSL协议，并提供丰富的应用程序供测试或其它目的使用。

而且Openssl可以提供对称加密算法、非对称加密算法、信息摘要算法、密钥和证书管理，实际上OpenSSL提供的CA应用程序就是一个小型的证书管理中心（CA），实现了证书签发的整个流程和证书管理的大部分机制。

查看公钥文件：

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

解密：

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

详细可以查看openssl

分解整数工具

在线网站分解factor.db

yafu
yafu用于自动整数因式分解，在RSA中，当p、q的取值差异过大或过于相近的时候，使用yafu可以快速的把n值分解出p、q值

下载好之后，进入yafu目录中输入yafu-x64进入命令行
最常用的命令是factor(n)，将n值分解，如：
在这里插入图片描述

实践一下：
Normal_RSA
这道题提供enc和pem文件，解这一类题需要先查看公钥文件中包含的信息，然后通过包含的信息再利用工具生成一个私钥文件用于解密即可
在这里插入图片描述
kail中自带openssl,先查看公钥文件

Exponent即为e,Modulus即为n,发现n是十六进制,先转换成十进制，再进行分解

在这里插入图片描述
有了p 和 q ,便可以求出d

1	d=10866948760844599168252082612378495977388271279679231539839049698621994994673

接下来就可以生成一个私钥，利用私钥求解密文，但是这里遇到点问题，没有办法使用RSAtool,参考师傅的通用脚本（py2）

# coding=utf-8
import math
import sys
from Crypto.PublicKey import RSA
 
keypair = RSA.generate(1024)
keypair.p =
keypair.q =
keypair.e =
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()

在kail中运行即可生成private.pem文件，运行openssl解密命令即可

常用的python 库

gmpy2

1	建议：安装这个库的话不要直接pip，直接下载wheel文件安装会好一些，只要版本对应一般不会出错，具体安装可以自行百度

这个库用于RSA计算非常方便，如:

#求逆元(模反元素)	d = gmpy2.invert(e,n) 
#判断n是不是素数 gmpy2.is_prime(n)
#欧几里得算法 gmpy2.gcd(a,b)
#扩展欧几里得算法 gmpy2.gcdext(a,b)

就例如这道题：
在这里插入图片描述
便可以利用gmpy2写一个脚本直接计算出d的值

pycrypto

1	这个库也是经常用于RSA计算，在windows上装会遇到一堆麻烦，kail中自带这个库，直接在kail中运行脚本就可以。

0x02 RSA考察题型

一、给出p、q、e、c求明文m

HGAME 2020——InfantRSA

题目描述如下：
在这里插入图片描述
而且给了一个python脚本

分析并结合百度，可以查找出int.from_bytes(x)的含义是把bytes类型的变量x，转化为十进制整数，具体介绍可以查看int.from_bytes和int.to_bytes函数介绍

通过观察可以发现是将flag转换成十进制整数，并赋给了m,所以这道题就是让求出m，然后再利用to_bytes()这个函数，将十进制整数转换成字节即可得出flag，既然明白了题目要考察的就写一个python脚本

import gmpy2 as gp
import binascii
p =  gp.mpz(681782737450022065655472455411)
q =  gp.mpz(675274897132088253519831953441)
e =  gp.mpz(13)
c =  gp.mpz(275698465082361070145173688411496311542172902608559859019841)
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(m)

得出结果：
在这里插入图片描述
接下来就是如何将十进制整数转换成字节了
(注意,长度一定要设置长一些,否则会报错）

这道题就是给出了p、q、e、c，无非就是在转换上做一些变动。

二、暴力分解 N

原理：
RSA的可靠性就是因为要分解因数是非常困难的，对于p、q、n、φ(n)、e、d这六个数，公钥用到了n、e，其余四个数是不公开的，其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏

1
2
3

（1）ed≡1 (mod φ(n)) 只有知道e和φ(n)，才能算出d
（2）φ(n)=(p-1)(q-1) 只有知道p和q，才能算出φ(n)
（3）n=pq 只有将n因数分解，才能算出p和q

因此如果可以暴力分解N的话，私钥就泄露了

JarvisOJ - Medium RSA

题目描述：

已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
N=322831561921859 e = 23
请解密出明文，提交时请将数字转化为 ascii 码提交
比如你解出的明文是 0x6162，那么请提交字符串 ab
提交格式：PCTF{明文字符串}

直接暴力分解N
在这里插入图片描述
接下来就写一个简单的py脚本即可

得出结果16进制转字符串即可

1
2
3

$ python3 5.py
0x33613559
3a5Y

适用于N较小的时候

三、共模攻击

拓展欧几里得算法：

给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)，其中一个很可能是负数

原理：
假设N不变，已知N,e1,e2（公钥）,c1,c2（密文），且e1和e2互质，由欧几里德算法可知

gcd(e1,e2)=1
再推出此式：
e1*s1+e2*s2 = 1
由扩展欧几里德算法，可以得到一组解
(s1,s2)
假设s1为正、s2为负
因
c1 = m^e1 mod N 
c2 = m^e2 mod N
故推出此方程式
(c1^s1*c2^s2)mod N= ((m^e1 mod N)^s1*(m^e2 mod N)^s2)mod N
根据模运算性质，可以化简为此方程式
(c1^s1*c2^s2)mod N = ((m^e1)^s1*(m^e2)^s2)mod N
(c1^s1*c2^s2)mod N = (m^(e1^s1+e2^s2))mod N
又因为
e1*s1+e2*s2 = 1
所以
(c1^s1*c2^s2)mod N = (m^(1))mod N
(c1^s1c2^s2)mod N = m mod N
即
c1^s1*c2^s2 = m
因此可以在不知道d1,d2情况下，解出m

适用条件：

1	当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击

Jarvis OJ——very hard RSA

在这里插入图片描述

发现题目所给的加密方式是用不同的公钥，相同的模数去加密同一段明文，这道题给了N,e1,e2,也给了flag.enc1,flag.enc2（即密文），因此使用RSA共模攻击即可解出这道题

了解了原理即可写出脚本：

# coding=utf-8
#py2
import string
import gmpy

# 扩展欧几里得算法
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():
    with open('flag.enc1', 'r') as f1:
        c1 = f1.read().encode('hex')
        c1 = string.atoi(c1, base=16)
        #string.atoi(s[,base])  字符串转换成数字  base是16那么s就只能是0x23或0X12这种形式的字符串
    with open('flag.enc2', 'r') as f2:
        c2 = f2.read().encode('hex')
        c2 = string.atoi(c2, base=16)

    n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
    e1 = 17
    e2 = 65537
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]

    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)

    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    #'{:x}'.format() 数字格式化
    print '{:x}'.format(int(m)).decode('hex')

if __name__ == '__main__':
    main()

即可得出flag

四、小公钥指数攻击

攻击条件：

当e=3时

原理：

当e特别小时，通常为3时，便可利用小公钥指数攻击
因a≡b (mod m)可推出b=a mod m
故
c ≡ m^3 mod N
所以
m^3 = c+k * N
m =  3√￣c+k x N
#注，这里是开三次根，不是乘3
可以从小到大枚举 k，依次开三次根，直到开出整数为止

Jarvis OJ——Extremely hard RSA
题目描述：
在这里插入图片描述
和之前的一道题相似，不过这里e为3，所以这道题就是小公钥指数进行攻击

了解了原理，既然自己写不出来脚本也能多少看的懂师傅们写的脚本

#!/usr/bin/python
# coding=utf-8
#py2
import gmpy
from Crypto.PublicKey import RSA
def calc(j):
    a, b = gmpy.root(cipher + j * N, 3)
    				 #c+k*N
    #gmpy.root(x,n) # x开n次根
    if b > 0:
        m = a
        print '{:x}'.format(int(m)).decode('hex')
		#'{:x}'.format() 数字格式化
with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    #读取公钥信息
    N = key.n
    e = key.e
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)
    #将16进制十进制
#需要爆破，所以速度会很慢
#inputs = range(0, 130000000)
#这里师傅在爆破后确定了范围，不要误以为小公钥指数攻击爆破范围就是range(118600000, 118720000)这样
inputs = range(118600000, 118720000)
result = []
map(calc, inputs)
#计算列表各个元素的开三次根
print len(result)

运行脚本即可得出flag

五、Rabin 算法

攻击条件：

当e=2时

原理：
在了解Rabin 算法之前，需要了解一些数学知识，如：中国剩余定理、欧拉准则，推荐看大师傅的博客，讲的非常详细。

中国剩余定理
 欧拉准则

Rabin算法是一种基于模平方和模平方根的非对称加密算法
在这里插入图片描述

如果p ≡ q ≡ 3 ( mod 4),则

一般情况下p ≡ q ≡ 3 ( mod 4)是满足的

Jarvis OJ——hard RSA
在这里插入图片描述
e=2，那就是Rabin 算法了，模仿大师傅的脚本

#!/usr/bin/python
# coding=utf-8
#py2
import gmpy
import string
from Crypto.PublicKey import RSA

# 读取公钥参数
with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = string.atoi(cipher, base=16)

print "please input p"
p = int(raw_input(), 10)
print 'please input q'
q = int(raw_input(), 10)
# 计算yp和yq
inv_p = gmpy.invert(p, q)
inv_q = gmpy.invert(q, p)

# 计算mp和mq
mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)

# 计算a,b,c,d
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % N
d = N - int(c)

for i in (a, b, c, d):
    s = '%x' % i
    if len(s) % 2 != 0:
        s = '0' + s
    print s.decode('hex')

运行脚本即可得出flag

总结:

除这些之外，RSA考察的点还有d 泄露攻击 等，之后再进行总结学习，这次先总结到这

Previous Post

记第一次线下AWD感受及复现

CATALOG

1. 前言：
2. 0x01 基本工具的使用

3. 0x02 RSA考察题型

3.0.1. 一、给出p、q、e、c求明文m
3.0.2. 二、暴力分解 N
3.0.3. 三、共模攻击
3.0.4. 四、小公钥指数攻击
3.0.5. 五、Rabin 算法

4. 总结:

