RSA主要攻击方法

摘 要

RSA 算法是迄今在网络安全领域应用最为广泛的非对称密码算法，其安全性是根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。另1方面，对 RSA 算法的攻击可针对设计与应用该算法的系统的某些缺陷。 本文研究了对 RSA 算法的攻击的主要方法, 并对攻击防御提出了建议。

第1章 RSA 算法描述

RSA算法是由Rivest、Shamir和Adleman开发的1种非对称加密算法，在此算法中公钥和私钥将会配合使用。迄今为止，RSA算法已然成为使用最广泛的公钥算法，究其原因即在于其易于实现及良好的安全性。使用RSA算法来开发密钥，每条消息都被映射成整数，通常被定义为分组密码，当用户解密数据时，密钥则用于验证，该过程增强了存储数据的数据完整性，为用户提供更好的安全性。在研究工作中，用户数据在存储到服务端之前将使用RSA算法进行加密，继而使用RSA算法生成私钥，只有拥有数据的用户才知道该算法。RSA算法中涉及的步骤分为密钥生成、加密和解密。对此拟做阐释分述如下。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BgiC9Yjg-1658985403425)(D:/temp/md_tutu/53ac4f99753e4602bdb9f74777034632.png)]

1.1 RSA 算法的初始化

• 任意选取两个不同的大素数p和q计算乘积 n=pq

• n 的欧拉函数 φ(n)： φ(n)=(p-1)(q-1)

• 任意选取一个大整数e，满足 gcd(e, φ(n))=1，整数e用做加密钥

• (注意：gcd是最大公约数,e的选取是很容易的，例如，所有大于p和q的素数都可用)

• 确定的解密钥d，满足 (de) mod φ(n) = 1

• 公开整数n和e，秘密保存d

由此得 公钥（n，e) 和 私钥（n，d)

1.2 RSA 算法用于加/解密

将明文 m 加密成密文c ：c = m^e mod n

将密文 c 解密为明文m： m = c^d mod n

使用pyhon实现代码如下:

import gmpy2
import libnum

e = 65537
# 产生随机素数
p = libnum.generate_prime(256)
q = libnum.generate_prime(256)

# 字符转数字
m = libnum.s2n(b'xiaoxiaoran')

n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

# 将明文 m 加密成密文c
c = pow(m, e, n)  # c = m^e mod n
# 将密文 c 解密为明文m
m = pow(c, d, n)  # m = c^d mod n

