前言

刷题的时候遇到了这个题[NISACTF 2022]public，在题目提示中他告诉了我是pailliar算法，所以就总结了一下。

什么是同态加密

同态加密是一种特殊的加密方法，它允许直接对加密数据执行计算，如加法和乘法，而计算过程不会泄露原文的任何信息。计算的结果仍然是加密的，拥有密钥的用户对处理过的密文数据进行解密后，得到的正好是处理后原文的结果。

又可以分为三种类型：半同态加密，部分同态加密，全同态加密。

半同态加密

只支持加法或者乘法中的一种运算。常见的就是RSA，Elgamal，Paillier。

部分同态加密

可同时支持加法和乘法运算，但支持的计算次数有限。

全同态加密

支持任意次的加法和乘法运算。

Paillier算法

密钥生成

1.随机挑选两个大素数p,q，满足gcd(p*q,(p-1)*(q-1))=1，且p和q的长度相同（安全性更高），同时|p|=|q|=r也保证了pq长度相同。

2.计算n=p*q,λ=lcm(p-1,q-1)，lcm指的是两个数的最小公倍数。

3.随机选择g∈Z*­n²,（n²在下面打不出来了啊啊啊），意思就是g是(0,n²)中的正整数，同时满足gcd(L(g**λ  mod  n²),n)=1。其实g=n+1，这个可以默认。

4.定义L函数，L(x)=(x-1)/n，计算μ=(L(g**λ   mod  n²))**-1  mod  n。

5.公钥为(n,g)，私钥为(λ,μ)。

注：在一些佬的文章中μ是没有的。

加密

1.明文m，满足m∈Zn

2.选择随机数r，满足r∈Z*n

3.计算密文c=g**m*r**n  mod n²

解密

1.输入密文c

2.计算明文消息m=L(c**λ  mod n²)*μ  mod n

解密的正确性

本质实际上是根据二项式定理然后去化简，因为wordpress真的不太好打符号，可以去康康这个。

例题

就拿nss的题目举例

task

import os
from Crypto.Util.number import *
flag=b"NSSCTF{xxxxxxxxxxxxxxxxxxx}"
p = getPrime(2048)
q = getPrime(2048)
n = p*q
g = n+1
flag = flag + os.urandom(256)
m = bytes_to_long(flag)
assert m < n
c=(pow(g,p,n*n)*pow(m,n,n*n))%(n*n)
print(f"c={str(c)}")
print(f"n={str(n)}")
print(f"hint={str(pow(m,n,n*n))}")
# c=
# n=
# hint=

思路：

给了hint=m**n  mod n²

还有c的值，那么就可以算出来g**p  mod n²的值

g=n+1

那么g**p=Σn+1

g**p-1=Σ(p*q),将这个式子除去n，再和n求gcd，就可以得到p

hint=m**n  mod n²可以当作一个rsa加密，利用这个式子就可以求出来m

exp

c=
n=
hint=

from Crypto.Util.number import *
import gmpy2

x = gmpy2.invert(hint,n**2)
temp = c * x % n**2

p = gmpy2.gcd(n,(temp-1)//n)
q = n // p
d = gmpy2.invert(n,(p-1)*(q-1))
m = pow(hint,d,n)
print(long_to_bytes(m))