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 .
Background [ edit ] Let p {\displaystyle p} be an odd prime. Define Γ = { x ∈ ( Z / p 2 Z ) ∗ | x ≡ 1 mod p } {\displaystyle \Gamma =\{x\in (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}|x\equiv 1{\bmod {p}}\}} . Γ {\displaystyle \Gamma } is a subgroup of ( Z / p 2 Z ) ∗ {\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}} with | Γ | = p {\displaystyle |\Gamma |=p} (the elements of Γ {\displaystyle \Gamma } are 1 , 1 + p , 1 + 2 p … 1 + ( p − 1 ) p {\displaystyle 1,1+p,1+2p\dots 1+(p-1)p} ).
Define L : Γ → Z / p Z {\displaystyle L:\Gamma \to \mathbb {Z} /p\mathbb {Z} } by L ( x ) = x − 1 p {\displaystyle L(x)={\frac {x-1}{p}}}
L {\displaystyle L} is a homomorphism between Γ {\displaystyle \Gamma } and the additive group Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } : that is, L ( a b ) = L ( a ) + L ( b ) mod p {\displaystyle L(ab)=L(a)+L(b){\bmod {p}}} . Since L {\displaystyle L} is bijective, it is an isomorphism.
One can now show the following as a corollary:
Let x ∈ Γ {\displaystyle x\in \Gamma } such that L ( x ) ≠ 0 mod p {\displaystyle L(x)\neq 0{\bmod {p}}} and y = x m mod p 2 {\displaystyle y=x^{m}{\bmod {p}}^{2}} for 0 ≤ m < p {\displaystyle 0\leq m<p} . Then
m = L ( y ) L ( x ) = y − 1 x − 1 mod p {\displaystyle m={\frac {L(y)}{L(x)}}={\frac {y-1}{x-1}}{\bmod {p}}} The corollary is a direct consequence of L ( x m ) = m ⋅ L ( x ) {\displaystyle L(x^{m})=m\cdot L(x)} .
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 = L ( c p − 1 mod p 2 ) {\displaystyle a=L(c^{p-1}{\bmod {p^{2}}})} . Compute b = L ( g p − 1 mod p 2 ) {\displaystyle b=L(g^{p-1}{\bmod {p^{2}}})} . 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}} . This can be done by applying L {\displaystyle L} , as follows.
By Fermat's little theorem , g p − 1 ≡ 1 mod p {\displaystyle g^{p-1}\equiv 1{\bmod {p}}} . Since g p − 1 ≢ 1 mod p 2 {\displaystyle g^{p-1}\not \equiv 1{\bmod {p}}^{2}} one can write g p − 1 = 1 + p r {\displaystyle g^{p-1}=1+pr} with 0 < r < p {\displaystyle 0<r<p} . Then L ( g p − 1 ) ≢ 0 mod p {\displaystyle L(g^{p-1})\not \equiv 0{\bmod {p}}} and the corollary from earlier applies: m = L ( ( g p − 1 ) m ) L ( g p − 1 ) mod p {\displaystyle m={\frac {L((g^{p-1})^{m})}{L(g^{p-1})}}{\bmod {p}}} .
Security [ edit ] 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 ( 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