El cifrado RC4 consta de dos partes: 1. El algoritmo de programación clave (KSA) y 2. El algoritmo de generación de pseudoaleatorio (byte) (PRGA). El KSA toma una matriz ordenada de 256 elementos (bytes que contienen valores 0, 1, 2, …, 255 en este orden), y luego usa una clave secreta de longitud variable para convertir la matriz en un orden pseudoaleatorio. Una vez que el KSA ha terminado, se supone que la matriz debe “verse” organizada al azar.
Después del KSA, comienza la parte PRGA y esta parte genera un byte a la vez. Cada paso PRGA perturba aún más la matriz mientras genera un byte.
El código C para el RC4 se proporciona a continuación: (Tenga en cuenta que estamos usando la función de módulo como “mod” en el código a continuación para mayor claridad. En un programa, esto debe reemplazarse por%. Además, intercambie (x, y) es la función para intercambiar los valores de x e y.)
- ¿Los programadores de computadoras son naturalmente buenos en matemáticas?
- ¿Qué es el retorno 0 en C?
- No entiendo correctamente la cita de Alan Kay sobre sus antecedentes matemáticos. ¿Alguien puede explicarlo en términos simples?
- ¿Cómo los logaritmos convierten la multiplicación en suma?
- Cómo implementar un programa en C para un polinomio como un tipo de datos abstractos (ADT)
KSA:
para ( i = 0; i <256; i ++) S [i]: = i; // inicializa la matriz
j: = 0
para ( i = 0; i <256; i ++) {
j: = (j + S [i] + tecla [i mod keylength]) mod 256;
intercambio (S [i], S [j]);
}
PRGA:
i: = 0; j: = 0;
hacer{
i: = (i + 1) mod 256;
j: = (j + S [i]) mod 256;
intercambio (S [i], S [j]);
K: = S [(S [i] + S [j]) mod 256];
salida K;
} while (requerido);
El objetivo de KSA es utilizar el siguiente método para producir una permutación aleatoria de un conjunto dado S. Tome un índice i que se mueve sobre todo el conjunto una vez, paso a paso. Tome otro índice j que se mueve aleatoriamente sobre la matriz. Luego intercambie el contenido de S [i] y S [j]. Haga esto mientras cubro todos los elementos de la matriz. Tenga en cuenta que Donald Knuth proporciona un algoritmo de aspecto similar (pero diferente) en su libro clásico, y los análisis muestran que la matriz al final del procedimiento será uniformemente aleatoria, si la elección de j fue uniformemente aleatoria en cada paso. Más sobre esto al final de esta publicación.
El truco en RC4 es utilizar la clave secreta para calcular j en cada paso del procedimiento anterior. Dado que la clave secreta es desconocida para un adversario, la matriz producida al final de KSA no será conocida por nadie más que los usuarios genuinos. El tamaño de la matriz se elige para que sea lo suficientemente grande (es decir, 256) para garantizar que la probabilidad de adivinar una ubicación de la matriz después de la KSA sea pequeña (es decir, 1/256 si la matriz fuera realmente aleatoria al final de la KSA).
Uno de los problemas con RC4 es que j se calcula en cada paso en función de una clave secreta y no “elegido uniformemente al azar” como sugiere Knuth. El segundo problema es que incluso si j se eligió uniformemente al azar, este método de producir una matriz aleatoria no funciona (más al final de esta publicación). Esto hace que el estado de RC4 sea algo predecible, teniendo altas correlaciones con la clave secreta. Una vez que un adversario puede estimar algunos bytes del estado después de KSA, también puede predecir la salida de unos pocos bytes iniciales de RC4 PRGA. Por ejemplo, el primer resultado fue mostrado por Mantin y Shamir, quienes mostraron que el segundo byte de RC4 PRGA está muy sesgado para ser el byte 0. Si la salida de PRGA fuera uniformemente aleatoria, uno esperaría que cualquier byte pudiera producirse con probabilidad 1/256. Sin embargo, este resultado mostró que el segundo byte es 0 con probabilidad 1/128 (es decir, el doble de probabilidad), y esto es independiente de la clave secreta.
Más tarde, se mostraron muchos otros sesgos de RC4. Muchos de ellos se enumeran en la página de Wikipedia: RC4.
El tema crucial que subyace en la mayoría de las debilidades de RC4 es que los pocos bytes de salida iniciales de RC4 están altamente correlacionados con la clave secreta.
PD: El diseño de KSA en RC4 NO es el mismo que el de Knuth shuffle, incluso si j fue aleatorio en cada paso. Para saber más sobre cuáles son los problemas de este diseño y cómo funciona Knuth shuffle, consulte esta publicación de blog de Jeff Atwood: The Danger of Naïveté.
