1. 项目概述一次经典的密码学实战复盘几年前打CISCN全国大学生信息安全竞赛的时候遇到一道Java实现的ElGamal密码题印象特别深。题目本身代码量不大但把ElGamal加密在CTF中一个非常经典的攻击点——随机数重用或者更准确地说随机数可预测/爆破——体现得淋漓尽致。这不仅仅是解一道题更是理解非对称加密中“随机性”重要性的绝佳案例。很多刚接触密码学的朋友觉得非对称加密牢不可破但实际应用中如果实现有瑕疵比如随机数生成器RNG出了问题再强的数学理论也可能被瞬间击穿。这道题就是一个典型它没有直接给你密钥而是给了你一个“有缺陷”的加密过程让你从密文和公开参数中反推出明文。今天我们就来彻底拆解这道题不仅还原解题过程更要把背后的数学原理、代码审计思路和爆破技巧讲透让你下次遇到同类问题能直接“秒杀”。2. 密码学背景与ElGamal算法核心解析要攻破一道题首先得理解它用的“盾”是什么。这道题的核心是ElGamal加密算法这是一种基于离散对数问题的非对称加密算法。和RSA基于大数分解不同ElGamal的安全性依赖于有限域上计算离散对数的困难性。2.1 ElGamal加密算法的数学流程我们先抛开代码用最直白的语言把ElGamal的加密解密过程捋一遍。它涉及几个关键角色大素数p一个非常大的质数所有运算都在模p的整数域中进行。生成元gg是模p的一个原根意味着g^1 mod p,g^2 mod p, ...,g^(p-1) mod p能生成1到p-1的所有整数顺序不同。私钥x一个随机选择的整数范围在1到p-2之间。公钥y由私钥计算得出y g^x mod p。(p, g, y)这三者一起构成公钥可以公开。随机数k这是加密时临时生成的一个随机数每次加密都应不同且不可预测范围同样在1到p-2之间。这个k是整个安全链条上最脆弱的一环也是本题的突破口。加密过程假设要加密明文m发送者拿到接收者的公钥(p, g, y)。选择一个随机数k。计算密文的第一部分c1 g^k mod p。计算密文的第二部分c2 m * (y^k) mod p。这里y^k (g^x)^k g^(xk) mod p。最终的密文是(c1, c2)这对组合。解密过程接收者用自己的私钥x接收者拿到密文(c1, c2)。计算共享秘密s c1^x mod p。因为c1 g^k所以s (g^k)^x g^(xk) mod p。注意这和加密时计算的y^k g^(xk)是同一个值。计算s在模p下的乘法逆元s_inv。即满足s * s_inv ≡ 1 (mod p)的数。恢复明文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的辅助函数 }关键漏洞分析随机数生成器Random random new Random();在Java中无参构造函数默认使用系统时间作为种子。在CTF题目环境中如果服务器进程启动后为我们加密我们无法控制或精确预测其种子单纯这一点通常不足以直接攻击。但问题不在这里。随机数k的位数BigInteger k new BigInteger(64, random);这行代码是致命伤。它的意思是生成一个随机的大整数k其最大位数为64位。注意BigInteger的构造函数(int bitLength, Random rnd)生成的是一个正数其位长正好是bitLength。也就是说k是一个64位的正整数。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’我们进行如下验证计算c1’ g^k’ mod p。比较c1’与真实的c1。如果c1’ c1那么恭喜我们猜中了真正的k因为c1 g^k mod p在模p下不同的k产生相同c1的概率极低碰撞概率。一旦k被确定我们就可以计算共享秘密s y^k mod p因为y已知。计算s的模逆s_inv满足s * s_inv ≡ 1 (mod p)。恢复明文m c2 * s_inv mod p。将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本身不是爆破计算的最优选择。我们通常会使用Pythongmpy2/pycryptodome库或C/CGMP库来编写爆破脚本因为它们的大数运算和循环速度更快。攻击方案设计步骤提取参数从题目文件或网络流量中提取公钥(p, g, y)和所有密文对(c1_i, c2_i)。确定k的搜索范围基于代码审计new BigInteger(64, random)理论上范围是[0, 2^64)。但有时为了降低难度范围可能更小比如[0, 2^32)或者k是顺序递增的。如果无法确定就从0开始暴力枚举。编写爆破脚本循环遍历候选k’计算c1_test pow(g, k’, p)并与目标c1比较。验证与解密找到k后计算s pow(y, k, p)求s的模逆然后计算m c2 * s_inv % p最后将m转换为字节。结果判断检查解密出的字节是否为可读的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_k0, end_k2**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(fProgress: 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.“)脚本优化要点使用gmpy2.powmod这是模幂运算比先计算幂再取模快无数倍。powmod(a, b, c)直接计算a^b mod c。范围设定brute_force_k函数的end_k参数很重要。原题是64位但实际比赛可能为了降低难度或者通过其他线索如代码中的其他随机数使用、时间戳等暗示k的范围更小。永远不要一上来就爆破2^64次。可以先尝试小范围如24位、32位并观察进度。如果题目给了多组密文可以尝试用第一组密文爆破一个较小的k如果成功再观察其他密文的k是否有规律比如递增。进度反馈在循环中加入进度打印让你知道程序在运行并估算剩余时间。解密验证解密后不能只看字符串解码因为明文可能不是UTF-8文本。一定要检查字节的原始值。常见的flag格式如flag{对应的十六进制是66 6c 61 67 7b。可以在脚本中加入自动判断if b‘flag{‘ in m_bytes:。多线程/多进程对于较大的搜索空间必须使用并行。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_workersnum_workers) as executor: futures [] for i in range(num_workers): start i * range_per_worker end (i1) * 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面向多组密文的爆破如果有多组(c1_i, c2_i)并且你怀疑它们使用不同的k_i那么你需要为每一组密文单独爆破。但脚本结构类似可以封装成一个函数循环处理每一组密文。6. 常见问题、调试技巧与扩展思考在实际操作中你可能会遇到各种问题。下面是一些踩坑经验和进阶思路。6.1 问题排查清单问题现象可能原因解决方案爆破脚本运行极慢毫无进度1. 搜索空间 (end_k) 设置过大如直接设2**64。2. 模幂运算powmod在循环中调用每次都是大数运算本身就很耗时。1.先从小范围试起比如2**20(约100万次)。2. 确认p,g,c1是否正确载入。用print输出它们的比特长度 (p.bit_length()) 确认。3.使用更高效的编程语言如C配合GMP库或者使用Python的gmpy2并确保已安装C优化版本。找到了k但解密出的字节乱码1. 明文编码方式不是简单的字节到大整数。可能经过了其他转换如Base64、Hex编码后再转整数。2. 解密公式用错或者模逆计算错误。3. 密文c2对应的是m * s mod p但m可能不是直接的消息而是消息的某种哈希或填充后的值。1. 检查题目描述或源代码看message是如何转换成BigInteger的。常见的是new BigInteger(1, messageBytes)其中1表示正数。2.验证解密公式用找到的k自己加密一个已知的测试消息m_test比如数字12345得到(c1_test, c2_test)。然后用你的解密流程去解c2_test看是否能恢复12345。这是最可靠的验证方法。3. 输出解密后的整数m然后尝试不同的转换to_bytes(..., ‘big‘),to_bytes(..., ‘little‘), 或者先转成16进制字符串再看。爆破完了指定范围没找到k1.k的生成范围比你想象的大。2.k的生成有偏移不是从0开始。3. 公钥y或密文c1提取错误。4. 题目用的g不是2而是其他值你误用了。1. 逐步扩大搜索范围比如从2**24到2**32。同时评估时间2**32次模幂运算在单核上可能需要数天必须并行。2. 检查源代码new BigInteger(64, random)生成的是正数且位长为64所以范围是[2^63, 2^64-1]吗不BigInteger(int bitLength, Random rnd)生成的是均匀分布在(0, 2^bitLength)范围内的随机数。所以k的范围是(0, 2^64)包括很小的数。从0开始搜索是合理的。3.仔细核对所有输入参数确保和题目给出的完全一致包括进制通常是16进制。4. 确认g的值。解密出的内容像是flag的一部分题目可能将flag分成了多个块每个块单独加密。你需要对每一个密文对(c1_i, c2_i)执行爆破每个块的k_i可能不同。然后将解密出的所有块按顺序拼接起来。编写脚本批量处理所有密文对。注意如果每个块的k都不同你需要为每个块单独爆破这非常耗时。但有时出题人会“放水”让所有块使用相同的k这样你只需要爆破一次。先验证这个猜想检查所有c1_i是否相同如果相同则k相同。6.2 实操心得与技巧参数提取是第一步也是容易出错的一步。题目可能以多种形式给出参数Java源代码中的赋值、文本文件、网络数据包。务必确保你提取的p,g,y,c1,c2是完整的、进制正确的。一个技巧是打印它们的bit_length()p应该是很大的数比如2048位c1和c2的位长应该接近p的位长。从小范围开始爆破。永远不要假设你需要爆破完整的64位空间。先试试2**20一百万次这通常几秒到一分钟就能跑完。如果没有结果再扩大到2**24一千六百万次这可能需要几分钟。逐步扩大同时观察解密出的中间结果是否有规律比如总是解码出部分可读字符。利用已知明文信息。如果flag有固定格式比如以flag{开头那么你可以利用这一点来优化爆破甚至不需要完全依赖c1。你可以枚举k然后解密检查解密出的字节是否以flag{的字节开头。这样你可以在找到完整k之前就提前确认成功。但这种方法需要你能够快速计算解密过程其计算量和直接比较c1‘差不多。注意编码细节。Java的BigInteger和 Python 的int/mpz在字节转换上可能略有不同。Java的toByteArray()方法会包含一个符号位最高位为符号位所以可能会在字节数组前面加一个零字节。而Python的int.to_bytes()需要指定长度和字节序。常见的处理方式是在Python中如果解密出的整数m转换成的字节串开头有多余的\x00可以尝试去掉它m_bytes.lstrip(b‘\x00‘)。调试时使用小参数。为了快速验证你的爆破和解密逻辑是否正确可以自己用小参数模拟一遍。比如选一个小的素数p23生成元g5随机生成私钥x和k加密一个已知消息然后用你的脚本去爆破和解密。这能帮你快速定位是数学公式错误、编码错误还是逻辑错误。6.3 扩展思考其他随机数相关漏洞这道题聚焦于随机数k的位数不足。在CTF和实际密码学应用中与随机数相关的漏洞还有多种变体随机数重用这是最经典的。如果同一个k加密了两个不同的消息攻击者可以直接计算m1/m2无需爆破。在ElGamal和DSA数字签名算法中都是致命伤。随机数生成器种子可预测如果Random的种子是基于时间等可预测的值攻击者可以重现整个随机数序列。在本题中虽然种子可能不可控但如果服务器每次启动都使用固定种子比如new Random(12345)那么所有k都是可预测的。随机数分布不均匀Random类在某些情况下可能不是密码学安全的。但在本题中主要矛盾是位数限制而不是分布。侧信道攻击通过分析加密时间、功耗等物理信息可能推断出k的部分信息从而缩小搜索空间。这在CTF中较少见但在硬件安全中很常见。理解这道题你就掌握了密码学中“实现安全”与“算法安全”同样重要的核心理念。一个在数学上无懈可击的算法可能因为一个糟糕的随机数生成器而土崩瓦解。在CTF中这类题目考察的正是你对算法实现细节的洞察力和将理论攻击转化为实际代码的能力。下次看到ElGamal或DSA你的第一反应就应该是它的随机数真的随机吗