Okamoto–Uchiyama Crypto

The Okamoto–Uchiyama 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 implementation of the key pair generation is:

The coding for this is then [here]:

import gmpy2
from Crypto.Util.number import *
import hashlib
 
def gen_key(k):
    p = getPrime(k)
    q = getPrime(k)
    n = p**2 * q
    while True:
        g = getRandomRange(1, n-1)
        g_p = pow(g, p-1, p**2)
        if pow(g_p, p, p**2) == 1:
            break
    r = getRandomRange(1, n-1)
    h = pow(r, n, n)
    return (n, g, h,p,q)

 
def encrypt(m, n, g, h):
    Mlen = len(bin(bytes_to_long(m))[2:])
    k = len(bin(n)[2:])/3
    rlen = getRandomRange(1, k - Mlen)
    R = long_to_bytes(getRandomInteger(rlen))
    r = bytes_to_long(hashlib.sha256(m + R).digest())
    c = (pow(g, bytes_to_long(m + R), n) * pow(h, r, n)) % n
    return c

def L(x, p):
    return (x-1)/p
 
def res(x, y, p):
    return x*(gmpy2.invert(y, p))


n,g,h,p,q=gen_key(80)

m="Hello"

if (len(sys.argv)>1):
    m=str(sys.argv[1])

c=encrypt(m, n, g, h)

print…