RSA算法的数学原理

欧拉函数及其重要性质

$n$ 是任意正整数，欧拉函数以 $\phi(n)$ 表示， $\phi(n)$ 等于所有小于等于 $n$ 的正整数中与 $n$ 互质的个数。比如在1~8里，与8互质的数字是1、3、5、7，因此 $\phi(8)=4$ 。我们探讨一些欧拉函数的特殊性质吧：

性质 1 $\phi(1)=1$ ，因为1与其自身互质，这是显而易见的。

性质 2 如果 $n$ 是质数，那么 $\phi(n)=n-1$ ，因为质数与每个小于其自身的正整数都互质。

性质 3 如果 $p$ 是质数， $k$ 是正整数，那么：
$\phi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right)$
这是因为所有小于等于 $p^k$ 的正整数有 $p^k$ 个这么多，其中只有不是 $p$ 的倍数才能与 $p^k$ 互质。而 $p$ 的倍数有： $1\times p, 2\times p, \dots,p^{k-1}\times p$ 这些，共有 $p^{k-1}$ 个。自然地就有 $\phi(p^k)=p^k-p^{k-1}$ 。

性质 4 如果 $p_1$ 与 $p_2$ 是两个互质的整数，那么：
$\phi(p_1\times p_2)=\phi(p_1)\times\phi(p_2)$

性质 5 欧拉定理 首先阐述一下 $x\equiv y(mod\space n)$ 表示x除以n的余数是y。用代码表示为x % n == y。欧拉定理是指：如果 $a$ 与 $n$ 互质，那么下面等式成立：
$a^{\phi(n)}\equiv1(mod\space n)$
或者说， $a^{\phi(n)}$ 除以 $n$ 余数为1。比如说3与7互质，依据性质2有 $\phi(7)=6$ ，那么 $3^6\div7$ 等于 $104$ 余1。欧拉定理是RSA算法的核心，其证明比较复杂就不阐述了（我也弄不懂）。

性质 6 模反元素 如果两个正整数a与n互质，那么一定可以找到一个整数b，使得a*b除以n余1，或者说：
$ab\equiv1(mod\space n)$
这个时候我们把b称为a的模反元素。欧拉定理可以证明模反元素必然存在， $a^{\phi(n)-1}$ 就是 $a$ 的模反元素： $a\times a^{\phi(n)-1}\equiv1(mod\space n)$ 。事实上模反元素不止一个，也可能是负数。

扩展欧几里得算法

在RSA算法中，对于以下方程
$e\cdot d - k\cdot\phi(n)=1$
已知 $e$ 与 $\phi(n)$ ，需要求解 $d$ 与 $k$ 。我们需要用扩展欧几里得算法进行求解。假设函数 $gcd(a,b)$ 是 $a$ 与 $b$ 的最大公约数，这里引出裴属定理：

Th 7 裴属定理 对于整数 $a$ 与 $b$ ，一定存在整数 $x$ 与 $y$ 使得 $ax+by=gcd(a,b)$ 。如果 $ax+by=m$ 有解，那么 $m$ 一定是 $gcd(a,b)$ 的倍数。

要证明上述定理，当 $b=0$ 时，此时 $gcd(a,b)=a$ ，令 $x=1,y=0$ 即可解。

当 $a\cdot b\neq0$ 时，设 $x_1$ 与 $y_1$ 满足 $ax_1+by_1=gcd(a,b)$ 。我们重新赋值，将 $b$ 替换为 $a\%b$ ，将 $a$ 替换为 $b$ ；设 $x_2$ 与 $y_2$ 满足：
$b\cdot x_2+a\%b\cdot y_2=gcd(b,a\%b)=gcd(a,b)$
于是有：
$b\cdot x_2+a\%b\cdot y_2=a\cdot x_1+b\cdot y_1$
我们假设 $b\cdot k+t=a$ ，即 $a$ 除以 $b$ 等于 $k$ 余 $t$ ，那么 $a\%b=a-b\cdot k$ ，于是有：
$a\cdot x_1+b\cdot y_1=b\cdot x_2+(a-k\cdot b)\cdot y_2$
解得：
$x_1=y_2,\space y_1=x_2-ky_2$
于是用扩展欧几里得算法求解原方程的代码就呼之欲出了：

int ext_gcd(int a, int b, int &x, int &y) {
    // 求解a*x+b*y=1的解(x, y)
    if (b == 0) {
        // 递归出口 给x与y赋值
        x = 1;
        y = 0;
        return a;
    }
    // 递归求解x2, y2
    int gcd = ext_gcd(b, a % b, x, y);
    // 通过x2, y2求解x1, y1
    int x2 = x, y2 = y;
    int k = a / b;  // a除以b向下取整
    x = y2;
    y = x2 - k * y;
    return gcd;
}

快速幂算法求模

在RSA算法的加密过程里我们将会计算a的b次方对n的余数，其中a与b可能都是超大整数，直接暴力计算不可行。我们需要用快速幂算法快速算出(a^b)%n，这个算法又叫蒙哥马利算法。

首先我们需要将b拆分为二进制之写法。设b=13，其二进制表示为1101，我们将二进制写法拆分成如下形式：
$13=1\times2^3+1\times2^2+0\times2^1+1\times2^0$
更一般地，假设十进制数字 $b$ 的二进制共有 $K$ 位，我们用 $b_k$ 为 $0$ 或 $1$ 表示其二进制的第 $k$ 位，那么有：
$b=b_K\cdot2^K+b_{K-1}\cdot2^{K-1}+\dots+b_0\cdot2^0$
那么：
$a^b=a^{b_K\cdot2^K}\times a^{b_{K-1}\cdot2^{K-1}}\times\dots\times a^{b_1\cdot2}\times a^{b_0}$
举个例子，我们要用快速幂算法计算 $3^{13}$ ，13表示为二进制是1101，那么就有：
$3^{13}=3^8\cdot3^4\cdot3^1$
这里描述一下快速幂算法计算 $3^{13}$ ：

