The Mistery of Paillier 1 - Writeup by AI
一、题目描述
- 题目来源: BugKu
- 题目类别: Crypto (密码学)
- 题目名称: The Mistery of Paillier 1
- 环境说明: 提供加密参数文件
enc
二、考点分析
知识点权重表
| 知识点 | 权重 | 重要性 |
|---|---|---|
| Paillier 密码系统原理 | 40% | ⭐⭐⭐⭐⭐ |
| 同态加密概念 | 20% | ⭐⭐⭐⭐ |
| 数论基础 (模运算、逆元) | 25% | ⭐⭐⭐⭐ |
| Python Crypto 库使用 | 15% | ⭐⭐⭐ |
核心考点
- Paillier 密码系统: 一种概率性公钥加密算法，由 Pascal Paillier 于 1999 年提出
- 解密原理: 已知私钥 λ(n) 的情况下如何解密
- L 函数: Paillier 解密中的特殊函数 L(u) = (u-1)/n
三、解题思路
攻击策略
这道题给出了 Paillier 加密的所有关键参数：
n: 公钥模数l: 私钥 λ(n) = lcm(p-1, q-1)cipher: 密文
突破口: 直接利用已知的 λ(n) 进行解密，无需分解 n。
技术路线
四、详细步骤
步骤 1: 分析 enc 文件
n=28969443953166212176900669471436119085757229026148586965849...l=28969443953166212176900669471436119085757229026148586965849...m=10806883603368964569219078899625489478507861213296041580418...cipher=63854683448762983415142014912887433959102983569904477940311...注意到文件给出了l(lambda)，这是解密的关键！
步骤 2: Paillier 解密公式
Paillier 解密的核心公式：
L(u)=u−1nL(u) = \frac{u - 1}{n}L(u)=nu−1
m=L(cλmod n2)⋅μmod nm = L(c^\lambda \mod n^2) \cdot \mu \mod nm=L(cλmodn2)⋅μmodn
其中：
- λ=lcm(p−1,q−1)\lambda = \text{lcm}(p-1, q-1)λ=lcm(p−1,q−1)(题目已给出)
- μ=λ−1mod n\mu = \lambda^{-1} \mod nμ=λ−1modn
步骤 3: 实现解密代码
fromCrypto.Util.numberimport*# 读取参数exec(open('enc').read())defpaillier_decrypt(cipher,l,n):"""Paillier 解密函数"""# 计算 n^2n2=n*n# 计算 c^lambda mod n^2u=pow(cipher,l,n2)# L 函数：L(u) = (u - 1) // ndefL(x,n):return(x-1)//n# 计算 mu = lambda^(-1) mod nmu=inverse(l,n)# 解密：m = L(c^lambda mod n^2) * mu mod ndecrypted_m=(L(u,n)*mu)%nreturndecrypted_m# 解密并转换decrypted=paillier_decrypt(cipher,l,n)flag=long_to_bytes(decrypted)print(flag.decode())步骤 4: 执行结果
$ python solve.py 开始解密... 解密结果(十进制):17762885766238205724357596051280157561518391029869976253... 解密结果(十六进制): 0x7368656c6c6d617465737b756e6c30636b5f7468335f4d797337... Flag: shellmates{XXX}
