rsa算法理解

  |   0 评论   |   0 浏览

1. 简介

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

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

2. 数学背景

2.1 欧拉函数

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

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

  1. \phi(1) = 1 因为1与任何数都保持了互质关系。
  2. 如果n为质数,\phi(n)=\phi(n-1)
  3. 如果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 个。

  1. 如果n可以分解成两个互质的整数乘积
n=p_1\cdot p_2

则:

\phi(n) = \phi(p_1\cdot p_2) = \phi(p_1) \cdot \phi(p_2)
  1. 任意大于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 欧拉定理

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

如果两个正整数 an互为质数,则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 模反元素

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

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

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。该步骤中选取的 pq 越大越难破解。
  • 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

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

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

因为 e,d,对于 \phi(n) 互为对方的模反元素,所以要想算出 d 必须算出\phi(n),若要由 n 算出 \phi(n) 需要将 n 分解成两个素数的乘积,也就是算n = p\cdot q中的 pq。而对于极大整数因式分解是极其困难的,所以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,此时 mq 互为质数,由欧拉函数可得:

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)

因为qp互质,所以 t 必然被 p 整除,t=t^\prime p

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

kp 重新替换成 mpq 替换成 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