 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

Okamoto–Uchiyama cryptosystem

Article Id: WHEBN0007503084
Reproduction Date:

 Title: Okamoto–Uchiyama cryptosystem Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Okamoto–Uchiyama cryptosystem

The Okamoto–Uchiyama cryptosystem was discovered 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.

Contents

• Scheme definition 1
• Key generation 1.1
• Message encryption 1.2
• Message decryption 1.3
• How the system works 2
• Security 3
• References 4

Scheme definition

Like many public key cryptosystems, this scheme works in the group (\mathbb{Z}/n\mathbb{Z})^*. A fundamental difference of this cryptosystem is that here n is a of the form p2q, where p and q are large primes. This scheme is homomorphic and hence malleable.

Key generation

A public/private key pair is generated as follows:

• Generate large primes p and q and set n=p^2 q.
• Choose g \in (\mathbb{Z}/n\mathbb{Z})^* such that g^p \neq 1 \mod p^2.
• Let h = gn mod n.

The public key is then (ngh) and the private key is the factors (pq).

Message encryption

To encrypt a message m, where m is taken to be an element in \mathbb{Z}/p\mathbb{Z}

• Select r \in \mathbb{Z}/n\mathbb{Z} at random. Set
C = g^m h^r \mod n

Message decryption

If we define L(x) = \frac{x-1}{p}, then decryption becomes

m = \frac{L\left(C^{p-1} \mod p^2\right)}{L\left(g^{p-1} \mod p^2 \right)} \mod p

How the system works

The group

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

The group (\mathbb{Z}/p^2\mathbb{Z})^* has a unique subgroup of order p, call it H. By the uniqueness of H, we must have

H = \{ x : x^p \equiv 1 \mod p \}.

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

We have

(g^mh^r)^{p-1} = (g^m g^{nr})^{p-1} = (g^{p-1})^m g^{p(p-1)rpq} = (g^{p-1})^m \mod p^2.

So to recover m we just need to take the logarithm with base gp−1, 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.