Je suis l'un des auteurs de Gimli. Nous avons déjà une version 2 tweet (280 caractères) en C mais j'aimerais voir à quel point elle peut être petite.

Gimli ( papier , site Web ) est une conception de permutation cryptographique à haut débit et à haut niveau de sécurité qui sera présentée à la Conférence sur le matériel cryptographique et les systèmes embarqués (CHES) 2017 (25-28 septembre).

La tâche

Comme d'habitude: pour rendre la petite implémentation utilisable de Gimli dans la langue de votre choix.

Il devrait pouvoir prendre en entrée 384 bits (ou 48 octets, ou 12 entier non signé ...) et retourner (peut modifier en place si vous utilisez des pointeurs) le résultat de Gimli appliqué sur ces 384 bits.

La conversion d'entrée décimale, hexadécimale, octale ou binaire est autorisée.

Boîtes de coin potentielles

Le codage entier est supposé être petit-endien (par exemple ce que vous avez probablement déjà).

Vous pouvez renommer Gimlien Gmais il doit toujours s'agir d'un appel de fonction.

Qui gagne?

Il s'agit de code-golf, donc la réponse la plus courte en octets l'emporte! Les règles standard s'appliquent bien sûr.

Une implémentation de référence est fournie ci-dessous.

Remarque

Certaines préoccupations ont été exprimées:

"Hé gang, veuillez implémenter mon programme gratuitement dans d'autres langues pour ne pas avoir à le faire" (merci à @jstnthms)

Ma réponse est la suivante:

Je peux facilement le faire en Java, C #, JS, Ocaml ... C'est plus pour le fun. Actuellement, nous (l'équipe Gimli) l'avons implémenté (et optimisé) sur AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, SSE-unrolled, AVX, AVX2, VHDL et Python3. :)

À propos de Gimli

L'état

Gimli applique une séquence de tours à un état de 384 bits. L'état est représenté comme un parallélépipède de dimensions 3 × 4 × 32 ou, de manière équivalente, comme une matrice 3 × 4 de mots de 32 bits.

Chaque tour est une séquence de trois opérations:

• une couche non linéaire, spécifiquement un SP-box 96 bits appliqué à chaque colonne;
• à chaque deuxième tour, une couche de mélange linéaire;
• à chaque quatrième tour, un ajout constant.

La couche non linéaire.

La SP-box se compose de trois sous-opérations: rotation des premier et deuxième mots; une fonction T non linéaire à 3 entrées; et un échange des premier et troisième mots.

La couche linéaire.

La couche linéaire se compose de deux opérations de swap, à savoir Small-Swap et Big-Swap. Small-Swap se produit tous les 4 tours à partir du 1er tour. Big-Swap se produit tous les 4 tours à partir du 3e tour.

Les constantes rondes.

Il y a 24 tours à Gimli, numérotés 24,23, ..., 1. Lorsque le nombre rond r est 24,20,16,12,8,4, nous XOR la ​​constante ronde (0x9e377900 XOR r) au premier mot d'état.

source de référence en 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);
    }
  }
}

Version tweetable en C

Ce n'est peut-être pas la plus petite implémentation utilisable mais nous voulions avoir une version standard C (donc pas d'UB, et "utilisable" dans une bibliothèque).

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

Vecteur de test

L'entrée suivante générée par

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

et les valeurs "imprimées" par

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

Ainsi:

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

devrait retourner:

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

CJam (114 caractères)

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

Il s'agit d'un bloc anonyme (fonction): si vous voulez le nommer, Gajoutez-le :G. Dans CJam, les noms attribués ne peuvent être que des lettres majuscules simples. Il y a de l'espace pour ajouter un commentairee# Gimli in CJam et laisser des caractères dans un seul tweet.

Test en ligne

Dissection

{                                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 octets

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

J'ai probablement gagné des octets avec ma méthode de swapping, mais c'est trop mignon pour ne pas l'utiliser.

C, 268 caractères (268 octets) en utilisant uint32_t

NB Étant donné que le code d'origine utilise <stdint.h>et tape Sas uint32_t *, je pense que l'utilisation de longest une triche pour entrer dans 280 caractères au détriment de la portabilité, ce qui est la raison de l'utilisation uint32_ten premier lieu. Si pour des raisons d'équité de comparaison, nous exigeons une utilisation cohérente de uint32_tet la signature explicite void gimli(uint32_t *), le code d'origine est en réalité 284 caractères, et le code orlp est de 276 caractères.

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

Cela peut être divisé en deux tweets avec des marqueurs de continuation comme

#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

et

*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 octets

Juste un port proche de 1: 1 de la référence pour commencer à jouer au golf.

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

Essayez-le en ligne!

JavaScript (ES6), 231 octets

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}

Démo

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

Assembleur x86 32 bits (112 octets)

(convention d'appel __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

Version Tweetable (encodage Base85 au format 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