Criptosistema Okamoto-Uchiyama

El criptosistema Okamoto-Uchiyama es un criptosistema de clave pública propuesto en 1998 por Tatsuaki Okamoto y Shigenori Uchiyama. El sistema funciona en el grupo multiplicativo de los números enteros módulo n , donde n tiene la forma p ² q y p y q son primos grandes . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

Fondo

Sea un primo impar. Defina . es un subgrupo de con (los elementos de son ). ${\displaystyle p}$ ${\displaystyle \Gamma =\{x\in (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}|x\equiv 1{\bmod {p}}\}}$ ${\displaystyle \Gamma }$ ${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}$ ${\displaystyle |\Gamma |=p}$ ${\displaystyle \Gamma }$ ${\displaystyle 1,1+p,1+2p\dots 1+(p-1)p}$

Definir por ${\displaystyle L:\Gamma \to \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle L(x)={\frac {x-1}{p}}}$

${\displaystyle L}$es un homomorfismo entre y el grupo aditivo : es decir, . Como es biyectivo, es un isomorfismo. ${\displaystyle \Gamma }$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle L(ab)=L(a)+L(b){\bmod {p}}}$ ${\displaystyle L}$

Ahora se puede demostrar lo siguiente como corolario:

Sea tal que y para . Entonces ${\displaystyle x\in \Gamma }$ ${\displaystyle L(x)\neq 0{\bmod {p}}}$ ${\displaystyle y=x^{m}{\bmod {p}}^{2}}$ ${\displaystyle 0\leq m<p}$

${\displaystyle m={\frac {L(y)}{L(x)}}={\frac {y-1}{x-1}}{\bmod {p}}}$

El corolario es una consecuencia directa de . ${\displaystyle L(x^{m})=m\cdot L(x)}$

Operación

Al igual que muchos criptosistemas de clave pública , este esquema funciona en grupo . Este esquema es homomórfico y, por lo tanto, maleable . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

Generación de claves

Un par de claves pública/privada se genera de la siguiente manera:

1. Generar dos primos grandes y . ${\displaystyle p}$ ${\displaystyle q}$
2. Calcular . ${\displaystyle n=p^{2}q}$
3. Elija un número entero aleatorio tal que . ${\displaystyle g\in \{2\dots n-1\}}$ ${\displaystyle g^{p-1}\not \equiv 1\mod p^{2}}$
4. Calcular . ${\displaystyle h=g^{n}{\bmod {n}}}$

La clave pública es entonces y la clave privada es . ${\displaystyle (n,g,h)}$ ${\displaystyle (p,q)}$

Encriptación

Un mensaje se puede cifrar con la clave pública de la siguiente manera. ${\displaystyle m<p}$ ${\displaystyle (n,g,h)}$

1. Elija un número entero aleatorio . ${\displaystyle r\in \{1\dots n-1\}}$
2. Calcular . ${\displaystyle c=g^{m}h^{r}{\bmod {n}}}$

El valor es el cifrado de . ${\displaystyle c}$ ${\displaystyle m}$

Descifrado

Un mensaje cifrado se puede descifrar con la clave privada de la siguiente manera. ${\displaystyle c}$ ${\displaystyle (p,q)}$

1. Calcular . ${\displaystyle a=L(c^{p-1}{\bmod {p^{2}}})}$
2. Calcular . y serán números enteros. ${\displaystyle b=L(g^{p-1}{\bmod {p^{2}}})}$ ${\displaystyle a}$ ${\displaystyle b}$
3. Utilizando el algoritmo euclidiano extendido , calcule el inverso del módulo : ${\displaystyle b}$ ${\displaystyle p}$

   ${\displaystyle b'=b^{-1}{\bmod {p}}}$.

4. Calcular . ${\displaystyle m=ab'{\bmod {p}}}$

El valor es el descifrado de . ${\displaystyle m}$ ${\displaystyle c}$

Ejemplo

Sea y . Luego . Seleccione . Luego . ${\displaystyle p=3}$ ${\displaystyle q=5}$ ${\displaystyle n=3^{2}\cdot 5=45}$ ${\displaystyle g=22}$ ${\displaystyle h=22^{45}{\bmod {4}}5=37}$

Ahora, para cifrar un mensaje , elegimos un número aleatorio y lo calculamos . ${\displaystyle m=2}$ ${\displaystyle r=13}$ ${\displaystyle c=g^{m}h^{r}{\bmod {n}}=22^{2}37^{13}{\bmod {4}}5=43}$

Para descifrar el mensaje 43, calculamos

${\displaystyle a={\frac {(43^{2}{\bmod {3}}^{2})-1}{3}}=1}$.

${\displaystyle b={\frac {(22^{2}{\bmod {3}}^{2})-1}{3}}=2}$.

${\displaystyle b'=2^{-1}{\bmod {3}}=2}$.

Y por último . ${\displaystyle m=ab'=2}$

Prueba de corrección

Queremos demostrar que el valor calculado en el último paso de descifrado, , es igual al mensaje original . Tenemos ${\displaystyle ab'{\bmod {p}}}$ ${\displaystyle m}$

${\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}}$

Para recuperar, necesitamos tomar el logaritmo discreto con base . Esto se puede hacer aplicando , de la siguiente manera. ${\displaystyle m}$ ${\displaystyle g^{p-1}}$ ${\displaystyle L}$

Por el pequeño teorema de Fermat , . Dado que se puede escribir con . Entonces y se aplica el corolario de antes: . ${\displaystyle g^{p-1}\equiv 1{\bmod {p}}}$ ${\displaystyle g^{p-1}\not \equiv 1{\bmod {p}}^{2}}$ ${\displaystyle g^{p-1}=1+pr}$ ${\displaystyle 0<r<p}$ ${\displaystyle L(g^{p-1})\not \equiv 0{\bmod {p}}}$ ${\displaystyle m={\frac {L((g^{p-1})^{m})}{L(g^{p-1})}}{\bmod {p}}}$

Seguridad

Se puede demostrar que invertir la función de cifrado es tan difícil como factorizar n , lo que significa que si un adversario pudiera recuperar el mensaje completo a partir del cifrado del mensaje, podría factorizar n . La seguridad semántica (lo que significa que los adversarios no pueden recuperar ninguna información sobre el mensaje a partir del cifrado) se basa en el supuesto de p -subgrupo, que supone que es difícil determinar si un elemento x en está en el subgrupo de orden p . Esto es muy similar al problema de residuosidad cuadrática y al problema de residuosidad superior . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

Referencias

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "Un nuevo criptosistema de clave pública tan seguro como la factorización". Avances en criptología – EUROCRYPT'98 . Apuntes de clase en informática . Vol. 1403. Springer. págs. 308–318. doi :10.1007/BFb0054135. ISBN 978-3-540-64518-4.