字符、字节与数字的相互转换

在诸如 RSA 的现代密码系统中，加密和解密的底层都是纯粹的数学运算。这就要求我们在加密前，必须将由字符组成的“文本消息”转换为“数字”；解密后，再将“数字”还原回“文本消息”。

以下是实现这些转换的核心流程与 Python 原生/第三方方法总结：

1. 基础转换：字符 $\leftrightarrow$ ASCII 序数

用于单个字符与其对应的 ASCII 数值之间的转换。

chr(整数)：ASCII 序数 $\rightarrow$ 字符。
- _示例_：chr(65) 结果为 'A'
ord(字符)：字符 $\rightarrow$ ASCII 序数（作用与 chr() 相反）。
- _示例_：ord('A') 结果为 65

2. 进阶转换：字节流 $\leftrightarrow$ 十六进制 (Hex)

在密码学中，数据经常以十六进制字符串或原始字节流（Bytes）的形式呈现。

bytes.fromhex('十六进制字符串')：十六进制 $\rightarrow$ 字节流。
- _示例_：bytes.fromhex('48656c6c6f') 结果为 b'Hello'
字节变量.hex()：字节流 $\rightarrow$ 十六进制（这是字节对象自带的实例方法）。
- _示例_：b'Hello'.hex() 结果为 '48656c6c6f'

3. 密码学核心链路：消息如何变成大整数？

为了满足数学运算的需求，标准的转换流程通常如下：

提取序数字节：将文本消息拆解为对应的字节数值。
转换为十六进制：将这些数值转化为十六进制表示。
拼接：将所有十六进制数值无缝连接在一起。
视为大数字：这个长长的十六进制串，既可以直接作为 Base-16（十六进制）数字参与运算，也可以转换为 Base-10（十进制）大整数。

4. 终极武器：PyCryptodome 库

为了省去手动拼接十六进制的繁琐步骤，Python 提供了强大的密码学专用库，可以一步到位实现字节流与大整数的互转。

环境准备：
- 安装：pip install pycryptodome
- 导入：from Crypto.Util.number import *
核心方法：
- bytes_to_long(字节流)：字节流 $\rightarrow$ 大整数（正向过程，加密前准备）。
- long_to_bytes(大整数)：大整数 $\rightarrow$ 字节流（逆向过程，解密后还原）。

XOR (异或运算) 及其核心性质

1. 核心概念与真值表

XOR（Exclusive OR）是一种按位运算符（Bitwise Operator）。它的核心逻辑非常简单：相同为 0，不同为 1。

符号表示：在密码学教材和数学公式中通常记作 $\oplus$；在编程语言和 CTF 题目中通常使用脱字符 ^。

XOR 真值表：

A	B	输出 (A $\oplus$ B)
0	0	0
0	1	1
1	0	1
1	1	0

XOR logic gate truth table, AI generated

2. 多字节与数据类型的 XOR

在实际运算中，XOR 并不局限于单个比特，它可以扩展到更长的数据：

二进制数：逐位进行运算。例如：$0110 \oplus 1010 = 1100$。
整数 (Integers)：在底层会先将十进制整数转换为二进制，再逐位异或。
字符串 (Strings)：先提取每个字符的 Unicode/ASCII 整数值，然后再进行异或（如上一题中将 label 的每个字符与 13 异或）。
🛠️ 必备工具：Python 的 pwntools 库提供了一个极其方便的 xor() 函数，可以直接对不同类型和长度的数据（如字节流、字符串）进行批量异或。

3. XOR 的四大核心数学性质 (解密关键)

在破解密码系统（尤其是块密码 Block Ciphers）时，理解并灵活运用以下四个性质是解开加密链条的关键：

交换律 (Commutative): 运算顺序不影响结果。
- $A \oplus B = B \oplus A$
结合律 (Associative): 链式运算可以无视括号顺序。
- $A \oplus (B \oplus C) = (A \oplus B) \oplus C$
单位元 (Identity): 任何数与 0 异或，结果不变（相当于“无操作”）。
- $A \oplus 0 = A$
自逆性 / 归零律 (Self-Inverse): 这是最重要的性质！ 任何数与自身异或，结果必定为 0。这也意味着 XOR 两次相同的密钥就能还原数据。
- $A \oplus A = 0$

