ElGamal加密随机数爆破攻击：从CTF实战解析密码学实现漏洞

1. 项目概述：一次经典的密码学实战复盘

几年前打CISCN（全国大学生信息安全竞赛）的时候，遇到一道Java实现的ElGamal密码题，印象特别深。题目本身代码量不大，但把ElGamal加密在CTF中一个非常经典的攻击点——随机数重用（或者更准确地说，随机数可预测/爆破）——体现得淋漓尽致。这不仅仅是解一道题，更是理解非对称加密中“随机性”重要性的绝佳案例。很多刚接触密码学的朋友，觉得非对称加密牢不可破，但实际应用中，如果实现有瑕疵，比如随机数生成器（RNG）出了问题，再强的数学理论也可能被瞬间击穿。这道题就是一个典型，它没有直接给你密钥，而是给了你一个“有缺陷”的加密过程，让你从密文和公开参数中反推出明文。今天，我们就来彻底拆解这道题，不仅还原解题过程，更要把背后的数学原理、代码审计思路和爆破技巧讲透，让你下次遇到同类问题能直接“秒杀”。

2. 密码学背景与ElGamal算法核心解析

要攻破一道题，首先得理解它用的“盾”是什么。这道题的核心是ElGamal加密算法，这是一种基于离散对数问题的非对称加密算法。和RSA基于大数分解不同，ElGamal的安全性依赖于有限域上计算离散对数的困难性。

2.1 ElGamal加密算法的数学流程

我们先抛开代码，用最直白的语言把ElGamal的加密解密过程捋一遍。它涉及几个关键角色：

1. 大素数p：一个非常大的质数，所有运算都在模p的整数域中进行。
2. 生成元g：g是模p的一个原根，意味着g^1 mod p,g^2 mod p, ...,g^(p-1) mod p能生成1到p-1的所有整数（顺序不同）。
3. 私钥x：一个随机选择的整数，范围在1到p-2之间。
4. 公钥y：由私钥计算得出，y = g^x mod p。(p, g, y)这三者一起构成公钥，可以公开。
5. 随机数k：这是加密时临时生成的一个随机数，每次加密都应不同且不可预测，范围同样在1到p-2之间。这个k是整个安全链条上最脆弱的一环，也是本题的突破口。

加密过程（假设要加密明文m）：发送者拿到接收者的公钥(p, g, y)。

1. 选择一个随机数k。
2. 计算密文的第一部分c1 = g^k mod p。
3. 计算密文的第二部分c2 = m * (y^k) mod p。这里y^k = (g^x)^k = g^(xk) mod p。
4. 最终的密文是(c1, c2)这对组合。

解密过程（接收者用自己的私钥x）：接收者拿到密文(c1, c2)。

1. 计算共享秘密s = c1^x mod p。因为c1 = g^k，所以s = (g^k)^x = g^(xk) mod p。注意，这和加密时计算的y^k = g^(xk)是同一个值。
2. 计算s在模p下的乘法逆元s_inv。即满足s * s_inv ≡ 1 (mod p)的数。
3. 恢复明文m = c2 * s_inv mod p。因为c2 = m * s，所以m = c2 * s_inv = m * s * s_inv = m (mod p)。

整个过程的美妙之处在于，加密者用公钥y和随机数k构造了共享秘密s；解密者用私钥x和收到的c1也能计算出同一个s。而攻击者只知道c1 = g^k，想从g和c1反推出k（即求解离散对数k = log_g(c1)），在p很大时是计算不可行的。

2.2 随机数k的重要性与攻击面

从上面流程可以看出，随机数k至关重要：

