Eu sou um dos autores de Gimli. Já temos uma versão de 2 tweets (280 caracteres) em C, mas eu gostaria de ver como ela pode ficar pequena.

Gimli ( documento , site ) é uma alta velocidade com design de permutação criptográfica de alto nível de segurança que será apresentada na Conferência sobre Hardware Criptográfico e Sistemas Incorporados (CHES) 2017 (25 a 28 de setembro).

A tarefa

Como de costume: para tornar a implementação reduzida do Gimli no idioma de sua escolha.

Ele deve receber 384 bits de entrada (ou 48 bytes ou 12 int sem sinal ...) e retornar (pode modificar no local se você usar ponteiros) o resultado do Gimli aplicado nesses 384 bits.

É permitida a conversão de entrada de decimal, hexadecimal, octal ou binário.

Casos de canto em potencial

Supõe-se que a codificação inteira seja little-endian (por exemplo, o que você provavelmente já possui).

Você pode renomear Gimlipara, Gmas ainda deve ser uma chamada de função.

Quem ganha?

Isso é código-golfe, então a resposta mais curta em bytes vence! Regras padrão se aplicam, é claro.

Uma implementação de referência é fornecida abaixo.

Nota

Alguma preocupação foi levantada:

"ei galera, implemente meu programa gratuitamente em outros idiomas para não precisar" (thx para @jstnthms)

Minha resposta é a seguinte:

Eu posso fazê-lo facilmente em Java, C #, JS, Ocaml ... É mais por diversão. Atualmente, nós (a equipe Gimli) implementamos (e otimizamos) o AVR, o Cortex-M0, o Cortex-M3 / M4, o Neon, o SSE, o SSE, o desenrolamento do SSE, o AVX, o AVX2, o VHDL e o Python3. :)

Sobre Gimli

O Estado

Gimli aplica uma sequência de rodadas a um estado de 384 bits. O estado é representado como um paralelepípedo com dimensões 3 × 4 × 32 ou, equivalentemente, como uma matriz 3 × 4 de palavras de 32 bits.

Cada rodada é uma sequência de três operações:

• uma camada não linear, especificamente uma caixa SP de 96 bits aplicada a cada coluna;
• em cada segunda rodada, uma camada de mistura linear;
• em cada quarta rodada, uma adição constante.

A camada não linear.

A caixa SP consiste em três suboperações: rotações da primeira e da segunda palavras; uma função T não linear de 3 entradas; e uma troca da primeira e terceira palavras.

A camada linear.

A camada linear consiste em duas operações de swap, a saber, Small-Swap e Big-Swap. O Small-Swap ocorre a cada 4 rodadas, começando na 1ª rodada. O Big-Swap ocorre a cada 4 rodadas, começando na 3ª rodada.

As constantes redondas.

Há 24 rodadas em Gimli, numeradas 24,23, ..., 1. Quando o número da ronda r é 24,20,16,12,8,4, XOR é a constante da ronda (0x9e377900 XOR r) para a primeira palavra de estado.

fonte de referência em C

#include <stdint.h>

uint32_t rotate(uint32_t x, int bits)
{
  if (bits == 0) return x;
  return (x << bits) | (x >> (32 - bits));
}

extern void gimli(uint32_t *state)
{
  int round;
  int column;
  uint32_t x;
  uint32_t y;
  uint32_t z;

  for (round = 24; round > 0; --round)
  {
    for (column = 0; column < 4; ++column)
    {
      x = rotate(state[    column], 24);
      y = rotate(state[4 + column],  9);
      z =        state[8 + column];

      state[8 + column] = x ^ (z << 1) ^ ((y&z) << 2);
      state[4 + column] = y ^ x        ^ ((x|z) << 1);
      state[column]     = z ^ y        ^ ((x&y) << 3);
    }

    if ((round & 3) == 0) { // small swap: pattern s...s...s... etc.
      x = state[0];
      state[0] = state[1];
      state[1] = x;
      x = state[2];
      state[2] = state[3];
      state[3] = x;
    }
    if ((round & 3) == 2) { // big swap: pattern ..S...S...S. etc.
      x = state[0];
      state[0] = state[2];
      state[2] = x;
      x = state[1];
      state[1] = state[3];
      state[3] = x;
    }

    if ((round & 3) == 0) { // add constant: pattern c...c...c... etc.
      state[0] ^= (0x9e377900 | round);
    }
  }
}

Versão Tweetable em C

Essa pode não ser a menor implementação utilizável, mas queríamos ter uma versão padrão C (portanto, não UB e "utilizável" em uma biblioteca).