4. 使用PWNTOOLS进行加密

Pwntools 的 xor() 函数是一个非常强大且灵活的工具，==专门用于在 CTF 比赛中进行字节级 XOR（异或）操作==。它支持字符串、字节串、整数或列表的异或，可以自动处理不同长度的密钥，是处理加密或混淆数据的理想工具。

常用方法与示例：

单字节/固定密钥异或：

from pwn import xor
# 字符与单字节异或
print(xor(b'hello', 0x55)) 
# 字符串与字符串异或
print(xor(b'hello', b'world'))

自动循环密钥：
如果密钥比数据短，xor() 会自动重复该密钥。
1
2
# key 'AB' 会被当作 'ABABAB'
print(xor(b'123456', b'AB'))

处理整数：

1 2	# 整数与字节串异或 print(xor(0x1234, b'\x01\x02'))

总结：

功能： 异或操作。
输入： 支持 bytes, str, int, list 等。
输出： 通常为 bytes 类型。
优点： 简洁，自动处理数据与密钥长度不一致的情况。

5.进阶：单字节爆破

# 1. 题目给定的十六进制密文  
hex_string = "73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d"  
  
# 2. 将十六进制转换为可操作的字节流 (Bytes)cipher_bytes = bytes.fromhex(hex_string)  
  
# 3. 开始爆破：遍历单字节的所有可能性 (0 到 255)for key in range(256):  
    decrypted_text = ""  
  
    # 将密文的每一个字节都与当前的 key 进行异或，并转回字符  
    for byte in cipher_bytes:  
        decrypted_text += chr(byte ^ key)  
  
    # 4. 自动化筛选：我们已知正确的明文必然包含 "crypto{"if "crypto{" in decrypted_text:  
        print(f"[+] 爆破成功！")  
        print(f" -> 找到正确密钥: {key} (十六进制: {hex(key)})")  
        print(f" -> 最终 Flag: {decrypted_text}")  
        break  # 找到正确答案后，直接终止循环

转轮密钥

key[i % len(key)] 的核心逻辑被称为 轮转密钥 或 循环密钥 机制。它的作用很简单：当需要加密的“明文”长度超过“密钥”长度时，让密钥首尾相连、循环往复地去匹配明文。

最大公约数

核心概念

最大公约数 (GCD / Highest Common Factor) 是指能同时整除两个正整数 $a$ 和 $b$ 的最大整数。

示例计算：
- 对于 $a = 12, b = 8$：
  - $12$ 的约数：${1, 2, 3, 4, 6, 12}$
  - $8$ 的约数：${1, 2, 4, 8}$
  - 对比可知最大公共约数为 $4$，因此 $\gcd(12, 8) = 4$。

互质 (Coprime)

定义：如果两个整数 $a, b$ 满足 $\gcd(a, b) = 1$，则称 $a$ 和 $b$ 是互质的（Coprime）。
- 例如：$a=11, b=17$ 均为素数（质数），除数只有 1 和自身，故 $\gcd(11,17)=1$，它们互质。
素数与互质的性质：
1. 如果 $a$ 和 $b$ 都是素数，它们必定互质。
2. 如果 $a$ 是素数，且 $b < a$，那么 $a$ 和 $b$ 必定互质。

思考题解答

题目提问： 考虑 $a$ 是素数且 $b > a$ 的情况，为什么它们不一定互质？

解答：因为 $b$ 完全有可能是 $a$ 的倍数。

例如：假设素数 $a = 3$，而 $b = 9$（满足 $b > a$）。此时 $\gcd(3, 9) = 3$。因为最大公约数不是 1，所以这种情况下它们不互质。

算法实现：欧几里得算法

在密码学和 CTF 中，处理的数字通常非常大，不能用穷举约数的方法。题目推荐使用欧几里得算法（辗转相除法）。

原理：两个正整数 $a$ 和 $b$ ($a>b$) 的最大公约数等于 $a$ 除以 $b$ 的余数 $c$ 和 $b$ 之间的最大公约数。即：$\gcd(a, b) = \gcd(b, a \bmod b)$。

