Paillier与同态加密基础

本文适合

CTF 密码学 入门学习者。学完你能：理解 Paillier与同态加密基础 的核心概念和基本用法

一句话判断

Paillier 的核心是“密文相乘对应明文相加”，所以如果题目想让你在不知道私钥的情况下合成结果，先看它是不是把同态性质直接暴露出来了。

题目中常见信号

公式里出现 g^m r^n mod n^2

说明：Paillier 典型结构

密文相乘后结果可预测

说明：加法同态被利用

明文是投票、金额、计数

说明：常见同态场景

题目把 Paillier 当“能直接加密所有东西”

说明：误用或组合漏洞

参数很小或随机数可复用

说明：可转向解密或伪造

核心概念

Paillier 允许对密文执行乘法，得到明文加法的对应结果：E(m1) * E(m2) = E(m1 + m2)。这不是漏洞本身，而是功能；漏洞通常来自“把功能当成安全边界”，或者参数过小、随机 r 可预测、解密接口泄露中间值。

分析时要区分：是要利用同态做计算，还是要绕过一个把同态链路误设计成认证流程的系统。

最小分析流程

1. 识别 Paillier 参数：n, g, n^2 和密文格式。
2. 判断题目目标：是合成明文、比较结果，还是恢复私钥。
3. 检查是否给了解密或比较 oracle。
4. 如果能拿到多个密文，尝试同态相乘/幂运算。
5. 如果参数小或 r 弱，考虑直接分解或复现随机。

最小验证示例

from phe import paillier

pub, priv = paillier.generate_paillier_keypair()
c1 = pub.encrypt(7)
c2 = pub.encrypt(11)
print(priv.decrypt(c1 + c2))

输出应为 18，说明密文相加对应明文相加。真实题里如果这个性质出现在投票、余额或计数流程中，就要看是否能借它构造越权结果。

常见利用 / 解题路线

路线总览：

• 同态加法：通过密文乘法合成目标明文。
• 计数篡改：把多个票、余额或分值组合成想要的结果。
• 比较绕过：利用同态和 oracle 组合得到阈值判断。
• 随机数弱：r 重复或可预测时，恢复结构。
• 小参数误用：参数过小或实现错误导致可分解。

常见失败原因

密文运算结果不对

排查动作：确认用的是 n^2 模数和正确的库对象

解密结果偏移

排查动作：检查是否有编码、裁剪或额外偏置项

只能看到同态，不能直接利用

排查动作：题目可能只是演示功能，继续找比较/验签逻辑

迷你案例

题目是一个投票系统，管理员说“票数可以同态累加”。你发现投票结果是 E(vote) 的乘积。构造三次 yes 的密文后上传，服务端解密得到总票数超过阈值，从而进入管理员分支。这里的关键不是破解 Paillier，而是把同态性质转成业务逻辑越权。