欧拉函数及其重要性质

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

性质 1 ，因为1与其自身互质，这是显而易见的。

性质 2 如果是质数，那么，因为质数与每个小于其自身的正整数都互质。

性质 3 如果是质数，是正整数，那么：

这是因为所有小于等于的正整数有个这么多，其中只有不是的倍数才能与互质。而的倍数有：这些，共有个。自然地就有。

性质 4 如果与是两个互质的整数，那么：

性质 5 欧拉定理 首先阐述一下表示x除以n的余数是y。用代码表示为x % n == y。欧拉定理是指：如果与互质，那么下面等式成立：

或者说，除以余数为1。比如说3与7互质，依据性质2有，那么等于余1。欧拉定理是RSA算法的核心，其证明比较复杂就不阐述了（我也弄不懂）。

性质 6 模反元素 如果两个正整数a与n互质，那么一定可以找到一个整数b，使得a*b除以n余1，或者说：

这个时候我们把b称为a的模反元素。欧拉定理可以证明模反元素必然存在，就是的模反元素：。事实上模反元素不止一个，也可能是负数。

扩展欧几里得算法

在RSA算法中，对于以下方程

已知与，需要求解与。我们需要用扩展欧几里得算法进行求解。假设函数是与的最大公约数，这里引出裴属定理：

Th 7 裴属定理 对于整数与，一定存在整数与使得。如果有解，那么一定是的倍数。

要证明上述定理，当时，此时，令即可解。

当时，设与满足。我们重新赋值，将替换为，将替换为；设与满足：

于是有：

我们假设，即除以等于余，那么，于是有：

解得：

于是用扩展欧几里得算法求解原方程的代码就呼之欲出了：

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表示为二进制是1101，那么就有：

这里描述一下快速幂算法计算：

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算法的流程：

生成密钥

1. 选择与两个超大质数，通常其二进制为1024或2048位。
2. 计算，计算与n互质的整数的个数；
3. 取正整数，需要满足且与互质。实际中通常取65537。
4. 计算对于的模反元素，即寻找整数以满足，或者说对于以下方程：，已知与，求解与，用扩展欧几里得算法可以求出来。
5. 销毁与，输出公钥，输出私钥。

加密与解密

1. 输入明文；
2. 计算密文，这里用上述的快速幂算法加速计算；
3. 解密过程为，这里用上述的快速幂算法加速计算。

于是一份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 关于的证明：

假设，即是余数，；

假设，即是余数，；

于是：

同样地，我们有：

证明-2 证明解密过程的正确性，即证明。首先我们从密文的计算式得到，代入解密式得到：

这里略去一些二项式展开的过程，证明上式等价于证明：

由于在生成密钥过程中有，所以只需证：

假如m与n互质，根据欧拉定理我们有，或者说：

两边同时取n次方，进行二项式展开：

两边同时乘以m：

由此得证。

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

引用

[1] 快速幂算法