Cheng, Yao's blog Cheng, Yao's blog

Record my life & study

目录
rsa算法理解
/  

rsa算法理解

1. 简介

rsa 是一种非对称密码算法,由三位数学家 Rivest、Shamir 和 Adleman 设计。其原理基于大数因式分解的复杂性。通常使用时,生成一对公私钥对,主要应用于以下两个场景。

  • 加解密: 使用公钥加密,只有持有私钥的人可以解密。
  • 签名和验签:使用私钥进行签名,公钥进行验签,用于一些数据签名,校验的场景。

2. 数学背景

2.1 欧拉函数

假设有正整数,欧拉函数的值等于小于的正整数里有多少个与互为质数。

欧拉函数有以下几个性质:

  1. 因为 1 与任何数都保持了互质关系。
  2. 如果为质数,
  3. 如果为质数的某一次方,即 :

这是因为当 时,当且仅当 不为 的倍数,才与 互质,而这样的数共有
例如:
,需要枚举所有小于的数中不为的倍数的数,这样的数共有个。

  1. 如果可以分解成两个互质的整数乘积

则:

  1. 任意大于 1 的正整数,都可以写成一系列质数的乘积。

根据第四条的结论,可以得到:

也就是欧拉函数计算的通用公式。

2.2 欧拉定理

欧拉函数主要是为了推导出欧拉定理:

如果两个正整数 互为质数,则的欧拉函数可以让下面的等式成立:

也就是 次方被除的余数为 1。例如, 互质,
所以 可以被 整除

为质数时,,所以此时可以得到:

这就是著名的费马小定理,是欧拉定理的特例。
欧拉定理是 RSA 的核心。

2.3 模反元素

如果两个整数 互质,则一定可以找到整数 ,使得 ,此时称 的模反元素。

欧拉定理可以证明模反元素必定存在:

也即 就是 的模反元素。

3. 秘钥计算

  • Step1:随机选取两个不相等的质数 ,
    如选取,。该步骤中选取的 越大越难破解。
  • Step2:计算 , 的乘积设为
    上例可得:
  • Step3:计算 的欧拉函数
    因为 , 均为素数,所以
  • Step4:随机选择一个整数 ,条件是,且 互质
    如上例中,选择 ,实际应用常选择 65537。
  • Step5:计算 对于 的模反元素

此时已知,只需要求得上述二元一次方程 的一组解即可。
在以上例子中可以找到一组解

  • Step6:将 封装成公钥,封装成私钥

4. 可靠性分析

上面的密钥生成步骤,一共出现六个数字:

其中,公钥用到了两个(),其余四个数字都是不公开的。其中最关键的是,因为 组成了私钥,一旦 泄漏,就等于私钥泄漏。

所以如果要破解 rsa,就要在已知 的情况下破解

因为 ,对于 互为对方的模反元素,所以要想算出 必须算出,若要由 算出 需要将 分解成两个素数的乘积,也就是算中的 。而对于极大整数因式分解是极其困难的,所以 RSA 几乎不可能被破解。

5. 加解密过程

5.1 加密

设消息为 , 公钥为

可以算出密文 为:

如上例中,假设

5.2 解密

解密要用私钥:

假设收到的信息为 2970,解密过程可得:

注意: RSA 只能加密小于的整数,如果要加密大于 的整数怎么办?主要有两种解决方法,种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如 DES),用这种算法的密钥加密信息,再用 RSA 公钥加密 DES 密钥。

6. 私钥解密的证明

要证明私钥解密过程是有效的,也就是证明:

根据加密规则:

所以原式等价于证明:

因为 对于 互为模反,所以
也即

接下来分两种情况:
(1) , 互质:
由欧拉定理可得:

由上面的式子推到出结论是因为一个取模的性质:乘积的模等于模的乘积。
(2) , 不互质:
此时,由于,所以要么,要么
假设,此时 互为质数,由欧拉函数可得:

(表示同余,上面的式子表示两边对 取余数相等) 这里用到同余的一个性质,对 同余的两个数乘以一个相同的数之后结果依然对 同余。将带入上式可得:

也即

以上关系转换成等式可以写成:

因为互质,所以 必然被 整除,

重新替换成 替换成 就可以得到:

参考


标题:rsa算法理解
作者:YaoCheng8667
地址:https://ycisme.xyz/articles/2021/12/21/1640093668458.html