Okamoto–Uchiyama Crypto
Published in
2 min readMay 18, 2019
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…