C: substitua a tabela AES FIPS-197 SubBytes pelo código de tempo constante

17

No FIPS-197 (o Padrão Avançado de Criptografia , conhecido como AES), ele é muito utilizado SubBytes, o que pode ser implementado 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 função não é arbitrária; é um mapeamento reversível, que consiste em uma inversão em um campo de Galois, seguida de uma transformação afim. Todos os detalhes estão na seção 5.1.1 do FIPS-197 ou na seção 4.2.1 (sob um nome ligeiramente diferente).

Um problema com a implementação como tabela é que ela se abre para os chamados ataques de tempo de cache .

Portanto, sua missão é criar um substituto exato para a SubBytes()função acima , que exibe comportamento em tempo constante; assumiremos que é o caso quando nada, dependendo da entrada xde, SubBytesfor usado:

  • como um índice de matriz,
  • como o controlo operando de if, while, for, case, ou operador ?:;
  • como qualquer operando de operadores &&, ||, !, ==, !=, <, >, <=, >=, *, /, %;
  • como o operando direito dos operadores >>, <<, *=, /=, %=, <<=, >>=.

O vencedor será um com o menor custo, obtido a partir do número de operadores executados no caminho de dados dependente da entrada, com um peso de 5 para os operadores unárias -e ~, bem como para <<1, >>1, +1, -1; 7 para todos os outros operadores, trocas com outras contagens ou acréscimos / subs de outras constantes (conversões de tipo e promoções são gratuitas). Por princípio, esse custo é inalterado por desenrolamentos de loops (se houver) e independente da entrada x. Como desempate, a resposta com o código mais curto após a remoção de espaços em branco e comentários ganha.

Pretendo designar uma entrada como resposta o mais cedo possível no ano de 2013, UTC. Considerarei respostas em idiomas que eu conheço, classificando-as como uma tradução direta para C não otimizada para tamanho.

Desculpas pela omissão inicial +1e -1nos operadores favorecidos, de elencos e promoções gratuitos e classificação de tamanho. Observe que *é proibido quando unário e como multiplicação.

fgrieu
fonte
11
Vale ressaltar que as pesquisas são gratuitas porque você pode incorporá-las como constantes.
Peter Taylor
"no início de 2013, UTC" - a data não seria mais interessante que o fuso horário?
Paŭlo Ebermann
@ PaŭloEbermann: Minha intenção deve estar clara agora.
fgrieu

Respostas:

13

Pontuação: 940 933 926 910, aproximação por torre de campo

public class SBox2
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    private static int SubBytes(int x) {
        int fwd;
        fwd  = 0x010001 & -(x & 1); x >>= 1; //   7+5+7+5+ | 24+
        fwd ^= 0x1d010f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x4f020b & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x450201 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xce080d & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xa20f0f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xc60805 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x60070e & -x;                // 7+7+5+     | 19+

        // Running total so far: 229

        int p1;
        {
            int ma = fwd;
            int mb = fwd >> 16;         // 7+         | 7+
            p1  = ma & -(mb&1); ma<<=1; //   7+5+7+5+ | 24+
            p1 ^= ma & -(mb&2); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&4); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&8);         // 7+7+5+7+   | 26+
            int t = p1 >> 3;            // 7+         | 7+
            p1 ^= (t >> 1) ^ (t & 0xe); // 7+5+7+7+   | 26+
        }

        // Running total so far: 229 + 152 = 381

        int y3, y2, y1, y0;
        {
            int Kinv = (fwd >> 20) ^ p1;     // 7+7+
            int w0 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w1 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w2 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w3 = Kinv & 1;               // 7+

            int t0 = w1 ^ w0 ^ (w2 & w3);      // 7+7+7+
            int t1 = w2 ^ (w0 | w3);           // 7+7+
            int t2 = t0 ^ t1;                  // 7+

            y3 = t2 ^ (t1 & (w1 & w3));        // 7+7+7+
            y2 = t0 ^ (w0 | t2);               // 7+7+
            y1 = w0 ^ w3 ^ (t1 & t0);          // 7+7+7+
            y0 = w3 ^ (t0 | (w1 ^ (w0 | w2))); // 7+7+7+7


        }

        // Running total so far: 381 + 24*7 + 3*5 = 564

        int p2;
        {
            int ma = fwd;
            p2  = ma & -y0; ma<<=1;       //   7+5+5+ | 17+
            p2 ^= ma & -y1; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y2; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y3;               // 7+7+5+   | 19+
            int t = p2 >> 3;              // 7+       | 7+
            p2 ^= (t >> 1) ^ (t & 0xe0e); // 7+5+7+7+ | 26
        }

        // Running total so far: 564 + 117 = 681

        int inv8;
        inv8  =  31 & -(p2 & 1);           //   7+5+7+   | 19+
        inv8 ^= 178 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 171 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  54 & -(p2 & 2); p2 >>= 6; // 7+7+5+7+7+ | 33+
        inv8 ^= 188 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  76 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 127 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^= 222 & -(p2 & 2);           // 7+7+5+7    | 26+

        return inv8 ^ 0x63;                // 7+         | 7+

        // Grand total: 681 + 229 = 910
    }
}

