Гимли, сделать его еще короче?

25

Я один из авторов Гимли. У нас уже есть версия с 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 входами; и обмен первым и третьим словами.

SP

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

Линейный слой состоит из двух операций подкачки, а именно, 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 
Biv
источник
3
Твит 140 символов, а не 280
Stan
1
Я знаю, именно поэтому он вписывается в 2;) twitter.com/TweetGimli .
Бив,
10
«Эй, банда, пожалуйста, реализуй мою программу бесплатно на других языках, чтобы мне не пришлось»
jstnthms
хахаха нет у меня это уже есть на Python, и я могу легко сделать это на Java, C #, JS. Это больше для удовольствия. :)
Biv
5
Код ссылки на сайте содержит критическую ошибку, -roundа не --roundозначает, что он никогда не заканчивается. Преобразование --в тире, вероятно, не рекомендуется в коде :)
orlp

Ответы:

3

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
}
Питер Тейлор
источник
На мгновение меня обескуражил тот факт, что выход не был в шестнадцатеричном формате (в онлайн-тесте). :)
Biv
15

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

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

orlp
источник
потерял или получил?
HyperNeutrino
@HyperNeutrino Получил, сделав меня неудачником :)
orlp
Ах, хорошо: P имеет смысл: P: P
HyperNeutrino
Это еще определенно улучшение, но это несколько обмана использовать unsignedвместо uint32_t(и кода OP был несколько обмана для использования long) , потому что идея шифра, что это очень портативные. (Фактически, в основном это экономит всего 8 байтов).
Питер Тейлор
1
@PeterTaylor Несмотря на то, что мой код похож, я на самом деле не конкурирую с кодом OP. Я работаю по правилам PPCG, где он должен работать по крайней мере с реализацией на платформе, а также с gcc32-битным или 64-битным процессором Intel (и, вероятно, со многими другими).
17
4

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
Питер Тейлор
источник
Использование longв моей версии безопасно (относительно переносимости), потому что минимальный размер long по стандарту составляет 32 бита (в отличие от int). Вращения xи yвыполняются до приведения в longназначении, что делает их безопасными (так как смещение вправо на значение со знаком зависит от CC). Актерский состав при возвращении в uint32_t* S) избавляется от верхних бит и переводит нас в правильное состояние :).
Бив
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;}}}

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

Роберто Грэм
источник
1
Зачем Integerвообще использовать ? o_O Так как вы не используете какой-либо Integerметод, нет причин не использовать ints здесь ...
Olivier Grégoire
@ OlivierGrégoire Я думаю, что только остаток от меня, пытаясь Integer.divideUnsigned, но я понял, что могу иметь >>>
Роберто Грэхем
s[0]^=(0x9e377900|r);(в самом конце) - вы не можете удалить лишние скобки?
Clashsoft
То же самое с s[4+c]>>>(23).
Clashsoft
1
Вы можете сделать гораздо меньше изменений и получить 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);}}}. Я в основном внес минимальные изменения, необходимые для его компиляции. Правила приоритета Java не очень отличаются от Си.
Питер Тейлор
2

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}

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

Arnauld
источник
0

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
Питер Ферри
источник