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:
  1. Generate two large primes and.
  2. Compute.
  3. Choose a random integer such that.
  4. Compute.
The public key is then and the private key is.

Encryption

A message can be encrypted with the public key as follows.
  1. Choose a random integer.
  2. Compute.
The value is the encryption of.

Decryption

An encrypted message can be decrypted with the private key as follows.
  1. Compute.
  2. Compute. and will be integers.
  3. Using the Extended Euclidean Algorithm, compute the inverse of modulo :
  4. :.
  5. 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 = L + L, and that the L is an isomorphism between these two groups. As is the case with the usual logarithm, L/L 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.