¿Existe un algoritmo de cifrado asimétrico que mantenga la longitud del texto plano?

9

Quiero proteger algunos registros cifrándolos sin proporcionar espacio de memoria adicional. ¿Existe un algoritmo de cifrado que mantendrá la longitud de los datos a cifrar? (es decir, plaintext.length = ciphertext.length)

    
pregunta Drew Lex 12.12.2012 - 19:44
fuente

5 respuestas

13

Básicamente, solicita un cifrado asimétrico que puede tener un tamaño de bloque igual a su mensaje, o al tamaño de carácter de su codificación de mensaje (8 bits para ASCII / UTF8, 16 y 32 para UTF-16 y -32 respectivamente).

Vanilla RSA técnicamente puede hacer esto; simplemente debe limitar el tamaño de bits del entero sin signo N , producido al elegir dos primos aleatorios p y q ( p por lo tanto, debe ser menor que sqrt ( N ), y el dominio de posibles valores de q se reduce cuanto más cerca de p esté a sqrt ( N )). El máximo N puede ser del mismo orden de magnitud que el mensaje concatenado, o incluso un divisor de este (hasta 1 byte / carácter)

Sin embargo, hay dos problemas serios con esto:

  • RSA solo es seguro para tamaños de clave muy grandes; su dificultad es inherente a la búsqueda de p y q que producen N , por lo que la seguridad de cualquier cifrado, incluida la RSA, está en tener una salida literal. -de-este-universo número de claves posibles para elegir **. Por lo tanto, adaptar el tamaño de la clave a la longitud del mensaje solo sería seguro desde la perspectiva del tamaño de la clave si el mensaje tuviera al menos 256 caracteres ASCII (produciendo un mensaje de 2048 bits que permite una clave de gran tamaño de forma segura). Los tamaños de mensaje pequeños (longitudes de clave de 8-32 bits) se dividen trivialmente; en el peor de los casos (para un atacante), una clave de 32 bits requiere encontrar un número entero primo p < sqrt (2 32 ) = 65536 que divide N de manera uniforme; Por el teorema del número primo solo hay 5900 posibilidades. Casi de manera factible, puede romper esa clave "a mano" con una calculadora.
  • Además, y más serio, RSA sin el relleno de cifrado adecuado es vulnerable a ataques de texto plano conocido y en casos que se reducen a ejemplos triviales. OAEP, el esquema de relleno RSA estándar de oro, utiliza dos funciones hash, una de las cuales debe tener una longitud de bit al menos el tamaño de bit del mensaje de texto plano, y la longitud del mensaje rellenado completo es igual a la suma del hash de ambas funciones longitudes de los mensajes, por lo que el mensaje rellenado siempre será mayor que el mensaje no rellenado.

Por lo tanto, el enfoque de RSA simple con un tamaño de clave personalizado debe considerarse fundamentalmente defectuoso. Todos los demás sistemas de clave pública que puedo encontrar, como el cifrado de curva elíptica, tienen limitaciones similares basadas en las matemáticas utilizadas para el cifrado.

** 2048 bits es el tamaño de clave recomendado más pequeño para los certificados digitales X.509. 2 2048 ~ = 3.2317e616. Poniendo este número en perspectiva, un volumen de Planck es 4.22419e − 105 m 3 ; esta unidad es, en teoría, la "resolución" granular del universo, basada en que la longitud de Planck es la distancia más pequeña que cualquier instrumento podría medir. El universo observable es al menos del orden de 1e27 m de radio (13.7 billones de años luz), por lo que la esfera de nuestro universo observable es ~ 4.189e79 m 3 ~ = 1.7e185 Pl 3 . Eso significa que si no solo pudiéramos "contar las estrellas y llamarlas por su nombre", sino también asignar un ordinal a cada fragmento granular de nuestro universo observable, el número de números que necesitaríamos es 400 dígitos decimales más corto que el número de números inherente al espacio de claves RSA.

    
respondido por el KeithS 13.12.2012 - 00:34
fuente
3

