ezDec

第一节：题目

题目给了一份 Paillier 的加密脚本：

def Gen():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1) * (q - 1)
    return n, phi

def Enc(m, n):
    while 1:
        r = randint(1, n)
        if GCD(r, n) == 1:
            break
    c = pow(n + 1, m, n**2) * pow(r, n, n**2) % pow(n, 2)
    return c
    
    
n = 153396211011150802817786720409497854855335807009308554623742617766338687957202189181399323636404512599740987069785432426073851317845807994224968901397122058915829056264442446377911660719557792351992477286189102744835410901118463454736945695694316266883012722210632296375435368060590606426473601302049741888291
phi = 153396211011150802817786720409497854855335807009308554623742617766338687957202189181399323636404512599740987069785432426073851317845807994224968901397122034114566998484506235039866557939786543950426114130461601701559155358442341547187940900303852879190072403580201918270223937947081447768438300627126739819352
c = 23454648989405998455733130363797025093915369298195332932532234307253066996867133848183383529921499342754070084339750432723101260156164092121746634956158905768156699869985985235027062789606436414762335952934868776399370328565784807635684203788254622367942236494702296234719951616388792136074106462217397877169534296587815760258248740713388625055612544133630291451685091324626452955144536285309806578562567743643707258971941866648097974497402558909259883552576424768761354715586575868939070605548594012898778666975120891943662846258866008745003057326832146910830020880162343978272933503463968624419774562173087275100835

给出 pk = n、sk = φ = (p-1)(q-1)、c，要我们解出 m。

第二节：过程

（以下内容借助了AI辅助了解推导公式，密文的组成，我也初步理解了Paillier的加密解密）

这道题核心：Paillier 的密文由明文和盲化因子组成， φ 可以解出盲化因子

密文组成

c = (n+1)^m * r^n  mod n²

(n+1)^m用于承载明文 m。
r^n 是一个随机数盲化因子，每次加密都不同，作用是防止直接看出 m。

在模 n² 下对 (n+1)^m 做二项式展开：

(n+1)^m = 1 + m·n + C(m,2)n² + ... ≡ 1 + m·n  (mod n²)

从 n² 项开始，这些项全部变成 0
所以 模 n² 下 (n+1)^m 就是 1 + mn。

盲化因子是 r^n。如果对密文再取 e 次幂，盲化因子会变成 r^(n·e)。由欧拉定理，当 r 与 n 互素时，模 n² 的欧拉函数是

φ(n²) = n²(1-1/p)(1-1/q) = n(p-1)(q-1) = n·φ(n)

也就是说，取 e = φ 就够用了
而φ 题目又是直接给你的，因此解这道题就比较简单了

取 φ 次幂之后：

c^φ ≡ (1 + mn)^φ ≡ 1 + m·φ·n   (mod n²)

最后取出m
c^φ - 1 现在等于 m·φ·n，除以 n 得到 m·φ，再乘上 φ 在模 n 下的逆元即可：
最后的解题逻辑就是这样的

x = pow(c, phi, n*n)
L = (x - 1) // n              # 这里就是 m*phi mod n
m = L * pow(phi, -1, n) % n

脚本

from Crypto.Util.number import long_to_bytes

n = 153396211011150802817786720409497854855335807009308554623742617766338687957202189181399323636404512599740987069785432426073851317845807994224968901397122058915829056264442446377911660719557792351992477286189102744835410901118463454736945695694316266883012722210632296375435368060590606426473601302049741888291
phi = 153396211011150802817786720409497854855335807009308554623742617766338687957202189181399323636404512599740987069785432426073851317845807994224968901397122034114566998484506235039866557939786543950426114130461601701559155358442341547187940900303852879190072403580201918270223937947081447768438300627126739819352
c = 23454648989405998455733130363797025093915369298195332932532234307253066996867133848183383529921499342754070084339750432723101260156164092121746634956158905768156699869985985235027062789606436414762335952934868776399370328565784807635684203788254622367942236494702296234719951616388792136074106462217397877169534296587815760258248740713388625055612544133630291451685091324626452955144536285309806578562567743643707258971941866648097974497402558909259883552576424768761354715586575868939070605548594012898778666975120891943662846258866008745003057326832146910830020880162343978272933503463968624419774562173087275100835

n2 = n * n
x = pow(c, phi, n2)
L = (x - 1) // n
m = (L * pow(phi, -1, n)) % n
print(long_to_bytes(m))

b'flag{n0w_u_kn0w_P411113r_3ncryp710n_5ch3m3!!!}'