RSA小结

Posted on | Edited on | Comments:

最近打比赛频频遇到各种学过又不会的密码学… 抽了点时间捣鼓了一下常见rsa攻击方法的原理，以后有时间继续填坑

RSA计算过程

涉及3个参数： n e d, 其中 {n, d}为私钥，{n, e}为公钥

phi(n) = (p-1) * (q-1)
d为e膜phi(n)的逆元(phi(n)为n的欧拉函数)

ed ≡ 1 (mod phi(n))

加密解密过程：c密文，m明文
加密：c ≡ m^e(mod n)
解密：m ≡ c^d(mod n)

rsa中e为随机选取的一个数，一般为65537
n由两个大素数(p,q)之积组成，公钥{n,e}为公开的，要破解rsa就得求出d，d为e模phi(n)的逆元，要求出phi(n)，必须分解n求得p,q，从而求得phi(n)=(p-1)*(q-1)

代码基础

  1. pow函数：
    python底层实现平方乘和算法
    解密：m ≡ c^d(mod n)使用pow函数
    m=pow(c,d,n)

数据处理

通过题目的数据文件，手工将参数提取：

  1. pem文件
    1.1 私钥解密flag：
    openssl rsautl -decrypt -in flag -inkey private.pem -out flag.txt
    1.2 公钥加密flag
    openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
    1.3 获取公钥的信息
    openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
  1. pcap文件
  2. PPC模式

Crack

直接分解n

n < 512 bit: 直接分解， https://factordb.com
n > 512 bit: 使用后面方法

利用公约数

题目特征：直接分解n无果后，尝试yafu。

两次公钥加密时使用的n1和n2有相同的素因子，则可以用欧几里得算法求出n1和n2的最大公因数，也就是其中一个素因子。

题目特征：给了若干个n，均不同，并且n都是2048bit、4096bit级别。

Fermat方法与Pollard rho方法

p、q相差过大或相近时，可以使用Fermat方法与Pollard rho方法分解n。

开源项目: yafu

低加密指数攻击

当e(e=3)和明文过小时，可以使用这种攻击方案：

  1. m^e<n时
    加密函数为：c ≡ m^e(mod n)， 若m^3<n， 直接对密文c进行开三次方即可解出明文。
    例题：
  1. m^e>n时
    c ≡ m^e + k*n, 对c+kn进行三次开方，并对k进行枚举，即可求得明文m。

低加密指数广播攻击

题目特征：一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且e都取了一个较小的数字。

分析：加密指数e选取较小，且使用相同加密指数进行群发消息(n不同)，可以使用广播攻击获得明文。

1
2
3
c1 ≡ m^e(mod n1)
c2 ≡ m^e(mod n2)
c3 ≡ m^e(mod n3)

利用中国剩余定理，解出m^e：
image_1d9c6jjt8bqdrao66julv1vn59.png-78.6kB

由于e很小，所以对m^e进行开方即可解出

低解密指数攻击

题目特征：e看起来很大就行了。

d为e模phi(n)的逆元，e很大那么d就小

脚本：https://github.com/pablocelayes/rsa-wiener-attack

这里注意一个细节问题，如果在运行脚本的时候报错，请在脚本前加上：
import sys
sys.setrecursionlimit(10000000)

共模攻击

题目特征：若干次加密，每次n都一样，明文根据题意也一样即可。

使用相同模数n对相同的密文m进行加密(e不同)，可以使用共模攻击求出明文：

1
2
c1 ≡ m^e1(mod n)
c2 ≡ m^e2(mod n)

易知: gcd(e1,e2) = 1
有: s*e1 + r*e2 = 1
推出：s*e1 + r*e2 ≡ 1 (mod n)
用扩展版欧几里得算法可求得s、r

构造表达式：

1
2
c1^s ≡ m^(e1*s)(mod n)
c2^r ≡ m^(e2*r)(mod n)

联立：

1
2
c1^s * c2^r ≡ m^[(e1*s)+(e2*r)] (mod n)
c1^s * c2^r ≡ m^1 (mod n)

解出明文：m = (c1^s * c2^r)(mod n)

一些例题

jarvisoj: Medium RSA

给了公钥和加密后的flag文件，先用openssl提取公钥信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ openssl  rsa -pubin -text -modulus -in warmup -in pubkey.pem 
RSA Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

分析, 给了我们m， 也就是phi(n)， 通过其求出p,q(①)，然后将n求出(②),通过表达式③将e的逆元d求出，从而将密文解出(⑤)

1
2
3
4
5
①：modulus = (p-1)(p-1)
②： n = p * q
③： e*d ≡ 1 (mod modulus)
④： 加密：c ≡ m^e (mod n)
⑤： 解密：m ≡ c^d (mod n)

尝试factor无解。
继续尝试用yafu分解m， 也就是phi(n),得到p和q

1
2
P39 = 319576316814478949870590164193048041239
P39 = 275127860351348928173285174381581152299

image_1d9eqhob11k6013iqqjilb7r9.png-17.8kB

根据e p q生成私钥文件,这里用rsatools

1
$ python3 rsatool.py -o private.pem -e 65537 -p 319576316814478949870590164193048041239 -q 275127860351348928173285174381581152299

接着拿着这个私钥用openssl解密：

1
2
$ openssl rsautl -decrypt -in flag.enc -inkey private.pem 
PCTF{256b_i5_m3dium}

jarvisoj: Hard RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
$ openssl  rsa -pubin -text -modulus -in warmup -in pubkey.pem
RSA Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 2 (0x2)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgEC
-----END PUBLIC KEY-----

很显然，这里加密指数e为2，采用低加密指数攻击。

参考：

  1. jarvisoj
  2. CTF中RSA的常见攻击方法