Python 脚本实现

def gcd(a, b):
    # 当余数 b 为 0 时，a 就是最大公约数
    while b != 0:
        a, b = b, a % b
    return a

# 测试题目给的例子
print(f"gcd(12, 8) = {gcd(12, 8)}")

扩展欧几里得算法

核心概念：贝祖等式

普通的 GCD 算法只告诉我们两个数的最大公约数是多少。但扩展欧几里得算法不仅能求出最大公约数，还能同时找到两个整数 $u$ 和 $v$，使得它们满足以下线性组合方程（即贝祖等式）：

$a \cdot u + b \cdot v = \gcd(a, b)$

在实际的密码学计算中，我们往往并不关心最大公约数本身（因为它通常是 1），我们真正渴求的是那两个系数 $u$ 和 $v$。

思考题解答

题目提问：已知 $p, q$ 都是素数（prime），你认为 $\gcd(p, q)$ 应该是多少？

解答：结果一定是 1。因为不同的素数之间没有任何大于 1 的公共约数，它们必然是互质的。

因此，对于这道题，我们要解的终极方程其实是：

$26513 \cdot u + 32321 \cdot v = 1$

为何它是解密 RSA 的关键？

题目中有一句非常关键的提示：“稍后，当我们学习解密 RSA 密文时，我们将需要这个算法来计算公钥指数的模逆元。”

在 RSA 加密中，为了求出私钥 $d$，我们需要解一个同余方程：$e \cdot d \equiv 1 \pmod{\phi}$。

这个方程在数学上等价于：$e \cdot d + \phi \cdot k = 1$。

仔细对比一下贝祖等式 $a \cdot u + b \cdot v = 1$：

$a$ 就是公钥 $e$
$b$ 就是 $\phi$
求出来的系数 $u$ 就是我们梦寐以求的 RSA 私钥 $d$！

算法实现与挑战解答

为了在 Python 中实现 eGCD，我们在原本 a, b = b, a % b 的基础上，需要额外跟踪商（quotient），从而逆向推导出 $u$ 和 $v$。

Python 脚本实现

def extended_gcd(a, b):
    # 初始化系数
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r != 0:
        # 计算商
        quotient = old_r // r
        
        # 核心逻辑：和普通的 gcd 一样更新余数，但同时更新系数
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    # old_r 是最大公约数
    # old_s 和 old_t 就是我们要求的 u 和 v
    return old_r, old_s, old_t

if __name__ == '__main__':
    p = 26513
    q = 32321
    
    gcd_val, u, v = extended_gcd(p, q)
    
    print(f"最大公约数 GCD: {gcd_val}")
    print(f"系数 u: {u}")
    print(f"系数 v: {v}")
    
    # 题目要求提交 u 和 v 中较小的那个数字
    flag = min(u, v)
    print(f"Flag: {flag}")

这是一份为你整理的关于模运算（Modular Arithmetic）的 Obsidian 笔记，你可以直接复制到你的笔记库中。

模运算

基础

核心概念：时钟算术

模运算 是现代密码学（如 RSA、ECC 椭圆曲线加密）的绝对基石。为了防止数字在加密计算过程中无限膨胀，同时利用“单向函数”的数学难度，密码学计算几乎全部都在一个特定的有限域（模数域）内进行。

通俗理解：想象一个 12 小时制的表盘。如果现在是下午 4 点，再过 9 个小时，时间不是 13 点，而是凌晨 1 点。
- 数学表达：$4 + 9 \equiv 1 \pmod{12}$
专业定义：同余理论。如果两个整数 $a$ 和 $b$ 满足 $a$ 除以 $m$ 的余数等于 $b$ 除以 $m$ 的余数，我们就说 $a$ 和 $b$ 在模 $m$ 下同余，记作 $a \equiv b \pmod m$。
在编程中的映射：同余在代码层面等价于求余数操作。即 a % m == b。

思考与应用

在渗透测试或 CTF 实战中，无论是处理古老的凯撒密码、维吉尼亚密码，还是现代的高级公钥密码体制，底层的核心轮转机制都是基于 %（取模运算）来实现数据在指定范围内的循环滚动。

挑战解答