#include<stdint.h>
#define P(V,W)x=V,V=W,W=x
void gimli(uint32_t*S){for(long r=24,c,x,y,z;r;--r%2?P(*S,S[1+y/2]),P(S[3],S[2-y/2]):0,*S^=y?0:0x9e377901+r)for(c=4;c--;y=r%4)x=S[c]<<24|S[c]>>8,y=S[c+4]<<9|S[c+4]>>23,z=S[c+8],S[c]=z^y^8*(x&y),S[c+4]=y^x^2*(x|z),S[c+8]=x^2*z^4*(y&z);}

Vetor de teste

A seguinte entrada gerada por

for (i = 0;i < 12;++i) x[i] = i * i * i + i * 0x9e3779b9;

e valores "impressos" por

for (i = 0;i < 12;++i) {
  printf("%08x ",x[i])
  if (i % 4 == 3) printf("\n");
}

portanto:

00000000 9e3779ba 3c6ef37a daa66d46 
78dde724 1715611a b54cdb2e 53845566 
f1bbcfc8 8ff34a5a 2e2ac522 cc624026 

deve retornar:

ba11c85a 91bad119 380ce880 d24c2c68 
3eceffea 277a921c 4f73a0bd da5a9cd8 
84b673f0 34e52ff7 9e2bef49 f41bb8d6 

CJam (114 caracteres)

