Okamoto–Uchiyama Crypto

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 "Message=",m
print "==Public key==="
print "n=",n
print "g=",g
print "h=",h
print "==Private key (80-bit prime)==="
print "p=",p
print "q=",q
print "==Cipher==="
print "c=",c

cp = pow(c, p-1, p**2)
gp = pow(g, p-1, p**2)
 
x = res(L(cp, p), L(gp, p), p) % p
print "Decrypted=",long_to_bytes(x)[:len(m)]

In this case we use 80-bit prime numbers. A sample run is:

Message= hello
==Public key===
n= 357144329288820404004007663971674051954729307045939508876563494539894121
g= 74558721989742112251918129606604269193466856239270146229917361695316131
h= 291137566036067020888880069146237786455056208502803564840520325588303272
==Private key (80-bit prime)===
p= 674079976099181585579683
q= 785997031903545276515489
==Cipher===
c= 329673349781747004422270221674380845959397726633927390038149409566494210
Decrypted= hello

While created in 1998, the Okamoto–Uchiyama has recently been applied into homomorphic encryption with:

Suwandi, R., Nasution, S. M., & Azmi, F. (2016, October). Okamoto-Uchiyama homomorphic encryption algorithm implementation in e-voting system. In 2016 International Conference on Informatics and Computing (ICIC) (pp. 329–333). IEEE.

References

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.