题目要求：计算以下两个同余式中的整数 $x$ 和 $y$，并提交两者中较小的那个数字。

计算 $x$：
- 方程：$11 \equiv x \pmod 6$
- 逻辑：$11 \div 6 = 1$，余数为 $5$。
- 结果：$x = 5$
计算 $y$：
- 方程：$8146798528947 \equiv y \pmod{17}$
- 逻辑：通过大数取模运算计算余数。
- 结果：$y = 4$

最终答案：
题目要求提交 $x$ 和 $y$ 中较小的整数。因为 $4 < 5$，所以最终的 Flag 为：
4

算法实现：Python 求模运算

def solve_mod_arithmetic():
    # 1. 计算 11 mod 6
    x = 11 % 6
    print(f"x 的值为: {x}")
    
    # 2. 计算大数 mod 17
    y = 8146798528947 % 17
    print(f"y 的值为: {y}")
    
    # 3. 获取两者中较小的值作为 Flag
    flag = min(x, y)
    print(f"最终提交的 Flag: {flag}")

if __name__ == '__main__':
    solve_mod_arithmetic()

python模块求模

1. 模幂运算：原生 Python 的 `pow()`

在 RSA 等加密中，经常需要计算 $a^b \pmod m$ 这样庞大的数字。千万不要写成 (a ** b) % m，这会导致内存爆炸和极长的计算时间。

最简便写法： 使用原生带有三个参数的 pow()。

a = 11
b = 3
m = 6

# 极其高效地计算 (11^3) mod 6
result = pow(a, b, m) 
print(result)

2. 求模逆元：pycryptodome 的 `inverse()`

你刚刚学习了用扩展欧几里得算法（eGCD）去手搓求 $u$ 和 $v$。在实际解题中，每次都自己写那个 while 循环太麻烦了。pycryptodome 直接把它封装成了一行代码。

在求 $e \cdot d \equiv 1 \pmod{\phi}$（即求 $e$ 在模 $\phi$ 下的逆元 $d$）时：

最简便写法：

from Crypto.Util.number import inverse

e = 65537
phi = 32321 # 假设的 phi 值

# 直接秒算模逆元（也就是 RSA 的私钥 d）
d = inverse(e, phi) 
print(f"算出的私钥 d 为: {d}")

注：Python 3.8 以上版本，原生的 pow(e, -1, phi) 也能直接求模逆元，效果和 inverse 一样。

模逆元与费马小定理

核心概念：有限域中的“分数”

在普通的数学运算中，如果 $3 \cdot d = 1$，那么 $d = \frac{1}{3}$，此时 $\frac{1}{3}$ 就是 $3$ 的乘法逆元。

但在模运算（有限域）的世界里，不存在小数和分数，只有整数。

定义：在模 $p$ 的环境下，如果找一个整数 $d$，使得它与 $a$ 相乘后除以 $p$ 的余数为 1，那么 $d$ 就是 $a$ 的模逆元。

数学表达：$a \cdot d \equiv 1 \pmod p$
通俗理解：在整数里找一个充当“分数/倒数”的替身。

_示例_：求 $3$ 在模 $13$ 下的逆元。

因为 $3 \times 9 = 27$，而 $27 = 13 \times 2 + 1$（即 $27 \equiv 1 \pmod{13}$）。

所以，在模 $13$ 的世界里，$3$ 的逆元就是 $9$。

关键定理：费马小定理

在处理非常大的数字时，不能靠口算或暴力穷举，需要借助数论定理。

定理内容：如果 $p$ 是一个素数，且 $a$ 不是 $p$ 的倍数，那么：
$a^{p-1} \equiv 1 \pmod p$
推导逆元公式：

将上式拆解为：$a \cdot a^{p-2} \equiv 1 \pmod p$
对比逆元的定义式 $a \cdot d \equiv 1 \pmod p$，可以直接得出求逆元的绝招：
逆元 $d = a^{p-2} \pmod p$

挑战解答 (Challenge Solution)

题目要求：计算 $d = 3^{-1}$，使得 $3 \cdot d \equiv 1 \pmod{13}$。

解题逻辑