• 唯一性：每次加密必须使用新的、不可预测的k。如果同一个k被用来加密两条不同的消息m1和m2，那么密文对分别是(c1, c2)和(c1‘, c2’)。注意，由于k相同，c1 = g^k mod p和c1‘ = g^k mod p是完全相同的！这就留下了致命隐患。
• 攻击场景：假设我们有两组密文，使用了相同的k：
  • 密文1:(c1, c2) = (g^k mod p, m1 * y^k mod p)
  • 密文2:(c1, c2‘) = (g^k mod p, m2 * y^k mod p)那么，我们可以计算c2 / c2‘ ≡ (m1 * y^k) / (m2 * y^k) ≡ m1 / m2 (mod p)。如果m1或m2已知，或者其格式有迹可循（比如都是ASCII字符串），我们就可以推算出另一个明文。更一般地，如果k不是完全重用，而是从一个很小的空间（例如，一个32位整数范围）内随机选取，那么攻击者可以暴力枚举所有可能的k，这就是“随机数爆破”攻击。

CISCN2018这道Java题，正是利用了后者——随机数k的生成范围存在缺陷，使得暴力枚举成为可能。题目通常会给出多个用相同公钥加密的密文（可能对应多个flag片段），以及最重要的源代码，让我们分析出k的生成规律。

3. 题目代码审计与漏洞定位

当时题目的核心代码片段（根据记忆和常见模式重构）大致如下：

