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, , 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 . This scheme is homomorphic and hence malleable.

Key generation
A public/private key pair is generated as follows:

 Generate two large primes  and .
 Compute .
 Choose a random integer  such that .
 Compute .

The public key is then  and the private key is .

Encryption
A message  can be encrypted with the public key  as follows.

 Choose a random integer .
 Compute .
The value  is the encryption of .

Decryption
An encrypted message  can be decrypted with the private key  as follows.
 Compute .
 Compute .  and  will be integers.
 Using the Extended Euclidean Algorithm, compute the inverse of  modulo :
.
 Compute .
The value  is the decryption of .

Example
Let  and . Then . Select . Then .

Now to encrypt a message , we pick a random  and compute .

To decrypt the message 43, we compute
 .
 .
 .
And finally .

Proof of correctness
We wish to prove that the value computed in the last decryption step, , is equal to the original message . We have

So to recover  we need to take the discrete logarithm with base .

The group
.

We define H which is subgroup of  and its cardinality is p-1

.

For any element x in , we have xp−1 mod p2 is in H, since p divides xp−1 − 1.

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

which is accomplished by

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

References

Public-key encryption schemes