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/n\mathbb)^*$, 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 $(\mathbb/n\mathbb)^*$. This scheme is homomorphic and hence malleable.

Key generation

A public/private key pair is generated as follows:

# Generate two large primes $p$ and $q$.
# Compute $n = p^2 q$.
# Choose a random integer $g \in \$ such that $g^ \not\equiv 1 \mod p^2$.
# 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 < p$ can be encrypted with the public key $(n,g,h)$ as follows.

# Choose a random integer $r \in \$.
# 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.
# Compute $a = \frac$.
# Compute $b = \frac$. $a$ and $b$ will be integers.
# Using the Extended Euclidean Algorithm, compute the inverse of $b$ modulo $p$:
#:$b' = b^ \bmod p$.
# 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^ \bmod 45 = 37$.

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

To decrypt the message 43, we compute
: $a = \frac = 1$.
: $b = \frac = 2$.
: $b' = 2^ \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^mh^r)^ \equiv (g^m g^)^ \equiv (g^)^m g^ \equiv (g^)^m \mod p^2$

So to recover $m$ we need to take the discrete logarithm with base $g^$.

The group
:$(\Z/n\Z)^* \simeq (\mathbb/p^2\mathbb)^* \times (\mathbb/q\mathbb)^*$.

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

:$H = \$.

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

The map $L(x) = \frac$ should be thought of as a logarithm from the cyclic group ''H'' to the additive group $\mathbb/p\mathbb$, 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 = 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 $(\mathbb/n\mathbb)^*$ is in the subgroup of order ''p''. This is very similar to the quadratic residuosity problem and the higher residuosity problem.

References

*

{{DEFAULTSORT:Okamoto-Uchiyama cryptosystem
Public-key encryption schemes