import java.math.BigInteger; import java.util.Random; public class ElGamalEncryption { private BigInteger p, g, y; // 公钥 private BigInteger x; // 私钥，服务器端持有，不公开 private Random random; public ElGamalEncryption() { // 初始化大素数p和生成元g（题目给出） p = new BigInteger("FFFFFFFFFFFFFFFFC90FDAA...（一个很大的16进制数）", 16); g = new BigInteger("2"); // 生成私钥x和公钥y random = new Random(); x = new BigInteger(p.bitLength() - 1, random); // 私钥是随机大数 y = g.modPow(x, p); // 计算公钥 y = g^x mod p } public BigInteger[] encrypt(BigInteger message) { // 加密函数 BigInteger k = new BigInteger(64, random); // 关键行：随机数k只有64位！ BigInteger c1 = g.modPow(k, p); BigInteger s = y.modPow(k, p); BigInteger c2 = message.multiply(s).mod(p); return new BigInteger[]{c1, c2}; } // ... 可能还有其他方法，比如将字符串转为BigInteger的辅助函数 }

关键漏洞分析：

1. 随机数生成器：Random random = new Random();在Java中，无参构造函数默认使用系统时间作为种子。在CTF题目环境中，如果服务器进程启动后为我们加密，我们无法控制或精确预测其种子，单纯这一点通常不足以直接攻击。但问题不在这里。
2. 随机数k的位数：BigInteger k = new BigInteger(64, random);这行代码是致命伤。它的意思是：生成一个随机的大整数k，其最大位数为64位。注意，BigInteger的构造函数(int bitLength, Random rnd)生成的是一个正数，其位长正好是bitLength。也就是说，k是一个64位的正整数。
3. 64位意味着什么？64位整数的最大值是2^64 - 1，大约是1.84e19。这个数字看起来很大，但在密码学攻击面前，它太小了。现代计算机进行数十亿（1e9）次运算是轻而易举的。2^64约等于1.84e19，虽然直接遍历2^64次仍然不现实（需要巨大的计算资源和时间），但题目往往会给其他限制条件或提示，使得搜索空间远小于2^64。例如，k可能是在一个更小的区间内生成，或者我们可以利用多组密文的信息来缩小范围。

审计结论：加密算法本身（ElGamal）是标准的，数学上没问题。但随机数k的熵（不确定性）严重不足，从密码学安全角度，k应该和私钥x一样，是一个接近p的位数（比如2048位）的大随机数。这里k被限制在64位，使得暴力枚举（爆破）成为可能。我们的攻击目标就从“求解离散对数”这个数学难题，降级为“在最多2^64个可能性中猜测k”。

注意：在实际审题时，我们还需要关注message（明文）是如何编码成BigInteger的。常见的是将字符串（如flag）的字节数组转换为一个大整数。这关系到我们爆破出k后，如何验证解出的明文是否正确（例如，解密后的字节数组是否包含可读的ASCII字符或特定的flag格式flag{...}）。

4. 攻击原理与爆破方案设计

既然知道了k只有64位，我们如何利用它来解密呢？回顾加密公式：c1 = g^k mod pc2 = m * (y^k) mod p

我们已知：公钥(p, g, y)，以及一组或多组密文(c1, c2)。我们不知道：私钥x、随机数k、明文m。

攻击思路： 我们无法直接攻破私钥x，但我们可以枚举所有可能的k’（从0到2^64-1，或者根据题目线索确定的更小范围）。对于每一个猜测的k’，我们进行如下验证：

1. 计算c1’ = g^k’ mod p。
2. 比较c1’与真实的c1。
   • 如果c1’ == c1，那么恭喜，我们猜中了真正的k！因为c1 = g^k mod p，在模p下，不同的k产生相同c1的概率极低（碰撞概率）。
3. 一旦k被确定，我们就可以计算共享秘密s = y^k mod p（因为y已知）。
4. 计算s的模逆s_inv，满足s * s_inv ≡ 1 (mod p)。
5. 恢复明文m = c2 * s_inv mod p。
6. 将m转换回字节或字符串，检查其是否符合预期格式（如包含flag字样），从而确认解密成功。

为什么能爆破？核心在于第一步的验证c1’ == c1。我们不需要知道任何关于明文m的信息，只需要用公钥参数g和p进行幂运算。对于每一个候选k’，计算g^k’ mod p是一次模幂运算。虽然2^64次模幂运算量很大，但并非天文数字。我们可以通过以下策略优化：

• 缩小搜索空间：题目可能暗示k的生成并非完全均匀随机64位。例如，Random对象可能被重置了种子，或者k是从一个固定的小列表中选取。仔细分析源代码和上下文（比如题目名称、描述）可能找到线索。
• 利用多组密文：如果题目给了多组用相同公钥加密的密文（对应flag的不同部分），并且它们使用了不同的k，那么爆破一个k只能解一条密文。但如果这些密文使用了相同的k（这是更严重的错误），那么你只需要爆破一次k，就能解密所有密文。本题更可能是前者，即每条密文对应一个独立的、可爆破的k。
• 并行计算：爆破是“令人愉悦的并行”问题，可以轻松分配到多个CPU核心甚至GPU上进行，大幅缩短时间。
• 使用更高效的语言和库：Java本身不是爆破计算的最优选择。我们通常会使用Python（gmpy2/pycryptodome库）或C/C++（GMP库）来编写爆破脚本，因为它们的大数运算和循环速度更快。

攻击方案设计步骤：

1. 提取参数：从题目文件或网络流量中，提取公钥(p, g, y)和所有密文对(c1_i, c2_i)。
2. 确定k的搜索范围：基于代码审计new BigInteger(64, random)，理论上范围是[0, 2^64)。但有时为了降低难度，范围可能更小（比如[0, 2^32)），或者k是顺序递增的。如果无法确定，就从0开始暴力枚举。
3. 编写爆破脚本：循环遍历候选k’，计算c1_test = pow(g, k’, p)，并与目标c1比较。
4. 验证与解密：找到k后，计算s = pow(y, k, p)，求s的模逆，然后计算m = c2 * s_inv % p，最后将m转换为字节。
5. 结果判断：检查解密出的字节是否为可读的ASCII字符串，并包含flag格式。

5. 实战爆破脚本编写与优化

这里我们用Python来演示爆破过程，因为它编写快捷，且有强大的gmpy2库支持高速大数运算。假设我们已经从题目中提取到了如下数据（数值为示例，非原题）：

import gmpy2 from gmpy2 import mpz # 1. 公钥参数 (示例值，实际题目中会给出很大的数) p = mpz(‘0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF‘) g = mpz(2) y = mpz(‘0x9ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF012345678‘) # 公钥y # 2. 密文 (示例，实际题目可能有多组) c1 = mpz(‘0x1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF‘) c2 = mpz(‘0xFEDCBA0987654321FEDCBA0987654321FEDCBA0987654321FEDCBA0987654321‘) # 3. 爆破函数 def brute_force_k(p, g, c1, start_k=0, end_k=2**24): # 示例中先试一个较小的范围 2^24 """暴力枚举k，范围[start_k, end_k)""" for k_guess in range(start_k, end_k): k_guess_mpz = mpz(k_guess) # 计算 g^{k_guess} mod p c1_test = gmpy2.powmod(g, k_guess_mpz, p) # 如果匹配，返回找到的k if c1_test == c1: return k_guess_mpz # 可选：每100万次输出一次进度 if k_guess % 1000000 == 0: print(f"Progress: k_guess = {k_guess}") return None # 4. 执行爆破 print(“Starting brute force...“) found_k = brute_force_k(p, g, c1, 0, 2**24) # 假设我们猜测k在24位以内 if found_k is not None: print(f“Found k: {found_k}“) # 5. 使用找到的k进行解密 # 计算共享秘密 s = y^k mod p s = gmpy2.powmod(y, found_k, p) # 计算s在模p下的乘法逆元 s_inv = gmpy2.invert(s, p) # invert函数计算模逆 # 恢复明文 m = c2 * s_inv mod p m = (c2 * s_inv) % p # 将明文大整数转换为字节 # 需要知道编码方式，常见的是将字节直接转为大整数 (int.from_bytes) # 这里假设明文是ASCII字符串，直接转换 try: # 将mpz转换为整数，然后转换为字节 m_bytes = int(m).to_bytes((m.bit_length() + 7) // 8, ‘big‘) # 尝试解码为UTF-8字符串 flag = m_bytes.decode(‘utf-8‘, errors=‘ignore‘).strip() print(f“Decrypted message (as string): {flag}“) # 也输出16进制和原始字节，便于检查 print(f“Decrypted bytes (hex): {m_bytes.hex()}“) print(f“Decrypted bytes (raw): {m_bytes}“) except Exception as e: print(f“Error during decoding: {e}“) print(f“Raw integer m: {m}“) else: print(“Failed to find k in the given range.“)

脚本优化要点：

1. 使用gmpy2.powmod：这是模幂运算，比先计算幂再取模快无数倍。powmod(a, b, c)直接计算a^b mod c。
2. 范围设定：brute_force_k函数的end_k参数很重要。原题是64位，但实际比赛可能为了降低难度，或者通过其他线索（如代码中的其他随机数使用、时间戳等）暗示k的范围更小。永远不要一上来就爆破2^64次。可以先尝试小范围（如24位、32位），并观察进度。如果题目给了多组密文，可以尝试用第一组密文爆破一个较小的k，如果成功，再观察其他密文的k是否有规律（比如递增）。
3. 进度反馈：在循环中加入进度打印，让你知道程序在运行，并估算剩余时间。
4. 解密验证：解密后不能只看字符串解码，因为明文可能不是UTF-8文本。一定要检查字节的原始值。常见的flag格式如flag{对应的十六进制是66 6c 61 67 7b。可以在脚本中加入自动判断：if b‘flag{‘ in m_bytes:。
5. 多线程/多进程：对于较大的搜索空间，必须使用并行。Python可以用concurrent.futures库或multiprocessing库来分割搜索区间。

   import concurrent.futures def brute_range(start, end): # 同上，但只搜索[start, end)区间 for k_guess in range(start, end): # ... 计算和比较 if found: return k_guess return None # 分割任务 total_range = 2**24 num_workers = 8 range_per_worker = total_range // num_workers with concurrent.futures.ProcessPoolExecutor(max_workers=num_workers) as executor: futures = [] for i in range(num_workers): start = i * range_per_worker end = (i+1) * range_per_worker if i != num_workers-1 else total_range futures.append(executor.submit(brute_range, start, end)) for future in concurrent.futures.as_completed(futures): result = future.result() if result is not None: print(f“Found k in parallel: {result}“) # 可以在这里终止其他进程（略复杂，示例省略） break

6. 面向多组密文的爆破：如果有多组(c1_i, c2_i)，并且你怀疑它们使用不同的k_i，那么你需要为每一组密文单独爆破。但脚本结构类似，可以封装成一个函数，循环处理每一组密文。

6. 常见问题、调试技巧与扩展思考

在实际操作中，你可能会遇到各种问题。下面是一些踩坑经验和进阶思路。

6.1 问题排查清单

6.2 实操心得与技巧

1. 参数提取是第一步，也是容易出错的一步。题目可能以多种形式给出参数：Java源代码中的赋值、文本文件、网络数据包。务必确保你提取的p,g,y,c1,c2是完整的、进制正确的。一个技巧是：打印它们的bit_length()，p应该是很大的数（比如2048位），c1和c2的位长应该接近p的位长。
2. 从小范围开始爆破。永远不要假设你需要爆破完整的64位空间。先试试2**20（一百万次），这通常几秒到一分钟就能跑完。如果没有结果，再扩大到2**24（一千六百万次），这可能需要几分钟。逐步扩大，同时观察解密出的中间结果是否有规律（比如总是解码出部分可读字符）。
3. 利用已知明文信息。如果flag有固定格式，比如以flag{开头，那么你可以利用这一点来优化爆破，甚至不需要完全依赖c1。你可以枚举k，然后解密，检查解密出的字节是否以flag{的字节开头。这样你可以在找到完整k之前就提前确认成功。但这种方法需要你能够快速计算解密过程，其计算量和直接比较c1‘差不多。
4. 注意编码细节。Java的BigInteger和 Python 的int/mpz在字节转换上可能略有不同。Java的toByteArray()方法会包含一个符号位（最高位为符号位），所以可能会在字节数组前面加一个零字节。而Python的int.to_bytes()需要指定长度和字节序。常见的处理方式是：在Python中，如果解密出的整数m转换成的字节串开头有多余的\x00，可以尝试去掉它：m_bytes.lstrip(b‘\x00‘)。
5. 调试时使用小参数。为了快速验证你的爆破和解密逻辑是否正确，可以自己用小参数模拟一遍。比如，选一个小的素数p=23，生成元g=5，随机生成私钥x和k，加密一个已知消息，然后用你的脚本去爆破和解密。这能帮你快速定位是数学公式错误、编码错误还是逻辑错误。

6.3 扩展思考：其他随机数相关漏洞

这道题聚焦于随机数k的位数不足。在CTF和实际密码学应用中，与随机数相关的漏洞还有多种变体：

1. 随机数重用：这是最经典的。如果同一个k加密了两个不同的消息，攻击者可以直接计算m1/m2，无需爆破。在ElGamal和DSA（数字签名算法）中都是致命伤。
2. 随机数生成器种子可预测：如果Random的种子是基于时间等可预测的值，攻击者可以重现整个随机数序列。在本题中，虽然种子可能不可控，但如果服务器每次启动都使用固定种子（比如new Random(12345)），那么所有k都是可预测的。
3. 随机数分布不均匀：Random类在某些情况下可能不是密码学安全的。但在本题中，主要矛盾是位数限制，而不是分布。
4. 侧信道攻击：通过分析加密时间、功耗等物理信息，可能推断出k的部分信息，从而缩小搜索空间。这在CTF中较少见，但在硬件安全中很常见。

理解这道题，你就掌握了密码学中“实现安全”与“算法安全”同样重要的核心理念。一个在数学上无懈可击的算法，可能因为一个糟糕的随机数生成器而土崩瓦解。在CTF中，这类题目考察的正是你对算法实现细节的洞察力和将理论攻击转化为实际代码的能力。下次看到ElGamal或DSA，你的第一反应就应该是：它的随机数，真的随机吗？