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.

Background

edit

Let   be an odd prime. Define  .   is a subgroup of   with   (the elements of   are  ).

Define   by  

  is a homomorphism between   and the additive group  : that is,  . Since   is bijective, it is an isomorphism.

One can now show the following as a corollary:

Let   such that   and   for  . Then

 

The corollary is a direct consequence of  .

Operation

edit

Like many public key cryptosystems, this scheme works in the group  . This scheme is homomorphic and hence malleable.

Key generation

edit

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

edit

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

edit

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

The value   is the decryption of  .

Example

edit

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

edit

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  . This can be done by applying  , as follows.

By Fermat's little theorem,  . Since   one can write   with  . Then   and the corollary from earlier applies:  .

Security

edit

Inverting the encryption function can be shown to be as hard as factoring n, meaning that if an adversary could recover the entire message from the encryption of the message they would be able to factor n. The semantic security (meaning adversaries cannot recover any information about the message from the encryption) 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

edit
  • Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring". Advances in Cryptology – EUROCRYPT'98. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 308–318. doi:10.1007/BFb0054135. ISBN 978-3-540-64518-4.