Okamoto–Uchiyama cryptosystem – Wikipedia

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/nZ)∗{displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}

, where n is of the form p²q and p and q are large primes.

Operation[edit]

Like many public key cryptosystems, this scheme works in the group

(Z/nZ)∗{displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}

. This scheme is homomorphic and hence malleable.

Key generation[edit]

A public/private key pair is generated as follows:

1. Generate two large primes
   p{displaystyle p}
   and q{displaystyle q}
   .
2. Compute
   n=p2q{displaystyle n=p^{2}q}
   .
3. Choose a random integer
   g∈{2…n−1}{displaystyle gin {2dots n-1}}
   such that gp−1≢1modp2{displaystyle g^{p-1}not equiv 1mod p^{2}}
   .
4. Compute
   h=gnmodn{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

can be encrypted with the public key

(n,g,h){displaystyle (n,g,h)}

as follows.

1. Choose a random integer
   r∈{1…n−1}{displaystyle rin {1dots n-1}}
   .
2. Compute
   c=gmhrmodn{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.

1. Compute
   a=(cp−1modp2)−1p{displaystyle a={frac {(c^{p-1}{bmod {p^{2}}})-1}{p}}}
   .
2. Compute
   b=(gp−1modp2)−1p{displaystyle b={frac {(g^{p-1}{bmod {p^{2}}})-1}{p}}}
   . a{displaystyle a}
   and b{displaystyle b}
   will be integers.
3. Using the Extended Euclidean Algorithm, compute the inverse of
   b{displaystyle b}
   modulo p{displaystyle p}
   :

   b′=b−1modp{displaystyle b’=b^{-1}{bmod {p}}}

   .

4. Compute
   m=ab′modp{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=32⋅5=45{displaystyle n=3^{2}cdot 5=45}

. Select

g=22{displaystyle g=22}

. Then

h=2245mod45=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=gmhrmodn=2223713mod45=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=(432mod32)−13=1{displaystyle a={frac {(43^{2}{bmod {3}}^{2})-1}{3}}=1}

.

b=(222mod32)−13=2{displaystyle b={frac {(22^{2}{bmod {3}}^{2})-1}{3}}=2}

.

b′=2−1mod3=2{displaystyle b’=2^{-1}{bmod {3}}=2}

.

And finally

m=ab′=2{displaystyle m=ab’=2}

.

Proof of correctness[edit]

We wish to prove that the value computed in the last decryption step,

ab′modp{displaystyle ab'{bmod {p}}}

, is equal to the original message

m{displaystyle m}

. We have

(gmhr)p−1≡(gmgnr)p−1≡(gp−1)mgp(p−1)rpq≡(gp−1)mmodp2{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

gp−1{displaystyle g^{p-1}}

.

The group

(Z/nZ)∗≃(Z/p2Z)∗×(Z/qZ)∗{displaystyle (mathbb {Z} /nmathbb {Z} )^{*}simeq (mathbb {Z} /p^{2}mathbb {Z} )^{*}times (mathbb {Z} /qmathbb {Z} )^{*}}

.

We define H which is subgroup of

Z/p2Z∗{displaystyle mathbb {Z} /p^{2}mathbb {Z} ^{*}}

and its cardinality is p-1

H={x:xp−1modp2=1+rp,0<r<p}{displaystyle H={x:x^{p-1}mod p^{2}=1+rp,0

.

For any element x in

(Z/p2Z)∗{displaystyle (mathbb {Z} /p^{2}mathbb {Z} )^{*}}

, we have x^p−1 mod p² is in H, since p divides x^p−1 − 1.

The map

L(x)=x−1p{displaystyle L(x)={frac {x-1}{p}}}

should be thought of as a logarithm from the cyclic group H to the additive group

Z/pZ{displaystyle mathbb {Z} /pmathbb {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((gp−1)m)L(gp−1)=mmodp.{displaystyle {frac {Lleft((g^{p-1})^{m}right)}{L(g^{p-1})}}=mmod 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/nZ)∗{displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}

is in the subgroup of order p. This is very similar to the quadratic residuosity problem and the higher residuosity problem.

References[edit]