A estrutura é essencialmente a mesma que a implementação de Boyar e Peralta - reduza a inversão em GF (2 ^ 8) a inversão em GF (2 ^ 4), divida-a em um prólogo linear, um corpo não linear e um epílogo linear, e, em seguida, minimize-os separadamente. Pago algumas penalidades pela extração de bits, mas compenso por poder fazer operações em paralelo (com algum preenchimento criterioso dos bits de fwd). Em mais detalhes...

fundo

Como mencionado na descrição do problema, o S-box consiste em uma inversão em uma implementação específica do campo Galois GF (2 ^ 8) seguida por uma transformação afim. Se você souber o que esses dois significam, pule esta seção.

Uma transformação afim (ou linear) é uma função f(x)que respeita f(x + y) = f(x) + f(y)e f(a*x) = a*f(x).

Um campo é um conjunto Fde elementos com dois elementos especiais, que chamaremos 0e 1, e dois operadores, que chamaremos +e *, que respeitarão várias propriedades. Nesta seção, vamos supor que x, ye zsão elementos de F.

  • Os elementos de Fum grupo abeliano formam +com 0a identidade: ie x + yé um elemento de F; x + 0 = 0 + x = x; cada xum tem um correspondente -xtal que x + (-x) = (-x) + x = 0; x + (y + z) = (x + y) + z; e x + y= y + x.
  • Os elementos de Foutros que não 0formam um grupo abeliano abaixo de *com 1a identidade.
  • Multiplicação distribui sobre a adição: x * (y + z) = (x * y) + (x * z).

Acontece que existem algumas limitações bastante severas em campos finitos:

  • Eles devem ter um número de elementos que é um poder de primo.
  • Eles são isomórficos com todos os outros campos finitos do mesmo tamanho (ou seja, existe realmente apenas um campo finito de um determinado tamanho, e quaisquer outros são apenas re-rotulamentos; chame esse campo de GF (p ^ k) onde pé o primo e ké o poder) .
  • O grupo multiplicativo F\{0}abaixo *é cíclico; ou seja, há pelo menos um elemento gque permite que cada elemento seja uma potência g.
  • Para potências maiores que 1, há uma representação como polinômios univariados de ordem kdo campo da ordem principal. Por exemplo, GF (2 ^ 8) tem uma representação em termos de polinômios xacima de GF (2). De fato, geralmente há mais de uma representação. Considere x^7 * xem GF (2 ^ 8); deve ser equivalente a algum polinômio da ordem 7, mas qual? Existem muitas opções que dão a estrutura correta; A AES escolhe fazer x^8 = x^4 + x^3 + x + 1(o polinômio lexicograficamente menor que funciona).

Então, como calculamos um inverso nessa representação específica de GF (2 ^ 8)? É um problema muito pesado para ser abordado diretamente, por isso precisamos decompô-lo.

Torres de campo: representando GF (2 ^ 8) em termos de GF (2 ^ 4)

Em vez de representar GF (2 ^ 8) com polinômios de 8 termos sobre GF (2), podemos representá-lo com polinômios de 2 termos sobre GF (2 ^ 4). Desta vez, precisamos escolher um polinômio linear para x^2. Suponha que escolhamos x^2 = px + q. Então (ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq).