# 数字转字符
print(libnum.n2s(int(m)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.3 RSA 算法用于数字签名

若A将签名信息传送给B, A签名的过程为:A用自己的私钥{d, n}对信息m进行签名, 即s≡md (modn) , 为签名, 并将s和消息m联合1起送给用户B, s可以置于m的前面或后面。

B验证的过程为:B用A的公钥{e, n}对s签名进行验证, 即m′≡se (modn) , 若m′=m, 则签名正确。用户B可以确认信息确实是由A发送的, 同时用户A也不能否认发送过这个信息, 因为除了用户A本人外, 其他任何人都无法由明文m产生s。

私钥产生数字签名, 公钥用于验证私钥产生的数字签名

使用pyhon实现代码如下:

import Crypto.Hash
import Crypto.Signature.PKCS1_v1_5
import Crypto.PublicKey.RSA


x = Crypto.PublicKey.RSA.generate(1024)

private = x.exportKey("PEM")  # 生成私钥
public = x.publickey().exportKey()   # 生成公钥

with open("private.pem", "wb") as x:
    x.write(private)
with open("public.pem", "wb") as x:
    x.write(public)


str = b"xiaoxiaoran"

with open("./private.pem", "rb") as x:
    c_rsa = Crypto.PublicKey.RSA.importKey(x.read())
    signer = Crypto.Signature.PKCS1_v1_5.new(c_rsa)
    msg_hash = Crypto.Hash.SHA256.new()
    msg_hash.update(str)
    sign = signer.sign(msg_hash)    # 使用私钥进行'sha256'签名
    # print(sign)

with open("./public.pem", "rb") as x:
    d_rsa = Crypto.PublicKey.RSA.importKey(x.read())
    verifer = Crypto.Signature.PKCS1_v1_5.new(d_rsa)
    msg_hash = Crypto.Hash.SHA256.new()
    msg_hash.update(str)
    verify = verifer.verify(msg_hash, sign)  # 使用公钥验证签名
    print(verify)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

第2章 RSA 算法的攻击方法

RSA算法的安全性依赖于大整数分解的困难性。最直接的攻击方法是分解n得到p, q, 进而基于e计算d, 随着计算机运算能力的不断提高, 通过2次筛法已能分解180多位的十进制素数, 增加p, q的长度已成为许多安全应用系统的加密要求。另1方面, 利用系统设计和实现的缺陷, 人们也提出了1些基于非因子分解方式破解RSA算法的方案。目前, 对RSA算法的攻击主要有以下几种:

2.1 对模数n的因子分解

可以尝试在相关网站(http://factordb.com)上进行查询。

这些网站上存储着已经分解过的n对应的p和q

分解模数n是最直接的攻击方法, 也是最困难的方法。攻击者可以获得公钥e和模数n;如果n=pq被成功分解, 则攻击者可以计算出φ (n) = (p-1) (q-1) , 进而从ed≡1 mod φ (n) 解得私钥d。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AV3cTBHu-1658985403426)(D:/temp/md_tutu/image-20220615162510590.png)]

2.2 对RSA的公共模数攻击

若1个多用户系统中只采用1个模数n, 不同的用户拥有不同的e和d, 系统将是危险的。在此系统中, 若有同1消息用不同的公钥加密, 这些公钥共模且互质, 那该信息无需私钥就可解密。举例来说, 设P为信息明文, 两个加密公钥为e1和e2, 公共模数是n, 有:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6kS67LUs-1658985403427)(D:/temp/md_tutu/wps4.jpg)]

如果攻击者获得 n、e1、e2、C1 和 C2，就能得到 P。 因为 e1 和 e2 互质，

故用欧几里德(Euclid)算 法 能 找 到 r 和 s，满 足：re1+se2=1，设 r 为 负

数，则

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4R6B11Ce-1658985403427)(D:/temp/md_tutu/wps5.jpg)]]

如果 P

使用pyhon实现代码如下:

import gmpy2
import libnum

# 产生随机素数
p = libnum.generate_prime(256)
q = libnum.generate_prime(256)

def xiao(e):
    m = libnum.s2n(b'xiaoxiaoran')
    n = p * q
    phi = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi)
    c = pow(m, e, n)  # c = m^e mod n
    return e, c

def gongmogongji(n, c1, c2, e1, e2):
    def egcd(a, b):
        if b == 0:
            return a, 0
        else:
            x, y = egcd(b, a % b)
            return y, x - (a // b) * y
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]
    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m

n = p*q
e1, c1 = xiao(65537)
e2, c2 = xiao(19)

result = gongmogongji(n, c1, c2, e1, e2)
print(libnum.n2s(int(result)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2.3 对 RSA 的小指数攻击

如果 RSA 系统的公钥 e 选取较小的值， 可以使加密和验证签名的速度有所提高。 但如果 e 取得太小，就容易受到小指数攻击。 例如，有同1系统的3个用户，分别使用不同的模数 n1，n2，n3，但都选取 e=3；另有1用户欲将同1明文消息 P 发送给以上3人，使用各人的公钥加密得

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sptM9Cd5-1658985403428)(D:/temp/md_tutu/wps6.jpg)]

1般地，n1，n2，n3 互素（否 则，会比较容易求出公因子，降低安全性），根据中国剩余定理，可由 C1，C2，C3 计算：C=P3 (modn1n2n3)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zTV4koKq-1658985403429)(D:/temp/md_tutu/wps7.jpg)]

2.3.1 低加密指数广播攻击

如果选取的加密指数e较小，且给多个接收方用这个e发送相同的明文（n不同），那么就可以进行广播攻击, 当收集到的加密消息个数大于或等于e时，有(假设e=3)如果是根据中国剩余定理，那么加密消息至少得有3个（1个和两个不能得出1组确切的解）

使用pyhon实现代码如下:

