Gimli, mach es noch kürzer?

25

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.

Zustand

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.

SP

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.

Linear

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.

Bildbeschreibung hier eingeben

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 
Biv
quelle
3
Ein Tweet ist 140 Zeichen, kein 280
Stan Strum
1
Ich weiß, weshalb es in 2 passt;) twitter.com/TweetGimli .
Biv
10
"Hey Gang, bitte implementiere mein Programm kostenlos in anderen Sprachen, damit ich nicht muss"
jstnthms
hahaha Nee, ich habe es bereits in Python und ich kann es leicht in Java, C #, JS machen. Es ist mehr für den Spaß. :)
Biv
5
Der Referenzcode auf der Website hat einen entscheidenden Fehler, -roundstatt --roundbedeutet , dass es nie endet. Die Konvertierung --in einen Bindestrich wird im Code wahrscheinlich nicht empfohlen :)
orlp

Antworten:

3

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
}
Peter Taylor
quelle
Für einen Moment wurde ich von der Tatsache, dass die Ausgabe nicht in hex (im Online-Test) war geworfen. :)
Biv
15

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.

orlp
quelle
verloren oder gewonnen?
HyperNeutrino
@HyperNeutrino Gewonnen, was mich zu einem Verlierer macht :)
orlp
Ah ok: P macht Sinn: P: P
HyperNeutrino
Dies ist definitiv immer noch eine Verbesserung, aber es ist etwas zu betrügen unsignedanstatt uint32_t(und OPs Code war etwas zu betrügen long), weil die Idee hinter der Chiffre ist, dass es sehr portabel ist. (Das spart im Prinzip nur 8 Bytes).
Peter Taylor
1
@PeterTaylor Obwohl mein Code ähnlich ist, konkurriere ich nicht wirklich mit OPs Code. Ich arbeite nach den Regeln von PPCG, wo es mit mindestens einer Implementierung auf einer Plattform funktionieren muss, und mit gcceiner 32-Bit- oder 64-Bit-Intel-CPU (und wahrscheinlich noch viel mehr).
Orlp
4

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
Peter Taylor
quelle
Die Verwendung von longin meiner Version ist sicher (in Bezug auf Portabilität), da die Mindestgröße eines Long standardmäßig 32 Bit beträgt (im Gegensatz zu int). Drehungen von xund ywerden vor dem Eingießen longbei der Zuweisung vorgenommen, um die Sicherheit zu gewährleisten (da die Verschiebung nach rechts vom vorzeichenbehafteten Wert CC-abhängig ist). Die Besetzung beim Zurückkehren zu uint32_t* S) entfernt die oberen Teile und versetzt uns in den richtigen Zustand :).
Biv
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!

Roberto Graham
quelle
1
Warum Integerüberhaupt verwenden? o_O Da Sie keine IntegerMethode verwenden, gibt es keinen Grund, ints hier nicht zu verwenden ...
Olivier Grégoire
@ OlivierGrégoire Ich denke, nur ein Rest von mir versucht Integer.divideUnsigned, aber ich erkannte, ich kann >>>
Roberto Graham
s[0]^=(0x9e377900|r);(ganz am Ende) - kannst du die zusätzlichen Klammern nicht fallen lassen?
Clashsoft
Gleiche mit s[4+c]>>>(23).
Clashsoft
1
Sie können weit weniger Änderungen vornehmen und erhalten 300: void P(int[]S,int a,int b){int x=S[a];S[a]=S[b];S[b]=x;}void gimli(int[]S){for(int r=24,c,x,y,z;r>0;S[0]^=y<1?0x9e377901+r:0){for(c=4;c-->0;){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);}y=r%4;if(--r%2>0){P(S,0,1+y/2);P(S,3,2-y/2);}}}. Ich habe im Grunde genommen die minimalen Änderungen vorgenommen, die erforderlich sind, damit es kompiliert werden kann. Javas Vorrangregeln unterscheiden sich nicht sehr von denen von C.
Peter Taylor
2

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

Arnauld
quelle
0

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
Peter Ferrie
quelle