# 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, $(\mathbb {Z} /n\mathbb {Z} )^{*}$ , where n is of the form p2q and p and q are large primes.

## Operation

Like many public key cryptosystems, this scheme works in the group $(\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 $p$ and $q$ .
2. Compute $n=p^{2}q$ .
3. Choose a random integer $g\in \{2\dots n-1\}$ such that $g^{p-1}\not \equiv 1\mod p^{2}$ .
4. Compute $h=g^{n}{\bmod {n}}$ .

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

### Encryption

A message $m can be encrypted with the public key $(n,g,h)$ as follows.

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

The value $c$ is the encryption of $m$ .

### Decryption

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

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

The value $m$ is the decryption of $c$ .

## Example

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

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

To decrypt the message 43, we compute

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

And finally $m=ab'=2$ .

## Proof of correctness

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

$(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 $m$ we need to take the discrete logarithm with base $g^{p-1}$ .

The group

$(\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 $\mathbb {Z} /p^{2}\mathbb {Z} ^{*}$ and its cardinality is p-1

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

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

The map $L(x)={\frac {x-1}{p}}$ should be thought of as a logarithm from the cyclic group H to the additive group $\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

${\frac {L\left((g^{p-1})^{m}\right)}{L(g^{p-1})}}=m\mod p.$ [further explanation needed]

## Security

The security of the entire message can be shown to be equivalent to factoring n.[clarification needed] The semantic security rests on the p-subgroup assumption, which assumes that it is difficult to determine whether an element x in $(\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.