from sympy.ntheory.modular import crt
from gmpy2 import iroot
import libnum

def rsa_def(e, m):
    p = libnum.generate_prime(256)
    q = libnum.generate_prime(256)
    m = libnum.s2n(m)
    n = p*q
    c = pow(m, e, n)
    listn.append(n)
    listc.append(c)

listn = []
listc = []

e = 40
m = 'xiaoxiaoran'

# 产生7组具有相同的e和明文m,不同的n和密文c
for i in range(7):
    rsa_def(e, m)

resultant, mod = crt(listn, listc)
value, is_perfect = iroot(resultant, e)
print(libnum.n2s(int(value)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.4 对 RSA 的选择密文攻击

选择密文攻击指的是攻击者能选择不同的密文，并拥有对应的明

文，由此推出想要的信息。 1般攻击者会伪装若干信息，让拥有私钥的

用户签名，由此获得有用的明文-密文对，然后推算想要的信息。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8hVDkj37-1658985403430)(D:/temp/md_tutu/wps8.jpg)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZKk9GRLG-1658985403431)(D:/temp/md_tutu/wps9.jpg)]

第3章 对 RSA 算法的攻击的防御建议

3.1 针对黑客使用因子分解攻击。

1. p与q均选择大素数 (大于1075) ;

2. p与q为强素数以确保因子分解攻击在有效时间内不会实现;

3. p与q这对素因子必须差别很大;

4. 必须使n也达到足够大 (600bit以上) 。这样密钥长度1定会大于2 048位, 黑客无法反求出私钥d, 无法实施攻击。

3.2 针对黑客使用小指数攻击。

e和d都应取较大的值, 并且使用独立填充消息 (随机数填充) , 使每个消息大小与n相同。这种做法保证了密钥长度在2 048位以上, 会给黑客推导私钥d的过程增加很大的难度。

3.3 针对黑客使用群体暴力破解。

笔者认为比较有效的措施是使用IDS (入侵检测系统) 发现黑客的暴力破解行为, 通过安全策略的定制限制黑客的暴力破解——最简单的设定就是限制某帐号几次登录不成功后进行帐号锁定并且不解锁。

3.4 针对黑客使用选择密文攻击。

采用好的公钥协议, 保证工作过程中实体不对其他实体任意产生的信息进行解密, 不对自己未见过的信息签名;

不对陌生人的随机文档签名, 签名时首先使用One-Way Hash Function对文档作HASH处理, 同时使用不同的签名算法;

适当加强消息的冗余度。这样可以增加协议的安全性, 黑客就无法绕开算法而直接攻击协议了。

3.5 针对黑客使用公共模数攻击。

不要让所有的人都使用同1个模数n。这样使得黑客只有通过推导密钥对才能恢复明文, 对黑客而言几乎是不可能完成的任务。

3.6 针对黑客使用计时攻击。

1. 随机延时:通过取幂算法增加1个随机延时迷惑计时攻击者;

2. 盲化:执行幂运算之前先将1个随机数与密文相乘, 使得计时攻击者不知计算机正在处理哪几位密文, 防止计时攻击者1位1位地进行分析。在RSA的安全算法中在乘积中使用了盲化操作, 其实现私钥的步骤如下①产生0~n之间的秘密随机数r;②计算c′=c (re) mod n;③计算M′= (c′) dmod n;④计算M=M′r-1mod n;

3. 将取幂时间常数化:保证每个幂运算在返回结果前耗费的操作时间相同。这样就大大增加了猜测时间的难度, 黑客的计时攻击根本无法完成。

3.7 针对黑客使用低熵攻击。

加密前对明文系统加以筛选, 去掉熵太小的明文空间或小明文空间。这样就能确保密钥位数大于2 048位, 使得解密表的范围大增, 黑客无法去查询。

3.8 针对黑客使用公共指数攻击。

将e的取值范围设的更宽些, 使得黑客无法完成对e值的猜测。

3.9 针对黑客使用算法漏洞攻击。

选择小于264的口令或者不采用RSA算法加密短密钥, 保证密钥位数大于2048位, 确保破解算法的运算量不小于指数运算的运算量, 让黑客破解的时间与空间代价剧增。