同态加密 ElGamal方案

原理

ElGamal方案

• generate_keys(p,g)

$$\begin{align} &x\in[1,p-1]\\ &y=g^x\ (mod\ p)\\ &\rightarrow x,y\\ \end{align}$$

• encrypt(m,p,g,y)

  $$\begin{align} &k\in[1,p-1]\\ &a=g^k\ (mod\ p)\\ &b=(y^k\ (mod\ p))*m\ (mod\ p)\\ &\rightarrow a,b\\ \end{align}$$

• decrypt(c,x,p)

  $$\begin{align} &c=(a,b)\\ &m=(a^{p-1-x}\ (mod\ p)*b)\ (mod\ p)\\ &\rightarrow m\\ \end{align}$$

• 同态加密过程

  • 生成一个大素数和生成元
  • 用generate_keys(p,g)生成公钥和私钥
  • 将字节串明文转换为大整数
  • 用encrypt(m,p,g,y)进行加密
• 同态解密过程
  • 用decrypt(c,x,p)进行解密

乘法同态

• homomorphic_addition(c1, c2, p)

$$\begin{align} &c_1=(a_1,b_1)\\ &c_2=(a_2,b_2)\\ &c = (a_1a_2,b_1b_2)\ (mod\ p)\\ &\rightarrow c \end{align}$$

• 加密过程
  • 选择明文
  • 用encrypt(m, p, g, y)分别对进行加密，得到
  • 用homomorphic_addition(c1, c2, p)计算得到密文
• 解密过程
  • 用decrypt(c3, x, p)进行解密

EXP

import random
from Crypto.Util.number import *
from hashlib import sha256

def generate_keys(p, g):
    """生成公钥和私钥"""
    x = random.randint(1, p-1)
    y = pow(g, x, p)
    return (x, y)

def encrypt(m, p, g, y):
    """加密明文m"""
    k = random.randint(1, p-1)
    a = pow(g, k, p)
    b = (pow(y, k, p) * m) % p
    return (a, b)

def decrypt(c, x, p):
    """解密密文c"""
    a, b = c
    m = (b * pow(a, p-1-x, p)) % p
    return m

# 选择大素数p和生成元g
p = getPrime(215)
g = 3

# 生成公钥和私钥
x, y = generate_keys(p, g)

# 要加密的明文
pt = b'flag{f1rst_attempt}'
m = bytes_to_long(pt)

# 加密明文
c = encrypt(m, p, g, y)

# 解密密文
m_decrypted = decrypt(c, x, p)
plain_text=long_to_bytes(m_decrypted)

print("原始消息：", pt, m)
print("加密后的消息：", c)
print("解密后的消息：", m_decrypted, plain_text)

def homomorphic_addition(c1, c2, p):
    """密文的乘法同态"""
    a1, b1 = c1
    a2, b2 = c2
    c = ((a1 * a2) % p, (b1 * b2) % p)
    return c

# 选择两个明文m1和m2
m1 = 12345
m2 = 67890

# 分别加密明文m1和m2
c1 = encrypt(m1, p, g, y)
c2 = encrypt(m2, p, g, y)

# 对密文进行加法同态
c3 = homomorphic_addition(c1, c2, p)

# 解密得到加法结果
m3 = decrypt(c3, x, p)

print("加密前的明文：", m1, m2, m1*m2)
print("加密后的密文：", c1, c2)
print("同态加密后的密文：", c3)
print("解密后的明文：", m3)

Output

原始消息： b'flag{f1rst_attempt}' 2284117282071553800931956111894576012213646461
加密后的消息： (34326925946024248202348149516524597794238307293963587312465083699, 29257544864745339573358716821088326225971289538713175924341045784)
解密后的消息： 2284117282071553800931956111894576012213646461 b'flag{f1rst_attempt}'
加密前的明文： 12345 67890 838102050
加密后的密文： (37592138195462689660118434358852570152863680935153357241889524484, 1881167267842650302000965248563504534698498707009490637556715361) (10920357203713901658735049057071888229387493718439911523237682598, 19754766075170064385339139856259981647190642647308101159400975124)
同态加密后的密文： (25162036149156949807143289802167075308069263753806093110671488815, 28248364394465727513102472477303058997839331903759424249041835410)
解密后的明文： 838102050

不过，有一种简单的技巧可以实现基本的加法同态，它被称为“乘法同态转化”。具体方法是，对于明文和，我们可以选择两个随机数和，然后计算和，然后对密文和进行乘法同态运算，得到密文，然后解密得到的明文就是。因此，我们可以通过减去和来获得的值，从而实现加法同态。