{24{[4/z{[8ZT].{8\#*G8#:Mmd+}__)2*\+.^W%\[_~;&8*\~@1$|2*@@&4*].^Mf%}%z([7TGT]R=4e!=\f=(2654435608R-_4%!*^\@]e_}fR}

Este é um bloco anônimo (função): se você quiser nomeá-lo G, acrescente :G. No CJam, os nomes atribuídos podem ser apenas letras maiúsculas. Há espaço para acrescentar um comentário e# Gimli in CJame deixar os caracteres em um único tweet.

Teste online

Dissecação

{                                e# Define a block
  24{                            e# For R=0 to 23...
    [                            e#   Collect values in an array
      4/z                        e#     Transpose to columns
      {                          e#     Map over each column
        [8ZT].{8\#*G8#:Mmd+}     e#       Rotations, giving [x y z]
        __)2*\+.^W%\             e#       => [y^z x^y x^z*2] [x y z]
        [_~;&8*\~@1$|2*@@&4*].^  e#       => [x' y' z']
        Mf%                      e#       Map out any bits which overflowed
      }%
      z                          e#    Transpose to rows
      ([7TGT]R=4e!=\f=           e#    Permute first row
      (2654435608R-_4%!*^        e#    Apply round constant to first element
      \@                         e#    Put the parts in the right order
    ]e_                          e#  Finish collecting in array and flatten
  }fR
}

C (gcc), 237 bytes

#define P(a,l)x=a;a=S[c=l>>r%4*2&3];S[c]=x;
r,c,x,y,z;G(unsigned*S){
for(r=24;r;*S^=r--%4?0:0x9e377901+r){
for(c=4;c--;*S++=z^y^8*(x&y))
x=*S<<24|*S>>8,y=S[4]<<9|S[4]>>23,z=S[8],S[8]=x^2*z^4*(y&z),S[4]=y^x^2*(x|z);
S-=4;P(*S,33)P(S[3],222)}}

Eu provavelmente ganhei bytes com meu método de troca, mas é muito fofo para não usar.

C, 268 caracteres (268 bytes) usando uint32_t

NB Como o código original usa <stdint.h>e digita Scomo uint32_t *, acho que o uso de longé uma trapaça para chegar a 280 caracteres à custa da portabilidade, que é a razão do uso uint32_tem primeiro lugar. Se para fins de comparação, exigimos o uso consistente uint32_te a assinatura explícita void gimli(uint32_t *), o código original é realmente 284 caracteres e o código do orlp é 276 caracteres.

#include<stdint.h>
#define R(V)x=S[V],S[V]=S[V^y],S[V^y]=x,
void gimli(uint32_t*S){for(uint32_t r=24,x,y,z,*T;r--;y=72>>r%4*2&3,R(0)R(3)*S^=y&1?0x9e377901+r:0)for(T=S+4;T-->S;*T=z^y^8*(x&y),T[4]=y^x^2*(x|z),T[8]=x^2*z^4*(y&z))x=*T<<24|*T>>8,y=T[4]<<9|T[4]>>23,z=T[8];}

Isso pode ser dividido em dois tweets com marcadores de continuação, como

#include<stdint.h>
#define R(V)x=S[V],S[V]=S[V^y],S[V^y]=x,
void gimli(uint32_t*S){for(uint32_t r=24,x,y,z,*T;r--;y=72>>r%4*2&3,R(0)R(3)// 1

e

*S^=y&1?0x9e377901+r:0)for(T=S+4;T-->S;*T=z^y^8*(x&y),T[4]=y^x^2*(x|z),T[8]=x^2*z^4*(y&z))x=*T<<24|*T>>8,y=T[4]<<9|T[4]>>23,z=T[8];}// 2/2

Java (OpenJDK 8) , 351 343 339 320 318 247 + 56 bytes

Apenas uma porta 1: 1 próxima da referência para começar a jogar.

void f(int[]x,int y,int z){int q=x[y];x[y]=x[z];x[z]=q;}

s->{for(int r=24,c,x,y,z;r>0;--r){for(c=0;c<4;x=s[c]<<24|s[c]>>>8,y=s[4+c]<<9|s[4+c]>>>23,z=s[8+c],s[8+c]=x^z<<1^(y&z)<<2,s[4+c]=y^x^(x|z)<<1,s[c++]=z^y^(x&y)<<3);if((r&3)==2){f(s,0,2);f(s,1,3);}if((r&3)<1){f(s,0,1);f(s,2,3);s[0]^=0x9e377900|r;}}}

Experimente online!

JavaScript (ES6), 231 bytes

s=>{for(r=25;--r;[a,b,c,d,...e]=s,s=r&1?s:r&2?[c,d,a,b,...e]:[b,a,d,c,...e],s[0]^=r&3?0:0x9e377900|r)for(c=4;c--;x=s[c]<<24|s[c]>>>8,y=s[j=c+4]<<9|s[j]>>>23,z=s[c+8],s[c+8]=x^z*2^(y&z)*4,s[j]=y^x^(x|z)*2,s[c]=z^y^(x&y)*8);return s}

Demo

let f =

s=>{for(r=25;--r;[a,b,c,d,...e]=s,s=r&1?s:r&2?[c,d,a,b,...e]:[b,a,d,c,...e],s[0]^=r&3?0:0x9e377900|r)for(c=4;c--;x=s[c]<<24|s[c]>>>8,y=s[j=c+4]<<9|s[j]>>>23,z=s[c+8],s[c+8]=x^z*2^(y&z)*4,s[j]=y^x^(x|z)*2,s[c]=z^y^(x&y)*8);return s}

console.log(
  f([
    0x00000000, 0x9e3779ba, 0x3c6ef37a, 0xdaa66d46,
    0x78dde724, 0x1715611a, 0xb54cdb2e, 0x53845566,
    0xf1bbcfc8, 0x8ff34a5a, 0x2e2ac522, 0xcc624026
  ])
  .map(x=>(x >>> 0).toString(16)).join(' ')
)

Assembler x86 de 32 bits (112 bytes)

(convenção de chamada __cdecl)

            pusha
            mov     ecx, 9E377918h
    loc_6:  mov     esi, [esp+24h]
            push    esi
            push    4
            pop     ebx
    loc_E:  lodsd
            ror     eax, 8
            mov     ebp, [esi+0Ch]
            rol     ebp, 9
            mov     edx, [esi+1Ch]
            push    eax
            push    ebp
            lea     edi, [edx+edx]
            and     ebp, edx
            shl     ebp, 2
            xor     edi, ebp
            xor     eax, edi
            mov     [esi+1Ch], eax
            pop     ebp
            pop     eax
            push    eax
            push    ebp
            xor     ebp, eax
            or      eax, edx
            shl     eax, 1
            xor     ebp, eax
            mov     [esi+0Ch], ebp
            pop     ebp
            pop     eax
            xor     edx, ebp
            and     eax, ebp
            shl     eax, 3
            xor     edx, eax
            push    edx
            dec     ebx
            jnz     short loc_E
            pop     esi
            pop     ebp
            pop     ebx
            pop     eax
            pop     edi
            mov     dl, cl
            and     dl, 3
            jnz     short loc_5B
            xchg    eax, ebx
            xchg    esi, ebp
            xor     eax, ecx
    loc_5B: cmp     dl, 2
            jnz     short loc_63
            xchg    eax, ebp
            xchg    esi, ebx
    loc_63: stosd
            xchg    eax, ebx
            stosd
            xchg    eax, ebp
            stosd
            xchg    eax, esi
            stosd
            dec     cl
            jnz     short loc_6
            popa
            retn

Versão Tweetable (codificação Base85 no formato z85):

v7vb1h> C} HbQuA91y51A: oWYw48G)? I = H /] rGf9Na> sA.DWu06 {6f # TEC ^ CM: # IeA-cstx7:>! VfVf # u * YB & mP (tuCl * + 7eENBP) $ :) Lh! k } t $ ^ wM51j% LDf $ HMAg2bB ^ MQP