RSA 非对称加密算法原理
欧拉函数
在数论中，对正整数n，欧拉函数 \(\varphi(n)\) 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。 欧拉函数
RSA 算法的核心: 欧拉定理
在数论中，欧拉定理（也称费马-欧拉定理或欧拉 \({\varphi}\) 函数定理）是一个关于同余的性质。欧拉定理表明，若 n,a为正整数，且 n,a 互素（即 \(\gcd(a,n)=1\) ），则
\[ a^{\phi{\left(n\right)}} \equiv 1 \pmod n \]
费马小定理: 欧拉定理的特例
费马定理的表达式 :
\[ a^{\phi{\left(n\right)}} \equiv 1 \pmod n \]
在特殊情况下, 当n为质数时, \(\varphi(n)=n-1\) , 此时, 欧拉定理的表述即为:
\[ a^{n-1} \equiv 1\pmod n \]
这个公式即为就是费马小定理。
模反元素
如果两个正整数 a 和 n 互质, 那么一定存在一个整数 b 满足:
\[ ab \equiv 1\pmod n \]
即, (ab - 1)能被n整除。 b就叫做a的模反元素。 显然的, 模反元素并不唯一, 对于模反元素b, 对于所有的正整数 \(m=b+kn\) 也为a的模反元素。
模反元素必然存在
对费马定理进行变形:
\[ a^{\phi\left({n}\right)}\equiv a\times a^{\phi\left(n\right)-1}\equiv 1 \pmod n \]
在此变形中, \(a^{\phi\left(n\right)-1}\) 即为a的模反元素。
RSA 基本概念
我们约定:
- RSA加密秘钥为E, 它是一个大整数。
- RSA解密秘钥为D, 它是一个大整数。
- RSA加密和解密需要用的模数N, 它是一个大整数。
RSA 加密过程
\[ 密文 = 明文^E mod N \]
RSA 加密过程就是这么简单, 它对明文做一个E次幂运算, 然后对N取模。 在这个过程中, E和N的组合就是公钥。
RSA 解密过程
对应的, RSA的解密过程也非常简单:
\[ 明文 = 密文^D mod N \]
RSA 的加密和解密过程完全一致, 只是它们换了一个秘钥, 进行了完全一样的运算。 在这个过程中, D和N的组合就是私钥。
非对称秘钥对的生成
在基本概念中, 约定了几个量, E, D, N 在这里,我么继续沿用, 额外的,在生成密钥对的过程中, 引入一个新的量L, 它只用于生成密钥对, 但是最终结果中我们并不体现它。
1. 求N
准备两个大质数p, q。(p和q要最够大)
\[ N=p \times q \]
2. 求L
L是 p-1 和 q-1 的最小公倍数。
\[ L=lcm(p-1, q-1) \]
实际上, 理论公式上, L应为ϕ(n), 这样后面的一系列推倒便是欧拉定理的应用了, 但是在实际中,它可以化简为更小的最小公倍数L, 这里,我们使用了实际中的化简方案
3. 求E
E是一个比1大, 比L小的数字,且E和L要互质, 即 E和L的最大公约数为1, 表达为数学语言为。
\[ \begin{eqnarray*} 1 < E < L \\ gcd(E, L) = 1 \end{eqnarray*} \]
计算E的过程我们采用随机穷举的模式, 使用伪随机数生成器, 随机生成一个1和L之间的数字, 判断是否满足它与L互质, 如果不满足, 则重复生成并判断下一个随机数。
至此, RSA的公钥部分E,N我们已经得到了, 公钥: (E, N)。
我们加入E和L互质的这个条件,是为了满足我们需要的解密参数D一定存在
4. 求D
\[ \begin{eqnarray*} 1 < D < L \\\\ E \times D\ mod\ L = 1 \end{eqnarray*} \]
按照上述的限制条件, 计算出D, 至此, 私钥部分也计算完成, 私钥为(D, N)。