Problema de mayor residuosidad

En criptografía , la mayoría de los criptosistemas de clave pública se basan en problemas que se consideran intratables. El problema de residuosidad superior (también llamado problema de residuo n -ésimo ^[1] ) es uno de esos problemas. Este problema es más fácil de resolver que la factorización de números enteros , por lo que la suposición de que este problema es difícil de resolver es más sólida que la suposición de que la factorización de números enteros es difícil.

Antecedentes matemáticos

Si n es un entero , entonces los enteros módulo n forman un anillo . Si n = pq donde p y q son primos , entonces el teorema del resto chino nos dice que

${\displaystyle \mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z} }$

Las unidades de cualquier anillo forman un grupo bajo la multiplicación, y el grupo de unidades en se denota tradicionalmente como . ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Del isomorfismo de anillo anterior, tenemos

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }}$

como un isomorfismo de grupos . Como se supuso que p y q eran primos, los grupos y son cíclicos de órdenes p −1 y q −1 respectivamente. Si d es un divisor de p −1, entonces el conjunto de d  ésimas potencias en forma un subgrupo de índice d . Si mcd( d , q −1) = 1, entonces cada elemento en es una d  ésima potencia, por lo que el conjunto de d  ésimas potencias en también es un subgrupo de índice d . En general, si mcd( d , q −1) = g , entonces hay ( q −1)/ g d  ésimas potencias en , por lo que el conjunto de d  ésimas potencias en tiene índice dg . Esto se ve más comúnmente cuando d = 2, y estamos considerando el subgrupo de residuos cuadráticos , es bien sabido que exactamente una cuarta parte de los elementos en son residuos cuadráticos (cuando n es el producto de dos primos, como es aquí). ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

El punto importante es que para cualquier divisor d de p −1 (o q −1) el conjunto de d  potencias forma un subgrupo de ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

Planteamiento del problema

Dado un entero n = pq donde p y q son desconocidos, un entero d tal que d divide a p −1, y un entero x < n , no es factible determinar si x es una d  -ésima potencia (equivalentemente d  -ésimo residuo) módulo n .

Nótese que si se conocen p y q es fácil determinar si x es un residuo d  -ésimo módulo n porque x será un residuo d  -ésimo módulo p si y sólo si

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod {p}}}$

Cuando d = 2, esto se llama problema de residuosidad cuadrática .

Aplicaciones

La seguridad semántica del criptosistema Benaloh y del criptosistema Naccache-Stern se basa en la intratabilidad de este problema.

Referencias

1. Zhang, Yuliang; Tsutomu Matsumoto; Hideki Imai (1988). "Aplicaciones criptográficas del problema de la residuosidad th con un entero impar". Transacciones del IEICE . 71 (8): 759–767. CiteSeerX  10.1.1.137.8511 .