2026-11-09 18:30:30 +01:00
|
|
|
from random import randint
|
|
|
|
|
from sympy import discrete_log
|
|
|
|
|
from functools import reduce
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def KeyGen(g: int, q: int) -> (int, int):
|
|
|
|
|
"""Generate a secure key for ElGamal.
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group.
|
|
|
|
|
q: The order of a group.
|
|
|
|
|
Returns:
|
|
|
|
|
return A public key and a secret key.
|
|
|
|
|
"""
|
|
|
|
|
k = randint(2, q - 1)
|
|
|
|
|
return pow(g, k, q), k
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Encrypt_cc(g: int, q: int, pk: int, m: int) -> (int, int):
|
|
|
|
|
"""Encrypt data using a public key
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group
|
|
|
|
|
q: The order of the group
|
|
|
|
|
pk: The public key used to cipher the message
|
|
|
|
|
m: A message to cipher.
|
|
|
|
|
Returns:
|
|
|
|
|
The ciphered message.
|
|
|
|
|
"""
|
|
|
|
|
r = randint(2, q - 1)
|
|
|
|
|
return (pow(g, r, q), (m * pow(pk, r, q)))
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Decrypt_cc(g: int, q: int, sk: int, c: (int, int)) -> int:
|
|
|
|
|
"""Decrypt an ElGamal cipher using a public key
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group
|
|
|
|
|
q: The order of the group
|
|
|
|
|
sk: The secret key to use to decipher
|
|
|
|
|
c: A ciphered message to clarify
|
|
|
|
|
Returns:
|
|
|
|
|
The clear message.
|
|
|
|
|
"""
|
2026-11-09 21:00:09 +01:00
|
|
|
return (c[1] * pow(c[0], -sk, q)) % q
|
2026-11-09 18:30:30 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
def Encrypt_ce(g: int, q: int, pk: int, m: int) -> (int, int):
|
|
|
|
|
"""Encrypt an ElGamal cipher using a public key using exponential
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group
|
|
|
|
|
q: The order of the group
|
|
|
|
|
pk: The public key to use to cipher
|
|
|
|
|
m: A message to cipher
|
|
|
|
|
Returns:
|
|
|
|
|
The ciphered message.
|
|
|
|
|
"""
|
|
|
|
|
r = randint(2, q - 1)
|
|
|
|
|
return (pow(g, r, q), (pow(g, m, q) * pow(pk, r, q)) % q)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Decrypt_ce(g: int, q: int, sk: int, c: (int, int)) -> int:
|
|
|
|
|
"""Encrypt an ElGamal cipher using a public key (exponential)
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group
|
|
|
|
|
q: The order of the group
|
|
|
|
|
sk: The secret key to use to decipher
|
|
|
|
|
c: A ciphered message to decipher
|
|
|
|
|
Returns:
|
|
|
|
|
The clear message.
|
|
|
|
|
"""
|
|
|
|
|
s = c[1] * pow(c[0], -sk, q)
|
|
|
|
|
return discrete_log(q, s, g)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Add_cipher(c: list[(int, int)]) -> int:
|
|
|
|
|
"""Add multiple ciphers together into a new ElGamal cipher.
|
|
|
|
|
Args:
|
|
|
|
|
c: A list of ciphers.
|
|
|
|
|
Returns:
|
|
|
|
|
The accumulation of ciphers.
|
|
|
|
|
"""
|
|
|
|
|
return reduce(lambda x, y: x + y[1], c, 0)
|
|
|
|
|
|
|
|
|
|
|
2026-11-09 21:00:09 +01:00
|
|
|
def KeyGen_central(g: int, q: int, N: int) -> ([int], int):
|
|
|
|
|
"""Generate N private key fragments and a public key.
|
2026-11-09 18:30:30 +01:00
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group.
|
|
|
|
|
q: The order of a group.
|
2026-11-09 21:00:09 +01:00
|
|
|
N: The number of privkey fragment to generate.
|
2026-11-09 18:30:30 +01:00
|
|
|
Returns:
|
2026-11-09 21:00:09 +01:00
|
|
|
N private keys fragments and 1 public key.
|
2026-11-09 18:30:30 +01:00
|
|
|
"""
|
|
|
|
|
keys = []
|
2026-11-09 21:00:09 +01:00
|
|
|
K = 1
|
2026-11-09 18:30:30 +01:00
|
|
|
for i in range(N):
|
2026-11-09 21:00:09 +01:00
|
|
|
pk_i, sk_i = KeyGen(g, q)
|
|
|
|
|
keys.append(sk_i)
|
|
|
|
|
K = (K * pk_i) % q
|
|
|
|
|
return keys, K
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Decrypt_central_cc(g: int, q: int, k: [int], c: (int, int)) -> int:
|
|
|
|
|
"""Decipher a secret using multiple private key fragments.
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group.
|
|
|
|
|
q: The order of a group.
|
|
|
|
|
k: A list of private key fragments.
|
|
|
|
|
c: A cipher to decipher.
|
|
|
|
|
|
|
|
|
|
Returns:
|
|
|
|
|
The deciphered message in cleartext.
|
|
|
|
|
"""
|
|
|
|
|
Y = 1
|
|
|
|
|
for K_i in k:
|
|
|
|
|
Y = (Y * pow(c[0], K_i, q)) % q
|
|
|
|
|
return (c[1] * pow(Y, -1, q)) % q
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Decrypt_central_ce(g: int, q: int, k: [int], c: (int, int)) -> int:
|
|
|
|
|
"""Decipher a secret using multiple private key fragments (exponential).
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
g: A generator for the group.
|
|
|
|
|
q: The order of a group.
|
|
|
|
|
k: A list of private key fragments.
|
|
|
|
|
c: A cipher to decipher.
|
|
|
|
|
|
|
|
|
|
Returns:
|
|
|
|
|
The deciphered message in cleartext.
|
|
|
|
|
"""
|
|
|
|
|
Y = 1
|
|
|
|
|
for K_i in k:
|
|
|
|
|
Y = (Y * pow(c[0], K_i, q)) % q
|
|
|
|
|
M = (c[1] * pow(Y, -1, q)) % q
|
|
|
|
|
return discrete_log(q, M, g)
|