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)=\frac{u-1}{n}$$

$$m=L(c^{\lambda }\mathrm{mod}{n}^2)\cdot \mu \mathrm{mod}n$$

其中：

• $\lambda =\text{lcm}(p-1,q-1)$ (题目已给出)
• $\mu ={\lambda }^{-1}\mathrm{mod}n$

步骤 3: 实现解密代码

from Crypto.Util.number import *

# 读取参数
exec(open('enc').read())

def paillier_decrypt(cipher, l, n):
    """Paillier 解密函数"""
    # 计算 n^2
    n2 = n * n
    
    # 计算 c^lambda mod n^2
    u = pow(cipher, l, n2)
    
    # L 函数：L(u) = (u - 1) // n
    def L(x, n):
        return (x - 1) // n
    
    # 计算 mu = lambda^(-1) mod n
    mu = inverse(l, n)
    
    # 解密：m = L(c^lambda mod n^2) * mu mod n
    decrypted_m = (L(u, n) * mu) % n
    
    return decrypted_m

# 解密并转换
decrypted = paillier_decrypt(cipher, l, n)
flag = long_to_bytes(decrypted)
print(flag.decode())

步骤 4: 执行结果

$ python solve.py

开始解密...
解密结果 (十进制): 17762885766238205724357596051280157561518391029869976253...
解密结果 (十六进制): 0x7368656c6c6d617465737b756e6c30636b5f7468335f4d797337...
Flag: shellmates{XXX}