Я один из авторов Гимли. У нас уже есть версия с 2 твитами (280 символов) в C, но я бы хотел посмотреть, насколько она может быть маленькой.

Gimli ( статья , веб-сайт ) - это высокоскоростной дизайн криптографической перестановки с высоким уровнем безопасности, который будет представлен на Конференции по криптографическому оборудованию и встраиваемым системам (CHES) 2017 (25-28 сентября).

Задание

Как обычно: сделать небольшую полезную реализацию Gimli на выбранном вами языке.

Он должен иметь возможность принимать в качестве входных данных 384 бита (или 48 байт, или 12 беззнаковых целых ...) и возвращать (может изменить на месте, если вы используете указатели) результат Gimli, примененный к этим 384 битам.

Допускается преобразование входных данных из десятичного, шестнадцатеричного, восьмеричного или двоичного.

Потенциальные угловые случаи

Предполагается, что целочисленное кодирование является прямым порядком байтов (например, то, что вы, вероятно, уже имеете).

Вы можете переименовать Gimliв, Gно это все равно должен быть вызов функции.

Кто выигрывает?

Это код-гольф, поэтому выигрывает самый короткий ответ в байтах! Стандартные правила применяются конечно.

Ссылочная реализация приведена ниже.

Заметка

Некоторая обеспокоенность была поднята:

«Эй, банда, пожалуйста, реализуй мою программу бесплатно на других языках, чтобы мне не пришлось» (спасибо @jstnthms)

Мой ответ следующий:

Я легко могу сделать это на Java, C #, JS, Ocaml ... Это больше для удовольствия. В настоящее время мы (команда Gimli) внедрили (и оптимизировали) это для AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, развернутых SSE, AVX, AVX2, VHDL и Python3. :)

О Гимли

Штат

Гимли применяет последовательность раундов к 384-битному состоянию. Состояние представлено в виде параллелепипеда с размерами 3 × 4 × 32 или, что эквивалентно, в виде матрицы 3 × 4 из 32-разрядных слов.

Каждый раунд представляет собой последовательность из трех операций:

• нелинейный уровень, в частности 96-битный SP-блок, применяемый к каждому столбцу;
• в каждом втором раунде слой линейного смешивания;
• в каждом четвертом раунде постоянное прибавление.

Нелинейный слой.

SP-бокс состоит из трех подопераций: повороты первого и второго слов; нелинейная Т-функция с 3 входами; и обмен первым и третьим словами.

Линейный слой.

Линейный слой состоит из двух операций подкачки, а именно, Small-Swap и Big-Swap. Мелкий обмен происходит каждые 4 раунда, начиная с 1-го раунда. Большой своп происходит каждые 4 раунда, начиная с 3-го раунда.

Круглые константы.

В Гимли 24 раунда, пронумерованных 24,23, ..., 1. Когда число раунда r равно 24,20,16,12,8,4, мы XOR округляем константу (0x9e377900 XOR r) до первого слова состояния.

справочный источник в 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);
    }
  }
}

Tweetable версия в C

Это может быть не наименьшая используемая реализация, но мы хотели иметь стандартную версию C (таким образом, нет UB и «можно использовать» в библиотеке).

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

Тестовый вектор

Следующий вход, сгенерированный

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

и «напечатанные» значения по

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

таким образом:

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

должен вернуть:

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

CJam (114 символов)

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

Это анонимный блок (функция): если вы хотите назвать его, Gдобавьте :G. В CJam назначенные имена могут состоять только из заглавных букв. Есть место, чтобы добавить комментарий e# Gimli in CJamи оставить символы в одном твите.

Онлайн тест

рассечение

{                                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 байтов

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

Я, вероятно, получил байты с моим методом обмена, но это слишком мило, чтобы не использовать.

C, 268 символов (268 байт), используя uint32_t

NB Так как оригинальный код использует <stdint.h>и печатает Sкак uint32_t *, я думаю, что использование кода long- это обман, позволяющий набрать 280 символов за счет переносимости, что и является причиной использования uint32_tв первую очередь. Если для справедливости сравнения нам требуется последовательное использование uint32_tи явная подпись void gimli(uint32_t *), то исходный код на самом деле составляет 284 символа, а код orlp - 276 символов.

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

Это может быть разделено на два твита с маркерами продолжения как

#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

а также

*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 байт

Всего лишь 1: 1 порт для начала игры в гольф.

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

Попробуйте онлайн!

JavaScript (ES6), 231 байт

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}

демонстрация

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-битный x86 ассемблер (112 байт)

(__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

Tweetable версия (кодировка Base85 в формате z85):

v7vb1h> C} HbQuA91y51A: oWYw48G) I = H /] rGf9Na> sA.DWu06 {6f # TEC ^ CM: # IEA-cstx7:!> VfVf # и * YB & Мр (tuCl * + 7eENBP) $ :) Lh к } т $ ^ wM51j% LDF $ HMAg2bB ^ MQP