É mais fácil encontrar um inverso nessa representação? Se (cx + d) = (ax + b)^-1obtivermos as equações simultâneas

  • ad + (b + ap)c = 0
  • bd + (aq)c = 1

Deixe D = [b(b+ap) + a^2 q]e ponha c = a * D^-1; d = (b + ap) * D^-1. Portanto, podemos fazer um inverso em GF (2 ^ 8) pelo custo de uma conversão para GF (2 ^ 4), um inverso e algumas adições e multiplicações em GF (2 ^ 4) e uma conversão de volta. Mesmo se fizermos o inverso por meio de uma tabela, reduzimos o tamanho da tabela de 256 para 16.

Detalhes da implementação

Para construir uma representação de GF (4), podemos escolher entre três polinômios para reduzir x^4:

  • x^4 = x + 1
  • x^4 = x^3 + 1
  • x^4 = x^3 + x^2 + x + 1

A diferença mais importante está na implementação da multiplicação. Para qualquer um dos três (que corresponde a poly3, 9, f), o seguinte funcionará:

// 14x &, 7x unary -, 3x <<1, 3x >>1, 3x >>3, 6x ^ gives score 226
int mul(int a, int b) {
    // Call current values a = a0, b = b0
    int p = a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x); a = a0 x; b = b0 div x

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^2); a = a0 x^2; b = b0 div x^2

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^3); a = a0 x^3; b = b0 div x^3

    p ^= a & -(b & 1);
    // p = a0 * b0

    return p;
}

No entanto, se escolhermos poly = 3, podemos lidar com o estouro de maneira muito mais eficiente, porque ela possui uma boa estrutura: não existe um estouro duplo, porque as duas entradas são cúbicas e x^6 = x^2 (x + 1)também cúbicas. Além disso, podemos salvar os turnos de b: como estamos deixando o overflow durar, a0 x^2não possui nenhum conjunto de bits correspondente a xou 1 e, portanto, podemos mascará-lo com -4 em vez de -1. O resultado é

// 10x &, 4x unary -, 3x <<1, 1x >>1, 1x >>3, 5x ^ gives score 152
int mul(int a, int b) {
    int p;
    p  = a & -(b & 1); a <<= 1;
    p ^= a & -(b & 2); a <<= 1;
    p ^= a & -(b & 4); a <<= 1;
    p ^= a & -(b & 8);
    // Here p = a0 * b0 but with overflow, which we need to bring back down.

    int t = p >> 3;
    p ^= (t >> 1) ^ (t & 0xe);
    return p & 15;
}

Ainda precisamos escolher os valores de pe qpara a representação de GF (2 ^ 8) sobre GF (2 ^ 4), mas não temos muitas restrições sobre eles. A única coisa que importa é que podemos obter uma função linear dos bits de nossa representação original para os bits da representação de trabalho. Isso é importante por duas razões: primeiro, é fácil fazer transformações lineares, enquanto uma transformação não linear exigiria uma otimização equivalente em dificuldade para otimizar apenas a caixa S inteira; segundo, porque podemos obter alguns benefícios colaterais. Para recapitular a estrutura:

GF256 SubBytes(GF256 x) {
    GF16 a, b, t, D, Dinv, c, d;

    (a, b) = f(x); // f is linear

    t = b + a * p;
    D = b * t + a * a * q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d); // finv is also linear
}

Se os bits de xsão x7 x6 ... x0então, uma vez que a transformação é linear, obtemos a = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Esquadre e chegamos a^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2onde as condições cruzadas são canceladas (porque em GF (2) 1 + 1 = 0). Então a^2também pode ser calculado como uma função linear de x. Podemos aumentar a transformação linear direta para obter:

GF256 SubBytes(GF256 x) {
    GF16 a, b, t, a2q, D, Dinv, c, d;

    (a, b, t, a2q) = faug(x);

    D = b * t + a2q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d);
}