res=1
底数=3
从右到左依次观察(1101)2每一位的值：
    第1位是1:
        res=res*底数=3
        底数=底数的平方=9
    第2位是0: 
        底数=底数的平方=81
    第3位是1:
        res=res*底数=3*81
        底数=底数的平方=6561
    第4位是1
        res=res*底数=3*81*6561
输出3*81*6561

一般地，快速幂算法可以写成：

long fast_pow(long a, long b) {
    // 快速幂算法求 a^b
    long res = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b = b >> 1;
    }
    return res;
}

取模运算不会干预乘法运算，于是我们马上就能写出快速幂算法求模的代码：

long fast_mode(long a, long b, long n) {
    // 快速幂算法求 a^b%n
    long res = 1;
    while (b) {
        if (b & 1) res = res * a % n;
        a = a * a % n;
        b = b >> 1;
    }
    return res;
}

RSA算法流程

理论讲完了，可以开始RSA算法的流程了。以下是RSA算法的流程：

生成密钥

选择 $p$ 与 $q$ 两个超大质数，通常其二进制为1024或2048位。
计算 $n=p\times q$ ，计算与n互质的整数的个数 $\phi(n)=(p-1)\times(q-1)$ ；
取正整数 $e$ ，需要满足 $e\in{2, 3, ..., \phi(n)}$ 且 $e$ 与 $\phi(n)$ 互质。实际中通常取65537。
计算 $e$ 对于 $\phi(n)$ 的模反元素 $d$ ，即寻找整数 $d$ 以满足 $e\cdot d\equiv1(mod\space n)$ ，或者说对于以下方程： $e\cdot d - k\cdot\phi(n)=1$ ，已知 $e$ 与 $\phi(n)$ ，求解 $d$ 与 $k$ ，用扩展欧几里得算法可以求出来。
销毁 $p$ 与 $q$ ，输出公钥 $(n,e)$ ，输出私钥 $(n,d)$ 。

加密与解密

输入明文 $m$ ；
计算密文 $c=m^e\%n$ ，这里用上述的快速幂算法加速计算；
解密过程为 $m=c^d\%n$ ，这里用上述的快速幂算法加速计算。

于是一份C++版本RSA算法代码就呼之欲出了。可惜的是cpp里long long类型只支持到64位，要在生产环境实现一份RSA加密算法，其数字至少需要1024位才足够安全。代码如下：

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;


ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll res = ext_gcd(b, a % b, x, y);
    ll t = y;
    y = x - (a / b) * y;
    x = t;
    return res;
}


ll fast_mode(ll a, ll b, ll n) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % n;
        a = a * a % n;
        b >>= 1;
    }
    return res;
}


void gen_key(ll p, ll q, ll &n, ll &e, ll &d) {
    n = p * q;
    ll phi = (p - 1) * (q - 1);
    e = 65537;
    ll y;
    // 求解e*d-k*phi=1
    ext_gcd(e, phi, d, y);
    if (d < 0) d += phi;
}


int main() {
    ll p = 61;
    ll q = 53;
    ll msg;
    cout << "Please input message: ";
    cin >> msg;
    ll n, e, d;
    gen_key(p, q, n, e, d);
    ll cipher = fast_mode(msg, e, n);
    ll msg_decrypted = fast_mode(cipher, d, n);
    cout << n << endl;
    cout << e << endl;
    cout << d << endl;
    cout << msg << endl;
    cout << cipher << endl;
    cout << msg_decrypted << endl;
    return 0;
}

附录

证明-1 关于 $(x\cdot y)\%n=\left(x\cdot y\%n\right)\%n=\left(x\%n\cdot y\%n\right)\%n$ 的证明：

假设 $n\cdot k_1+m_1=x$ ，即 $m_1$ 是余数， $x\%n=m_1$ ；

假设 $n\cdot k_2+m_2=y$ ，即 $m_2$ 是余数， $y\%n=m_y$ ；

于是：
$(x\cdot y)\%n=\left[(n\cdot k_1+m_1)(n\cdot k_2+m_2)\right]\%n\\=(n^2k_1k_2+nk_1m_2+nk_2m_1+m_1m_2)\%n\\=(m_1m_2)\%n\\=\left(x\%n\cdot y\%n\right)\%n$

同样地，我们有：
$(x\cdot y\%n)\%n=\left[(nk_1+m_1)m_2\right]\%n\\=(nk_1m_2+m_1m_2)\%n\\=(m_1m_2)\%n$

证明-2 证明解密过程的正确性，即证明 $m=c^d\%n$ 。首先我们从密文的计算式 $c=m^e\%n$ 得到 $c=m^e-nh$ ，代入解密式得到：
$m=\left(m^e-nh\right)^d\%n$
这里略去一些二项式展开的过程，证明上式等价于证明：
$m=m^{ed}\%n$
由于在生成密钥过程中有 $ed=k\phi(n)+1$ ，所以只需证：
$m=m^{k\phi(n)+1}\%n$

假如m与n互质，根据欧拉定理我们有 $m^{\phi(n)}\equiv1(mod\space n)$ ，或者说：
$nt_0+1=m^{\phi(n)}$
两边同时取n次方，进行二项式展开：
$m^{k\phi(n)}=(nt_0+1)^k=nt_1+1$
两边同时乘以m：
$m^{k\phi(n)+1}=mnt_1+m$
由此 $m=m^{k\phi(n)+1}\%n$ 得证。

假如m与n并不互质，略。

引用

[1] 快速幂算法