1. 项目缘起为什么要在Python里“重造轮子”你可能在不少密码学教材里见过那些优雅的数学公式和定理比如欧几里得算法、模幂运算、求乘法逆元。看书的时候觉得逻辑清晰了然于胸可真要自己动手写代码去实现一个简单的RSA加密或者理解椭圆曲线签名ECDSA里那个“求模逆”的步骤时是不是感觉隔了一层纱公式是公式代码是代码中间好像缺了点什么。这就是我动手做这个项目的初衷——通过Python代码亲手把密码学里那些“黑盒”运算拆开看看里面每一个齿轮是怎么转的。很多人学密码学容易陷入两个极端要么沉迷于数学理论证明离实际应用太远要么直接调用cryptography这类成熟库的encrypt()、sign()函数对底层发生了什么一无所知。前者让人难以落地后者则会在遇到诡异bug时束手无策比如为什么我的密钥对无法生成为什么签名验证总是不通过。这个项目就是想填平这道沟壑。我们不生产新的密码算法我们只是核心运算的“搬运工”和“解剖师”。通过Python实现它们你会对“模运算下为什么需要乘法逆元”、“大素数如何检测”、“公钥密码体系如何依赖数论难题”有肌肉记忆般的理解。从相关热搜词也能看出大家的痛点模运算、乘法逆元、110101000模2除1001运算过程这看起来像是一个手算模2除法的具体例子。这说明很多朋友正在从理论转向实践在动手过程中遇到了具体的计算障碍。我的目标就是让这些抽象概念变成你屏幕上可运行、可调试、可修改的一行行Python代码。注意本项目所有代码均为教学演示用途旨在揭示原理。实际生产环境中请务必使用像cryptography、PyCryptodome这样的经过严格审计和测试的成熟密码学库切勿使用自己编写的密码学代码处理真实敏感数据。2. 环境准备与基础工具打造你的密码学“手术台”工欲善其事必先利其器。我们不需要复杂的IDE一个能运行Python的环境和几个基础库就足够了。但这里面的几个选择值得说道说道。2.1 Python环境与核心库选择首先确保你安装了Python 3.7或以上版本。密码学运算尤其是涉及大整数的在Python 3中有着天然的优势因为它的整数类型是任意精度的Bignum这意味着你可以直接计算像2**1024这样的天文数字而不会溢出这是C/C/Java等语言需要特殊库才能支持的特性。我们将主要依赖两个库random模块Python标准库用于生成随机数例如在生成大素数或密钥时。但请注意对于密码学级别的随机性random模块是不安全的因为它生成的是伪随机数可能被预测。在我们的教学场景中出于简单和可复现性可以暂时使用它。我会在相关部分明确指出这一点并展示如何替换为密码学安全的随机源如secrets模块。math模块Python标准库提供一些基础数学函数如math.gcd计算最大公约数但在实现扩展欧几里得算法时我们会自己动手实现以理解过程。为什么不直接用numpy或sympynumpy针对的是数值计算数组对于单个大整数的数论运算并非最优且依赖外部库。sympy是符号计算库功能强大但笨重我们只需要最基础的算术运算。用纯Python实现能保证代码的透明度和可移植性让你看清每一个比特的流动。2.2 第一个密码学概念模运算及其Python实现模运算Modular Arithmetic是密码学的基石可以说是“时钟算术”。a mod n的结果就是a除以n后的余数这个余数总是在0到n-1之间。在Python中取模运算符是%。这看起来很简单但有一个关键陷阱需要特别注意Python的%运算符结果始终是非负的。这对于密码学来说是一个非常好的特性因为它保证了结果的一致性。# 模运算示例 print(17 % 5) # 输出: 2 print(-17 % 5) # 输出: 3 (而不是 -2) 因为 -17 -4 * 5 3 print(17 % -5) # 输出: -3 (行为不同但密码学中模数n通常是正整数)在密码学中模数n几乎总是正整数。所以-17 mod 5 3这个特性非常有用。它意味着(a mod n)的结果总是在[0, n-1]这个范围内这简化了很多后续运算。现在让我们来解决热搜词里的那个具体问题110101000模2除1001运算过程。这描述的是一个二进制串的模2除法常见于循环冗余校验CRC或某些纠错码也是有限域GF(2)上多项式除法的一种表现形式。虽然这不是典型的公钥密码学运算但理解它有助于建立“模运算”的直觉。110101000是二进制转换为十进制是424。1001是二进制转换为十进制是9。所以问题等价于“424除以9的余数是多少”。但“模2除”暗示了这是按位异或的除法。我们假设这是指以1001二进制为除数的模2除法类似于CRC计算。def mod2_division(dividend_bin, divisor_bin): 模拟二进制模2除法异或除法 dividend_bin: 被除数二进制字符串如 110101000 divisor_bin: 除数二进制字符串如 1001 返回余数的二进制字符串 # 将字符串转换为整数列表方便操作 dividend list(map(int, dividend_bin)) divisor list(map(int, divisor_bin)) len_divisor len(divisor) # 被除数末尾补0位数比除数少1这是标准CRC计算步骤 # 但根据题意‘110101000模2除1001’可能‘110101000’已经是待计算值 # 我们假设dividend已经是被除数可能是数据补位后的 working dividend[:] # 复制一份进行操作 # 或者如果dividend是纯数据则需要补 len(divisor)-1 个0 # working dividend [0] * (len_divisor - 1) # 执行模2除法异或 for i in range(len(working) - len_divisor 1): if working[i] 1: # 如果当前位是1则执行异或 for j in range(len_divisor): working[i j] ^ divisor[j] # 按位异或 # 余数就是working的最后 len_divisor - 1 位 remainder working[-(len_divisor - 1):] return .join(map(str, remainder)) # 测试 dividend 110101000 divisor 1001 remainder mod2_division(dividend, divisor) print(f二进制模2除法{dividend} % {divisor} 的余数是 {remainder}) # 输出可能是 000 或 001 等具体取决于算法初始假设 # 更严谨的做法需要明确是CRC计算还是简单的整数取模。实际上对于“110101000 mod 1001”如果我们把它理解为整数的十进制取模运算即424 mod 9那么答案很简单print(424 % 9) # 输出: 1所以110101000模2除1001的整数余数结果是1。这个例子告诉我们看到密码学或计算机领域的“模运算”时首先要明确上下文是在整数域上还是在多项式域GF(2)上这对我们的代码实现有决定性影响。3. 核心数论算法实现从欧几里得到中国剩余定理掌握了模运算我们就可以向密码学大厦的地基——数论算法——进发了。这些算法是RSA、Diffie-Hellman、椭圆曲线等现代密码体系的钢筋水泥。3.1 欧几里得算法与扩展欧几里得算法最大公约数Greatest Common Divisor, GCD的概念很简单但高效计算它的欧几里得算法辗转相除法却非常美妙。给定两个整数a和b它们的最大公约数gcd(a, b)是能同时整除它们的最大正整数。朴素实现不推荐用于大数def gcd_naive(a, b): gcd 1 for i in range(1, min(abs(a), abs(b)) 1): if a % i 0 and b % i 0: gcd i return gcd这个算法的时间复杂度是O(min(a, b))对于密码学中动辄数百位的大整数来说完全是天文数字。欧几里得算法递归版本基于定理gcd(a, b) gcd(b, a mod b)。直到b0时a就是最大公约数。def gcd_euclid(a, b): 计算最大公约数。 while b ! 0: a, b b, a % b return abs(a) # 返回绝对值确保为正 # 测试 print(gcd_euclid(48, 18)) # 输出: 6 print(gcd_euclid(17, 5)) # 输出: 1 (互质)这个算法效率极高时间复杂度约为O(log(min(a, b)))。即使对于几千位的整数也能瞬间完成。欧几里得算法很重要但它的扩展版本——扩展欧几里得算法——才是密码学的明星。它不仅能求出gcd(a, b)还能找到整数x和y使得满足贝祖等式a*x b*y gcd(a, b)。为什么这个很重要因为当a和n互质即gcd(a, n) 1时我们可以找到a在模n下的乘法逆元具体来说如果gcd(a, n) 1那么扩展欧几里得算法给出的x就是a在模n下的逆元因为a*x n*y 1意味着a*x ≡ 1 (mod n)。def extended_gcd(a, b): 扩展欧几里得算法。 返回 (gcd, x, y) 使得 a*x b*y gcd(a, b) if b 0: return (abs(a), 1 if a 0 else -1, 0) # 处理符号保证gcd为正 else: gcd, x1, y1 extended_gcd(b, a % b) # 根据递归结果回溯计算x, y x y1 y x1 - (a // b) * y1 return (gcd, x, y) def mod_inverse(a, n): 使用扩展欧几里得算法求乘法逆元。 返回 a 在模 n 下的逆元即满足 a * x ≡ 1 (mod n) 的 x。 如果逆元不存在a与n不互质则抛出异常。 gcd, x, _ extended_gcd(a, n) if gcd ! 1: raise ValueError(f乘法逆元不存在因为 gcd({a}, {n}) {gcd}不等于1) else: # x 可能是负数需要调整到 [0, n-1] 范围 return x % n # 测试求 17 在模 3120 下的逆元 (RSA解密中会用到类似计算) a, n 17, 3120 try: inv mod_inverse(a, n) print(f{a} 在模 {n} 下的乘法逆元是 {inv}) print(f验证: ({a} * {inv}) % {n} {(a * inv) % n}) except ValueError as e: print(e)运行结果会显示17在模3120下的逆元并且验证结果应为1。这个mod_inverse函数就是你未来实现RSA解密、椭圆曲线签名等算法时计算私钥核心组件私钥指数d的关键工具。3.2 模幂运算快速计算 a^b mod n密码学中充斥着这样的计算a^b mod n。例如在RSA加密中c m^e mod n解密中m c^d mod n。这里的a,b,n都是非常大的整数b可能是成百上千位。直接先计算a^b再取模是行不通的因为a^b这个中间结果会大到没有任何计算机内存可以存储。解决方案是模幂运算核心思想是在乘法的每一步中都进行取模操作让中间结果始终保持在一个较小的范围内。最常用的算法是“平方-乘”算法Exponentiation by Squaring。原理假设我们要计算a^b mod n。将指数b用二进制表示例如b 13二进制是1101。初始化结果result 1。从二进制最高位开始遍历无论当前位是0还是1都将底数平方并取模a (a * a) % n。如果当前二进制位是1则将当前结果与底数相乘并取模result (result * a) % n。遍历完所有位后result即为所求。def mod_pow(base, exponent, modulus): 快速模幂运算计算 (base^exponent) % modulus 的高效算法。 使用平方-乘算法。 if modulus 1: return 0 result 1 base base % modulus # 确保底数小于模数 while exponent 0: # 如果当前位是1 if exponent % 2 1: result (result * base) % modulus # 右移一位相当于除以2 exponent exponent 1 # 底数平方 base (base * base) % modulus return result # 测试计算 7^13 mod 11 # 7^13 96889010407 96889010407 mod 11 ? print(mod_pow(7, 13, 11)) # 输出: 2 # 验证 pow(7, 13, 11) 是Python内置函数结果应为2 print(pow(7, 13, 11)) # 输出: 2我们实现的mod_pow和Python内置的pow(base, exponent, modulus)功能一致且效率极高。理解这个算法的关键在于它将指数运算的复杂度从O(exponent)降低到了O(log exponent)这是处理密码学大数的生命线。3.3 素性检测如何判断一个大数是素数RSA密钥生成的第一步就是生成两个大素数p和q。怎么判断一个上百位的随机数是素数呢确定性算法如试除法对于大数来说太慢。实践中使用概率性素性检测算法最经典的就是米勒-拉宾检验。米勒-拉宾检验原理 基于费马小定理的一个强化版。对于一个待测奇数n我们将其写成n 2^s * d 1其中d是奇数。然后随机选择一个底数a2 a n-2检查以下序列计算x a^d mod n。如果x 1或x n-1则n可能为素数进入下一轮测试。否则将x平方s-1次每次平方后检查x mod n是否等于n-1。如果某次等于则n可能为素数进入下一轮。如果以上都不满足则n一定是合数。重复这个过程k次k是安全参数例如20次每次用不同的随机a。如果n通过了所有k轮测试那么我们可以说n是素数的概率极高错误概率小于4^{-k}。import random def is_probable_prime(n, k20): 米勒-拉宾概率性素性检测。 n: 待检测的大整数奇数。 k: 检测轮数轮数越多准确率越高耗时也越长。 返回如果n很可能为素数返回True如果n是合数返回False。 if n 2: return False if n in (2, 3): return True if n % 2 0: return False # 将 n-1 写成 2^s * d 的形式 s, d 0, n - 1 while d % 2 0: s 1 d // 2 # 进行k轮测试 for _ in range(k): a random.randrange(2, n - 1) # 随机选择底数 x pow(a, d, n) # 使用内置快速模幂 if x 1 or x n - 1: continue # 本轮通过继续下一轮 for _ in range(s - 1): x pow(x, 2, n) if x n - 1: break # 本轮通过跳出内层循环 else: # 如果内层循环完整执行完未break则n是合数 return False # 通过所有k轮测试 return True def generate_large_prime(bit_length1024, k20): 生成一个指定位数的大素数概率性。 bit_length: 所需素数的二进制位数。 k: 米勒-拉宾检测轮数。 返回一个很可能为素数的整数。 while True: # 生成一个指定位数的随机奇数 # 注意random.getrandbits 不是密码学安全的教学演示用。 # 生产环境应使用 secrets.randbits 或 Crypto.Random.get_random_bytes candidate random.getrandbits(bit_length) # 确保是奇数且最高位是1保证位数 candidate | (1 (bit_length - 1)) | 1 if is_probable_prime(candidate, k): return candidate # 测试生成一个512位的素数演示用实际RSA至少2048位 prime generate_large_prime(512) print(f生成一个512位素数前20位: {hex(prime)[:20]}...) print(f用内置简单方法验证费马小定理: {pow(2, prime-1, prime) 1})重要提醒上述代码中的random.randrange和random.getrandbits不适用于生成密码学密钥因为它们产生的随机数可能被预测。真实场景中必须使用密码学安全的随机数生成器CSPRNG如Python的secrets模块secrets.randbelow或cryptography库中的相关函数。4. 综合实战模拟一个简化版的RSA密钥生成与加解密现在让我们把前面所有的“齿轮”——模逆元、模幂运算、大素数生成——组装起来实现一个教科书级别的RSA算法。请注意这依然是教学演示版本省略了填充方案如OAEP、密钥格式等关键安全组件切勿用于真实加密。4.1 RSA密钥生成原理与代码RSA密钥生成步骤如下选择两个大素数p和q。计算模数n p * q。n的长度比特数就是RSA密钥的长度。计算欧拉函数φ(n) (p-1) * (q-1)。选择公钥指数e通常是一个较小的素数如65537 (0x10001)。要求1 e φ(n)且gcd(e, φ(n)) 1。计算私钥指数d是e在模φ(n)下的乘法逆元。即满足e * d ≡ 1 (mod φ(n))。import random from math import gcd # 使用我们之前写的函数但为了安全演示这里用一个小素数生成函数替代 def get_small_prime(): 返回一个小的素数用于演示。真实环境必须用 generate_large_prime。 small_primes [65537, 17, 19, 23, 29] return random.choice(small_primes) def rsa_key_generation(bit_length128): 生成RSA密钥对演示用bit_length较小。 返回: (public_key, private_key)其中 public_key (e, n), private_key (d, n) print(步骤1: 生成两个大素数p和q) p generate_large_prime(bit_length//2) # 各取一半长度 q generate_large_prime(bit_length//2) # 确保p和q不同 while p q: q generate_large_prime(bit_length//2) print(f p {hex(p)[:30]}...) print(f q {hex(q)[:30]}...) print(步骤2: 计算模数 n p * q) n p * q print(f n {hex(n)[:30]}... (密钥长度约为 {n.bit_length()} 位)) print(步骤3: 计算欧拉函数 φ(n) (p-1)*(q-1)) phi_n (p - 1) * (q - 1) print(f φ(n) {hex(phi_n)[:30]}...) print(步骤4: 选择公钥指数 e) e 65537 # 行业标准 # 检查 e 是否与 φ(n) 互质 if gcd(e, phi_n) ! 1: # 如果不互质极罕见尝试另一个常用值 e 17 if gcd(e, phi_n) ! 1: raise ValueError(无法找到合适的公钥指数e请重新生成素数。) print(f e {e}) print(步骤5: 计算私钥指数 d (e 在模 φ(n) 下的逆元)) d mod_inverse(e, phi_n) print(f d {hex(d)[:30]}...) public_key (e, n) private_key (d, n) return public_key, private_key # 生成一个小的密钥对用于演示128位非常不安全仅用于演示 print(--- 开始生成RSA密钥对 ---) public_key, private_key rsa_key_generation(128) print(f\n公钥 (e, n): {public_key[0]}, {hex(public_key[1])[:30]}...) print(f私钥 (d, n): {hex(private_key[0])[:30]}..., {hex(private_key[1])[:30]}...)4.2 RSA加密与解密过程加密过程对于明文消息m需要是小于n的整数计算密文c m^e mod n。 解密过程对于密文c计算明文m c^d mod n。def rsa_encrypt(plaintext_int, public_key): RSA加密。 plaintext_int: 整数形式的明文必须小于 n。 public_key: 元组 (e, n)。 返回: 整数形式的密文。 e, n public_key if plaintext_int n: raise ValueError(明文必须小于模数n。) # 使用快速模幂运算 ciphertext_int mod_pow(plaintext_int, e, n) return ciphertext_int def rsa_decrypt(ciphertext_int, private_key): RSA解密。 ciphertext_int: 整数形式的密文。 private_key: 元组 (d, n)。 返回: 整数形式的明文。 d, n private_key # 使用快速模幂运算 plaintext_int mod_pow(ciphertext_int, d, n) return plaintext_int # 演示 print(\n--- RSA加密解密演示 ---) # 假设我们的明文是数字 42 (在实际中文本需要先编码为整数例如用PKCS#1填充) m 42 print(f原始明文 m {m}) # 加密 c rsa_encrypt(m, public_key) print(f加密后密文 c m^e mod n {c}) # 解密 m_decrypted rsa_decrypt(c, private_key) print(f解密后明文 m c^d mod n {m_decrypted}) # 验证 if m m_decrypted: print(✓ 加解密成功) else: print(✗ 加解密失败)运行这段代码你会看到明文42被加密成一个看起来随机的大整数然后再正确解密回来。这就是RSA非对称加密的核心公钥(e, n)可以公开任何人都能用它加密但只有持有私钥(d, n)的人才能解密。其安全性基于大整数分解难题从公开的n难以分解出p和q从而无法计算φ(n)和私钥d。4.3 常见问题与实战踩坑点自己实现一遍后你会对以下坑点有深刻体会明文必须小于模数n这是RSA数学原理决定的。如果明文m n那么加密过程m^e mod n就无法唯一还原出m。在实际应用中通过填充方案如RSA-OAEP将原始数据分割并填充到比n小的块中。没有填充的RSA教科书RSA是不安全的。素数生成是性能瓶颈生成大素数非常耗时。我们演示中用128位瞬间完成。但2048位的RSA密钥生成可能需要几秒甚至更长时间。生产级库使用了更优化的素性检测算法和随机数生成策略。选择公钥指数e我们固定用了65537。为什么因为它二进制表示中只有两个110000000000000001这使得模幂运算m^65537 mod n非常快只需要17次模平方和2次模乘。同时它是一个素数与大多数φ(n)互质的概率极高。私钥指数d的计算如果e和φ(n)不互质mod_inverse函数会报错。这意味着你选的p和q不合适虽然概率极低。解决方案是重新生成素数。侧信道攻击我们写的mod_pow是基础版本其执行时间可能与指数d的比特位相关。真实的密码学库会使用“恒定时间”算法来防止通过计时攻击推测出私钥d。这是教学代码与工业级代码的巨大差距之一。5. 从模运算到椭圆曲线概念延伸与学习路径通过实现这些基础运算你已经掌握了对称密码和非对称密码以RSA为例背后的核心数论工具。但密码学的世界远不止于此。热搜词中提到了密码学基础这正是一个系统学习的起点。下一步可以探索的方向对称加密尝试实现AES的S盒变换、轮密钥加等基本操作理解置换和混淆。虽然完整AES很复杂但其核心的有限域GF(2^8)上的乘法与我们之前提到的模2除法有异曲同工之妙。哈希函数实现一个简化版的SHA-256的压缩函数体验如何将任意长度数据“压缩”成固定长度的摘要。这会涉及大量的位运算和模加法。椭圆曲线密码学ECC这是当前的主流趋势。ECC的安全性基于椭圆曲线离散对数问题。你需要理解如何在椭圆曲线群上定义“点加法”和“点乘法”标量乘法。这里的“模运算”发生在定义椭圆曲线的素数域或二进制域上。实现一个在素数域上的椭圆曲线点加和点乘算法将是理解ECC密钥交换ECDH和数字签名ECDSA的关键一步。你会发现求乘法逆元在点加运算中至关重要因为计算斜率时需要做模逆。中国剩余定理CRT在RSA解密或签名时利用私钥(d, p, q)和CRT可以大幅提高运算速度。其原理是将模n的大数运算分解为模p和模q的两个较小数的运算最后再合并结果。实现CRT加速的RSA解密是一个很好的练习。给学习者的建议 不要满足于调用cryptography.fernet或Crypto.PublicKey.RSA。像完成这个项目一样选择一个核心算法如Diffie-Hellman密钥交换、DSA签名然后尝试用Python从最底层的模幂、模逆开始一步步构建它。过程中你会遇到无数错误类型转换、边界条件、算法理解偏差……每一个错误的调试过程都是对密码学原理的一次深刻复习。当我第一次自己写出能工作的RSA加解密时那种对“公钥”和“私钥”数学关系的通透感是任何教科书都无法给予的。后来在实现椭圆曲线签名时因为一个模逆运算的符号错误调试了整整两天最终找到原因时对有限域运算的理解瞬间上了一个台阶。这些亲手踩过的坑最终都变成了你知识体系中最牢固的部分。密码学不是魔法它是一系列精妙数学工具的组合。而Python是你拆解和把玩这些工具的最佳放大镜和解剖刀。