Estrictamente hablando, ningún cifrado asimétrico seguro puede mantener la longitud del texto sin formato. El problema es que la clave pública, al ser pública, es conocida por todos. Por lo tanto, todos pueden "probar" los plaintexts potenciales y cifrarlos, para ver si el resultado coincide con el texto cifrado. Esa es una búsqueda exhaustiva en el texto simple en lugar de la clave, y funciona porque el texto simple tiene algún "significado" y por lo tanto una estructura. Por ejemplo, si se cifran los pedidos bancarios, solo hay unos pocos miles de millones de combinaciones posibles de cantidad y cuenta de destino, y esto es susceptible de una búsqueda exhaustiva.

Para evitar este problema, un algoritmo de cifrado asimétrico seguro NO DEBE ser determinista : el proceso de cifrado DEBE incluir algo de aleatoriedad, de modo que un texto simple dado, cifrado con una clave pública dada, puede resultar en una Gran conjunto de posibles cifrados. Esto es lo que sucede, por ejemplo, en RSA, como se define en PKCS # 1 : el texto en claro es primero rellenado con bytes aleatorios. Tras el descifrado, el relleno se detecta y elimina de forma inequívoca, por supuesto.

No ser determinista implica necesariamente que el conjunto de posibles textos cifrados es mucho más grande que el conjunto de posibles plaintexts; en otras palabras, el texto cifrado es necesariamente más grande que el texto simple.

Al menos, la sobrecarga de tamaño se puede mantener constante (un incremento fijo, en lugar de un aumento de tamaño proporcional a la longitud del mensaje de entrada) por el método habitual de cifrado híbrido : cifras asimétricamente una secuencia de bytes aleatorios K , que luego usas para el cifrado simétrico del texto plano. En ese caso, puede reemplazar el cifrado asimétrico con un mecanismo de intercambio de claves; Si tiene un presupuesto de tamaño, sugiero echar un vistazo a curva elíptica Diffie-Hellman : con la curva estándar P-256, puede mantener la sobrecarga por mensaje a 32 bytes.

Con RSA, asumiendo que el mensaje para cifrar es más largo que la clave, podría bajar un poco más (el relleno PKCS # 1 v1.5 implica al menos 11 bytes de sobrecarga; con una clave RSA de 2048 bits, podría cifre con RSA los primeros 229 bytes del mensaje, y una clave simétrica de 16 bytes, y luego use esa clave para el resto del mensaje con AES-CTR; eso sería una sobrecarga de 27 bytes).

    
respondido por el Thomas Pornin 28.12.2012 - 17:16
fuente
1

Suena como si estuvieras buscando "Format Preserving Encryption", si no has visto FPE antes, echa un vistazo al artículo wiki sobre él. Tiene muchas buenas referencias.

enlace

No estoy seguro de que exista tal cosa como el formato asimétrico que preserva el cifrado ... hay mucha discusión al respecto cuando se busca ese término.

    
respondido por el mgjk 13.12.2012 - 02:46
fuente
0

Sospecho que hay un error tipográfico en tu línea de título. Si "asimétrico" es "simétrico", entonces mi respuesta es: Todos los cifrados de bloque típicos satisfacen su conticción. Si la longitud del bloque es un problema para su aplicación, puede usar un cifrado de flujo. (No tengo conocimiento de ningún algoritmo de cifrado asimétrico que satisfaga su condición. Incluso supongo que eso es imposible).

    
respondido por el Mok-Kong Shen 12.12.2012 - 21:39
fuente
-2

Si se trata de un algoritmo definido por software, deberías usar otro registro para almacenar los pasos temporales a medida que lo descifraste.

Será mejor que veas algo como AES-NI .

    
respondido por el Sean Madden 12.12.2012 - 20:27
fuente

Lea otras preguntas en las etiquetas