RSA加解密

1.getPrime(X) 是 PyCryptodome 库中 _Crypto.Util.number_模块提供的一个函数，用于生成一个X位****的随机素数。

2.bytes_to_long 是密码学编程中常用的一个函数，它的作用是将字节串（bytes）转换为一个长整数（long integer）。

如：

取一个字节串（比如 b'flag{abc123}'）。
将这个字节串看作一个非常大的、以256为基数的数字。（因为一个字节byte有8位bits，可以表示 2^8 = 256 种不同的值，即0到255）
将这个“数字”转换成我们数学中常用的十进制整数。

举个例子：
假设我们有一个很短的字节串 b'\x01\x02'。

第一个字节是 \x01，其十进制值是 1。
第二个字节是 \x02，其十进制值是 2。

转换过程就像我们计算一个两位数：
这个数字 = (第一个字节的值) * (256)^1 + (第二个字节的值) * (256)^0
b'\x01\x02' 转换为整数就是 1 * 256 + 2 * 1 = 258。

b'flag{******}' 要长得多，所以转换后会得到一个非常非常大的整数。

为什么在RSA中需要这么做？

RSA加密算法的核心数学操作（如 pow(m, e, n)）是针对整数进行的。它无法直接处理字符串。

所以，加密的标准步骤是：

将明文消息（字符串）转换为字节串。b'flag{...}' 就是这个字节串。
使用 bytes_to_long 将这个字节串转换为一个大的整数 m。
对整数 m 进行加密操作 c = m^e mod n，得到密文整数 c。

解密则是相反的过程：

对密文整数 c 进行解密操作 m = c^d mod n，得到原始的明文的整数形式 m。
使用 long_to_bytes 将这个整数 m 转换回字节串。
将字节串解码，就得到了原始的字符串明文 'flag{...}'。

总结

函数	作用	类比
`bytes_to_long`	将字节串转换为一个大整数	把一句话“翻译”成一个巨大的号码
`long_to_bytes`	将一个大整数转换回字节串	把那个巨大的号码“翻译”回原来那句话

在你提供的代码中：
m = bytes_to_long(b'flag{******}')
这行代码的目的就是为了得到整数 m，以便后续进行 pow(m, e, n) 的加密运算。

3.字符串通过bytes_to_long➡m（明文）

e（加密指数Encryption exponent）通常是一个比较小的质数（如 3, 17, 65537）

n：模数（Modulus）。这是公钥的另一部分，它是一个极其巨大的数，由两个或多个大质数相乘得到，即 n = p * q（在标准RSA中）

· mod：取模运算。意思是求 m^e 除以 n 后的余数。因为 m^e 本身可能大得不可思议（远超宇宙原子总数），取模运算可以确保结果 c 是一个小于 n 的数，使其可以被处理和存储。

· c：密文（Ciphertext），即加密后的结果。它看起来就像一个随机的大整数。
直观比喻

想象一下加密就像把一个秘密信息放进一个巨大的、有无数圈的密码转盘里：

m（明文）：你想发送的秘密数字（比如 10）。
e（公钥）：告诉你将转盘顺时针转动多少圈（比如 5 圈）。
n（模数）：转盘上一共有多少格（比如 15 格）。
加密操作 m^e mod n：

· 你先使劲转动转盘：10^5 = 100,000。这相当于转了100,000圈。

· 但转盘只有15格，转再多圈，最终停下来时指针指向的格子只和“总圈数除以15的余数”有关。

· 所以我们计算 100,000 ÷ 15 的余数。15 * 6666 = 99990，100,000 - 99,990 = 10。

· 所以最终指针指向第 10 格。
c（密文）：你告诉别人最终指针指向了 10 这个格子。光看 10 这个结果，没人能猜到你是从 10 开始转了 5 圈到的，还是从其他地方转来的。这就是加密。

为什么这个操作是加密？

这个公式是单向函数：

· 正向计算（加密）很容易：给定 m, e, n，计算机可以很快算出 c。

· 反向计算（解密）极其困难：如果只知道 c, e, n，想倒推出原始的 m 是什么，在数学上被称为“求模的e次根”问题。当 n 非常大（比如2048位）时，即使用世界上最快的计算机，也需要花上亿年的时间来暴力破解。

只有持有私钥 d 的人，才能通过另一个公式 m = c^d mod n 轻松地解密，恢复出原始信息 m。

n = pqr # 由三个质数相乘得到巨大的模数

c = pow(m, e, n) # 这就是在计算 c = m^e mod n

print(“c=”, c) # 输出密文

这段代码正是使用公钥 (e, n) 对信息 m（即flag）进行加密，产生了你需要去解密的密文 c。

部分含义角色

c = m^e mod n RSA加密核心公式用公钥把明文变成密文

m = c^d mod n RSA解密核心公式用私钥把密文变回明文

n 模数公钥的另一部分，决定加密强度

**e** = 锁门的方法（公开）加密指数公钥的一部分
**d** = 开门的钥匙（私有）d = pow(e, -1, phi_n)
**c** = 锁好的门 c 密文加密后的结果，看起来像乱码
**m** = 门内的东西 m 明文的数字形式想要保护的信息

只有用正确的钥匙 d 才能打开锁着的门 c 得到里面的东西 m。

在RSA加解密的过程中，公钥与私钥可以分别用做加密与解密。使用公钥加密的信息，可以用私钥解密。使用私钥加密的信息，可以用公钥解密。加解密的数学过程是相同的。

b'flag{...}' 
    ↓ bytes_to_long()
m (明文数字) → 被RSA加密 → c (密文)
    ↑ long_to_bytes()        ↓ 给你解密
b'flag{...}' ← 你的目标   c (你拿到的)

gcd 是 最大公约数（Greatest Common Divisor）gcd(a, b) = 能同时整除 a 和 b 的最大正整数。

在RSA的欧拉定理中：

如果 gcd(m, n) = 1，那么 m^φ(n) ≡ 1 mod n

如果 gcd(m, n) ≠ 1，欧拉定理不直接适用，需要中国剩余定理等其他方法。

由于模数是 2 的幂，我们可以使用 Pohlig-Hellman 算法，这比 Pollard Rho 更高效

Pollard Rho 算法

使用 sympy 的 discrete_log 或 gmpy2 求解 e，高效且省内存。
正确解方程组得到 p、q、r，验证是否为质数。
计算 n、phi (n)、d，解密 c 得到 m，转换为 flag。

为什么在RSA中需要这么做？

总结

Steam好友代码