The Mistery of Paillier 1 - Writeup by AI

The Mistery of Paillier 1 - Writeup by AI

一、题目描述

• 题目来源: BugKu
• 题目类别: Crypto (密码学)
• 题目名称: The Mistery of Paillier 1
• 环境说明: 提供加密参数文件enc

二、考点分析

知识点权重表

核心考点

1. Paillier 密码系统: 一种概率性公钥加密算法，由 Pascal Paillier 于 1999 年提出
2. 解密原理: 已知私钥 λ(n) 的情况下如何解密
3. 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}