e reduzimos para três multiplicações e uma adição. Também podemos estender o código de multiplicação para fazer as duas multiplicações Dinvparalelamente. Portanto, nosso custo total é uma transformação linear direta, uma adição, duas multiplicações, uma inversa em GF (2 ^ 4) e uma transformação linear posterior. Podemos fazer a transformação linear pós-inversa da caixa S e obtê-la essencialmente de graça.

O cálculo dos coeficientes para as transformações lineares não é muito interessante, nem a micro-otimização para salvar uma máscara aqui e uma mudança lá. A parte interessante restante é a otimização deinverse_GF16. Existem 2 ^ 64 funções diferentes, de 4 a 4 bits, portanto, uma otimização direta requer muita memória e tempo. O que fiz foi considerar 4 funções de 4 bits a 1 bit, limitar o custo total permitido para qualquer função (com um custo máximo de 63 por função, posso enumerar todas as expressões adequadas em menos de um minuto), e para cada tupla de funções, elimine subexpressões comuns. Após 25 minutos de trituração, acho que o melhor inverso possível com esse limite tem um custo total de 133 (uma média de 33,25 por bit da saída, o que não é ruim, considerando que a expressão mais barata para qualquer bit individual é 35) .

Ainda estou experimentando outras abordagens para minimizar a inversão em GF (2 ^ 4), e uma abordagem que constrói de baixo para cima em vez de cima para baixo produziu uma melhoria de 133 para 126.

Peter Taylor
fonte
Fantástico! Eu confirmo que funciona! Um detalhe: o oitavo & 1pode ser aparado (especialmente se xfor unsigned char; CHAR_BITé 8 no codegolf).
fgrieu
@grgrieu, bom ponto.
Peter Taylor
8

Pontuação: 980 = 7 * 5 + 115 * 7 + 7 * 5 + 15 * 7, minimização de Boyar e Peralta

Encontrei Uma nova técnica combinatória de minimização de lógica com aplicações em criptografia de Joan Boyar e René Peralta, que (exceto o formalismo em C) faz o que é necessário. A técnica usada para derivar suas equações é patenteada por nada menos que os EUA. Acabei de fazer uma tradução direta em C de suas equações , gentilmente vinculada aqui .

unsigned char SubBytes_Boyar_Peralta(unsigned char x7){
  unsigned char 
  x6=x7>>1,x5=x6>>1,x4=x5>>1,x3=x4>>1,x2=x3>>1,x1=x2>>1,x0=x1>>1,
  y14=x3^x5,y13=x0^x6,y9=x0^x3,y8=x0^x5,t0=x1^x2,y1=t0^x7,y4=y1^x3,y12=y13^y14,y2=y1^x0,
  y5=y1^x6,y3=y5^y8,t1=x4^y12,y15=t1^x5,y20=t1^x1,y6=y15^x7,y10=y15^t0,y11=y20^y9,y7=x7^y11,
  y17=y10^y11,y19=y10^y8,y16=t0^y11,y21=y13^y16,y18=x0^y16,t2=y12&y15,t3=y3&y6,t4=t3^t2,
  t5=y4&x7,t6=t5^t2,t7=y13&y16,t8=y5&y1,t9=t8^t7,t10=y2&y7,t11=t10^t7,t12=y9&y11,
  t13=y14&y17,t14=t13^t12,t15=y8&y10,t16=t15^t12,t17=t4^t14,t18=t6^t16,t19=t9^t14,
  t20=t11^t16,t21=t17^y20,t22=t18^y19,t23=t19^y21,t24=t20^y18,t25=t21^t22,t26=t21&t23,
  t27=t24^t26,t28=t25&t27,t29=t28^t22,t30=t23^t24,t31=t22^t26,t32=t31&t30,t33=t32^t24,
  t34=t23^t33,t35=t27^t33,t36=t24&t35,t37=t36^t34,t38=t27^t36,t39=t29&t38,t40=t25^t39,
  t41=t40^t37,t42=t29^t33,t43=t29^t40,t44=t33^t37,t45=t42^t41,z0=t44&y15,z1=t37&y6,
  z2=t33&x7,z3=t43&y16,z4=t40&y1,z5=t29&y7,z6=t42&y11,z7=t45&y17,z8=t41&y10,z9=t44&y12,
  z10=t37&y3,z11=t33&y4,z12=t43&y13,z13=t40&y5,z14=t29&y2,z15=t42&y9,z16=t45&y14,z17=t41&y8,
  t46=z15^z16,t47=z10^z11,t48=z5^z13,t49=z9^z10,t50=z2^z12,t51=z2^z5,t52=z7^z8,t53=z0^z3,
  t54=z6^z7,t55=z16^z17,t56=z12^t48,t57=t50^t53,t58=z4^t46,t59=z3^t54,t60=t46^t57,
  t61=z14^t57,t62=t52^t58,t63=t49^t58,t64=z4^t59,t65=t61^t62,t66=z1^t63,s0=t59^t63,
  s6=t56^t62,s7=t48^t60,t67=t64^t65,s3=t53^t66,s4=t51^t66,s5=t47^t65,s1=t64^s3,s2=t55^t67;
  return (((((((s0<<1|s1&1)<<1|s2&1)<<1|s3&1)<<1|s4&1)<<1|s5&1)<<1|s6&1)<<1|s7&1)^0x63;}
