同态加密攻击面Paillier/FHE 噪声考点概念同态加密允许在密文上直接运算Paillier 是典型加法同态E(m1)·E(m2) 解密m1m2常考验证同态性质或利用密文运算结果反推明文。FHE 的噪声随运算增长超过阈值解密即失败参数选错/噪声管理失衡Paillier 公式密钥生成选等长大素数 p、qn pqλ lcm(p−1, q−1)取 g n1μ L(g^λ mod n²)^(−1) mod n其中 L(u) (u−1)/n公钥 (n, g)私钥 (λ, μ)。加密 c g^m · r^n mod n²r 随机取自 Z_n^*解密 m L(c^λ mod n²)·μ mod n。运算规则二项式展开给 (1n)^m ≡ 1mnmod n²故 gn1 时 L(g^λ) λ、μ λ^(−1) mod n这是密钥自洽的根源。密文相乘模 n²即明文相加E(m1)·E(m2) ≡ g^(m1m2)·(r1·r2)^n ≡ E(m1m2)。密文自乘 k 次得 E(k·m)密文乘 g^t 得 E(mt)随机数 r 必须与 n 互素且不可重用否则同态性与语义安全性破坏。同态只到加法与标量乘法对明文的乘法运算没有对应的密文操作这是判定题目考点的主要信号。演算p3、q5n 15、n² 225、λ lcm(2,4) 4、g n1 16g^λ 16⁴ ≡ 14·15 61mod 225L(61) (61−1)/15 4 λμ 4^(−1) mod 15 44·416≡1。 加密 E(2, r2)g² 256 ≡ 31r^n 2^15 32768 ≡ 143c1 31·143 4433 ≡ 158mod 225。 加密 E(4, r4)g⁴ ≡ 614^15 2^30 ≡ 143² ≡ 199c2 61·199 12139 ≡ 214。 同态验证c1·c2 158·214 33812 ≡ 62mod 225解密 D(62)62² ≡ 1919² 361 ≡ 136L(136) 135/15 9m 9·4 36 ≡ 6 24顺带 D(c1) 2、D(c2) 4 亦逐项核对成立。r 若取 3 则 gcd(3,15)≠1同态链在 r^n 项上断裂教学时特意换 r4。通常以纯数学演示题出现给出 Paillier 公钥求同态和或噪声增长概念题识别特征提示语Paillier、homomorphic、同态、FHE/BFV/CKKS后两者多为概念题。 计算特征给出 (n, g) 与多个密文问 m1m2或让在密文上做乘/加。靶场题目Paillier赣CTFWriteup题目Paillier赣CTF 识别m1 pq1 即 Paillier 的 g n01记 n0 pqc 是标准 Paillier 密文模 n0²指数即明文破题点不在同态而在先分解 n0——relation 是故意的泄密因子。 解题 恢复素因子由二项式定理 relation (1949p2023)^q ≡ 2023^qmod p又由费马小定理 2023^(pq) ≡ 2023^qmod p故 gcd(pow(2023, pq, pq) − relation, pq) p从而 p、q 俱得。 标准解密λ lcm(p−1, q−1)D(c) L(c^λ mod n0²)·L(g^λ mod n0²)^(−1) mod n0 直接得到 flag。flag{i_10ve_crypto!}脚本from math import gcd from Crypto.Util.number import long_to_bytes ​ n0 0 c 0 relation 0 ​ if n0 and c and relation: p gcd(n0, pow(2023, n0, n0) - relation) q n0 // p assert p * q n0 ​ N2 n0 * n0 lam (p - 1) * (q - 1) // gcd(p - 1, q - 1) L lambda u: (u - 1) // n0 Lg L(pow(n0 1, lam, N2)) Lc L(pow(c, lam, N2)) m (Lc * pow(Lg, -1, n0)) % n0 print(long_to_bytes(m)) else: print(先取得 pq、c、relation 三个大整数贴入参数位再运行解密)题目Paillier 同态加法模拟题识别描述含 Paillier问密文相乘解密结果即考加法同态。 解题按 keygen 算 λ lcm(p−1, q−1)、μ L(g^λ mod n²)^(−1) mod n计算 c1·c2 mod n²解密 D(c1·c2) L((c1·c2)^λ)·μ 即 m1m2。脚本from math import gcd, lcm ​ L lambda u, n: (u - 1) // n p, q 61, 53 n, g p * q, p * q 1 lam lcm(p - 1, q - 1) mu pow(L(pow(g, lam, n * n), n), -1, n) dec lambda c: (L(pow(c, lam, n * n), n) * mu) % n enc lambda m, r: (pow(g, m, n * n) * pow(r, n, n * n)) % (n * n) c1, c2 enc(42, 17), enc(43, 19) print(dec((c1 * c2) % (n * n)))工具Sage Cell Server脚本from math import gcd ​ def lcm(a, b): return a // gcd(a, b) * b def L(x, n): return (x - 1) // n ​ p, q 61, 53 n p * q n2 n * n lam lcm(p - 1, q - 1) g n 1 mu pow(L(pow(g, lam, n2), n), -1, n) ​ def enc(m, r): return (pow(g, m, n2) * pow(r, n, n2)) % n2 def dec(c): return (L(pow(c, lam, n2), n) * mu) % n ​ m1, m2 42, 43 c1, c2 enc(m1, 17), enc(m2, 19) m_sum dec((c1 * c2) % n2) print(Paillier 同态加法: dec(enc(42)*enc(43)) %d % m_sum) assert m_sum m1 m2 print(SUCCESS: flag{paillier_homomorphic_demo})