Ich bin einer der Autoren von Gimli. Wir haben bereits eine 2-Tweet-Version (280 Zeichen) in C, aber ich würde gerne sehen, wie klein sie werden kann.

Gimli ( Papier , Webseite ) ist ein Entwurf für kryptografische Permutation mit hoher Geschwindigkeit und hohem Sicherheitsniveau, der auf der Konferenz über kryptografische Hardware und eingebettete Systeme (CHES) 2017 (25.-28. September) vorgestellt wird.

Die Aufgabe

Wie immer: Die kleinteilige, nutzbare Implementierung von Gimli in der Sprache Ihrer Wahl.

Es sollte in der Lage sein, 384 Bits (oder 48 Bytes oder 12 vorzeichenlose Int ...) als Eingabe zu verwenden und das Ergebnis von Gimli, das auf diese 384 Bits angewendet wurde, zurückzugeben (kann an Ort und Stelle geändert werden, wenn Sie Zeiger verwenden) .

Die Eingabeumwandlung von Dezimal, Hexadezimal, Oktal oder Binär ist zulässig.

Mögliche Eckfälle

Die Ganzzahlkodierung wird als Little-Endian-Kodierung angenommen (z. B. was Sie wahrscheinlich bereits haben).

Sie können umbenennen Gimliin , Gaber es muss noch ein Funktionsaufruf sein.

Wer gewinnt?

Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes! Es gelten selbstverständlich Standardregeln.

Eine Referenzimplementierung ist unten angegeben.

Hinweis

Einige Bedenken wurden laut:

"hey gang, bitte implementiere mein programm kostenlos in anderen sprachen, damit ich nicht muss" (danke an @jstnthms)

Meine Antwort lautet wie folgt:

Ich kann es leicht in Java, C #, JS, Ocaml tun ... Es ist mehr für den Spaß. Derzeit haben wir (das Gimli-Team) es auf AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, SSE-entrollt, AVX, AVX2, VHDL und Python3 implementiert (und optimiert). :)

Über Gimli

Der Staat

Gimli wendet eine Folge von Runden auf einen 384-Bit-Zustand an. Der Zustand wird als Parallelepiped mit den Dimensionen 3 × 4 × 32 oder äquivalent als 3 × 4-Matrix von 32-Bit-Wörtern dargestellt.

Jede Runde ist eine Folge von drei Operationen:

• eine nichtlineare Schicht, insbesondere eine 96-Bit-SP-Box, die auf jede Spalte angewendet wird;
• in jeder zweiten Runde eine lineare Mischschicht;
• in jeder vierten Runde eine ständige Ergänzung.

Die nichtlineare Schicht.

Die SP-Box besteht aus drei Unteroperationen: Rotation des ersten und des zweiten Wortes; eine nichtlineare T-Funktion mit 3 Eingängen; und ein Tausch des ersten und dritten Wortes.

Die lineare Schicht.

Die lineare Ebene besteht aus zwei Swap-Operationen, nämlich Small-Swap und Big-Swap. Small-Swap tritt alle 4 Runden ab der ersten Runde auf. Big-Swap erfolgt alle 4 Runden ab der 3. Runde.

Die runden Konstanten.

Es gibt 24 Runden in Gimli, nummeriert 24,23, ..., 1. Wenn die Rundenzahl r 24,20,16,12,8,4 ist, XOREN wir die Rundenkonstante (0x9e377900 XOR r) zum ersten Zustandswort.

Bezugsquelle in 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);
    }
  }
}

Tweetbare Version in C

Dies ist möglicherweise nicht die kleinste verwendbare Implementierung, aber wir wollten eine C-Standardversion (also keine UB und "verwendbar" in einer Bibliothek).

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

Vektor testen

Die folgende Eingabe wurde generiert von

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

und "gedruckte" Werte von

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

somit:

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

sollte zurückkehren:

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

CJam (114 Zeichen)

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

Dies ist ein anonymer Block (Funktion): Wenn Sie ihn benennen möchten, Gfügen Sie ihn hinzu :G. In CJam können zugewiesene Namen nur einzelne Großbuchstaben sein. Es ist Platz, um einen Kommentar anzufügen e# Gimli in CJamund Zeichen in einem einzigen Tweet zu haben.

Online-Test

Präparation

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

Wahrscheinlich habe ich mit meiner Austauschmethode Bytes gewonnen, aber es ist zu niedlich, um es nicht zu verwenden.

C, 268 Zeichen (268 Bytes) unter Verwendung von uint32_t

Hinweis: Da der ursprüngliche Code as verwendet <stdint.h>und eingibt , ist die Verwendung von ein Cheat, um auf Kosten der Portabilität auf 280 Zeichen zu kommen, was der Grund für die Verwendung ist . Wenn wir für einen fairen Vergleich die konsequente Verwendung und die explizite Signatur benötigen , ist der Originalcode wirklich 284 Zeichen und der orlp-Code 276 Zeichen.Suint32_t *longuint32_tuint32_tvoid gimli(uint32_t *)

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

Dies kann in zwei Tweets mit Fortsetzungsmarkierungen als aufgeteilt werden

#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

und

*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

Nur ein 1: 1-Hafen in der Nähe, von dem aus Sie mit dem Golfen beginnen können.

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

Probieren Sie es online!

JavaScript (ES6), 231 Byte

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

32-Bit-x86-Assembler (112 Byte)

(__cdecl Aufrufkonvention)

            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

Tweetbare Version (Base85-Codierung im z85-Format):

v7vb1h> C} HbQuA91y51A: oWYw48G)? I = H /] rGf9Na> sA.DWu06 {6f # TEC ^ CM: # IeA-cstx7:>! } t $ ^ wM51j% LDf $ HMAg2bB ^ MQP