fgrieu
fonte
Uau, realmente funciona e muito barato. Ao desmontar, são de fato 144 instruções, excluindo prólogo, epílogo e instruções de movimentação.
Ugoren
5

Pontuação: 10965

Isso usa o mesmo princípio de desenrolar a pesquisa de matriz. Pode exigir lançamentos extras.

Obrigado a ugoren por apontar como melhorar is_zero.

// Cost: 255 * (5+7+24+7) = 10965
unsigned char SubBytes(unsigned char x) {
    unsigned char r = 0x63;
    char c = (char)x;
    c--; r ^= is_zero(c) & (0x63^0x7c); // 5+7+24+7 inlining the final xor
    c--; r ^= is_zero(c) & (0x63^0x77); // 5+7+24+7
    // ...
    c--; r ^= is_zero(c) & (0x63^0x16); // 5+7+24+7
    return r;
}

// Cost: 24
// Returns (unsigned char)-1 when input is 0 and 0 otherwise
unsigned char is_zero(char c) {
    // Shifting a signed number right is unspecified, so use unsigned
    unsigned char u;
    c |= -c;               // 7+5+
    u = (unsigned char)c;
    u >>= (CHAR_BITS - 1); // 7+
    c = (char)u;
    // c is 0 if we want -1 and 1 otherwise.
    c--;                   // 5
    return (unsigned char)c;
}
Peter Taylor
fonte
2
Para um número inteiro c, (c|-c)>>31é 0 para 0 e -1 caso contrário.
Ugoren
@ugoren, em idiomas sensíveis, sim. Em C, o deslocamento à direita de um tipo não assinado não é especificado.
Peter Taylor
11
Eu acho que você quer dizer assinado. Mas este site não é realmente famoso pela conformidade estrita com os padrões. Além disso, você c >> 4parece ter assinado o turno certo para mim. E se você realmente insiste - ((unsigned int)(c|-c))>>31é c?1:0.
Ugoren
@ugoren, você está certo, eu quis dizer assinado. Os c >>4trabalhos com ou sem extensão de sinal. Mas é bom usar um turno não assinado: ele será editado quando chegar em casa e poderá usar um computador adequado em vez de um telefone. Obrigado.
Peter Taylor
3

Pontuação: 9109, abordagem algébrica

Deixarei a abordagem de pesquisa caso alguém possa melhorá-la drasticamente, mas acontece que uma boa abordagem algébrica é possível. Esta implementação encontra a inversa multiplicativa usando o algoritmo de Euclid . Escrevi em Java, mas em princípio pode ser portado para C - comentei as partes que seriam alteradas se você quisesse retrabalhá-lo usando apenas tipos de 8 bits.

Obrigado a ugoren por apontar como diminuir a is_nonzeroverificação em um comentário na minha outra resposta.

