2021-12-21 / 密码学

rsa算法理解

1. 简介

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

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

2. 数学背景

2.1 欧拉函数

假设有正整数n，欧拉函数\phi(n)的值等于小于n的正整数里有多少个与n互为质数。

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

\phi(1) = 1 因为 1 与任何数都保持了互质关系。
如果n为质数，\phi(n)=\phi(n-1)
如果n为质数的某一次方，即 n = p^k:

\phi(p^k) = p^k - p^{k-1} = p^k\cdot (1- \frac{1}{p} )

这是因为当 m < n 时，当且仅当 m 不为 p 的倍数，m才与 n 互质，而这样的数共有p^{k-1}个(1\cdot p, 2\cdot p, ..., p^{k-1}\cdot p)。
例如：
对 n = 7^3 求 \phi(n) ，需要枚举所有小于 7^3的数中不为 7的倍数的数，这样的数共有 7^3-7^2=294 个。

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

n=p_1\cdot p_2

则：

\phi(n) = \phi(p_1\cdot p_2) = \phi(p_1) \cdot \phi(p_2)

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

n = p_1^{k_1}\cdot p_2^{k_2}...\cdot p_r^{k_r}

根据第四条的结论，可以得到：

\phi(n) = \phi(p_1^{k_1})\cdot\phi(p_2^{k_3})...\cdot\phi(p_r^{k_r}) =n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})

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

2.2 欧拉定理

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

如果两个正整数 a 和 n互为质数，则n的欧拉函数\phi(n)可以让下面的等式成立：

a^{\phi(n)} \mod n = 1

也就是a的 \phi(n) 次方被n除的余数为 1。例如， 3 和 7 互质，\phi(7) = 6，
所以 3^7 - 1 = 728可以被 7 整除 (728/7=104) 。

当 p 为质数时，\phi(p) = p-1，所以此时可以得到：

a^{p-1} \mod p = 1 \ \ \ (p为质数)

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

2.3 模反元素

如果两个整数 a 和 n 互质，则一定可以找到整数 b ，使得 a \cdot b \ \mod n=1，此时称 b 为 a 的模反元素。

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

a^{\phi(n)} \mod n = 1 \Rightarrow a\cdot a^{\phi(n) - 1}\mod n = 1

也即 a^{\phi(n) - 1} 就是 a 的模反元素。

3. 秘钥计算

Step1：随机选取两个不相等的质数 p , q
如选取p=61,q=53。该步骤中选取的 p，q 越大越难破解。
Step2：计算 p , q 的乘积设为n
上例可得：

n=p\cdot q =61\cdot 53=3233

Step3：计算 n 的欧拉函数 \phi(n)
因为 p , q均为素数，所以

\phi(n) = \phi(p\cdot q) = \phi(p)\phi(q) = (p-1)(q-1) \\ \Rightarrow \phi(3233)=60\cdot 52=3120

Step4：随机选择一个整数 e，条件是 1< e < \phi(n)，且 e 与 \phi(n) 互质
如上例中，选择 e=17 ，实际应用常选择 65537。
Step5：计算 e 对于 \phi(n) 的模反元素 d

ed\mod \phi(n) = 1 \\ \Rightarrow ed = k\phi(n)+1

此时\phi(n)和e已知，只需要求得上述二元一次方程 k,d的一组解即可。
在以上例子中可以找到一组解 d=2753，k=15。

Step6：将 (n, e) 封装成公钥，(n,d)封装成私钥。

rsa\_pub = (3233,17) \\ rsa\_private = (3233, 2753)

4. 可靠性分析

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

p 　　q 　　n 　　\phi(n) 　　e 　　d

其中，公钥用到了两个（n 和 e），其余四个数字都是不公开的。其中最关键的是d，因为 n 和 d 组成了私钥，一旦 d 泄漏，就等于私钥泄漏。

所以如果要破解 rsa，就要在已知 n 和 e 的情况下破解 d。

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

5. 加解密过程

5.1 加密

设消息为 m，公钥为 (e, n)

可以算出密文 c 为：

c = m^e \mod n

如上例中，假设 m=65：

c = 65^{17} \mod 3233 = 2970

5.2 解密

解密要用私钥：

m = c^d \mod n

假设收到的信息为 2970，解密过程可得：

m = 2970^{2753} \mod 3233 = 65

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

6. 私钥解密的证明

要证明私钥解密过程是有效的，也就是证明：

c^d \mod n = m

根据加密规则：

c = m^e \mod n \\ \Rightarrow c = m^e - k\cdot n \\ \Rightarrow c^d \mod n= (m^e-k\cdot n)^d \mod n \\ \Rightarrow c^d \mod n= m^{ed} \mod n

所以原式等价于证明：

m^{ed} \mod n = m

因为e, d 对于 \phi(n) 互为模反，所以 ed \mod \phi(n) = 1。
也即ed = t\cdot \phi(n) +1

m^{ed} \mod n = m^{t \cdot \phi(n) + 1} \mod n

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

m^{\phi(n)} \mod n = 1 \\ \Rightarrow m^{t \cdot \phi(n) + 1} \mod n = m \cdot (m^{t \cdot \phi(n)} \mod n) = m

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

m^{\phi(q)} \equiv 1 \ (mod \ q)

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

[(kp)^{q-1} ]^{(p-1)\cdot h} \equiv 1 \ (mod \ q) \\ \Rightarrow [(kp)^{q-1} ]^{(p-1)\cdot h} \cdot kp \equiv kp \ (mod \ q) \\

也即

(kp)^{t \cdot \phi(n) + 1} \equiv kp \ (mod \ q) \\

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

(kp)^{t \cdot \phi(n) + 1} = tq + kp \\ \Rightarrow (kp)\cdot (kp)^{t\cdot \phi(n)} = tq + kp \\ \Rightarrow p(k\cdot kp) = p (\frac{tq}{p} + k)

因为q，p互质，所以 t 必然被 p 整除，t=t^\prime p。

(kp)^{t \cdot \phi(n) + 1} = t^\prime pq + kp

将 kp 重新替换成 m，pq 替换成 n 就可以得到：

m^{t \cdot \phi(n) + 1} = t^\prime n + m \\ \Rightarrow m^{t \cdot \phi(n) + 1} \mod n = m

参考

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

Cheng, Yao's blog

Record my life & study