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, \(({\mathbb {Z}}/n{\mathbb {Z}})^{*}\) [theory]. \(n\) uses the calculation of \(p^2q\) and where \(p\) and \(q\) are large prime numbers [paper]:
Okamoto–Uchiyama |
Key generation
A public/private key pair is generated as follows:
- Generate large primes p and q and set \(n = p^2 q\).
- \( g\in ({\mathbb {Z}}/n{\mathbb {Z}})^{*}\) such that \(g^{p-1}\neq 1\mod p^{2}\).
- Let \(h = g^n \pmod n\).
The public key is \((n, g, h)\) and then the private key is \((p, q)\).
Message encryption
To encrypt a message m, where m is taken to be an element in \(2^{k-1}\).
Select \( r\in \mathbb {Z} /n\mathbb {Z}\) at random.
The cipher is then: \(C=g^{m}h^{r} \pmod n\)
Message decryption
Next we define the function of: \(L(x)=\frac{x-1}{p}\).
We then decrypt with \(m={\frac {L\left(C^{{p-1}}\mod p^{2}\right)}{L\left(g^{{p-1}}\mod p^{2}\right)}} \pmod p\)
Coding
The coding is:
import libnum from Crypto.Util.number import * import hashlib import sys 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 if (k1): m=str(sys.argv[1]) if (len(sys.argv)>2): prime=int(sys.argv[2]) n,g,h,p,q=gen_key(prime) print("Message=",m) print("==Public key====") print("n=",n) print("g=",g) print("h=",h) print("==Private key (%d-bit prime)===" % prime) print("p=",p) print("q=",q) c=encrypt(m.encode(), n, g, h) print("==Cipher===") print("c=",c) print("Decrypted=",decrypt(c,p).decode()[:len(m)]))]
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
Reference
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.
Coding example [here].