Jestem jednym z autorów Gimli. Mamy już wersję z 2 tweetami (280 znaków) w C, ale chciałbym zobaczyć, jak mała może być.

Gimli ( papier , strona internetowa ) to projekt z dużą szybkością i permutacją kryptograficzną o wysokim poziomie bezpieczeństwa, który zostanie zaprezentowany podczas Konferencji na temat sprzętu kryptograficznego i systemów wbudowanych (CHES) 2017 (25-28 września).

Zadanie

Jak zwykle: aby niewielka użyteczna implementacja Gimli w wybranym przez Ciebie języku.

Powinien być w stanie pobrać 384 bity (lub 48 bajtów lub 12 znaków bez znaku ...) i zwrócić (może zmodyfikować w miejscu, jeśli używasz wskaźników) wynik Gimli zastosowany na tych 384 bitach.

Dozwolona jest konwersja wejściowa z dziesiętnej, szesnastkowej, ósemkowej lub binarnej.

Potencjalne narożne skrzynki

Zakłada się, że kodowanie liczb całkowitych ma charakter endianowy (np. To, co prawdopodobnie już masz).

Możesz zmienić nazwę Gimlina, Gale wciąż musi to być wywołanie funkcji.

Kto wygrywa?

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach! Oczywiście obowiązują standardowe zasady.

Implementacja referencyjna znajduje się poniżej.

Uwaga

Pojawiły się pewne obawy:

„hej, proszę, zaimplementuj mój program za darmo w innych językach, aby nie musiałem” (podziękowania dla @jstnthms)

Moja odpowiedź jest następująca:

Z łatwością mogę to zrobić w Javie, C #, JS, Ocaml ... To jest więcej dla zabawy. Obecnie My (zespół Gimli) wdrożyliśmy (i zoptymalizowaliśmy) w AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, SSE-Unrolled, AVX, AVX2, VHDL i Python3. :)

O Gimli

Stan

Gimli stosuje sekwencję rund do stanu 384-bitowego. Stan jest reprezentowany jako równoległościan o wymiarach 3 × 4 × 32 lub, równoważnie, jako macierz 3 × 4 32-bitowych słów.

Każda runda jest sekwencją trzech operacji:

• warstwa nieliniowa, w szczególności 96-bitowy moduł SP nałożony na każdą kolumnę;
• w każdej drugiej rundzie liniowa warstwa mieszająca;
• w co czwartej rundzie stały dodatek.

Warstwa nieliniowa.

SP-box składa się z trzech podoperacji: rotacji pierwszego i drugiego słowa; 3-wejściowa nieliniowa funkcja T; i zamiana pierwszego i trzeciego słowa.

Warstwa liniowa.

Warstwa liniowa składa się z dwóch operacji wymiany, mianowicie Small-Swap i Big-Swap. Small-Swap występuje co 4 rundy, zaczynając od 1. rundy. Big-Swap odbywa się co 4 rundy, począwszy od 3 rundy.

Stałe rundy.

Gimli ma 24 rundy o numerach 24,23, ..., 1. Gdy liczba rundy r wynosi 24,20,16,12,8,4 XOR, stała XOR (0x9e377900 XOR r) do pierwszego słowa stanu.

źródło odniesienia w 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);
    }
  }
}

Wersja tweetowana w C.

Być może nie jest to najmniejsza użyteczna implementacja, ale chcieliśmy mieć wersję standardową C (a zatem brak UB i „użyteczną” w bibliotece).

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

Wektor testowy

Następujące dane wejściowe wygenerowane przez

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

i „wydrukowane” wartości przez

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

a zatem:

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

powinien zwrócić:

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

CJam (114 znaków)

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

Jest to anonimowy blok (funkcja): jeśli chcesz go nazwać, Gdołącz :G. W CJam przypisanym nazwom mogą być tylko pojedyncze wielkie litery. Jest miejsce na dodanie komentarza e# Gimli in CJami pozostawienie znaków w jednym tweecie.

Test online

Sekcja

{                                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 bajtów

#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)}}

Prawdopodobnie zyskałem bajty dzięki metodzie wymiany, ale jest to zbyt urocze, aby nie używać.

C, 268 znaków (268 bajtów) przy użyciu uint32_t

Uwaga: Ponieważ oryginalny kod używa <stdint.h>i typów Sjako uint32_t *, myślę, że użycie longjest oszustwem, aby dostać się do 280 znaków kosztem przenośności, co jest powodem użycia uint32_tw pierwszej kolejności. Jeśli dla uczciwości porównania potrzebujemy konsekwentnego użycia uint32_ti wyraźnego podpisu void gimli(uint32_t *), oryginalny kod to tak naprawdę 284 znaki, a kod orlp to 276 znaków.

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

Można to podzielić na dwa tweety ze znacznikami kontynuacji jako

#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

i

*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 bajtów

Tylko blisko 1: 1 port odniesienia, od którego można zacząć grać w golfa.

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

Wypróbuj online!

JavaScript (ES6), 231 bajtów

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}

Próbny

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(' ')
)

32-bitowy asembler x86 (112 bajtów)

(__cdecl konwencja wywoływania)

            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

Wersja z tweetowaniem (kodowanie Base85 w formacie 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