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.
fonte
Respostas:
Pontuação:
940 933 926910, aproximação por torre de campoA 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 respeitaf(x + y) = f(x) + f(y)ef(a*x) = a*f(x).Um campo é um conjunto
Fde elementos com dois elementos especiais, que chamaremos0e1, e dois operadores, que chamaremos+e*, que respeitarão várias propriedades. Nesta seção, vamos supor quex,yezsão elementos deF.Fum grupo abeliano formam+com0a identidade: iex + yé um elemento deF;x + 0 = 0 + x = x; cadaxum tem um correspondente-xtal quex + (-x) = (-x) + x = 0;x + (y + z) = (x + y) + z; ex + y=y + x.Foutros que não0formam um grupo abeliano abaixo de*com1a identidade.x * (y + z) = (x * y) + (x * z).Acontece que existem algumas limitações bastante severas em campos finitos:
pé o primo eké o poder) .F\{0}abaixo*é cíclico; ou seja, há pelo menos um elementogque permite que cada elemento seja uma potênciag.kdo campo da ordem principal. Por exemplo, GF (2 ^ 8) tem uma representação em termos de polinômiosxacima de GF (2). De fato, geralmente há mais de uma representação. Considerex^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 fazerx^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 escolhamosx^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âneasad + (b + ap)c = 0bd + (aq)c = 1Deixe
D = [b(b+ap) + a^2 q]e ponhac = 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 + 1x^4 = x^3 + 1x^4 = x^3 + x^2 + x + 1A 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á: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 ex^6 = x^2 (x + 1)também cúbicas. Além disso, podemos salvar os turnos deb: como estamos deixando o overflow durar,a0 x^2não possui nenhum conjunto de bits correspondente axou 1 e, portanto, podemos mascará-lo com -4 em vez de -1. O resultado éAinda precisamos escolher os valores de
peqpara 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:Se os bits de
xsãox7 x6 ... x0então, uma vez que a transformação é linear, obtemosa = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Esquadre e chegamosa^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ãoa^2também pode ser calculado como uma função linear dex. Podemos aumentar a transformação linear direta para obter: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 de
inverse_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.
fonte
& 1pode ser aparado (especialmente sexforunsigned char;CHAR_BITé 8 no codegolf).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 .
fonte
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.fonte
(c|-c)>>31é 0 para 0 e -1 caso contrário.c >> 4parece ter assinado o turno certo para mim. E se você realmente insiste -((unsigned int)(c|-c))>>31éc?1:0.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.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.fonte
Pontuação: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (assumindo que os loops se desenrolavam)
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 quandox=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.fonte
-(2+2)cálculo de pontuação? Edit: ah, inlining cria ae<<1a>>1.Pontuação
19681692, usando a tabela de pesquisaNota: 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
fonte
w>>bRHS foi calculado a partir dexw >> bondebdepende da entrada; tambémx/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.w >> bé absolutamente essencial (Eu preciso ver se ele pode ser corrigido sem reescrever tudo.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.fonte