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,
Contents
Scheme definition
Like many public key cryptosystems, this scheme works in the group
Key generation
A public/private key pair is generated as follows:
The public key is then (n, g, h) and the private key is the factors (p, q).
Message encryption
To encrypt a message m, where m is taken to be an element in
Message decryption
If we define
How the system works
The group
The group
For any element x in
The map L should be thought of as a logarithm from the cyclic group H to the additive group
We have
So to recover m we just need to take the logarithm with base gp−1, 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