RSA算法详解及相关数学原理解析
前言
为了记录自己学习密码学的过程，也是为了便于个人应付相关课程的考核，故写此博客。
本博客总结了怎么用C++手搓一个RSA算法，以及补补欠缺的一些数学知识和可能欠缺的一些其他算法的实现。
参考了其他人的相关博客，用便于我自己理解的话和方式和一些便于复现的示例做了一下总结。
Note:
- 编程语言使用C++
- 涉及到的数学知识不一定都跟RSA相关。
目录
目录- RSA算法详解及相关数学原理解析
相关数学知识
为了便于复习，涉及到的数学知识和一些算法会给出相应的概念和实现。
质数
一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数） ；否则称为合数。
1不是质数，也不是合数。
互质数
公约数只有1的两个数，叫做互质数。
互质数的性质：
- 如果 \(a\) 和 \(b\) 互质，那么 \(a^n\) 和 \(b^m\) 也互质，其中 \(n\) 和 \(m\) 是任意正整数。
- 如果 \(a\) 和 \(b\) 互质， \(b\) 和 \(c\) 互质，那么 \(a\) 和\(c\) 不一定互质，但\(a\)和\(bc\)的最大公约数。
整除
整除是指一个整数除以另一个不是0的整数，得到的商是整数，而没有余数。
\[{\exists}{\ }a,b,k\in\mathbb{Z}{\quad}a=b{\times}k \]那么我们就可以说 \(b\) 整除 \(a\)，或者说 \(a\) 被 \(b\) 整除，用数学符号表示为 \(b|a\)（小整除大，大被小整除）。
以下是一些整除的关键性质：
-
传递性：
\[a \mid b \land b \mid c \implies a \mid c \] -
和的性质：
\[a \mid b \land a \mid c \implies a \mid (b + c) \land a \mid (b - c) \] -
积的性质：
\[a \mid b \land c \mid d \implies ac \mid bd \] -
指数性质：
\[a \mid b \implies \forall n \in \mathbb{Z}^+, a \mid b^n \] -
线性组合：
\[a \mid b \land a \mid c \implies \forall x, y \in \mathbb{Z}, a \mid (xb + yc) \] -
除法算法（也称为带余除法）：
\[\forall a, b \in \mathbb{Z}, b > 0, \exists! q, r \in \mathbb{Z} \text{ 使得 } a = bq + r \land 0 \leq r < b \] -
素因子性质：
\[p \text{ 是素数} \land p \mid ab \implies p \mid a \lor p \mid b \] -
最小公倍数与最大公约数：
\[\forall a, b \in \mathbb{Z}, \exists \text{lcm}(a, b) \land \text{gcd}(a, b) \implies a \times b = \text{gcd}(a, b) \times \text{lcm}(a, b) \]
同余
同余（Congruence）是数论中的一个概念，它描述了两个整数在除以一个固定正整数（称为模数）时余数相同的关系。如果两个整数 \(a\) 和 \(b\) 除以正整数 \(n\) 后余数相同，那么我们说 \(a\) 和 \(b\) 同余模 \(n\)，记作：
\[a \equiv b \pmod{n} \]
同余的性质包括：
-
自反性：
\[a \equiv a \pmod{n} \] -
对称性：
\[a \equiv b \pmod{n} \implies b \equiv a \pmod{n} \] -
传递性：
\[a \equiv b \pmod{n} \land b \equiv c \pmod{n} \implies a \equiv c \pmod{n} \] -
加法性质：
\[a \equiv b \pmod{n} \land c \equiv d \pmod{n} \implies a + c \equiv b + d \pmod{n} \] -
减法性质：
\[a \equiv b \pmod{n} \land c \equiv d \pmod{n} \implies a - c \equiv b - d \pmod{n} \] -
乘法性质：
\[a \equiv b \pmod{n} \land c \equiv d \pmod{n} \implies ac \equiv bd \pmod{n} \] -
幂的性质：
\[\forall k \in \mathbb{Z}^+, \left( a \equiv b \pmod{n} \right) \implies \left( a^k \equiv b^k \pmod{n} \right) \] -
乘法逆元的存在性（若 \(gcd(a, n) = 1\)）：
\[\exists x \implies ax \equiv 1 \pmod{n} \] -
除法性质（若 \(gcd(a, n) = 1\) 且 \(gcd(c, n) = 1\)）：
\[a \equiv b \pmod{n} \implies \frac{a}{c} \equiv \frac{b}{c} \pmod{n} \] -
欧拉定理（若 \(gcd(a, n) = 1\)）：
\[a^{\phi(n)} \equiv 1 \pmod{n} \]其中 \(\phi(n)\) 是欧拉函数，表示小于或等于 \(n\) 且与 \(n\) 互质的正整数的数量。
-
费马小定理（若 (p) 是素数）：
\[\forall a \in \mathbb{Z}, \left( p \text{ 是素数且 } \gcd(a, p) = 1 \right) \implies \left( a^{p-1} \equiv 1 \pmod{p} \right) \]
模运算
模运算是一种算术运算，它涉及到整数的加、减、乘等运算，但在特定的模数 \(n\) 下进行。具体来说，对于任意整数 \(a\) 和正整数 \(n\) ，模运算的结果是指 \(a\) 除以 \(n\) 后的余数，常写作 \(a \mod n\) 。模运算中的模数 \(n\) 决定了结果的范围，即结果总是小于 \(n\) 的非负整数。
模运算的性质包括：
-
加法性质：
\[(a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n \] -
减法性质：
\[(a - b) \mod n = [(a \mod n) - (b \mod n)] \mod n \] -
乘法性质：
\[(a \times b) \mod n = [(a \mod n) \times (b \mod n)] \mod n \] -
幂运算性质：
\[(a^k) \mod n = [(a \mod n)^k] \mod n \] -
加法逆元存在性：
对于每个整数 \(a\) ，存在加法逆元 \(-a\) 使得 \((a + (-a)) \mod n = 0\)。 -
乘法逆元存在性（若 \(gcd(a, n) = 1\)）：
存在整数 \(b\) 使得 \((a \times b) \mod n = 1\)。 -
分配律：
\[(a \times (b + c)) \mod n = [(a \times b) \mod n + (a \times c) \mod n] \mod n \]
欧拉函数
欧拉函数，记作 \(\phi(n)\)，是数论中的一个重要函数，它计算的是不超过正整数 \(n\) 且与 \(n\) 互质的正整数的数量。两个数互质意味着它们的最大公约数 \(gcd\) 为1。
对于正整数 \(n\)，欧拉函数 \(\phi(n)\) 定义为：
\[\phi(n) = \left| \{ k \in \mathbb{Z} \mid 1 \leq k \leq n \text{ 且 } \gcd(k, n) = 1 \} \right| \]欧拉函数的性质有：
-
欧拉定理：
\[a^{\phi(n)} \equiv 1 \pmod{n} \]
如果 \(a\) 与 \(n\) 互质，则： -
乘性函数：
\[\phi(mn) = \phi(m) \phi(n) \]
如果 \(m\) 和 \(n\) 互质，则： -
素数幂的性质：
\[\phi(p^k) = p^k - p^{k-1} \]
如果 \(p\) 是素数，\(k\) 是正整数，则： -
不同素数乘积的性质：
\[\phi(p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}) = p_1^{k_1-1}(p_1-1) p_2^{k_2-1}(p_2-1) \cdots p_m^{k_m-1}(p_m-1) \]
如果 \(p_1, p_2, \ldots, p_m\) 是不同的素数，\(k_1, k_2, \ldots, k_m\) 是正整数，则： -
欧拉函数的界限：
\[\phi(n) \leq n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right) \]
对于任何正整数 \(n\)，其中 \(p_1, p_2, \ldots, p_m\) 是 \(n\) 的不同素因子。
欧拉定理 & 费马小定理
欧拉定理
如果 \(a\) 和 \(n\) 互质（即 \(\gcd(a, n) = 1\)），则：
\[a^{\phi(n)} \equiv 1 \pmod{n} \]其中 \(\phi(n)\) 是欧拉函数，表示不超过 \(n\) 且与 \(n\) 互质的正整数的数量。
性质和相关定理：
-
如果 \(a\) 和 \(n\) 互质，则 \(a^k \equiv 1 \pmod{n}\) 的最小正整数 \(k\) 是 \(\phi(n)\) 的因数。
-
如果 \(p\) 是素数，则 \(\phi(p^k) = p^k - p^{k-1}\)，对于 \(k \geq 1\)。
-
如果 \(n\) 有素因子分解 \(n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}\)，则：
\[\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right) \]
费马小定理
费马小定理指出，如果 \(p\) 是一个素数，\(a\) 是一个整数，且 \(a\) 不能被 \(p\) 整除，则以下同余关系成立：
\[a^{p-1} \equiv 1 \pmod{p} \]费马小定理的性质和相关定理：
-
逆元的存在性：
\[a^{p-2} \equiv a^{-1} \pmod{p} \]
如果 \(p\) 是素数，\(a\) 是不被 \(p\) 整除的整数，则：这表明 \(a\) 模 \(p\) 有乘法逆元，且该逆元是 \(a^{p-2}\)。
-
定理的逆否形式：
\[a^{p-1} \not\equiv 1 \pmod{p} \]
如果 \(p\) 是素数，\(a\) 是不被 \(p\) 整除的整数，如果：则 \(a\) 不是模 \(p\) 下的费马见证。
-
卡迈克尔数：
\[a^{n-1} \equiv 1 \pmod{n} \]
存在合数 \(n\)（称为卡迈克尔数），使得对于所有与 \(n\) 互质的整数 \(a\)，都有：这些数是费马小定理的合数类比。
素性测试
费马小定理可以用来快速测试一个数是否可能是素数。如果一个数 \(p\) 对于某个整数 \(a\) 不满足：
\[a^{p-1} \equiv 1 \pmod{p} \]则 \(p\) 肯定不是素数。
线性同余方程(Linear Congruence Equation)
线性同余方程是形如：
\[ax \equiv b \pmod{n} \]的方程，其中 \(a,b\) 和 \(n\) 是给定的整数，\(x\) 是我们需要从区间 \(0 \leq x < n\) 中求解的未知数，当解不唯一时，需要求出全体解。
用逆元求解
当 \(a\) 和 \(n\) 互素（即 \(\gcd(a, n) = 1\)）时，我们可以找到 \(a \mod n\) 的乘法逆元 \(a^{-1}\)，然后将方程两边乘以 \(a^{-1}\) 来求得一个唯一解 \(x\)：
\[x \equiv a^{-1}b \pmod{n} \]
假设 \(a\) 和 \(n\) 不互素（即 \(\gcd(a,n)=d>1\)），此时不一定有解。设 \(d = \gcd(a, n)\)，则 \(d\) 不一定能整除 \(b\)。如果 \(d \nmid b\)不成立，则无解，因为对于任意的 \(x\)，方程 \(ax \equiv b \pmod{n}\) 的左侧始终可被 \(d\) 整除，而右侧不可被 \(d\) 整除，因此无解。
如果 \(d \mid c\)，则通过将方程两边 \(a\)、\(b\) 和 \(c\) 除以 \(d\)，得到一个新的方程：
\[\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}} \]其中 \(\frac{a}{d}\) 和 \(\frac{m}{d}\) 已经互素，这种情形已经解决，于是得到 \(x\) 作为 \(x\) 的解。
很明显，\(x + \frac{m}{d}\) 也将是原始方程的解。这不是唯一的解。可以看出，原始方程有如下 \(d\) 个解：
\[x, x + \frac{m}{d}, x + 2\frac{m}{d}, \ldots, x + (d-1)\frac{m}{d} \]总之，线性同余方程的解的数量等于 \(\gcd(a, m)\) 或等于 \(\frac{m}{\gcd(a, m)}\)。
用扩展欧几里得算法求解
对于 \(a\) 和 \(n\) 不互质的情况，我们可以使用扩展欧几里得算法来求解。首先，我们找到 \(a\) 和 \(n\) 的最大公约数 \(d\)：
\[d = \gcd(a, n) \]如果 \(d\) 不能整除 \(b\)，则线性同余方程无解。如果 \(d\) 能整除 \(b\)，则我们可以将方程两边同时除以 \(d\)，得到一个新的方程：
\[\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}} \]现在，我们可以对新的方程使用扩展欧几里得算法来找到一组特解 \((x_0, y_0)\)，然后根据以下公式得到所有解：
\[x \equiv x_0 + k\frac{n}{d} \pmod{n} \]其中 \(k\) 是任意整数。
具体如何计算，在后面乘法逆元部分给出
线性同余方程的性质
- 解的存在性：
线性同余方程 \(ax \equiv b \pmod{n}\) 有解当且仅当 \(\gcd(a, n) \mid b\)。 - 解的唯一性：
如果 \(a\) 和 \(n\) 互质，则线性同余方程在模 \(n\) 下有唯一解。 - 解的个数：
如果 \(d = \gcd(a, n)\)，则线性同余方程 \(ax \equiv b \pmod{n}\) 有解当且仅当 \(d \mid b\)。在这种情况下，方程模 \(n\) 有恰好 \(d\) 个不同的解。
贝祖定理(裴蜀定理)
设 \(a_1, a_2, \ldots, a_n\) 是不全为零的整数，对任意整数 \(d\)，如果 \(d\) 是 \(a_1, a_2, \ldots, a_n\) 的最大公约数，则存在整数 \(x_1, x_2, \ldots, x_n\) 使得：
\[d = a_1x_1 + a_2x_2 + \cdots + a_nx_n \]贝祖定理可以推广到多个整数的情形：
- 逆定理：如果 \(d\) 是 \(a_1, a_2, \ldots, a_n\) 的公因数，且存在整数 \(x_1, x_2, \ldots, x_n\) 使得：
\(d = a_1x_1 + a_2x_2 + \cdots + a_nx_n\)
则 \(d\) 是 \(a_1, a_2, \ldots, a_n\) 的最大公约数。 - 多个整数：对于 \(n\) 个不全为零的整数 \(a_1, a_2, \ldots, a_n\)，存在整数 \(x_1, x_2, \ldots, x_n\) 使得：
\(a_1x_1 + a_2x_2 + \cdots + a_nx_n = \gcd(a_1, a_2, \ldots, a_n)\)
对于自然数 \(a\) 和 \(b\)，如果 \(a\) 和 \(b\) 互素，考察不定方程 \(ax + by = c\)，其中 \(x\) 和 \(y\) 为自然数。如果方程有解，则称 \(c\) 可以被 \(a\) 和 \(b\) 表示。对于任意整数 \(c\)，\(a\) 和 \(b\) 中有且仅有一个可以被表示。
将方程 \(ax + by = c\) 看作一条直线，直线与两坐标轴在第一象限围成三角形。当 \(c\) 可以被表示时，直线恰好经过一个整点；当 \(c\) 不可被表示时，直线不经过整点。
快速模幂算法
快速幂算法（也称为快速指数算法或模幂算法）是一种用于高效计算大数幂次的算法，特别是在模运算的环境下。这种算法可以快速计算形如 \(a^{b} \mod n\) 的表达式，其中 \(a\) 是底数，\(b\) 是指数（通常是一个非常大的数），而 \(n\) 是模数。这种计算在密码学、数论和计算机科学中非常常见。
快速幂算法利用了下面几个性质。
任何正整数都可以唯一地表示为二进制形式：
\[b=2^{k}+2^{j}+{\ldots}+2^{i} \]幂次合并：
\[a^{b}=a^{2^{k}}.a^{2^{j}}{\ldots}.a^{2^{i}} \]取模的运算法制：
\[(a*b)\pmod p=(a \pmod {p}*b \pmod {p})\pmod{p} \]即，多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果。那么我们就可以对每次分出的幂的结果进行取模后再相乘以得到最后的结果。
下面以 \(7^{5} \mod 1000\) 作为例子，计算器的计算结果是807
\[7^{5}=16,807 \]将5转换为二进制101，可得：
\[5=1*2^2+1*2^0 \]\(7^5\)就可以分解为下式：
\[7^5=7^{2^0}*7^{2^2} \]我们可以发现，幂的结果就是这个拆分过程中，指数的二进制表示上为1的部分乘以相应的底数的所有部分的乘积。但直接这样去算不行，我们要用快速幂算法进行计算。
快速幂算法的核心思想就是每一步将指数分成两半，相应的底数则做平方计算（具体就是，指数为奇数，将当前的底数乘以ans，指数为偶数，则继续进行细分）。如下面的过程所示：
\[7^5=7^1*7^4=7^1*49^2=7^1*2401^1 \]由模的运算法则可得：
\[7^5\pmod{1000}=(7^1\pmod{1000}\cdot7^4\pmod{1000})\pmod{1000} \]\[=(7^1 \pmod {1000} \cdot 7^4 \pmod {1000}) \pmod {1000} \]\[=(7^1 \pmod {1000} \cdot 49^2 \pmod {1000}) \pmod {1000} \]\[=(7^1 \pmod {1000} \cdot 2401^1 \pmod {1000}) \pmod {1000} \]\[=(7\cdot401)\pmod{1000} \]\[=807 \]
据此，假设一开始的 \(index=5\)，\(ans=1\)，\(base=7\)，\(mod=1000\)
\(index\) 为奇数，可得
\[index\quad{\&}\quad1=1 \]\[ans=ans*base \pmod {1000}=7 \]\[index=index>>1=2 \]\[base=base^{2} \pmod {1000}=49 \]\(index\) 为偶数，可得
\[index \quad {\&} \quad 1=0 \]\[index=index>>1=1 \]\[base=base^{2}\pmod {1000}=401 \]index为奇数，可得
\[index \quad {\&} \quad 1=0 \]\[ans=ans*base\pmod{1000}=7*401 \pmod {1000}=807 \]\[index=index>>1=0 \]\[base=base^{2}\pmod {1000} \]\(index\) 满足条件小于等于0，循环结束。
C++代码实现如下：
#include <iostream>
template <typename T>
T qmod(T base, T index, T mod) {
T ans =1;
while(index>0) {
if(index&1) {
ans = (ans*base)%mod;
}
index>>=1;
base = (base*base)%mod;
}
return ans;
}
int main() {
int base = 7;
int index = 5;
int mod = 1000;
int ans = qmod(base, index, mod);
std::cout<<ans<<std::endl;
return 0;
}
乘法逆元
如果一个线性同余方程
\[ax \equiv 1 \pmod b \]则 \(x\) 称为 \(a \mod b\) 的逆元，记作 \(a^{-1}\)
-
逆元的乘积：
\[bc \equiv (ad)^{-1} \pmod{n} \]
如果 \(b\) 是 \(a\) 模 \(n\) 的乘法逆元，\(c\) 是 \(d\) 模 \(n\) 的乘法逆元，则： -
逆元的逆元：
\[a \equiv b^{-1} \pmod{n} \]
如果 \(b\) 是 \(a\) 模 \(n\) 的乘法逆元，则： -
逆元的幂：
\[b^k \equiv (a^k)^{-1} \pmod{n} \]
如果 \(b\) 是 \(a\) 模 \(n\) 的乘法逆元，则对于任何整数 \(k\)： -
费马小定理：
\[a^{p-1} \equiv 1 \pmod{p} \]
如果 \(p\) 是素数，\(a\) 是不被 \(p\) 整除的整数，则：这意味着 \(a^{p-2}\) 是 \(a\) 模 \(p\) 的乘法逆元。
扩展欧几里德算法求乘法逆元
根据以下两个定理，可以求出线性同余方程\(ax \equiv b \pmod{n}\)的解。
定理 1：线性同余方程\(ax \equiv b \pmod{n}\)可以改写为如下线性不定方程：
\[ax + ny = b \]其中 \(x\) 和 \(y\) 是未知数。这两个方程是等价的，有整数解的充要条件为 \(\gcd(a, n) \mid b\)。
应用扩展欧几里得算法可以求解该线性不定方程。根据定理 1，对于线性不定方程 \(ax + ny = \gcd(a, n)\)，可以先用扩展欧几里得算法求出一组特解 \((x_0, y_0)\) ，也就是 \(a x_0 + n y_0 = \gcd(a, n)\)，然后两边同时除以 \(\gcd(a, n)\)，再乘以\(b / \gcd(a, n)\)，就得到了方程\(ax \equiv b \pmod{n}\)的一个解。
于是找到方程的一个解：
\[x = x_0 \cdot \frac{b}{\gcd(a, n)} \]定理 2：若\(\gcd(a, n) = d\)，且\((x_0, y_0)\)为方程\(ax + ny = d\)的一组解，则该方程的任意解可表示为：
\[x = x_0 + \frac{n}{d}t \]\[y = y_0 - \frac{a}{d}t \]并且对任意整数 \(t\) 都成立。
根据定理 2，可以从已求出的一个解，求出方程的所有解。实际问题中，往往要求出一个最小整数解，也就是一个特解：
\[x = x_0 + \frac{n}{d}t \]其中有 \(t\) 使得\(0 \leq x < n\)。
由乘法逆元的定义，我们可以知道如果一个线性同余方程
\[ax \equiv 1 \pmod b \]则 \(x\) 称为 \(a \mod b\) 的逆元，记作 \(a^{-1}\)
那么上式就可以被改写成如下的线性不定方程：
\[ax+ny=1 \]求解得到的 \(x\) 就是我们需要的乘法逆元。
下面以RSA算法作为例子，进行实例演练。
已知有素数 \(p=47,q=71\)，可以求得 \(n=p \times q=47 \times 71 = 3337\)
由欧拉函数的性质，可求得 \(\phi(n) = \phi(p)\phi(q) = (p-1)(q-1) = 46 \times 70 = 3220\)
取随机的与 \(\phi(n)\) 互素的 \(e=79\) ，即 \(gcd(e,\phi(n))=1\)
那么我们需要求解线性同余方程 \(ed \equiv 1 \pmod {\phi(n)}\)，去求得 \(e \mod {\phi(n)}\) 的乘法逆元 \(d\)
该线性同余方程可以改写成下式：
\[ed+\phi(n)y=gcd(e,\phi(n))=1 \]由素数定理可知，\(d,y \in \mathbb{Z}\)
下面进行手算计算演示：
设\(a=e,b=\phi(n)，代入gcd(a,b)\)
\[gcd(79,3220),79*x+3220*y=1 \]\[gcd(3220,{79} \mod {3220})=gcd(3220,79),3220*x+79*y=1 \]\[gcd(79,{3220} \mod {79})=gcd(79,60),79*x+60*y=1 \]\[gcd(60,{79} \mod 60)=gcd(60,19),60*x+19*y=1 \]\[gcd(19,{60}\mod{19})=gcd(19,3),19*x+3*y=1 \]\[gcd(3,{19} \mod {3})=gcd(3,1),3*x+1*y=1 \]\[gcd(1,3 \mod 1)=gcd(1,0)，1*x+0*y=1 \]此时 \(b==0\)，由方程 \(ax+by=gcd(a,b)=1\)，可以得到 \(x_0=1,y_0=0\)，开始回代：
\[x_1=y_0=0,y_1=x_0-\frac{a}{b}\cdot y_0=1-\lfloor\frac31\rfloor\cdot0=1 \]\[x_2=y_1=1,y_2=x_1-\frac{a}{b}\cdot y_1=0-\lfloor\frac{19}{3}\rfloor\cdot1=-6 \]\[x_3=y_2=-6,y_3=x_2-\frac{a}{b}\cdot y_2=1-\lfloor\frac{60}{19}\rfloor\cdot-6=19 \]\[x_4=y_3=19,y_4=x_3-\frac{a}{b}\cdot y_3=-6-\lfloor\frac{79}{60}\rfloor\cdot19=-25 \]\[x_5=y_4=-25,y_5=x_4-\frac{a}{b}\cdot y_4=19-\lfloor\frac{3220}{79}\rfloor\cdot19=1019 \]\[x_6=y_5=1019,y_6=x_5-\frac{a}{b}\cdot y_5=-25-\lfloor\frac{79}{3220}\rfloor\cdot1019=-25 \]这里的 \(x_6=1019\) 就是我们要求的乘法逆元 \(d\)
费马小定理求乘法逆元
费马小定理的表述如下：
如果 \(p\) 是一个质数，且 \(a\) 是任何一个不是 \(p\) 的倍数的整数，则 \(a^{p-1}-1\) 是 \(p\) 的倍数，用数学公式表示为：
\[a^{p-1}\equiv1 \pmod p \]重写该式可得：
\[a*a^{p-2} \equiv 1 \pmod p \]由此我们就可以知道 \(a\) 的乘法逆元是 \(a^{p-2} \pmod p\)，用快速模幂算法可以快速求得（前提是，模数必须是一个质数）。
如何寻找最大公约数(Greatest Common Divisor，GCD)
欧几里得算法(Euclidean algorithm)
假设有两个数 \(a,b\;(a>b)\)，如果 \(b\) 是 \(a\) 的约数，那么 \(b\) 就是二者的最大公倍数。
如果不能整除，则有下式：
\[a=b{\times}q+r,\quad(c<b) \]不难得出 \(r=a{\;}mod{\;}b\)
也可得出 \(r=a-bk,\left(k\in\mathbb{N}^{*}\right)\)
我们假设 \(a\) 和 \(b\) 的一个公约数是 \(d\)，那么我们可以得到下面的式子：
\[\frac{r}{d}=\frac{a}{d}-\frac{b}{d}k \]右边的式子的结果显然是一个整数，我们就可以得出 \(d|r\)
由 \(d|a, {\ } d|b\) 且 \(d|r\)，我们就可以得出 \(d\) 也是 \(b\) 和 \(r\) 的公约数。
逆向来看，如果说 \(b\) 和 \(r\) 的一个公约数是 \(d\) ，我们也可以根据 \(bk+r=a\) 得到 \(\frac{b}{d}k+\frac{r}{d}=\frac{a}{d}\)，从而得到 \(d|a\)，证明 \(d\) 也是 \(a\) 和 \(b\) 的公约数。
最终我们可以得到下面的结论：
\[gcd(a,b)=gcd(b,a{\ }mod{\ }b) \]这个式子允许我们不断进行递归求解，直到 \(b=0\)，此时的 \(a\) 就是最大公约数。
于是，我们就可以得到一个简单的递归实现：
#include<iostream>
template<typename T>
T euclidean_algorithm(T a,T b){
return (b==0)?a:euclidean_algorithm(b,a%b);
}
int main(){
int num1 = 36;
int num2 = 60;
std::cout << "The GCD of " << num1 << " and " << num2 << " is " << euclidean_algorithm(num1, num2) << std::endl;
return 0;
}
非递归实现也很简单：
#include<iostream>
template<typename T>
T euclidean_algorithm(T a,T b){
while(b!= 0){
T temp = b;
b = a % b;
a = temp;
}
return a;
}
int main(){
int num1 = 36;
int num2 = 60;
std::cout << "The GCD of " << num1 << " and " << num2 << " is " << euclidean_algorithm(num1, num2) << std::endl;
return 0;
}
扩展欧几里德算法(Extend euclidean algorithm)
扩展欧几里得算法是用于求解两个整数 \(a\) 和 \(b\) 的最大公约数 \(gcd\)，并且能够找到一组整数解 \(x\) 和 \(y\) 使得 \(ax + by = \gcd(a, b)\)。这个算法是欧几里得算法的扩展，它不仅可以用来求最大公约数，还可以用来解决一些线性同余方程和求逆元等问题。
扩展欧几里得算法基于以下定理：对于任意整数 \(a\) 和 \(b\)，存在整数 \(x\) 和 \(y\) 使得 \(ax + by = \gcd(a, b)\)。这个定理被称为贝祖定理（Bézout's identity）。
算法步骤：
- 初始化两个数组或变量来存储 \(x\) 和 \(y\) 的值。
- 使用欧几里得算法求 \(a\) 和 \(b\) 的最大公约数。
- 在求最大公约数的过程中，通过回代的方式计算出 \(x\) 和 \(y\) 的值。
扩展欧几里得算法的数学表达式可以表示为：
\[ax + by = \gcd(a, b) \]其中，\(a\) 和 \(b\) 是给定的整数，\(x\) 和 \(y\) 是求解的整数。
下面是扩展欧几里德算法的C++实现：
#include <iostream>
// 函数用于计算最大公约数，并返回 ax + by = gcd(a, b) 的解
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - (a / b) * y;
return d;
}
int main() {
int a, b;
int x, y;
std::cin >> a >> b;
int gcd = exgcd(a, b, x, y);
std::cout << "gcd: " << gcd << std::endl;
std::cout << "x: " << x << std::endl;
std::cout << "y: " << y << std::endl;
return 0;
}
实现回代的原理和过程分析
我们只知道可以回代，那么问题来了，为什么可以回代呢？
这里我们做一下分析。
首先，我们知道扩展欧几里得算法的数学表达式可以表示为：
\[ax + by = \gcd(a, b) \]若 \(gcd(a,b)=1\)，上式可以表示为下式：
\[ax+by=1 \]当扩展欧几里德算法递归求解到基础情况 \(b=0\) 时， \(gcd(a,b)=a\)，此时由式子
\[x{\cdot}a+y{\cdot}0=a \]可以得到 \(x=1,y=0\)
递归过程中，如果 \(b \neq 0\)，我们可以写出 \(gcd(a,b)=gcd(b,a \mod b)\)
进而，我们可以将问题分解为更小的子问题。
设 \(d=gcd(a,b)\)，则有：
\[d=a\cdot x+b\cdot y \]由于 \(a\mod b=a-\lfloor\frac{a}{b}\rfloor\cdot b\)，若我们将上述的 \(a\) 替换，就可以得到：
\[d=(b\cdot\lfloor\frac{a}{b}\rfloor+({a} \mod {b}))\cdot x+b\cdot y \]\[d=b\cdot\left(\lfloor\frac{a}{b}\rfloor\cdot x+y\right)+\left(a\mod b\right)\cdot x \]设 \(q=\lfloor\frac{a}{b}\rfloor\)，可得：
\[d=b\cdot\left(qx+y\right)+\left(a\mod b\right)\cdot x \]设 \(x_1=(qx+y),y_1=x\)，可得：
\[d=b\cdot x_1+\left(a\mod b\right)\cdot y_1 \]当我们抵达基础情况的时候，就可以进行回代，从而求出中途每个式子的 \((x,y)\)，回到最初的式子时，就得出了最初的 \(ax + by = \gcd(a, b)\) 的解。
直接推公式的话看着有些抽象，没关系，我们可以上示例（有些熟悉？因为我复用了）。
设\(a=79,b=3220，且gcd(a,b)=1，代入gcd(a,b)\)
\[gcd(79,3220),79*x+3220*y=1 \]\[gcd(3220,{79} \mod {3220})=gcd(3220,79),3220*x+79*y=1 \]\[gcd(79,{3220} \mod {79})=gcd(79,60),79*x+60*y=1 \]\[gcd(60,{79} \mod 60)=gcd(60,19),60*x+19*y=1 \]\[gcd(19,{60}\mod{19})=gcd(19,3),19*x+3*y=1 \]\[gcd(3,{19} \mod {3})=gcd(3,1),3*x+1*y=1 \]\[gcd(1,3 \mod 1)=gcd(1,0)，1*x+0*y=1 \]此时 \(b==0\)，由方程 \(ax+by=gcd(a,b)=1\)，可以得到 \(x_0=1,y_0=0\)，开始回代：
\[x_1=y_0=0,y_1=x_0-\frac{a}{b}\cdot y_0=1-\lfloor\frac31\rfloor\cdot0=1 \]\[x_2=y_1=1,y_2=x_1-\frac{a}{b}\cdot y_1=0-\lfloor\frac{19}{3}\rfloor\cdot1=-6 \]\[x_3=y_2=-6,y_3=x_2-\frac{a}{b}\cdot y_2=1-\lfloor\frac{60}{19}\rfloor\cdot-6=19 \]\[x_4=y_3=19,y_4=x_3-\frac{a}{b}\cdot y_3=-6-\lfloor\frac{79}{60}\rfloor\cdot19=-25 \]\[x_5=y_4=-25,y_5=x_4-\frac{a}{b}\cdot y_4=19-\lfloor\frac{3220}{79}\rfloor\cdot19=1019 \]\[x_6=y_5=1019,y_6=x_5-\frac{a}{b}\cdot y_5=-25-\lfloor\frac{79}{3220}\rfloor\cdot1019=-25 \]我们根据这个计算过程详细解析一下怎么回代的。
对于基础情况，我们知道 \(x_0=1,y_0=0\)，怎么求得上一层的 \(x_1，y_1\)呢？
正向的情况是， \(d=a\cdot x_1+b\cdot y_1 \implies d=b\cdot x_0+\left(a\mod b\right)\cdot y_0\) ，其中 \(x_0=(qx_1+y_1),y_0=x_1\)
那么反向的情况则可以理解为 \(x_1=y_0,y_1=x_0-q\cdot x_1=x_0-q*y_0=x_0-\lfloor\frac{a}{b}\rfloor\cdot y_0\)
由此可以得到递推公式
\[x_n=y_{n-1} \]\[y_{n}=x_{n-1}-\lfloor\frac{a}{b}\rfloor\cdot{y_{n-1}} \]其中 \(0 \leq n \leq \text{递归总次数}\)。
以上，就是回代的实现原理和过程分析。
更相减损术(Decreases technique)
如果 \(a = b\)，则 \(a\) 和 \(b\) 的最大公约数显然是 \(a\)（或 \(b\)），因为任何数与自身的最大公约数就是它本身。
假设 \(a > b > 0\)，执行更相减损术的一次操作：\(a' = a - b\)，需要证明
\[\text{gcd}(a, b) = \text{gcd}(b, a') \]
- 设 \(d = \text{gcd}(a, b)\)，则 \(d | a\) 且 \(d | b\)
- 因为 \(d | a\)，所以 \(d | (a - b) = a'\)（由整除的和的运算性质可得）
- 因此，\(d\) 是 \(b\) 和 \(a'\) 的公约数
- 反之，设 \(d' = \text{gcd}(b, a')\)，则 \(d' | b\) 且 \(d' | a'\)
- 因为 \(d' | a'\) 且 \(a' = a - b\)，所以 \(d' | a\)（由整除的和的运算性质可得）
- 因此，\(d'\) 是 \(a\) 和 \(b\) 的公约数
- 由于 \(d\) 和 \(d'\) 都是 \(a\) 和 \(b\) 的最大公约数，所以 \(d = d'\)
- 得证，\(\text{gcd}(a, b) = \text{gcd}(b, a')\)
由此，我们可以不断地对 \(a\) 和 \(b\) 执行更相减损术，直到 \(a\) 和 \(b\) 相等，此时的数就是最大公约数。
#include<iostream>
template<typename T>
T decreases_technique(T a, T b){
while(a!=b){
a-=b;
}
return a;
}
int main(){
int a = 100, b = 5;
std::cout<<"The GCD of "<< a << " and " << b << " is " <<decreases_technique(a,b)<<std::endl;
return 0;
}
如何选择最小公倍数(Least Common Multiple, LCM)
求解最小公倍数的公式如下：
\[lcm(a,b)=\frac{a\times b}{\operatorname{gcd}\left(a,b\right)} \]因此，求解两个数的最小公倍数的最常见的做法就是先求出它们的 gcd
RSA公钥密码体制简述
RSA是一种公钥密码体制（又称非对称密码体制）。所谓非对称密码体制，同此前的替代和置换的操作不同，它基于一种特殊的数学函数（即单向陷门函数）对明文进行加密和解密。具体操作如下：
-
有两把钥匙和一个锁，
- 一把可对外公开，称为公钥（public key），用KU或者PK表示；
- 另一把被严格保密，只有密钥所有者才知道，称为密钥（private key 或者 secret key），用KR或者SK表示；
- 单向陷门函数则是锁，神奇的地方在于，用公钥加密的明文，一般只能用私钥才能解密（例如，RSA是基于大整数N分解的数学难题），简单来说，就是正向由m得到c很容易，但是在缺少k的情况下几乎不可能从c得到m；
-
用公钥对m加密，得到c
-
用密钥对c解密，得到m
公钥密码体制的安全是由其所用的单向陷门函数所保障的。
而RSA公钥密码体制所采用的单向陷门函数，就是基于大整数分解的数学难题，简述其实现过程如下：
-
选择两个秘密的大素数p和q，计算n=p*q
-
计算n的欧拉函数
\[\varphi\left(n\right)=\varphi\left(p\right)\varphi\left(q\right)=\left(p-1\right)\left(q-1\right) \] -
随机选择一个与n的欧拉函数互素的整数e作为公钥
-
求出整数e的乘法逆元d作为私钥
-
得到公钥对(e,n)，密钥对(d,n)
-
用公钥对对明文m做加密运算
\[c=E(m)=m^{e}{\quad}mod{\quad}n \] -
用密钥对对密文c做解密运算
\[m=D(c)=c^{d}{\quad}mod{\quad}n \]
RSA加解密实现
简单的实现
#include<iostream>
enum option: int {
ENCODE,
DECODE,
};
template <typename T>
T qmod(T base, T index, T mod) {
T ans =1;
while(index>0) {
if(index&1) {
ans = (ans*base)%mod;
}
index>>=1;
base = (base*base)%mod;
}
return ans;
}
// 函数用于计算最大公约数，并返回 ax + by = gcd(a, b) 的解
template <typename T>
T exgcd(T a, T b, T &x, T &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
T d = exgcd(b, a % b, x, y);
T temp = x;
x = y;
y = temp - (a / b) * y;
return d;
}
template<typename T>
T RSA(T input,T p, T q, T e, T d,int op){
switch (op)
{
case option::ENCODE:
return qmod(input, e, p*q);
break;
case option::DECODE:
return qmod(input, d, p*q);
break;
default:
break;
return -1;
}
return -1;
}
template<typename T>
T get_d(T p, T q, T e){
T d, x, y;
exgcd(e, (p-1)*(q-1), x, y);
d = x;
if (d < 0){
d += (p-1)*(q-1);
}
return d;
}
int main(){
long long p, q, e, d, input;
int op;
std::cout << "Enter p: ";
std::cin >> p;
std::cout << "Enter q: ";
std::cin >> q;
std::cout << "Enter e: ";
std::cin >> e;
d = get_d(p, q, e);
std::cout << "d = " << d << std::endl;
std::cout << "Enter input: ";
std::cin >> input;
std::cout << "Enter option (0 for encode, 1 for decode): ";
std::cin >> op;
if(op == option::ENCODE){
std::cout << "Encoded message: " << RSA(input, p, q, e, d, op) << std::endl;
}
else if(op == option::DECODE){
std::cout << "Decoded message: " << RSA(input, p, q, e, d, op) << std::endl;
}
return 0;
}
程序从2开始选择e
#include<iostream>
enum option: int {
ENCODE,
DECODE,
};
template <typename T>
T qmod(T base, T index, T mod) {
T ans =1;
while(index>0) {
if(index&1) {
ans = (ans*base)%mod;
}
index>>=1;
base = (base*base)%mod;
}
return ans;
}
template<typename T>
T gcd(T a,T b){
while(b!= 0){
T temp = b;
b = a % b;
a = temp;
}
return a;
}
// 函数用于计算最大公约数，并返回 ax + by = gcd(a, b) 的解
template <typename T>
T exgcd(T a, T b, T &x, T &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
T d = exgcd(b, a % b, x, y);
T temp = x;
x = y;
y = temp - (a / b) * y;
return d;
}
template<typename T>
T RSA(T input,T p, T q, T e, T d,int op){
switch (op)
{
case option::ENCODE:
return qmod(input, e, p*q);
break;
case option::DECODE:
return qmod(input, d, p*q);
break;
default:
break;
return -1;
}
return -1;
}
template<typename T>
T get_d(T p, T q, T e){
T d, x, y;
exgcd(e, (p-1)*(q-1), x, y);
d = x;
if (d < 0){
d += (p-1)*(q-1);
}
return d;
}
template<typename T>
T get_e(T p, T q){
T e = 2;
T phi = (p-1)*(q-1);
while(gcd(e, phi)!= 1){
e++;
}
return e;
}
int main(){
long long p, q, e, d, input;
int op;
std::cout << "Enter p: ";
std::cin >> p;
std::cout << "Enter q: ";
std::cin >> q;
e = get_e(p, q);
std::cout << "e = " << e << std::endl;
d = get_d(p, q, e);
std::cout << "d = " << d << std::endl;
std::cout << "Enter input: ";
std::cin >> input;
std::cout << "Enter option (0 for encode, 1 for decode): ";
std::cin >> op;
if(op == option::ENCODE){
std::cout << "Encoded message: " << RSA(input, p, q, e, d, op) << std::endl;
}
else if(op == option::DECODE){
std::cout << "Decoded message: " << RSA(input, p, q, e, d, op) << std::endl;
}
return 0;
}
Result:
Enter p: 47
Enter q: 71
e = 3
d = 2147
Enter input: 688
Enter option (0 for encode, 1 for decode): 0
Encoded message: 2842
Enter p: 47
Enter q: 71
e = 3
d = 2147
Enter input: 2842
Enter option (0 for encode, 1 for decode): 1
Decoded message: 688
进一步集成RSA
#include<iostream>
enum option: int {
ENCODE,
DECODE,
};
template <typename T>
T qmod(T base, T index, T mod) {
T ans =1;
while(index>0) {
if(index&1) {
ans = (ans*base)%mod;
}
index>>=1;
base = (base*base)%mod;
}
return ans;
}
template<typename T>
T gcd(T a,T b){
while(b!= 0){
T temp = b;
b = a % b;
a = temp;
}
return a;
}
// 函数用于计算最大公约数，并返回 ax + by = gcd(a, b) 的解
template <typename T>
T exgcd(T a, T b, T &x, T &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
T d = exgcd(b, a % b, x, y);
T temp = x;
x = y;
y = temp - (a / b) * y;
return d;
}
template<typename T>
T get_d(T p, T q, T e){
T d, x, y;
exgcd(e, (p-1)*(q-1), x, y);
d = x;
if (d < 0){
d += (p-1)*(q-1);
}
return d;
}
template<typename T>
T get_e(T p, T q){
T e = 2;
T phi = (p-1)*(q-1);
while(gcd(e, phi)!= 1){
e++;
}
return e;
}
template<typename T>
T RSA(T input,T p, T q, int op){
T e = get_e(p, q);
std::cout << "e = " << e << std::endl;
T d = get_d(p, q, e);
std::cout << "d = " << d << std::endl;
switch (op)
{
case option::ENCODE:
return qmod(input, e, p*q);
break;
case option::DECODE:
return qmod(input, d, p*q);
break;
default:
break;
return -1;
}
return -1;
}
int main(){
long long p, q, e, d, input;
int op;
std::cout << "Enter p: ";
std::cin >> p;
std::cout << "Enter q: ";
std::cin >> q;
std::cout << "Enter input: ";
std::cin >> input;
std::cout << "Enter option (0 for encode, 1 for decode): ";
std::cin >> op;
if(op == option::ENCODE){
long long encoded = RSA(input, p, q, op);
std::cout << "Encoded message: " << encoded << std::endl;
}
else if(op == option::DECODE){
long long decoded = RSA(input, p, q, op);
std::cout << "Decoded message: " << decoded << std::endl;
}
return 0;
}
Result:
Enter p: 47
Enter q: 71
Enter input: 688
Enter option (0 for encode, 1 for decode): 0
e = 3
d = 2147
Encoded message: 2842
Enter p: 47
Enter q: 71
Enter input: 2842
Enter option (0 for encode, 1 for decode): 1
e = 3
d = 2147
Decoded message: 688
参考资料
- RSA算法基础详解: https://www.cnblogs.com/hykun/p/RSA.html
- RSA算法详解：万字文章详解RSA的加密与解密: https://blog.csdn.net/m0_64359306/article/details/140291832
- OI-wiki: https://oi-wiki.org/math/number-theory/gcd/
标签：frac,gcd,pmod,RSA,cdot,详解,数学原理,equiv,mod From： https://www.cnblogs.com/testtraveler/p/18499698