public class SBox
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    // Total cost: 9109
    public static int SubBytes(int x)
    {
        x = inv_euclid(x); // 9041
        x = affine(x);     // 68
        return x;
    }

    // Total cost: 68
    private static int affine(int s0) {
        int s = s0;
        s ^= (s0 << 1) ^ (s0 >> 7); // 5 + 7
        s ^= (s0 << 2) ^ (s0 >> 6); // 7 + 7
        s ^= (s0 << 3) ^ (s0 >> 5); // 7 + 7
        s ^= (s0 << 4) ^ (s0 >> 4); // 7 + 7
        return (s ^ 0x63) & 0xff;   // 7 + 7
    }

    // Does the inverse in the Galois field for a total cost of 24 + 9010 + 7 = 9041
    private static int inv_euclid(int s) {
        // The first part of handling the special case: cost of 24
        int zeromask = is_nonzero(s);

        // NB the special value of r would complicate the unrolling slightly with unsigned bytes
        int r = 0x11b, a = 0, b = 1;

        // Total cost of loop: 7*(29+233+566+503+28) - 503 = 9010
        for (int depth = 0; depth < 7; depth++) { // 7*(
            // Calculate mask to fake out when we're looping further than necessary: cost 29
            int mask = is_nonzero(s >> 1);

            // Cost: 233
            int ord = polynomial_order(s);

            // This next block does div/rem at a total cost of 6*(24+49) + 69 + 59 = 566
            int quot = 0, rem = r;
            for (int i = 7; i > 1; i--) {                   // 6*(
                int divmask = is_nonzero(ord & (rem >> i)); // 24+7+7
                quot ^= (1 << i) & divmask;                 // 7+0+7+ since 1<<i is inlined on unrolling
                rem ^= (s << i) & divmask;                  // 7+7+7) +
            }
            int divmask1 = is_nonzero(ord & (rem >> 1));    // 24+7+5
            quot ^= 2 & divmask1;                           // 7+7+
            rem ^= (s << 1) & divmask1;                     // 7+5+7+
            int divmask0 = is_nonzero(ord & rem);           // 24+7
            quot ^= 1 & divmask0;                           // 7+7+
            rem ^= s & divmask0;                            // 7+7

            // This next block does the rest for the cost of a mul (503) plus 28
            // When depth = 0, b = 1 so we can skip the mul on unrolling
            r = s;
            s = rem;
            quot = mul(quot, b) ^ a;
            a = b;
            b ^= (quot ^ b) & mask;
        }

        // The rest of handling the special case: cost 7
        return b & zeromask;
    }

    // Gets the highest set bit in the input. Assumes that it's always at least 1<<1
    // Cost: 233
    private static int polynomial_order(int s) {
        int ord = 2;
        ord ^= 6 & -((s >> 2) & 1);           // 7+7+5+7+7 = 33 +
        ord ^= (ord ^ 8) & -((s >> 3) & 1);   // 7+7+7+5+7+7 = 40 +
        ord ^= (ord ^ 16) & -((s >> 4) & 1);  // 40 +
        ord ^= (ord ^ 32) & -((s >> 5) & 1);  // 40 +
        ord ^= (ord ^ 64) & -((s >> 6) & 1);  // 40 +
        ord ^= (ord ^ 128) & -((s >> 7) & 1); // 40
        return ord;
    }

    // Returns 0 if c is 0 and -1 otherwise
    // Cost: 24
    private static int is_nonzero(int c) {
        c |= -c;   // 7+5+
        c >>>= 31; // 7+ (simulating a cast to unsigned and right shift by CHAR_BIT)
        c = -c;    // 5+ (could be saved assuming a particular implementation of signed right shift)
        return c;
    }

    // Performs a multiplication in the Rijndael finite field
    // Cost: 503 (496 if working with unsigned bytes)
    private static int mul(int a, int b) {
        int p = 0;
        for (int counter = 0; counter < 8; counter++) { // 8*(_+_
            p ^= a & -(b & 1);                          // +7+7+5+7
            a = (a << 1) ^ (0x1b & -(a >> 7));          // +5+7+7+5+7
            b >>= 1;                                    // +5)
        }
        p &= 0xff;                                      // +7 avoidable with unsigned bytes
        return p;
    }
}
Peter Taylor
fonte
2

Pontuação: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (assumindo que os loops se desenrolavam)

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};

