En FIPS-197 (el Estándar de cifrado avanzado , conocido como AES), se utiliza mucho SubBytes, lo que podría implementarse como
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};
return t[x];}
Esta función no es arbitraria; Es un mapeo reversible, que consiste en una inversión en un campo de Galois seguido de una transformación afín. Todos los detalles están en FIPS-197 sección 5.1.1 o aquí sección 4.2.1 (bajo un nombre ligeramente diferente).
Un problema con la implementación como tabla es que se abre a los llamados ataques de sincronización de caché .
Por lo tanto, su misión es idear un reemplazo exacto para la SubBytes()función anterior , que exhibe un comportamiento de tiempo constante; asumiremos que ese es el caso cuando no se usa nada dependiendo de la entrada xde SubBytes:
- como un índice de matriz,
- como el control operando de
if,while,for,case, o el operador?:; - como cualquier operando de operadores
&&,||,!,==,!=,<,>,<=,>=,*,/,%; - como el operando derecho de los operadores
>>,<<,*=,/=,%=,<<=,>>=.
El ganador será uno con el costo más bajo, obtenido a partir del número de operadores ejecutados en la ruta de datos de entrada-dependiente, con un peso de 5 para los operadores unarios -y ~así como para <<1, >>1, +1, -1; peso de 7 para todos los demás operadores, turnos con otros recuentos o adiciones / subscripciones de otras constantes (los tipos de lanzamientos y promociones son gratuitos). Por principio, ese costo no cambia al desenrollar los bucles (si los hay), y es independiente de la entrada x. Como factor decisivo, gana la respuesta con el código más corto después de eliminar espacios en blanco y comentarios.
Planeo designar una entrada como respuesta lo antes posible en el año 2013, UTC. Consideraré las respuestas en los idiomas que conozco, clasificándolas como una traducción directa a C no optimizada para el tamaño.
Disculpas por la omisión inicial de +1y -1en los operadores favorecidos, de lanzamientos gratuitos y promociones, y clasificación de tamaño. Tenga en cuenta que *está prohibido tanto cuando es unario como de multiplicación.
fuente
Respuestas:
Puntuación:
940933926910, enfoque de torre de campoLa estructura es esencialmente la misma que la implementación de Boyar y Peralta: reduzca la inversión en GF (2 ^ 8) a la inversión en GF (2 ^ 4), divídala en un prólogo lineal, un cuerpo no lineal y un epílogo lineal, y luego minimizarlos por separado. Pago algunas penalizaciones por la extracción de bits, pero lo compenso al poder realizar operaciones en paralelo (con un poco de relleno juicioso de los bits de
fwd). Con más detalle...Antecedentes
Como se menciona en la descripción del problema, el cuadro S consiste en una inversión en una implementación particular del campo de Galois GF (2 ^ 8) seguido de una transformación afín. Si sabe lo que ambos significan, omita esta sección.
Una transformación afín (o lineal) es una función
f(x)que respetaf(x + y) = f(x) + f(y)yf(a*x) = a*f(x).Un campo es un conjunto
Fde elementos con dos elementos especiales, que llamaremos0y1, y dos operadores, que llamaremos+y*, que respeta varias propiedades. En esta sección, se supone quex,yyzson elementos deF.Fforma un grupo abeliano bajo+con0como la identidad: es decir,x + yes un elemento deF;x + 0 = 0 + x = x; cada unoxtiene un correspondiente-xtal quex + (-x) = (-x) + x = 0;x + (y + z) = (x + y) + z; yx + y=y + x.Fotro que0forma un grupo abeliano bajo*con1como la identidad.x * (y + z) = (x * y) + (x * z).Resulta que hay algunas limitaciones bastante severas en los campos finitos:
pestá el primo ykes el poder) .F\{0}debajo*es cíclico; es decir, hay al menos un elemento degtal manera que cada elemento es un poderg.kdel campo del orden primo. Por ejemplo, GF (2 ^ 8) tiene una representación en términos de polinomios dexmás de GF (2). De hecho, generalmente hay más de una representación. Considerex^7 * xen GF (2 ^ 8); debe ser equivalente a algún polinomio de orden 7, pero ¿cuál? Hay muchas opciones que dan la estructura correcta; AES elige hacerx^8 = x^4 + x^3 + x + 1(el polinomio lexicográficamente más pequeño que funciona).Entonces, ¿cómo calculamos un inverso en esa representación particular de GF (2 ^ 8)? Es un problema demasiado difícil de abordar directamente, por lo que debemos desglosarlo.
Torres de campo: representando GF (2 ^ 8) en términos de GF (2 ^ 4)
En lugar de representar GF (2 ^ 8) con polinomios de 8 términos sobre GF (2), podemos representarlo con polinomios de 2 términos sobre GF (2 ^ 4). Esta vez tenemos que elegir un polinomio lineal para
x^2. Supongamos que elegimosx^2 = px + q. Entonces(ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq).¿Es más fácil encontrar un inverso en esta representación? Si
(cx + d) = (ax + b)^-1obtenemos las ecuaciones simultáneasad + (b + ap)c = 0bd + (aq)c = 1Dejar
D = [b(b+ap) + a^2 q]y ponerc = a * D^-1;d = (b + ap) * D^-1. Entonces podemos hacer un inverso en GF (2 ^ 8) por el costo de una conversión a GF (2 ^ 4), un inverso y algunas adiciones y multiplicaciones en GF (2 ^ 4), y una conversión de regreso. Incluso si hacemos lo inverso por medio de una tabla, hemos reducido el tamaño de la tabla de 256 a 16.Detalles de implementacion
Para construir una representación de GF (4) podemos elegir entre tres polinomios para reducir
x^4:x^4 = x + 1x^4 = x^3 + 1x^4 = x^3 + x^2 + x + 1La diferencia más importante está en la implementación de la multiplicación. Para cualquiera de los tres (que corresponden a
poly3, 9, f) funcionará lo siguiente:Sin embargo, si elegimos
poly = 3, podemos manejar el desbordamiento de manera mucho más eficiente porque tiene una estructura agradable: no hay doble desbordamiento, porque las dos entradas son cúbicas yx^6 = x^2 (x + 1)también son cúbicas. Además, podemos guardar los cambios deb: ya que estamos dejando que el desbordamiento dure,a0 x^2no tiene ningún bit establecido correspondiente axo 1, por lo que podemos enmascararlo con -4 en lugar de -1. El resultado esTodavía tenemos que elegir los valores de
pyqpara la representación de GF (2 ^ 8) sobre GF (2 ^ 4), pero no tenemos muchas restricciones sobre ellos. Lo único que importa es que podemos obtener una función lineal de los bits de nuestra representación original a los bits de la representación de trabajo. Esto es importante por dos razones: en primer lugar, es fácil realizar transformaciones lineales, mientras que una transformación no lineal requeriría una optimización equivalente en dificultad a la optimización de todo el S-box; En segundo lugar, porque podemos obtener algunos beneficios secundarios. Para recapitular la estructura:Si los bits de
xsonx7 x6 ... x0entonces, dado que la transformación es lineal, obtenemosa = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Ajústalo y obtenemosa^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2donde se cancelan los términos cruzados (porque en GF (2),1 + 1 = 0). Pora^2lo tanto , también se puede calcular como una función lineal dex. Podemos aumentar la transformación lineal directa para obtener:y tenemos tres multiplicaciones y una suma. También podemos extender el código de multiplicación para hacer las dos multiplicaciones
Dinven paralelo. Por lo tanto, nuestro costo total es una transformación lineal hacia adelante, una suma, dos multiplicaciones, una inversa en GF (2 ^ 4) y una transformación lineal hacia atrás. Podemos lanzar la transformación lineal post-inversa del S-box y obtener eso esencialmente gratis.El cálculo de los coeficientes para las transformaciones lineales no es muy interesante, y tampoco lo es la microoptimización para guardar una máscara aquí y un cambio allí. La parte interesante restante es la optimización de
inverse_GF16. Hay 2 ^ 64 funciones diferentes de 4 bits a 4 bits, por lo que una optimización directa requiere mucha memoria y tiempo. Lo que he hecho es considerar 4 funciones de 4 bits a 1 bit, poner un límite al costo total permitido para cualquier función (con un costo máximo de 63 por función puedo enumerar todas las expresiones adecuadas en menos de un minuto), y para cada tupla de funciones, elimine la subexpresión común. Después de 25 minutos de procesamiento, encuentro que el mejor inverso posible con ese límite tiene un costo total de 133 (un promedio de 33.25 por bit de salida, lo cual no es malo teniendo en cuenta que la expresión más barata para cualquier bit individual es 35) .Todavía estoy experimentando con otros enfoques para minimizar la inversión en GF (2 ^ 4), y un enfoque que construye de abajo hacia arriba en lugar de de arriba hacia abajo ha arrojado una mejora de 133 a 126.
fuente
& 1se puede recortar (especialmente sixesunsigned char;CHAR_BITes 8 en codegolf).Puntuación: 980 = 7 * 5 + 115 * 7 + 7 * 5 + 15 * 7, minimización de Boyar y Peralta
Encontré una nueva técnica de minimización de lógica combinacional con aplicaciones a la criptología de Joan Boyar y René Peralta, que (salvo el formalismo C) hace lo que se requiere. La técnica utilizada para derivar sus ecuaciones está patentada por nada menos que Estados Unidos. Acabo de hacer una traducción C directa de sus ecuaciones , amablemente vinculada aquí .
fuente
Puntuación: 10965
Esto utiliza el mismo principio de desenrollar la búsqueda de matriz. Puede requerir moldes adicionales.
Gracias a ugoren por señalar cómo mejorar
is_zero.fuente
(c|-c)>>31es 0 para 0 y -1 en caso contrario.c >> 4parece un giro a la derecha firmado para mí. Y si realmente insistes, lo((unsigned int)(c|-c))>>31esc?1:0.c >>4obras con o sin extensión de signo. Pero es una buena idea usar un turno sin firmar: se editará cuando llegue a casa y pueda usar una computadora adecuada en lugar de un teléfono. Gracias.Puntuación: 9109, enfoque algebraico
Dejaré el enfoque de búsqueda en caso de que alguien pueda mejorarlo drásticamente, pero resulta que es posible un buen enfoque algebraico. Esta implementación encuentra el inverso multiplicativo usando el algoritmo de Euclides . Lo escribí en Java pero, en principio, puede portarse a C: he comentado las partes que cambiarían si desea volver a trabajarlo utilizando solo tipos de 8 bits.
Gracias a ugoren por señalar cómo acortar el
is_nonzerocheque en un comentario sobre mi otra respuesta.fuente
Puntuación: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (asumiendo bucles desenrollados)
Explicación:
Esencialmente, una búsqueda de matriz se vuelve a implementar utilizando operadores bit a bit y siempre procesando toda la matriz. Recorremos la matriz y xor
xcon cada índice, luego usamos operadores bit a bit para negar lógicamente el resultado, por lo que obtenemos 255 cuandox=iy 0 de lo contrario. Hacemos bit a bit, y esto con el valor de la matriz, de modo que el valor elegido no cambia y los demás se convierten en 0. Luego tomamos el bit a bit o de esta matriz, sacando así solo el valor elegido.Las dos
1 << joperaciones desaparecerían como parte del desenrollado del bucle, reemplazándolas con las potencias de 2 de 1 a 128.fuente
-(2+2)viene el cálculo de puntuación? Editar: ah, la creación de líneas crea ay<<1a>>1.Puntuación
19681692, usando la tabla de búsquedaNota: Esta solución no pasa los criterios debido a
w >> b.Usando la tabla de búsqueda, pero leyendo 8 bytes a la vez.
3 * 7 + 32 * (6 * 7 + 2 * 5) + 7 = 692
fuente
w>>bRHS ha calculado a partir dexw >> bdondebdepende de la entrada; Tambiénx/8,x%8y*= (1-badi). El primero es especialmente probable que degenere en una dependencia de tiempo en las CPU de gama baja. Sin embargo, la idea de usar variables amplias ciertamente tiene potencial.w >> bes bastante esencial (que necesito para ver si se puede solucionar sin tener que reescribir todo.Tabla de búsqueda y máscara, puntaje = 256 * (5 * 7 + 1 * 5) = 10240
Utiliza la búsqueda de tablas con una máscara para seleccionar solo el resultado que queremos. Utiliza el hecho de que
j|-jes negativo (cuando i! = X) o cero (cuando i == x). Shifting crea una máscara de todo uno o de cero, que se utiliza para seleccionar solo la entrada que queremos.fuente