这里模数 $13$ 是素数，直接套用费马小定理推导的公式：
$d = 3^{13-2} \pmod{13}$，即求 $3^{11} \pmod{13}$ 的值。

计算得出 $d = 9$。

最终提交答案：

9

算法实现

写法 1：原生模幂运算（适用于模数 $p$ 为素数）

利用费马小定理，结合 Python 极速的原生 pow() 函数：

a = 3
p = 13
# pow(底数, 指数, 模数) -> 计算 a^(p-2) mod p
d = pow(a, p - 2, p) 
print(f"逆元为: {d}")

写法 2：通用求法（适用于任何互质情况，如 RSA）

遇到模数不是素数的情况，直接调用 pycryptodome 库：

from Crypto.Util.number import inverse

a = 3
m = 13
# 底层自动调用扩展欧几里得算法(eGCD)
d = inverse(a, m)
print(f"逆元为: {d}")

二次剩余

核心概念拆解

1. 什么是二次剩余？

在普通的实数世界里，正数可以开平方，负数不能开平方。
在模 $p$ 的有限域世界里，数字同样被分为了两派：

二次剩余：如果存在一个整数 $a$，使得 $a^2 \equiv x \pmod p$，那么 $x$ 就是二次剩余。说白了，就是在这个模环境下，$x$ 能开得出完美的平方根。
二次非剩余：不管你怎么试，都找不到一个 $a$ 的平方模 $p$ 等于它。这就相当于模世界里的“负数”，开不了根号。

2. 核心特性：成双成对的根
就像现实中 $3^2 = 9$，并且 $(-3)^2 = 9$ 一样。题目里也明确提示了：如果 $a^2 = x$，那么 $(-a)^2 = x$。

在模 $p$ 的世界里，负数 $-a$ 其实就等价于 $p - a$。

所以，一旦某个数字有平方根，它必定有两个解，分别是 $a$ 和 $p - a$。

sympy库实现二次剩余

from sympy.ntheory.residue_ntheory import sqrt_mod  
  
p = 29  
# 我们想看看 6 在模 29 下的平方根  
root = sqrt_mod(6, p)  
  
if root:  
    print(f"6 的较小平方根是: {root}")  
    print(f"6 的另一个平方根是: {p - root}")  
else:  
    print("找不到平方根，它是二次非剩余")

勒让德符号与大素数二次剩余求解

核心痛点与解决思路

在模算术中求解二次剩余（即求模平方根 $x^2 \equiv a \pmod p$）时，如果模数 $p$ 是一个极小的素数（如 29），我们可以通过穷举法遍历 $1$ 到 $p-1$ 来寻找答案。

然而，在真实的密码学环境或 CTF 竞赛中，$p$ 往往是一个高达 1024 位或 2048 位的超大素数。此时暴力破解的时间复杂度为 $O(p)$，计算到宇宙毁灭也无法完成。

为了应对超大素数，我们必须将解题过程拆分为两步，并使用数学定理来实现 $O(\log p)$ 级别的极速计算：

第一步（探测）：在不计算平方根的前提下，瞬间判断一个数到底“能不能”开平方。
第二步（提取）：在确认能开平方后，利用特定条件瞬间提取出平方根。

勒让德符号—— 二次剩余探测器

勒让德符号提供了一种极其高效的方法，用于判断一个整数 $a$ 是否是奇素数 $p$ 的二次剩余。它的核心思想基于费马小定理的推论。

符号表示：$(a/p)$ 或 $(a|p)$

计算公式：

$(a/p) \equiv a^{(p-1)/2} \pmod p$

探测器输出的三种状态：

根据欧拉准则（Euler’s criterion），将数字 $a$ 代入上述公式，结果必然且只会是以下三种情况之一：

结果为 $1$：说明 $a$ 是模 $p$ 的二次剩余（Quadratic Residue）。即 $a$ 在模 $p$ 下必然存在平方根。
结果为 $-1$（在模 $p$ 下表现为 $p-1$）：说明 $a$ 不是模 $p$ 的二次剩余（Quadratic Non-Residue）。即 $a$ 在模 $p$ 下绝对无法开平方，属于无解状态。
结果为 $0$：说明 $a \equiv 0 \pmod p$，即 $a$ 是 $p$ 的倍数（在实战中极少考察此种边缘情况）。

