Okamoto–Uchiyama Public Key Encryption And Additive Homomorphic Encryption

The Okamoto–Uchiyama [1] technique is a public key encryption system created by Tatsuaki Okamoto and Shigenori Uchiyama. It uses the multiplicative group of integers modulo n, (ℤ/nℤ)∗. n is the calculation of p²q and where p and q are large prime numbers [paper]:

The coding for this is then [here]:

import sympy
import random
import math

# Based on https://github.com/serengil/LightPHE/blob/master/lightphe/cryptosystems/OkamotoUchiyama.py

def generate_keys(key_size: int) -> dict:


        private = {}
        public = {}


        p = sympy.randprime(200, 2 ** int(key_size / 2) - 1)


        q = sympy.randprime(200, 2 ** int(key_size / 2) - 1)

        n = p * p * q

        g = random.randint(2, n)

        if pow(g, p - 1, p * p) == 1:
            raise ValueError("Fermat's Little Theorem must be satisfied")

        h = pow(g, n, n)

        public["n"] = n
        public["g"] = g
        public["h"] = h
        private["p"] = p
        private["q"] = q…