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
        private["g"] = g

        return public,private

def generate_random_key(n) -> int:

        return random.randint(1, n - 1)

def encrypt(plaintext: int, public) -> int:


        g = public["g"]
        n = public["n"]
        h = public["h"]
        r = generate_random_key(n)


        return (pow(g, plaintext, n) * pow(h, r, n)) % n

def decrypt(ciphertext: int,private):

        p = private["p"]
        g = private["g"]

        a = lx(p,pow(ciphertext, p - 1, p * p))
        b = lx(p,pow(g, p - 1, p * p))
        return (a * pow(b, -1, p)) % p

def lx(p: int,x: int) -> int:

        if x % p != 1:
            print(f"Input passed to lx ({x}) must be identical to 1 in modulo {p}")
        if math.gcd(x, p * p) != 1:
            print(f"gcd({x}, {p}^2) must be equal to 1")
        y = (x - 1) // p
        assert y - int(y) == 0
        return int(y)

m=17
size=256

if (len(sys.argv)>1):
        m=int(sys.argv[1])
if (len(sys.argv)>2):
        size=int(sys.argv[2])

public,private=generate_keys(size)
print(f"Private key: {private}")
print(f"Public key: {public}")

c=encrypt(m,public)
dec=decrypt(c,private)


print(f"\nMessage: {m}")
print(f"\nCipher: {c}")
print(f"Decrypted: {dec}")

A sample run is [here]:

Private key: 
{'p': 73506797133534210339939825224991990737, 
'q': 63535511110237257160981124879281539629, 
'g': 69428159835846308998731703183367263706351611577996600740389770407534417982262529834048417964384309212216862995975}

Public key: 
{'n': 343298201155602460395245488500596527939778773205351698557568312378814813995896542172306449462451248687728199284301, 
'g': 69428159835846308998731703183367263706351611577996600740389770407534417982262529834048417964384309212216862995975, 
'h': 158325815464233978201820737393431723061447290724824551595748800077766086735665678994002849738085177127192155091280}

Message: 17

Cipher: 128628502757750375109393918843556717745310373866813512061779851892050763428967444015087078819353781767843293643595
Decrypted: 17

While created in 1998, the Okamoto–Uchiyama has recently been applied to homomorphic encryption. For this, we basically multiply the ciphertext values, and which will perform an additional of the plaintext values.

The homomorphic example is:

Okamoto Uchiyama Public Key Encryption

References

[1] Okamoto, T., & Uchiyama, S. (1998, May). A new public-key cryptosystem as secure as factoring. In International conference on the theory and applications of cryptographic techniques (pp. 308–318). Springer, Berlin, Heidelberg.