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 p²q 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:

Generate two large primes $p$ and $q$ .
Compute $n=p^{2}q$ .
Choose a random integer $g\in \{2\dots n-1\}$ such that $g^{p-1}\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 \{1\dots n-1\}$ .
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 {(c^{p-1}{\bmod {p^{2}}})-1}{p}}$ .
Compute $b={\frac {(g^{p-1}{\bmod {p^{2}}})-1}{p}}$ . $a$ and $b$ will be integers.
Using the Extended Euclidean Algorithm, compute the inverse of $b$ modulo $p$ :
$b'=b^{-1}{\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^{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<r<p\}

.

For any element x in $(\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 $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.

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 {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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.