El S-box de Rijndael es una operación de uso frecuente en el cifrado y descifrado AES . Normalmente se implementa como una tabla de búsqueda de 256 bytes. Eso es rápido, pero significa que necesita enumerar una tabla de búsqueda de 256 bytes en su código. Apuesto a que alguien en esta multitud podría hacerlo con menos código, dada la estructura matemática subyacente.
Escriba una función en su idioma favorito que implemente el S-box de Rijndael. El código más corto gana.
code-golf
math
cryptography
Keith Randall
fuente
fuente
Respuestas:
Ruby, 161 caracteres
Para verificar el resultado, puede usar el siguiente código para imprimirlo en forma de tabla:
fuente
GolfScript, 60 caracteres
Este código define una función llamada
S
que toma un byte y le aplica el S-box de Rijndael. (También usa una función auxiliar interna llamadar
para guardar algunos caracteres).Esta implementación utiliza una tabla de logaritmos para calcular los inversos GF (2 8 ), como lo sugiere Thomas Pornin . Para guardar algunos caracteres, se recalcula toda la tabla de logaritmos para cada byte de entrada; aun así, y a pesar de que GolfScript es un lenguaje muy lento en general, este código solo tarda unos 10 ms en procesar un byte en mi computadora portátil anterior. Precalcular la tabla de logaritmo (as
L
) la acelera hasta aproximadamente 0,5 ms por byte, con el modesto costo de tres caracteres más:Por conveniencia, aquí hay un arnés de prueba simple que llama a la función
S
, como se definió anteriormente, para calcular e imprimir todo el cuadro S en hexadecimal como en Wikipedia :Prueba este código en línea.
(La demostración en línea calcula previamente la tabla de logaritmos para evitar tomar demasiado tiempo. Aun así, el sitio en línea de GolfScript a veces puede expirar al azar; este es un problema conocido con el sitio, y una recarga generalmente lo soluciona).
Explicación:
Comencemos con el cálculo de la tabla de logaritmo, y específicamente con la función auxiliar
r
:Esta función toma dos entradas en la pila: un byte y una máscara de bits de reducción (una constante entre 256 y 511). Duplica el byte de entrada, multiplica la copia por 2 y, si el resultado excede 255, lo XOR con la máscara de bits para devolverlo a 256.
Dentro del código de generación de la tabla de registro, la función
r
se llama con la máscara de bits de reducción 283 = 0x11b (que corresponde al polinomio de reducción Rijndael GF (2 8 ) x 8 + x 4 + x 3 + x + 1), y el resultado es XORed con el byte original, multiplicándolo efectivamente por 3 (= x + 1, como polinomio) en el campo finito de Rijndael. Esta multiplicación se repite 255 veces, comenzando desde el byte 1, y los resultados (más un byte inicial cero) se recopilan en una matriz de 257 elementosL
que se ve así (se omite la parte central):La razón por la que hay 257 elementos es que, con el 0 antepuesto y con 1 ocurriendo dos veces, podemos encontrar el inverso modular de cualquier byte dado simplemente buscando su índice (basado en cero) en esta matriz, negándolo y mirando arriba el byte en el índice negado en la misma matriz. (En GolfScript, como en muchos otros lenguajes de programación, los índices de matriz negativos cuentan hacia atrás desde el final de la matriz). De hecho, esto es exactamente lo que hace el código
L?~)L=
al comienzo de la funciónS
.El resto del código llama a la función auxiliar
r
cuatro veces con la máscara de bits de reducción 257 = 2 8 + 1 para crear cuatro copias rotadas en bits del byte de entrada invertido. Todos estos se recopilan en una matriz, junto con la constante 99 = 0x63, y se juntan XOR para producir la salida final.fuente
x86-64 Código de máquina -
23 22 2019 bytesUtiliza el conjunto de instrucciones AES-NI
Usando las convenciones de llamadas de Windows, toma un byte y genera un byte. No es necesario invertir el,
ShiftRows
ya que no afecta el primer byte.fuente
La tabla se puede generar sin calcular inversos en el campo finito GF (256), utilizando logaritmos. Se vería así (código Java,
int
para evitar problemas con elbyte
tipo firmado ):La idea es que 3 es un generador multiplicativo de GF (256) *. La tabla
t[]
es tal quet[x]
es igual a 3 x ; desde 3 255 = 1, obtenemos que 1 / (3 x ) = 3 255-x .fuente
0x1B
(uno 1 en el literal hexadecimal) en lugar de0x11B
int
tipo es de 32 bits en Java; Debo cancelar el bit más alto.GolfScript (82 caracteres)
Utiliza variables globales
A
yB
, y crea la función como variable globalS
.La inversión de Galois es fuerza bruta; Experimenté con una
mul
función separada que podría reutilizarse para la transformación afín posterior a la inversión, pero resultó ser más costosa debido al diferente comportamiento de desbordamiento.Esto es demasiado lento para una demostración en línea: se agotaría incluso en las dos primeras filas de la tabla.
fuente
Python, 176 caracteres
Esta respuesta es para la pregunta-comentario de Paŭlo Ebermann sobre cómo hacer que la función sea de tiempo constante. Este código se ajusta a la factura.
fuente
re
esto puede generar la tabla de búsqueda en tiempo de compilación, podría guardar algunos haciendo ubyte un parámetro genérico
Edición directa
ubyte
aubyte
sin búsquedas de la matriz, sin ramificaciones y bucles totalmente desenrollablesedit2 utilizó algo de @Thomas para crear la tabla de búsqueda
fuente
Stax , 53 bytes
Ejecutar y depurarlo
No tengo una comprensión particular de las cajas S Esta es una conversión de la solución de Thomas Pornin (¡8 años!) .
fuente