RSA小结

最近打比赛频频遇到各种学过又不会的密码学… 抽了点时间捣鼓了一下常见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: 直接分解, http://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),得到pq

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的常见攻击方法