RSA加密算法分析

简介

RSA加密算法属于公钥加密算法或非对称加密算法，是目前使用最广泛的公钥密码算法之一，以其高安全性而著称。

算法原理

RSA加密算法原理包括密钥生成、加密和解密三个主要步骤。

密钥生成

  1. 选择两个大质数：$p$ 和 $q$。
  2. 计算模数：$n=p×q$。$n$用于加密和解密
  3. 计算欧拉函数：计算$ϕ(n)=(p−1)×(q−1)\phi(n) = (p-1) \times (q-1)ϕ(n)=(p−1)×(q−1)$。
  4. 选择公钥指数：选择一个整数e，使得$1<e<ϕ(n)1 < e < \phi(n)1<e<ϕ(n)$ 且与$ϕ(n)\phi(n)ϕ(n)$互质，通常选择 $e=65537$。
  5. 计算私钥指数：计算$d$，使得 $d×emodϕ(n)=1$，可以通过扩展欧几里得算法计算出 $d$。

最终结果，公钥为$(n,e)$，私钥为$(n,d)$。

加密

给定明文 $m$（确保 $m<n$），加密过程如下：
$$
c=m^e mod*n
$$

其中 $c$ 为密文。

解密

给定密文C，解密过程如下：

$$
m=c^d mod n
$$

例题

BUUCTF rsa

下载附件，拿到两个文件：flag.enc、pub.key。

看名称就知道flag.enc应该是加密的flag，pub.key应该是密钥。

拿到公钥我们通过在线工具（密钥解析）解析分解公钥拿到以下信息。

公钥指数及模数信息:
key长度： 256
模数： C0332C5C64AE47182F6C1C876D42336910545A58F7EEFEFC0BCAAF5AF341CCDD
指数： 65537 (0x10001)

即e=65537，n（将模数转换为十进制）

通过工具yafu分解模数来得到p和q。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
import rsa

#公钥指数
e=65537
#RSA模数，是两个指数p和q的乘积
n=86934482296048119190666062003494800588905656017203025617216654058378322103517
#p和q是RSA的两个质数因子
p=285960468890451637935629440372639283459
q=304008741604601924494328155975272418463

#计算phin，phin是n的欧拉函数值
phin=(q-1)*(p-1)

#计算私钥指数d
d=gmpy2.invert(e,phin)

#使用计算出的值创建RSA私钥对象
key=rsa.PrivateKey(n,e,int(d),p,q)

with open("./flag.enc","rb+") as f:
    f=f.read()
flag=rsa.decrypt(f,key)
print(flag)
≡