unsigned char ret_val = 0;
int i,j;
for(i=0;i<256;i++) {
  unsigned char is_index = (x ^ ((unsigned char) i));
  for(j=0;j<8;j++) {
   is_index |= (is_index << (1 << j)) | (is_index >> (1 << j));
  }
  is_index = ~is_index;
  ret_val |= is_index & t[i];
}

return ret_val;}

Explicação:

Essencialmente, uma pesquisa de matriz é reimplementada usando operadores bit a bit e sempre processando toda a matriz. Fazemos um loop pela matriz e xor xcom cada índice, depois usamos operadores bit a bit para negar logicamente o resultado, obtendo 255 quando x=ie 0 em caso contrário. Nós bit a bit - e isso com o valor da matriz, para que o valor escolhido seja inalterado e os outros se tornem 0. Então pegamos o bit a bit - ou dessa matriz, retirando apenas o valor escolhido.

As duas 1 << joperações desapareceriam como parte do desenrolar do loop, substituindo-as pelas potências de 2 de 1 a 128.

histocrata
fonte
Agora, veja se é possível realmente fazer as contas usando operadores bit a bit.
histocrat
Examinando o algoritmo aqui , duvido que seja possível implementar a inversão polinomial sem repetir todos os bytes pelo menos uma vez como substituto de algumas das etapas de tempo polinomial. Portanto, isso pode superar qualquer solução "inteligente". Suspeito que ajustar essa consulta de matriz em tempo constante seja uma avenida mais promissora.
histocrat
Agradável. A função rj_sbox em aes.c aqui pode dar inspiração (embora, como esteja, não corresponda à pergunta).
fgrieu
De onde vem o -(2+2)cálculo de pontuação? Edit: ah, inlining cria ae <<1a >>1.
22612 Peter Taylor
0

Pontuação 1968 1692, usando a tabela de pesquisa

Nota: Esta solução não passa nos critérios por causa de w >> b.

Usando a tabela de pesquisa, mas lendo 8 bytes por vez.
3 * 7 + 32 * (6 * 7 + 2 * 5) + 7 = 692

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};

  unsigned long long *t2 = (unsigned long long *)t;
  int a = x>>3, b=(x&7)<<3;                       // 7+7+7
  int i;
  int ret = 0;
  for (i=0;i<256/8;i++) {                         // 32 *
      unsigned long long w = t2[i];
      int badi = ((unsigned int)(a|-a))>>31;      // 7+7+5
      w &= (badi-1);                              // +7+7
      a--;                                        // +5
      ret |= w >> b;                              // +7+7
  }
  return ret & 0xff;                              // +7
}
Ugoren
fonte
Eu não acho que isso atenda à definição de tempo constante na pergunta, porque o w>>bRHS foi calculado a partir dex
Peter Taylor
Existem várias violações: w >> bonde bdepende da entrada; também x/8, x%8e *= (1-badi). O primeiro provavelmente degenerará em uma dependência de tempo em CPUs de última geração. No entanto, a ideia de usar variáveis ​​amplas certamente tem potencial.
fgrieu
Não li as instruções com atenção suficiente. Posso corrigir a maioria dos problemas, mas w >> bé absolutamente essencial (Eu preciso ver se ele pode ser corrigido sem reescrever tudo.
ugoren
0

Consulta e máscara da tabela, pontuação = 256 * (5 * 7 + 1 * 5) = 10240

Usa a pesquisa de tabela com uma máscara para selecionar apenas o resultado que queremos. Usa o fato de que j|-jé negativo (quando i! = X) ou zero (quando i == x). A mudança cria uma máscara tudo-um ou tudo-zero que é usada para selecionar apenas a entrada que queremos.

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};

unsigned char SubBytes(unsigned char x) {
  unsigned char r = 255;
  for (int i = 0; i < 256; i++) {
    int j = i - x;
    r &= t[i] | ((j | -j) >> 31);
  }
  return r;
}
Keith Randall
fonte
Não é o mesmo que a minha segunda resposta, exceto menos otimizada?
Peter Taylor
Perto, eu acho. Estou usando o turno assinado para não precisar fazer o -1 no final.
Keith Randall