首发于知乎：https://zhuanlan.zhihu.com/p/76006823
写在前面：这是RSA系列的学习文章，如果你真的想学习CTF中RSA类型的题目都有哪些特点的话，建议大家花时间细下心来好好看。
在讲之前我们先来看一个著名网红老师李永乐的视频，了解一下RSA的一些基本知识。
一遍不行看两遍，两遍不行看三遍。切记一定要看懂这个视频，否则，下面写的很有可能就看不懂了。虽说密码学和数学相关性很大，但是一步一步的学并没有那么难。记住千万不要还没开始就放弃了。
视频链接:
https://www.bilibili.com/video/av26639065/www.bilibili.com/video/av26639065/
2025.03更新：因为写培训课件刚好涉及到这部分内容，就花了些时间，把之前发布RSA的文章进行了重构。删除了一些没用的内容，引入了很多铺垫知识：质数、质因数、质因数分解、最大公约数、互质、模运算、同余定理、逆元、模逆元、欧几里得算法、扩展欧几里得算法等。
创作不易，您的点赞就是对我最大的支持。
一、Python模块安装
下面是RSA题目中常用到的模块安装，采用的是Python2的环境。
1、安装gmpy2模块
|
|
2、安装libnum模块
|
|
3、安装pycipher模块
|
|
4、安装Crypto模块
|
|
安装这几个模块就差不多了。
二、数学基础
1、质数
质数是一个大于1的自然数，且除了1和它本身之外，不能被其他任何自然数整除。
质数示例：
2 是质数（它只能被1和2整除）
3 是质数（它只能被1和3整除）
5 是质数（它只能被1和5整除）
7 是质数（它只能被1和7整除）
不是质数的示例：
4 不是质数（它能被1、2、4整除）
6 不是质数（它能被1、2、3、6整除）
8 不是质数（它能被1、2、4、8整除）
2、质因数
质因数是一个整数的质数因子。也就是说，质因数是可以整除该整数的质数。
18的质因数：18 可以分解为 2 × 3 × 3。 这里，2和3都是质因数。
20的质因数：20 可以分解为 2 × 2 × 5。 这里，2和5是质因数。
3、质因数分解
质因数分解是将一个整数分解成一系列质数的乘积。换句话说，就是找出一个数所有的质因数，并将它们相乘来重构原始数字。
质因数分解过程：
（1）从最小的质数 2 开始，检查是否能够整除该数。
（2）如果能整除，就把该数除以这个质数，得到一个新的商。继续用前面这个相同的质数反复尝试整除这个新商，直到不能再整除为止。
（3）如果当前质数不能整除该数。尝试下一个更大的质数。重复这个过程，直到最终的商也是一个质数，这个数就是最后的一个因子。
（4）最终，把所有找到的质因数列出来，就完成了质因数分解。
示例，对 50 进行质因数分解：
（1）先从最小的质数 2 开始尝试：
尝试质数2，50 ÷ 2 = 25 能被整除，得到新的商 25。
（2）继续分解新的商 25：
尝试质数2，25 ÷ 2 不能整除，跳过 2，换下一个更大的质数。
尝试质数3，25 ÷ 3 不能整除，跳过 3，换下一个更大的质数。
尝试质数5，25 ÷ 5 = 5 能被整除，得到新的商 5。
（3）继续分解新的商 5：
尝试质数5，5 ÷ 5 = 1 能被整除，且商1为质数，无法再被分解，分解结束。
因此，50的质因数分解结果为： $50=2×5×5$ 或者 $50 = 2 × 5^2$
当尝试到 质数 5 并成功整除后，新的商 仍然从 5 继续除，而不是回到 2。 因为我们是按照 递增的质数顺序 进行除法，如果一个数能被 5 整除，那说明它已经没有比 5 更小的质因数了（否则早在 2 或 3 时就已经除尽了）。所以 只需要继续用当前的质数 5 试，直到不能整除后，再换下一个更大的质数。
一般情况下，进行质因数分解我们通常使用 factordb 来完成。
（1）命令行方式安装及使用
pip3 install factordb-pycli
（2）在线网站
https://factordb.com/index.php
4、最大公约数
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为 (a, b)，同样的 a，b，c的最大公约数记为 (a,b,c)，多个整数的最大公约数也有同样的记号。
求最大公约数有多种方法，常见的有短除法、辗转相除法、质因数分解法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为 [a,b]。
a、最大公约数(短除法)
短除法是求最大公因数的一种方法，也可用来求最小公倍数。求几个数最大公因数的方法，开始时用观察比较的方法，即：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。后来，使用分解质因数法来分别分解两个数的因数，再进行运算。之后又演变为短除法。短除法运算方法是先用一个被除数除以能被它除尽的一个质数，以此类推，除到两个数的商是互质数为止。
b、最大公约数(欧几里得算法/辗转相除法)
欧几里得算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式 gcd(a, b) = gcd(b, a mod b)，继续递归，直到 b=0，此时 a 就是最大公约数。
5、互质
互质 是指两个整数的最大公约数（gcd, Greatest Common Divisor)为1。即它们没有公共的质因数。如果 gcd(a,b) = 1，那么就称 a 和 b 互质。
互质的例子：
15 = 3 × 5
32 = 2 × 2 × 2 × 2 × 2
没有共同的质因数 → 15 和 32 互质
非互质的例子：
18 = 2 × 3 × 3
24 = 2 × 2 × 2 × 3
共同的质因数是 2 和 3 → 18 和 24 不互质
互质的性质:
（1）任意一个数都和 1 互质：gcd(a,1) = 1。例如 7 和 1 互质。
（2）两个连续整数必定互质：比如 14 和 15 一定互质，因为相邻的两个数不会有相同的质因数。
（3）如果 a 和 b 互质，并且 a 和 c 互质，那么 a 和 bc 也是互质的。
6、模运算
模运算是数论中的一个非常基础和重要的概念。简单来说，模运算是将一个整数除以另一个整数，并返回它们的余数。通常我们用符号 a mod m 来表a 除以 m 后的余数。
假设有两个整数 a 和 m，其中 m 通常叫做“模”或“模数”，模运算的结果是 a 除以 m 后的余数。可以用公式表示为： a mod m = r。
其中，r是余数，并且满足：0 ≤ r ≤ m。
（1）17 mod 12 的计算过程：
将 17 除以 12，得到商 1，余数是 5。
所以，17 mod 12 = 5。
（2）20 mod 4 的计算过程：
将 20 除以 4，得到商 5，余数是 0。
所以，20 mod 4 = 0。
模运算最直观的应用就是在一些周期性的问题中，比如：
- 时钟：假设现在是 10 点，过了 5 小时后是什么时候呢？直接计算 10 + 5 = 15 ，但 15 点就是 3 点了，这时我们就用模 12 来计算。 15 mod 12 = 3 ，所以答案是 3 点。这里的 12 就是模数，表示时钟有 12 个小时。
- 循环：比如计算数组索引时，数组大小固定。当数组的索引超过数组的长度时，可以用模运算来保证索引值不会超出边界。
a、模运算基本性质
（1）加法性质(可以先对 a 和 b 分别取模，然后再加法，最后再对结果取模) $$ (a + b)\ mod\ m = [(a\ mod\ m) + (b\ mod\ m)]\ mod\ m $$ （2）减法性质(可以先对 a 和 b 分别取模，然后再减法，最后再对结果取模) $$ (a - b)\ mod\ m = [(a\ mod\ m) - (b \ mod \ m)] \ mod \ m $$ （3）加法性质(可以先对 a 和 b 分别取模，然后再加法，最后再对结果取模) $$ (a × b) \ mod \ m = [(a \ mod \ m) × (b \ mod \ m)] \ mod \ m $$ （4）模幂性质(可以先对 a 取模，然后再做幂运算，最后再对结果取模) $$ a^b \ mod \ m = ((a \ mod \ m)^b) \ mod \ m $$ （5）结合律 $$ (a + b + c) \ mod \ m = [ (a + b) + c] \ mod \ m = [ a + (b + c)]\ mod\ m $$
$$ (a × b × c) \ mod \ m = [ (a × b) × c] \ mod \ m = [ a × (b × c)] \ mod \ m $$
（6）交换律 $$ (a + b) \ mod \ m = (b + a) \ mod \ m $$
$$ (a × b) \ mod \ m = (b × a) \ mod \ m $$
（7）分配律 $$ (a + b) × c \ mod \ m = [(a \ mod \ m + b \ mod \ m) × c] \ mod \ m $$
$$ a × (b + c) \ mod \ m = [(a × b) \ mod \ m + (a × c) \ mod \ m] \ mod \ m $$
b、取整符号
符号 ⌊ ⌋ 和 ⌈ ⌉ 用来表示 向下取整 和 向上取整。
（1）符号 ⌊x⌋ 表示 向下取整，即将一个数 x 向下取到最接近的整数。例如：
⌊3.7⌋=3（取下一个整数）
⌊−2.3⌋=−3（取下一个小于 −2.3 的整数）
（2）符号 ⌈x⌉ 表示 向上取整，即将一个数 x 向上取到最接近的整数。例如：
⌈3.7⌉=4（取上一个整数）
⌈−2.3⌉=−2（取上一个大于 −2.3 的整数）
c、求余公式
$$ 余数 r = a \ mod \ m = a \ – \ m × ⌊\frac{a}{m}⌋（ ⌊\frac{a}{m}⌋是a除以m后的商的整数部分） $$
17 mod 12 的计算过程：
余数 r = 17 mod 12
= 17 – 12 × ⌊17/12⌋
= 17 – 12 × ⌊1.4167⌋
= 17 – 12 × 1 = 5
(17 ÷ 12 = 1 余 5)
5 mod 12的计算过程：
余数 r = 5 mod 12
= 5 – 12 × ⌊5/12⌋
= 5 – 12 × ⌊0.4167⌋
= 5 – 12 × 0 = 5
(5 在 mod 12 里面，可直出余数5)
5 mod 5 的计算过程：
余数 r = 5 mod 5
= 5 – 5 × ⌊5/5⌋
= 5 – 5 × 1 = 0
(任何数对自己本身取模的结果都是0)
7、同余定理
同余定理是数论中的一个重要概念，用于描述两个整数在模同一个正整数时余数相同的关系。
17 mod 12 的余数为5：
r = 17 mod 12 = 17 – 12 × 1 = 5
5 mod 12 的余数为5：
r = 5 mod 12 = 5 – 12 × 0 = 5
所以，我们可以说“17和5对模12同余”。
给定一个正整数m，如果两个整数 a 和 b 满足 (a−b) 能被m整除，即 m|(a−b) ，那么就称整数a与b对模m同余，记作： $$ a ≡ b\ (mod\ m) $$ （1）m∣(a−b) 意思是 m 整除 a−b，或者说 a−b 能被 m 整除。
（2）符号 ≡ 表示“同余”，读作“同余于”或“恒等于”。上面等式可读作：a同余于b模m，或a与b关于模m同余，或a恒等于b模m，或a与b关于模m恒等。
（3）如果 a 和 b 的差 (a−b) 能被 m 整除，这意味着 a 和 b 的差 (a−b) 是 m 的倍数。也就是说，存在一个整数 k，使得 a−b=k⋅m 。
（4）mod 的写法：表示取模运算时，不加括号，例如： 17 mod 12 = 5 ；当表达的是等价关系，强调两个数模 m 余数相同时，需加括号，例如：$a ≡ b\ (mod\ m)$，表示取模 m 后，两边 a 和 b 是等价的，即：a mod m = b mod m
为什么 a-b 的差能被m整除，就称整数a与b对模m同余？
假设我们有两个整数 a 和 b，并且它们对模 m 同余，即：$a ≡ b\ (mod\ m)$
根据同余的定义，这意味着它们的余数是相同的。所以，我们有：a mod m = b mod m
根据求余公式，余数 r = a mod m = a – m × $\frac{a}{m}$。那么，a mod m 和 b mod m 的余数 $r_{1}$ 和 $r_{2}$ 可以表示为：
$r_{1}$ = a mod m = a – m × ⌊$\frac{a}{m}$⌋ = a – m × $q_{1}$
$r_{2}$ = b mod m = b – m × ⌊$\frac{a}{m}$⌋ = b – m × $q_{2}$
那么：
a = m × $q_{1}$ + $r_{1}$
b = m × $q_{2}$ + $r_{2}$
因此：
a – b = (m × $q_{1}$ + $r_{1}$) – (m × $q_{2}$ + $r_{2}$)
= m × ($q_{1}$ - $q_{2}$) + ($r_{1}$ - $r_{2}$)
= m × ($q_{1}$ - $q_{2}$) + 0
= m × ($q_{1}$ - $q_{2}$)
因此：a – b 是 m 的倍数，也就是说，a – b 能被 m 整除，即： a - b 的差能被m整除，就称整数a与b对模m同余。
a、同余定理基本性质
自反性：
a ≡ a (mod m)。
即任何整数对模 m 同余于自身。
对称性：
如果 a ≡ b (mod m)，那么一定有 b ≡ a (mod m)。
即同余关系可以交换顺序。
传递性：
如果 a ≡ b (mod m)， b ≡ c (mod m)，那么 a ≡ c (mod m)。
即如果两个数分别与第三个数同余，那么它们彼此也同余。
加法性质：
如果 a ≡ b (mod m)， c ≡ d (mod m)，那么 a + c ≡ b + d (mod m)。
同余可以用于加法，结果仍然保持同余关系。
减法性质：
如果 a ≡ b (mod m)， c ≡ d (mod m)，那么 a - c ≡ b - d (mod m)。
同余可以用于减法，结果仍然保持同余关系。
乘法性质：
如果 a ≡ b (mod m)， c ≡ d (mod m)，那么 a · c ≡ b · d (mod m)。
同余可以用于乘法，结果仍然保持同余关系。
幂运算(指数)性质：
a ≡ b (mod m)，那么对于任意正整数 k，有：a^k ≡ b^k (mod m)。
即同余可以用于幂运算。
乘法消去律性质：
如果 a · c ≡ b · c (mod m)，且 c 与 m 互质(即gcd(c, m) = 1)，则 a ≡ b (mod m) 。
即在保证 c 与 m 互质的前提下，可以在同余式的两边同时除以 c。
模数取余性质：
如果 a ≡ b (mod m) ，那么 a mod m = b mod m。
即如果 a 和 b 同余，那么a 和 b 除以 m 的余数必然相等。
8、逆元
在数学中，逆元（Inverse Element） 指的是对某种运算来说，一个数和它的逆元进行运算后能得到单位元（加法的单位元是 0，乘法的单位元是 1）。
（1）加法逆元是指，对于一个数 a，找到一个数 b，使得：a + b = 0
也就是说，b 是 a 的相反数，记作：b = -a 。
例如：5 的逆元是 −5，因为：5 ＋ (-5) = 0。
（2）乘法逆元是指，对于一个数 a，找到一个数 b，使得：a × b= 1
也就是说，b 是 a 的倒数，记作：$b = \frac{1}{a}$ ，要注意的是，只有非零数才有乘法逆元。例如： 5 的乘法逆元是 $5 × \frac{1}{5} = 1$ ，因为： $5 × \frac{1}{5} = 1$；0 没有乘法逆元，因为任何数乘以 0 都不会得到 1。
9、模逆元
模逆元（Modular Inverse）是乘法逆元的一个特殊情况，指的是在模 m 意义下的乘法逆元。
对于一个整数 a，如果存在整数 b，使得： $$ a × b ≡ 1 \ (mod \ m) $$ 那么这个 b 就被称为 a 在模 m 下的模逆元，记作： $$ b ≡ \frac{1}{a} \ mod \ m \ 或\ b ≡ a^{-1} \ mod\ m $$ 也就是说，b 是一个数，使得 a 乘以它后，结果除以 m 的余数是 1。
注意：a × b ≡ 1 (mod m)，表示在模m下，a × b 和 1 是等价的，即 a × b mod m = 1 mod m，并不是指 a × b = 1。也可说：a × b − 1 = k × m(k ∈ Z)。
在等式$ a × b ≡ 1\ (mod\ m)$中，对于整数 a 和 a 在模 m 下的模逆元 a−1 存在的条件： $$ gcd(a, m) = 1 $$ 即 a 和 m 是互质的，否则 a 在模 m 下是没有逆元的。
示例1：求 3 在模 7 下的逆元 b，即找到 b 使得： 3 × b ≡ 1 (mod 7)
gcd(3, 7) = 1， 3 在模 7 下模逆元，依次尝试 b 的值：
3 × 1 = 3，3 ≢ 1 (mod 7)
3 × 2 = 6，6 ≢ 1 (mod 7)
3 × 3 = 9，9 ≢ 1 (mod 7)
3 × 4 = 12，12 ≢ 1 (mod 7)
3 × 5 = 15，15 ≡ 1 (mod 7) ✅
所以，3 在模 7 下的模逆元是 5。
示例2：求 4 在模 8 下的逆元 b，即找到 b 使得： 4 × b ≡ 1 (mod 8)
gcd(4, 8) ≠ 1，不满足互质条件，所以 4 在模 8 下没有模逆元。
mpz 类型是 gmpy2 提供的任意精度整数类型，用于处理超出 Python 原生 int 处理范围的大整数，同时提供更快的数学运算性能。
11、扩展欧几里得算法
扩展欧几里得算法(Extended Euclidean algorithm)(ExGCD) 是欧几里得算法（又叫辗转相除法）的扩展。已知整数 a，b，扩展欧几里得算法可以在求得 a，b 的最大公约数的同时，找到整数 x，y 使它们满足裴蜀等式 $a·x+b·y=gcd(a,b)$。这个等式也被称为贝祖等式或贝祖定理。
在欧几里得算法中，我们仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到裴蜀等式中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。
扩展欧几里得算法可以用来计算模逆元，而计算模逆元是RSA加密算法中生成公钥、私钥的必要步骤。
求解模逆元原理：
对于整数a，b，如果它们互质，即 $gcd(a,b)=1$，如果存在一个整数 x，使得$ax ≡ 1\ (mod\ b)$，那么这个 x 就是 a 在模 b 下的逆元。
贝祖定理告诉我们：
对于任意整数 a, b，如果它们互质，即：$gcd(a,b) = 1$ ，那么根据 贝祖定理$ax + by = gcd(a,b)$，一定存在整数 x, y，使得：$ax + by = 1$ 。
这个方程是 整数等式，而我们希望从中得到 模运算 下的等式，所以要对等式的两边同时取模 b 得到同余关系。 $$ (ax + by)\ mod\ b ≡ 1\ (mod\ b) $$ 分解公式 $(ax + by)\ mod\ b ≡ 1\ (mod\ b)$：
$$ (ax\ mod\ b) + (by\ mod\ b) ≡ 1\ (mod\ b) $$ 第二项 $ (by\ mod\ b)$，这里的 by 是 b 的整数倍(y 是整数)，因为任何整数倍的 b 取模都是0($by ≡ 0\ mod\ b$)，带入化简。
$$ (ax\ mod\ b) + 0 ≡ 1\ (mod\ b) $$
$$ ax\ mod\ b ≡ 1\ (mod\ b) $$
$$ ax ≡ 1\ (mod\ b) $$
这正是模逆元的定义，这说明 x 就是 a 在模 b 下的模逆元。
注意： $ax\ mod\ b ≡ 1\ (mod\ b)$ 与 $ax ≡ 1\ (mod\ b)$ 这两种写法是等价的，但它们的表达方式略有不同。
ax mod b ≡ 1 (mod b)：
这里的 ax mod b 表示 ax 除以 b 后的余数， ≡ 1 (mod b) 表示这个余数等于1。
因此，ax mod b ≡ 1 (mod b) 的意思是：ax 除以 b 的余数是1。
ax ≡ 1 (mod b) ：
这是同余式的标准写法。它表示 ax 和 1 在模 b 下是同余的，即 ax 除以 b 的余数等于 1。
换句话说，ax – 1 是 b 的倍数。
求解模逆元示例：
已知整数 a = 3，b = 7，求 a 在模 b 下的模逆元？
求 a 在模 b 下的模逆元，根据模逆元定义 $a × b ≡ 1\ (mod\ m)$ ，求 a 在模 b 下的模逆元，即求 $ax ≡ 1\ (mod\ b)$ 的模逆元x，即求满足以下同余方程的整数x：$3x ≡ 1\ (mod\ 7)$
首先，确保 a 和 b 互质。
>>> gmpy2.gcd(3, 7)
>>> mpz(1)
接着，使用扩展欧几里得算法求解贝祖等式。
根据 a = 3，b = 7，gcd(a, b) = 1，ax + by = gcd(a, b)，故要求解 3x + 7y = 1。
第一步：普通欧几里得算法(计算最大公因数)
在计算 gcd(3,7) 时，a = 3，b = 7。因为欧几里得算法要求第一个参数比第二个参数大，所以我们先交换顺序计算：gcd(7, 3)
gcd(7, 3) = gcd(3, 7 mod 3) = gcd(3, 1)
7 ÷ 3 = 2 余 1 即： 7 = 3 × 2 + 1
gcd(3, 1) = gcd(1, 3 mod 1) = gcd(1, 0)
3 ÷ 1 = 3 余 0 即： 3 = 3 × 1 + 0
所以 gcd(3, 7) = 1，所以贝祖等式有整数解。
第二步：逆向回溯求解x，y (要求解 3x + 7y = 1)
我们需要把最大公因数 1 表示成 3 和 7 的线性组合：
因为 7 = 3 × 2 + 1
所以 1 = 7－3 × 2
所以 1 = 7－2 × 3
所以 1 = 1 × 7 + (-2) × 3
所以 1 = 3 × (-2) + 7 × 1
因此，x = -2，y = 1。
第三步：取模调整
由于模逆元要求的是正整数解，我们需要把 x = -2 转换成模 7 下的最小正整数：
x′ = (-2) + 7 = 5
所以模逆元就是x = 5。
第四步：结果验证
前面提到求满足以下同余方程的整数x：$$3x ≡ 1\ (mod\ 7)$$
带入 x = 5 验证，3 × 5 = 15 ≡ 1 (mod 7)
因为 15 ÷ 7 = 2 余 1，所以 5 确实是 3 在模 7 下的模逆元。
最终，求得模逆元为：5。
12、欧几里得算法与扩展欧几里得算法(Python版)
欧几里得算法与扩展欧几里得算法Python代码实现：
一般实际使用时，我们可以直接使用 gmpy2 模块提供的对应函数。
三、RSA概述
RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。
四、RSA基本原理
RSA 算法的核心思想是利用两个大素数的乘积生成公钥和私钥。其数学基础依赖于 模幂运算 和 整数因子分解困难性。
（1）选取两个大素数 p 和 q ，通常选取 1024-bit、2048-bit 或更大的素数。
（2）计算它们的乘积：$n = p × q$（n被称为模数(modulus)，其长度决定了密钥的强度）
（3）计算 n 的欧拉函数 $φ(n)$ ：$φ(n) = (p − 1)(q − 1)$
（4）选择一个公开的加密指数 e ：要求 $1 < e < φ(n)$ 且 $gcd(e,\ φ(n))=1$ ，即 e 与 $φ(n)$ 互质。e常用值为65537。
（5）计算解密指数 d ：d 是 e 关于 φ(n) 的模逆元，$d ≡ e^{-1} (mod\ φ(n))$ ，也就是说：$e × d ≡ 1 (mod \ φ(n)) $，通过扩展欧几里得算法可求出 d 的值。
（6）最后得到公钥和私钥。公钥 (Public Key)：(n,e)，公开用于加密。 私钥 (Private Key)： (n,d)，必须保密，用于解密。
注意：1024-bit就是1024位，就对应实际位数吗？比如123456就是6位？
在计算机中，bit（比特）表示二进制的位数。1024-bit 意味着这个数在 二进制 下由 1024 位 组成。
以二进制表示，它可能是：101101001011...（共 1024 位）。
转换为十进制后，通常是 309 位到 310 位左右 的超大整数，例如：
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
上述过程简化下：
消息加密：$m^e $ 除以 n 求余数即为 c(密文) $$ c ≡ m^{e}(mod \ n) $$ 消息解密：$c^d$ 除以 n 求余数即为 m(明文) $$ m ≡ c^{d} (mod \ n) $$
RSA算法题目1
按照RSA算法，若选取两奇数 p = 5，q = 3，加密指数 e = 7，则私钥指数 d 的值为？
由 p = 5，q = 3，e = 7，得：$n = p × q = 15$，$φ(n) = (p − 1)(q − 1) = 8$
由 $e × d ≡ 1\ (mod \ φ(n))$ 得：$7×d ≡ 1\ (mod \ 8)$
即求解 7 在模 8 下的模逆元 d。
gmpy2中的 gcdext 函数可以求解模逆元，但是存在求出负数的情况，需要我们手动将其转换到对应的模数下面。所以，一般我们在RSA算法中求解模逆元 d 时，会直接使用 gmpy2 的 invert 函数。
RSA算法题目2
看看题目名"VeryEasyRSA"，按道理说应该不难，这是我们就要借用"Python"来帮我们解题了。
解题脚本如下：
|
|
或者
|
|
上面的两种解法只是调用的模块不同，但计算效果是一样的，后面的题目中也会经常使用这些模块，具体想用哪个模块看自己的心情就好。不过建议使用gmpy2模块，该模块的功能更强大。
四、SageMath的安装
SageMath 是在GPL协议下发布的开源数学软件，并且整合了许多已有的开源软件包到一个基于Python的统一界面下。其目标是创造一个Magma，Maple，Mathematica和Matlab的开源替代品。
SageMath 包含了从线性代数、微积分，到密码学、数值计算、组合数学、群论、图论、数论等各种初高等数学的计算功能。
SageMath 的功能十分强大，现在很多CTF比赛的密码学题目都是能用Sage去求解的。建议大家花一部分时间去学习下。
(1)Linux系统安装SageMath
Ubuntu22.04下通过apt包管理器进行安装：
|
|
需要注意的是，不同的Linux发行版，包管理器中的SageMath版本是不一样的，具体的Linux发行版对应的SageMath的版本可通过该链接进行查看(https://repology.org/project/sagemath/versions)。官网建议，安装的SageMath版本不要低于9.2。
(2)Macos系统安装SageMath
Macos可直接下载相应版本的dmg安装包，双击安装即可。
下载地址：https://github.com/3-manifolds/Sage_macOS/releases
(3)Windows系统安装SageMath
Windows版的话，官方给出的安装方法是通过WSL子系统的方式进行安装。Windows Subsystem for Linux(WSL)本质的话就是在Windows上安装一个Linux环境。装好Linux环境后，再和上面的示例一样，使用包管理器安装SageMath就可以了。
各版本的安装可参考官网：https://doc.sagemath.org/html/en/installation/index.html
通过上面任何一种方式安装完SageMath后，都可在命令行中输入sage打开SageMath。
如果觉得安装麻烦的话，可以使用在线的sage：
Sage Cell Serversagecell.sagemath.org/
个人推荐使用本地安装的，毕竟这样没了网络也可用。
五、SageMath的使用
因为SageMath的功能太过强大，详细的使用方法请参考：
这里仅针对上面的使用教程翻译整理了一小部分，部分示例进行了修改，以便更通俗的去理解。(以后可能会不定期更新这部分)。
(1)赋值运算、关系运算、算数运算
Sage 使用=进行赋值操作。
|
|
Sage 使用==、<=、>=、<、和>进行关系的比较运算。示例如下：
|
|
Sage 提供所有基本的数学运算：
|
|
Sage 还提供了许多熟悉的数学函数。下面是几个例子：
|
|
如上面的最后一个示例所示，一些数学表达式会直接返回"精确值"，而不是数值"近似值"。如果需要要获得计算结果的数值近似值，需要使用函数N或方法n(函数N和方法n是指numerical_approx)。
|
|
函数N和方法n都支持可选参数digits和prec。
①digits参数是指控制数值的精度，它指定了所需的十进制有效数字的位数。例如，如果digits = 3，则函数将返回 3 位十进制有效数字位数的数值结果。
②prec参数也是控制数值精度的一个参数，但与digits参数不同的是，它指定了所需的二进制有效数字的位数。例如，如果prec = 11，则函数将返回 11 位二进制有效数字位数的数值结果。
二进制有效数字位数基于2的幂，而十进制有效数字位数基于10的幂。
二进制有效数字位数和十进制有效数字位数之间如何转换呢？
10个二进制有效数字位数最多可以表示1024(2^10)个不同的值，3个十进制有效数字位数最多可以表示1000(10^3)个不同的值，10个二进制有效数字位数和3个十进制有效数字位数能表示的数值是差不多的。
在十进制和二进制之间的转换中，每3.32个二进制数字位相当于约1个十进制数字位。因此，如果我们想要通过保留 n 位二进制数字来近似保留 m 位十进制数字，可以使用下面公式：
$n ≈ 3.32m$
例如，如果希望保留 3 位十进制有效数字的位数，我们可以使用prec = 10(3.32*3=9.95)来表示。由于浮点数的存储方式，不是所有的二进制数字都是等价于有效数字的。在实际测试中，可以发现prec = 10只能表示出 2 位十进制有效数字位数，所以，必须再大一点，使用prec = 11才能表示出 3 位十进有效数字位数。
同理，如果需要根据二进制有效位数求解下大概能表示的十进制有效位数的话，可以使用下面公式：
$ m≈\cfrac{n}{3.32} $
例如，当prec = 11时，我们可以计算出该方式可以表示出大概 3 个有效十进制数字位数($113.32≈3.31$)。
在SageMath中，digits和prec参数通常是用来控制RealNumber对象的精度的。如果表达式中包含其他类型的对象，如复数、矩阵等，那么这些对象的精度可能不受digits和prec参数的影响。
|
|
在 Python 中，变量是动态类型的，它们可以引用任何 Python 对象，并且可以在运行时更改其引用的对象类型。这意味着，变量的类型是在运行时动态推断的。示例如下：
|
|
相反，静态类型的 C 编程语言在编译时会要求变量被声明为特定类型，并且只能在其范围内保存相应类型的值。这意味着，变量类型在编译时是静态确定的。
(2)获取帮助
SageMath 内置丰富的文档，可通过键入函数名称或常量＋问号的方式来访问：
|
|
Sage 还提供Tab 完成的自动补全功能：键入函数的前几个字母，然后按 Tab 键。例如，如果你输入"ta"紧接着按"Tab按键"，Sage 将打印 tachyon、tan、tanh、taylor。这提供了一种在 Sage 中查找函数名称和其他结构的好方法。
(3)函数、缩进、计数
要在 SageMath 中定义一个新函数，需要使用 def 命令并在变量名称列表后加上一个冒号。例如：
|
|
在 Python 中，代码块不像许多其他语言那样由大括号或开始和结束块表示。相反，代码块由缩进表示，缩进必须完全匹配。例如：
|
|
在大多数情况下，一行以换行结尾，行尾不需要分号。但是，你可以将多个语句放在一行，用分号分隔：
|
|
SageMath 中最基本的数据结构是列表。例如，使用范围，以下命令创建一个列表：
|
|
这是一个更复杂的列表：
|
|
与许多编程语言一样，列表索引是从 0 开始的。
|
|
使用len(v)可以获取列表 v 的长度，使用v.append(obj)将新对象追加到 v 的末尾，使用 del v[i] 可以删除 v 的第 i 个条目：
|
|
另一个重要的数据结构是字典。字典和列表很相似，除了它可以用几乎任何对象进行索引(索引必须是不可变的)：
|
|
你还可以使用类定义新的数据类型。用类封装数学对象是一种强大的技术，可以帮助简化和组织你的Sage程序。下面，我们定义了一个类，它表示最多为 n 的偶数正整数列表。
|
|
Evens对象创建时会调用__init__方法初始化对象。__repr__方法打印出对象。我们在__init__方法的第二行调用列表构造方法。
我们创建一个类 Evens 的对象，如下所示：
|
|
e 会使用我们定义的__repr__方法进行打印。要查看底层数字列表，请使用列表函数：
|
|
我们还可以访问 n 属性或将 e 视为列表。
|
|
(4)基本代数和微积分
…
…