Implementar la caja S de Rijndael

15

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.

Keith Randall
fuente
1
Puntos de bonificación (votos positivos de mi parte) si la función resultante es de tiempo constante (es decir, no hay rutas de código dependientes de datos o accesos de matriz o lo que sea compatible con su idioma).
Paŭlo Ebermann
@ Los accesos a la matriz PaŭloEbermann son de tiempo constante en muchos idiomas (está agregando un valor (escalado) a un puntero y eliminando la referencia, esta es la razón por la que una tabla de búsqueda es tan rápida)
monstruo de trinquete el
@ratchetfreak Los accesos de matriz son O (1), pero el tiempo de acceso real depende de aciertos o errores de caché, por ejemplo, lo que conduce a ataques de canal lateral en AES.
Paŭlo Ebermann
@ PaŭloEbermann, pero puede usar el código más corto para llenar una tabla de búsqueda, que luego encajará bien debajo de una página de memoria.
Peter Taylor
@ PaŭloEbermann y si la mesa 256 de longitud se almacena a lo largo del código (como enumeración generada en tiempo de compilación) que casi garantiza un acierto de caché
monstruo de trinquete

Respuestas:

6

Ruby, 161 caracteres

R=0..255
S=R.map{|t|t=b=R.select{|y|x=t;z=0;8.times{z^=y*(x&1);x/=2;y*=2};r=283<<8;8.times{r/=2;z^r<z/2&&z^=r};z==1}[0]||0;4.times{|r|t^=b<<1+r^b>>4+r};t&255^99}

Para verificar el resultado, puede usar el siguiente código para imprimirlo en forma de tabla:

S.map{|x|"%02x"%x}.each_slice(16){|l|puts l*' '}
Howard
fuente
7

GolfScript, 60 caracteres

{[[0 1{.283{1$2*.255>@*^}:r~^}255*].@?~)={257r}4*99]{^}*}:S;

Este código define una función llamada Sque toma un byte y le aplica el S-box de Rijndael. (También usa una función auxiliar interna llamada rpara 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:

[0 1{.283{1$2*.255>@*^}:r~^}255*]:L;{[L?~)L={257r}4*99]{^}*}: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 :

"0123456789abcdef"1/:h; 256, {S .16/h= \16%h= " "++ }% 16/ n*

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:

{1$2*.255>@*^}: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 rse 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 elementos Lque se ve así (se omite la parte central):

[0 1 3 5 15 17 51 85 255 26 46 ... 180 199 82 246 1]

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ón S.

El resto del código llama a la función auxiliar rcuatro 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.

Ilmari Karonen
fuente
7

x86-64 Código de máquina - 23 22 20 19 bytes

Utiliza el conjunto de instrucciones AES-NI

66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1  
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

Usando las convenciones de llamadas de Windows, toma un byte y genera un byte. No es necesario invertir el, ShiftRowsya que no afecta el primer byte.

yo'
fuente
2
Por una vez, x86_64 extrae una matemática y tiene una función incorporada para eso.
moonheart08
6

La tabla se puede generar sin calcular inversos en el campo finito GF (256), utilizando logaritmos. Se vería así (código Java, intpara evitar problemas con el bytetipo firmado ):

int[] t = new int[256];
for (int i = 0, x = 1; i < 256; i ++) {
    t[i] = x;
    x ^= (x << 1) ^ ((x >>> 7) * 0x11B);
}
int[] S = new int[256];
S[0] = 0x63;
for (int i = 0; i < 255; i ++) {
    int x = t[255 - i];
    x |= x << 8;
    x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
    S[t[i]] = (x ^ 0x63) & 0xFF;
}

La idea es que 3 es un generador multiplicativo de GF (256) *. La tabla t[]es tal que t[x]es igual a 3 x ; desde 3 255 = 1, obtenemos que 1 / (3 x ) = 3 255-x .

Thomas Pornin
fuente
¿No debería ser 0x1B(uno 1 en el literal hexadecimal) en lugar de0x11B
Ratchet Freak
@ratchetfreak: no, debe ser 0x11B (lo intenté). El inttipo es de 32 bits en Java; Debo cancelar el bit más alto.
Thomas Pornin
ah, no me di cuenta de eso
monstruo de trinquete
¿Es eso un >>> en lugar de un >> en la línea 4?
Joe Z.
@ JoeZeng: ambos funcionarían. En Java, '>>>' es el "turno sin signo", '>>' es el "turno con signo". Se diferencian por cómo manejan el bit de signo. Aquí, los valores nunca serán lo suficientemente anchos para que el bit de signo sea distinto de cero, por lo que no hay diferencia real.
Thomas Pornin
6

GolfScript (82 caracteres)

{256:B,{0\2${@1$3$1&*^@2/@2*.B/283*^}8*;;1=},\+0=B)*:A.2*^4A*^8A*^128/A^99^B(&}:S;

Utiliza variables globales Ay B, y crea la función como variable global S.

La inversión de Galois es fuerza bruta; Experimenté con una mulfunció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.

Peter Taylor
fuente
El mío es más rápido (y más corto). +1 de todos modos, sin embargo.
Ilmari Karonen
4

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.

def S(x):
 i=0
 for y in range(256):
  p,a,b=0,x,y
  for j in range(8):p^=b%2*a;a*=2;a^=a/256*283;b/=2
  m=(p^1)-1>>8;i=y&m|i&~m
 i|=i*256;return(i^i/16^i/32^i/64^i/128^99)&255
Keith Randall
fuente
La multiplicación en tiempo constante depende de la plataforma (incluso en plataformas de 32 bits, por ejemplo, ARM Cortex M0). Ver esta pregunta relacionada
fgrieu
1
@fgrieu Claro, pero todas estas son multiplicaciones por constantes, que pueden implementarse fácilmente en tiempo constante usando turnos y sumas.
Keith Randall
2

re

ubyte[256] getLookup(){

    ubyte[256] t=void;
    foreach(i;0..256){
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * 0x1B);
    }
    ubyte[256] S=void;
    S[0] = 0x63;
    foreach(i;0..255){
        int x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        S[t[i]] = cast(ubyte)(x & 0xFF) ^ 0x63 ;
    }
    return S;

}

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 ubytea ubytesin búsquedas de la matriz, sin ramificaciones y bucles totalmente desenrollables

B[256] S(B:ubyte)(B i){
    B mulInv(B x){
        B r;
        foreach(i;0..256){
            B p=0,h,a=i,b=x;
            foreach(c;0..8){
                p^=(b&1)*a;
                h=a>>>7;
                a<<=1;
                a^=h*0x1b;//h is 0 or 1
                b>>=1;
            }
            if(p==1)r=i;//happens 1 or less times over 256 iterations
        }
        return r;
    }
    B s= x=mulInv(i);
    foreach(j,0..4){
        x^=(s=s<<1|(s>>>7));
    }
    return x^99;
}

edit2 utilizó algo de @Thomas para crear la tabla de búsqueda

monstruo de trinquete
fuente