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
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
![{\displaystyle m={\frac {L(y)}{L(x)}}={\frac {y-1}{x-1}}{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32940bf5a296e8ee778e82fe3360166f64af2f73)
The corollary is a direct consequence of
.
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
![{\displaystyle (g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}g^{p(p-1)rpq}\equiv (g^{p-1})^{m}\mod p^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1864240be5911614d1be8fc4ba16dfa6fe3d23ce)
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
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
- 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.
Public-key cryptography |
---|
Algorithms | |
---|
Theory | |
---|
Standardization | |
---|
Topics | |
---|
|
|
|
---|
General | |
---|
Mathematics | |
---|
Category |
|