同态加密_学习笔记

半同态加密

Paillier加密系统

基本介绍

1.密钥生成 Paillier加密系统的密钥生成过程需要选择两个大素数，并使用它们来生成公钥和私钥。

• 选择两个大素数 $ p $ 和 $ q $。

• 计算模数 $ n = p \times q $，其中 $ n $ 是模数，公钥中的一个部分。

• 计算加密系统的秘密参数 $ \lambda(n) = \text{lcm}(p-1, q-1) $，其中 $ \text{lcm} $ 是最小公倍数，$ \lambda(n) $ 是加密系统的秘密参数。

• 选择一个随机整数 $ g $，要求 $ g $ 的阶为 $ n $ 的整数倍，$g^\lambda=1+an\ mod\ n^2$,$gcd(L(g^\lambda\ mod\ n^2),n)=1$,一般而言$g=n+1$是一个比较选择
• 计算 $ \mu = \left( L(g^{\lambda(n)} \mod n^2) \right)^{-1} \mod n $，其中 $ L(x) = \frac{x - 1}{n} $ 是一个辅助函数。

最终，Paillier的公钥是$(n,g)$,私钥是$(\lambda,\mu)$

2.加密 要求密文$m < n$

• 选择一个随机整数 $ r $,要求$ r < n $

• 加密 $ c=g^m\cdot r^n mod\ n^2 $

3.解密

• 解密 $m=L(c^\lambda \ mod\ n^2)\cdot\mu \ mod\ n $

4.同态性 这个系统仅有加法同态性 对密文$m1\ m2$

• $c_1=g^{m_1}\cdot r_1^{n}\ mod\ n^2$
• $c_2=g^{m_2}\cdot r_2^{n}\ mod\ n^2$

同态加法

• $c_3=c_1 \cdot c_2\ mod\ n^2 $

证明:

• $c_3=g^{m_1+m_2}\cdot (r_1\cdot r_2)^{n}\ mod\ n^2$

设$r_3=r_1\cdot r_2$

• 则$c_3=g^{m_1+m_2}\cdot (r_3)^{n}\ mod\ n^2$

对$c_3$解密:

• $m_3=L(c_3^\lambda \ mod\ n^2)\cdot \mu \ mod\ n $
• $m_3=L((g^{m_1+m_2}\cdot (r_3)^{n}\ mod\ n^2)^\lambda \ mod\ n^2)\cdot \mu \ mod\ n$
• $m_3=L((g^{(m_1+m_2)\cdot \lambda}\cdot (r_3)^{n\cdot \lambda}) \ mod\ n^2)\cdot \mu \ mod\ n$

利用$r^{n\cdot \lambda}=1\ mod\ n^2$

• $m_3=L((g^{(m_1+m_2)\cdot \lambda}) \ mod\ n^2)\cdot \mu \ mod\ n$

代入解密函数$L(x)=(x-1)/n$，注意以下就$g=n+1$进行讨论 分析$g^{m\cdot \lambda}\ mod\ n^2$

• $g^{m\cdot \lambda}\ mod\ n^2=(n+1)^{m\cdot \lambda}\ mod\ n^2$

二项式定理

• $(n+1)^{m\cdot \lambda}\ mod\ n^2=1+(m\cdot \lambda)\cdot n \ mod\ n^2$ #高阶项被约掉了

代入$L(x)=(x-1)/n$

• $L((g^{(m_1+m_2)\cdot \lambda}) \ mod\ n^2)=L(1+(m\cdot \lambda)\cdot n \ mod\ n^2)=m\cdot \lambda\ mod\ n$

所以

• $L((g^{(m_1+m_2)\cdot \lambda}) \ mod\ n^2)=m\cdot \lambda\ mod\ n$
• $m_3=L((g^{(m_1+m_2)\cdot \lambda}) \ mod\ n^2)\cdot \mu \ mod\ n=(m_1+m_2)\cdot \lambda\cdot \mu\ mod\ n$

利用$\mu$的定义$ \mu = \left( L(g^{\lambda(n)} \mod n^2) \right)^{-1} \mod n $

• $m_3=m_1+m_2\ mod\ n$

得证 其实上面的证明就是对解密的证明，如果解密已被证明,在令$m_3=L((g^{(m_1+m_2)\cdot \lambda}\cdot (r_3)^{n\cdot \lambda}) \ mod\ n^2)\cdot \mu \ mod\ n$已经可以有$m_3=m_1+m_2$

python实现

