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 ,
(
Z
/
n
Z
)
∗
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
, where n is of the form p 2 q and p and q are large primes .
Operation [ edit ]
Like many public key cryptosystems , this scheme works in the group
(
Z
/
n
Z
)
∗
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
. This scheme is homomorphic and hence malleable .
Key generation [ edit ]
A public/private key pair is generated as follows:
Generate two large primes
p
{\displaystyle p}
and
q
{\displaystyle q}
.
Compute
n
=
p
2
q
{\displaystyle n=p^{2}q}
.
Choose a random integer
g
∈
{
2
…
n
−
1
}
{\displaystyle g\in \{2\dots n-1\}}
such that
g
p
−
1
≢
1
mod
p
2
{\displaystyle g^{p-1}\not \equiv 1\mod p^{2}}
.
Compute
h
=
g
n
mod
n
{\displaystyle h=g^{n}{\bmod {n}}}
.
The public key is then
(
n
,
g
,
h
)
{\displaystyle (n,g,h)}
and the private key is
(
p
,
q
)
{\displaystyle (p,q)}
.
Encryption [ edit ]
A message
m
<
p
{\displaystyle m<p}
can be encrypted with the public key
(
n
,
g
,
h
)
{\displaystyle (n,g,h)}
as follows.
Choose a random integer
r
∈
{
1
…
n
−
1
}
{\displaystyle r\in \{1\dots n-1\}}
.
Compute
c
=
g
m
h
r
mod
n
{\displaystyle c=g^{m}h^{r}{\bmod {n}}}
.
The value
c
{\displaystyle c}
is the encryption of
m
{\displaystyle m}
.
Decryption [ edit ]
An encrypted message
c
{\displaystyle c}
can be decrypted with the private key
(
p
,
q
)
{\displaystyle (p,q)}
as follows.
Compute
a
=
(
c
p
−
1
mod
p
2
)
−
1
p
{\displaystyle a={\frac {(c^{p-1}{\bmod {p^{2}}})-1}{p}}}
.
Compute
b
=
(
g
p
−
1
mod
p
2
)
−
1
p
{\displaystyle b={\frac {(g^{p-1}{\bmod {p^{2}}})-1}{p}}}
.
a
{\displaystyle a}
and
b
{\displaystyle b}
will be integers.
Using the Extended Euclidean Algorithm , compute the inverse of
b
{\displaystyle b}
modulo
p
{\displaystyle p}
:
b
′
=
b
−
1
mod
p
{\displaystyle b'=b^{-1}{\bmod {p}}}
.
Compute
m
=
a
b
′
mod
p
{\displaystyle m=ab'{\bmod {p}}}
.
The value
m
{\displaystyle m}
is the decryption of
c
{\displaystyle c}
.
Example [ edit ]
Let
p
=
3
{\displaystyle p=3}
and
q
=
5
{\displaystyle q=5}
. Then
n
=
3
2
⋅
5
=
45
{\displaystyle n=3^{2}\cdot 5=45}
. Select
g
=
22
{\displaystyle g=22}
. Then
h
=
22
45
mod
4
5
=
37
{\displaystyle h=22^{45}{\bmod {4}}5=37}
.
Now to encrypt a message
m
=
2
{\displaystyle m=2}
, we pick a random
r
=
13
{\displaystyle r=13}
and compute
c
=
g
m
h
r
mod
n
=
22
2
37
13
mod
4
5
=
43
{\displaystyle c=g^{m}h^{r}{\bmod {n}}=22^{2}37^{13}{\bmod {4}}5=43}
.
To decrypt the message 43, we compute
a
=
(
43
2
mod
3
2
)
−
1
3
=
1
{\displaystyle a={\frac {(43^{2}{\bmod {3}}^{2})-1}{3}}=1}
.
b
=
(
22
2
mod
3
2
)
−
1
3
=
2
{\displaystyle b={\frac {(22^{2}{\bmod {3}}^{2})-1}{3}}=2}
.
b
′
=
2
−
1
mod
3
=
2
{\displaystyle b'=2^{-1}{\bmod {3}}=2}
.
And finally
m
=
a
b
′
=
2
{\displaystyle m=ab'=2}
.
Proof of correctness [ edit ]
We wish to prove that the value computed in the last decryption step,
a
b
′
mod
p
{\displaystyle ab'{\bmod {p}}}
, is equal to the original message
m
{\displaystyle m}
. We have
(
g
m
h
r
)
p
−
1
≡
(
g
m
g
n
r
)
p
−
1
≡
(
g
p
−
1
)
m
g
p
(
p
−
1
)
r
p
q
≡
(
g
p
−
1
)
m
mod
p
2
{\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}}
So to recover
m
{\displaystyle m}
we need to take the discrete logarithm with base
g
p
−
1
{\displaystyle g^{p-1}}
.
The group
(
Z
/
n
Z
)
∗
≃
(
Z
/
p
2
Z
)
∗
×
(
Z
/
q
Z
)
∗
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}\simeq (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}\times (\mathbb {Z} /q\mathbb {Z} )^{*}}
.
We define H which is subgroup of
Z
/
p
2
Z
∗
{\displaystyle \mathbb {Z} /p^{2}\mathbb {Z} ^{*}}
and its cardinality is p-1
H
=
{
x
:
x
p
−
1
mod
p
2
=
1
+
r
p
,
0
<
r
<
p
}
{\displaystyle H=\{x:x^{p-1}\mod p^{2}=1+rp,0<r<p\}}
.
For any element x in
(
Z
/
p
2
Z
)
∗
{\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}
, we have x p −1 mod p 2 is in H , since p divides x p −1 − 1.
The map
L
(
x
)
=
x
−
1
p
{\displaystyle L(x)={\frac {x-1}{p}}}
should be thought of as a logarithm from the cyclic group H to the additive group
Z
/
p
Z
{\displaystyle \mathbb {Z} /p\mathbb {Z} }
, 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
L
(
(
g
p
−
1
)
m
)
L
(
g
p
−
1
)
=
m
mod
p
.
{\displaystyle {\frac {L\left((g^{p-1})^{m}\right)}{L(g^{p-1})}}=m\mod p.}
[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
(
Z
/
n
Z
)
∗
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
is in the subgroup of order p . This is very similar to the quadratic residuosity problem and the higher residuosity problem .
References [ edit ]
Algorithms
Theory Standardization Topics