Powered by
Share this page on
Article provided by Wikipedia

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, , where n is of the form p2q and p and q are large "primes.


Scheme definition[edit]

Like many "public key cryptosystems, this scheme works in the group . A fundamental difference of this cryptosystem is that here n is an integer of the form p2q, where p and q are large "primes. This scheme is "homomorphic and hence "malleable.

Key generation[edit]

A public/private key pair is generated as follows:

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

Message encryption[edit]

To encrypt a message m, where m is taken to be an element in

Message decryption[edit]

If we define , then decryption becomes

How the system works[edit]

The group


The group has a unique subgroup of order p, call it H. By the uniqueness of H, we must have


For any element x in , 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 , 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

So to recover m we just need to take the logarithm with base gp−1, which is accomplished by


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 is in the subgroup of order p. This is very similar to the "quadratic residuosity problem and the "higher residuosity problem.


) ) WikipediaAudio is not affiliated with Wikipedia or the WikiMedia Foundation.