El criptosistema Benalo es una modificación del criptosistema Goldwasser-Micali . Su principal diferencia es que el criptosistema le permite encriptar un bloque de datos a la vez, mientras que en el esquema de Goldwasser y Micali, cada bit de datos se encripta por separado [1] .
Diseñado por Josh Benalo en 1988. Ha sido utilizado en sistemas de votación electrónica [2] .
El sistema es parcialmente homomórfico . Como ocurre con muchos criptosistemas de clave pública, este sistema opera en el grupo , donde es el producto de dos números primos .
Entonces la clave pública es , y la clave secreta es .
Cifrado de mensajes :
Primero, tenga en cuenta que para cualquier y , se cumple lo siguiente:
Así, para calcular , conociendo , se realiza la operación del logaritmo discreto de con respecto a la base . Si el número es pequeño, es posible encontrarlo mediante una búsqueda exhaustiva, es decir, comprobando la igualdad para todos . Para valores grandes de , el hallazgo se puede realizar mediante el algoritmo de Gelfond-Shanks (algoritmo de pasos grandes y pequeños) , obteniendo la complejidad temporal del descifrado .
Descifrado de texto cifrado :
El criptosistema Benalo es homomórfico con respecto a la operación de suma:
, ¿dónde está la función de cifrado del mensaje?
La fuerza del criptosistema Benalo se basa en el problema intratable de los residuos de alto grado. Conociendo el tamaño del bloque , el módulo y el texto cifrado , donde se desconoce la factorización del número , es computacionalmente difícil determinar el texto sin formato .