En criptografía , la mayoría de los criptosistemas de clave pública se basan en problemas que se cree que son intratables. El problema de la mayor residuosidad (también llamado problema n-ésimo-residuosidad [1] ) es uno de esos problemas. Este problema es más fácil de resolver que la factorización de enteros , por lo que la suposición de que este problema es difícil de resolver es más fuerte que la suposición de que la factorización de enteros es difícil.
Fondo matemático
Si n es un número entero , entonces los números enteros módulo n forman un anillo . Si n = pq , donde p y q son números primos , entonces el teorema chino del resto nos dice que
El grupo de unidades de cualquier anillo forma un grupo , y el grupo de unidades en se denota tradicionalmente .
Del isomorfismo anterior, tenemos
como un isomorfismo de grupos . Desde p y q se supone que prima, 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 enforman un subgrupo de índice d . Si mcd ( d , q -1) = 1, entonces cada elemento enes una d- ésima potencia, por lo que el conjunto de d- ésima potencia entambién es un subgrupo del índice d . En general, si mcd ( d , q -1) = g , entonces hay ( q -1) / ( g ) d- ésima potencias en, por lo que el conjunto de d- ésimas potencias entiene í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 enson residuos cuadráticos (cuando n es el producto de exactamente dos números primos, como aquí).
El punto importante es que para cualquier divisor d de p -1 (o q -1) el conjunto de d- ésimas potencias forma un subgrupo de
Planteamiento del problema
Dado un número entero n = pq donde p y q son desconocidos, un número entero d tal que d divide p -1 y un número entero x < n , no es factible determinar si x es una d- ésima potencia (equivalentemente d- ésimo residuo) módulo n .
Tenga en cuenta que si p y q son conocidos, es fácil determinar si x es un d º de residuos módulo n porque x será un d º de residuos modulo p si y sólo si
Cuando d = 2, esto se denomina problema de residuosidad cuadrática .
Aplicaciones
La seguridad semántica del criptosistema Benaloh y el criptosistema Naccache-Stern se basa en la intratabilidad de este problema.
Referencias
- ^ Zhang, Yuliang; Tsutomu Matsumoto; Hideki Imai (1988). "Aplicaciones criptográficas del problema de th-Residuosity con un entero impar". Transacciones del IEICE . 71 (8): 759–767. CiteSeerX 10.1.1.137.8511 .