数学直觉：

由费马小定理可知 $a^{p-1} \equiv 1 \pmod p$。我们可以将其视为 $(a^{(p-1)/2})^2 \equiv 1 \pmod p$。在模 $p$ 的域中，平方等于 $1$ 的数只有 $1$ 和 $-1$。勒让德符号巧妙地利用了这一点，将所有数字强行划分为“有解(1)”和“无解(-1)”两大阵营。

勒让德符号的重要乘法性质（进阶拓展）：

$\text{二次剩余} \times \text{二次剩余} = \text{二次剩余}$ （即 $1 \times 1 = 1$）
$\text{二次剩余} \times \text{二次非剩余} = \text{二次非剩余}$ （即 $1 \times -1 = -1$）
$\text{二次非剩余} \times \text{二次非剩余} = \text{二次剩余}$ （即 $-1 \times -1 = 1$）

第二步：神级捷径公式 —— 当 $p \equiv 3 \pmod 4$

当我们使用勒让德符号确认了某个数 $a$ 是二次剩余后，接下来就是求出具体的平方根 $x$。

在一般情况下，求大素数模平方根需要使用极其复杂的 Tonelli-Shanks 算法。但如果出题人给定的素数 $p$ 满足特殊条件 $p \equiv 3 \pmod 4$，我们就可以直接使用以下公式秒杀：

$x \equiv a^{(p+1)/4} \pmod p$

(注：求出第一个根 $x$ 后，由于模运算中平方根总是成对出现，第二个根必定为 $p - x$)

为什么探测器与捷径可以完美闭环？（底层代数推导）

这个捷径公式之所以成立，完全是因为它建立在勒让德符号的结果之上。

我们将算出的 $x$ 进行平方验证：

$x^2 \equiv (a^{(p+1)/4})^2 \equiv a^{(p+1)/2} \pmod p$

将指数拆分为 $\frac{p-1}{2} + 1$：

$x^2 \equiv a^{(p-1)/2} \cdot a^1 \pmod p$

关键点：由于我们在第一步已经用勒让德符号确认了 $a$ 是二次剩余，所以 $a^{(p-1)/2} \pmod p$ 的值必然等于 1。

将其代入式中：

$x^2 \equiv 1 \cdot a \equiv a \pmod p$

完美证明了公式得出的 $x$ 就是我们要找的平方根。

字符、字节与数字的相互转换

1. 基础转换：字符 $\leftrightarrow$ ASCII 序数

2. 进阶转换：字节流 $\leftrightarrow$ 十六进制 (Hex)

3. 密码学核心链路：消息如何变成大整数？

4. 终极武器：PyCryptodome 库

XOR (异或运算) 及其核心性质

1. 核心概念与真值表

2. 多字节与数据类型的 XOR

3. XOR 的四大核心数学性质 (解密关键)

4. 使用PWNTOOLS进行加密

5.进阶：单字节爆破

转轮密钥

最大公约数

核心概念

互质 (Coprime)

思考题解答

算法实现：欧几里得算法

Python 脚本实现

扩展欧几里得算法

核心概念：贝祖等式

思考题解答

为何它是解密 RSA 的关键？

算法实现与挑战解答

Python 脚本实现

模运算

基础

核心概念：时钟算术

思考与应用

挑战解答

算法实现：Python 求模运算

python模块求模

1. 模幂运算：原生 Python 的 pow()

2. 求模逆元：pycryptodome 的 inverse()

模逆元与费马小定理

核心概念：有限域中的“分数”

关键定理：费马小定理

挑战解答 (Challenge Solution)

算法实现

二次剩余

核心概念拆解

sympy库实现二次剩余

勒让德符号与大素数二次剩余求解

核心痛点与解决思路

勒让德符号—— 二次剩余探测器

探测器输出的三种状态：

勒让德符号的重要乘法性质（进阶拓展）：

第二步：神级捷径公式 —— 当 $p \equiv 3 \pmod 4$

为什么探测器与捷径可以完美闭环？（底层代数推导）

1. 模幂运算：原生 Python 的 `pow()`

2. 求模逆元：pycryptodome 的 `inverse()`