from gmpy2 import *  
import libnum  
from Crypto.Util.number import *  
import random  
# 密钥生成函数
def generate_keys(n):
    """
    生成 Paillier 加密系统的公钥和私钥。
    
    参数:
        n (int): 素数的位数。
    
    返回:
        public_key (tuple): 公钥 (n, g)。
        private_key (tuple): 私钥 (lambda_n, mu)。
    """
    p = getPrime(n)  
    q = getPrime(n)  
    while p == q:  
        q = getPrime(n)
    n = p * q  
    lambda_n = lcm(p - 1, q - 1)  
    g = n + 1  
    mu = gmpy2.invert((pow(g, lambda_n, n**2) - 1) // n, n)
    return (n, g), (lambda_n, mu)  
# 加密函数
def encrypt(m, public_key):
    """
    使用公钥加密明文 m。
    
    参数:
        m (int): 明文。
        public_key (tuple): 公钥 (n, g)。
    
    返回:
        c (int): 密文。
    """
    n, g = public_key  
    r = random.randint(1, n - 1)  
    c = (pow(g, m, n**2) * pow(r, n, n**2)) % n**2
    return c  

# 解密函数
def decrypt(c, private_key, public_key):
    """
    使用私钥解密密文 c。
    
    参数:
        c (int): 密文。
        private_key (tuple): 私钥 (lambda_n, mu)。
        public_key (tuple): 公钥 (n, g)。
    
    返回:
        m (int): 解密后的明文。
    """
    n, g = public_key  
    lambda_n, mu = private_key  
    m = ((pow(c, lambda_n, n**2) - 1) // n * mu) % n
    return m  

# 同态加法函数
def evaladd(c1, c2, public_key):
    """
    对两个密文进行同态加法运算。
    
    参数:
        c1 (int): 第一个密文。
        c2 (int): 第二个密文。
        public_key (tuple): 公钥 (n, g)。
    
    返回:
        c (int): 同态加法后的密文。
    """
    n, g = public_key  
    c = (c1 * c2) % n**2
    return c 

# 主程序
if __name__ == '__main__':
    # 生成公钥和私钥
    public_key, private_key = generate_keys(128)
    
    # 生成两个随机明文
    m_1 = random.randint(1, 100321331)
    m_2 = random.randint(1, 100321331)
    m = m_1 + m_2  # 计算明文的和
    
    # 加密明文
    c_1 = encrypt(m_1, public_key)
    c_2 = encrypt(m_2, public_key)
    
    # 对密文进行同态加法
    c = evaladd(c_1, c_2, public_key)
    
    # 解密密文
    decrypted_m = decrypt(c, private_key, public_key)
    
    # 输出结果
    print(f"明文: {m_1}+{m_2}={m}, 加密后: {c}, 解密后: {decrypted_m}")

ElGamal加密系统

基本介绍

它基于 Diffie-Hellman 密钥交换协议，主要用于加密和数字签名。ElGamal 算法的安全性依赖于离散对数问题的难解性。

1.密钥生成

• 选择一个大素数 $ p $

• 选择一个生成元 $ g $,生成元$g$是$p$的一个原根即$g$的阶是$\phi(p)=p-1 $

• 选择一个私钥整数$x$，$1<x<p-1$

• 计算公钥，$y=g^x\ mod\ p$ 最终公钥是$(p,g,y)$,私钥为$x$

2.加密过程

• 选择一个随机整数$k,1< k < p-1 $
• 计算密文的第一部分$c_1,c_1=g^k\ mod\ p$
• 计算密文的第二部分$c_2,c_2=M*y^k\ mod\ p$ 密文为$(c_1,c_2)$

3.解密过程

• 计算$s=c_1^x\ mod\ p$
• 计算密文$M=s^{-1}*c_2\ mod\ p$

4.同态验证(乘法)

• 记消息$m^1,m^2$,有对应密文对$(c_1^1,c_2^1),(c_1^2,c_2^2)$
• 同态乘法为对应的模乘法，有$c_1^3=c_1^1c_1^2,\ \ c_2^3=c_2^1c_2^2$
• 代入加密，有 $c_1^3=g^{k_1}g^{k_2}\ mod\ p=g^{k_3}\ mod\ p,k_3=k_1k_2$ $c_2^3=m_1m_2y^{g_3}\ mod\ p$
• 分析对应关系显然$m_3=m_1*m_2$,得证

python实现

from gmpy2 import *  
from Crypto.Util.number import *  
import random 
from sage.all import *

class ElGama:
    def __init__(self,n):
        self.p = getPrime(n)
        self.g=primitive_root(self.p)
        self.x=randint(1,(self.p-1))
        self.y=pow(self.g,self.x,self.p)

    def encrypt(self,m):   
        k=randint(1,self.p-1)
        c_1=pow(self.g,k,self.p)
        c_2=pow(self.y,k,self.p)*m%self.p
        return (c_1,c_2)
    
    def decrypt(self,c):  
        c_1,c_2=c
        s = pow(c_1, self.x, self.p)
        s_inv=gmpy2.invert(s,self.p)
        m=c_2*s_inv%self.p
        return m
    
elg=ElGama(32)
print(elg.decrypt(elg.encrypt(123)))

全同态加密