Okamoto–Uchiyama cryptosystem

The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$, where n is of the form p²q and p and q are large primes.

Operation

Like many public key cryptosystems, this scheme works in the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$. This scheme is homomorphic and hence malleable.

Key generation

A public/private key pair is generated as follows:

1. Generate two large primes ${\displaystyle p}$ and ${\displaystyle q}$.
2. Compute ${\displaystyle n=p^{2}q}$.
3. Choose a random integer ${\displaystyle g\in \{2\dots n-1\}}$ such that ${\displaystyle g^{p-1}\not \equiv 1\mod p^{2}}$.
4. Compute ${\displaystyle h=g^{n}{\bmod {n}}}$.

The public key is then ${\displaystyle (n,g,h)}$ and the private key is ${\displaystyle (p,q)}$.

Encryption

A message ${\displaystyle m<p}$ can be encrypted with the public key ${\displaystyle (n,g,h)}$ as follows.

1. Choose a random integer ${\displaystyle r\in \{1\dots n-1\}}$.
2. Compute ${\displaystyle c=g^{m}h^{r}{\bmod {n}}}$.

The value ${\displaystyle c}$ is the encryption of ${\displaystyle m}$.

Decryption

An encrypted message ${\displaystyle c}$ can be decrypted with the private key ${\displaystyle (p,q)}$ as follows.

1. Compute ${\displaystyle a={\frac {(c^{p-1}{\bmod {p^{2}}})-1}{p}}}$.
2. Compute ${\displaystyle b={\frac {(g^{p-1}{\bmod {p^{2}}})-1}{p}}}$. ${\displaystyle a}$ and ${\displaystyle b}$ will be integers.
3. Using the Extended Euclidean Algorithm, compute the inverse of ${\displaystyle b}$ modulo ${\displaystyle p}$:

   ${\displaystyle b'=b^{-1}{\bmod {p}}}$.

4. Compute ${\displaystyle m=ab'{\bmod {p}}}$.

The value ${\displaystyle m}$ is the decryption of ${\displaystyle c}$.

Example

Let ${\displaystyle p=3}$ and ${\displaystyle q=5}$. Then ${\displaystyle n=3^{2}\cdot 5=45}$. Select ${\displaystyle g=22}$. Then ${\displaystyle h=22^{45}{\bmod {4}}5=37}$.

Now to encrypt a message ${\displaystyle m=2}$, we pick a random ${\displaystyle r=13}$ and compute ${\displaystyle c=g^{m}h^{r}{\bmod {n}}=22^{2}37^{13}{\bmod {4}}5=43}$.

To decrypt the message 43, we compute

${\displaystyle a={\frac {(43^{2}{\bmod {3}}^{2})-1}{3}}=1}$.

${\displaystyle b={\frac {(22^{2}{\bmod {3}}^{2})-1}{3}}=2}$.

${\displaystyle b'=2^{-1}{\bmod {3}}=2}$.

And finally ${\displaystyle m=ab'=2}$.

Proof of correctness

We wish to prove that the value computed in the last decryption step, ${\displaystyle ab'{\bmod {p}}}$, is equal to the original message ${\displaystyle m}$. We have

${\displaystyle (g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}g^{p(p-1)rpq}\equiv (g^{p-1})^{m}\mod p^{2}}$

So to recover ${\displaystyle m}$ we need to take the discrete logarithm with base ${\displaystyle g^{p-1}}$.

The group

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}\simeq (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}\times (\mathbb {Z} /q\mathbb {Z} )^{*}}$.

We define H which is subgroup of ${\displaystyle \mathbb {Z} /p^{2}\mathbb {Z} ^{*}}$ and its cardinality is p-1

${\displaystyle H=\{x:x^{p-1}\mod p^{2}=1+rp,0<r<p\}}$.

For any element x in ${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}$, we have x^p−1 mod p² is in H, since p divides x^p−1 − 1.

The map ${\displaystyle L(x)={\frac {x-1}{p}}}$ should be thought of as a logarithm from the cyclic group H to the additive group ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$, and it is easy to check that L(ab) = L(a) + L(b), and that the L is an isomorphism between these two groups. As is the case with the usual logarithm, L(x)/L(g) is, in a sense, the logarithm of x with base g.

which is accomplished by

${\displaystyle {\frac {L\left((g^{p-1})^{m}\right)}{L(g^{p-1})}}=m\mod p.}$

Security

The security of the entire message can be shown to be equivalent to factoring n. The semantic security rests on the p-subgroup assumption, which assumes that it is difficult to determine whether an element x in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ is in the subgroup of order p. This is very similar to the quadratic residuosity problem and the higher residuosity problem.

References

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring". Advances in Cryptology — EUROCRYPT'98. Lecture Notes in Computer Science. 1403. Springer. pp. 308–318. doi:10.1007/BFb0054135.