Okamoto–Uchiyama cryptosystem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

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

[further explanation needed]

Security[edit]

The security of the entire message can be shown to be equivalent to factoring n.[clarification needed] 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[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. 1403. Springer. pp. 308–318. doi:10.1007/BFb0054135.