Saya salah satu penulis Gimli. Kami sudah memiliki versi 2-tweet (280 karakter) di C tapi saya ingin melihat seberapa kecil itu bisa didapat.

Gimli ( kertas , situs web ) adalah kecepatan tinggi dengan desain permutasi kriptografi tingkat keamanan tinggi yang akan dipresentasikan pada Konferensi Perangkat Keras Kriptografi dan Sistem Tertanam (CHES) 2017 (25-28 September).

Tugas

Seperti biasa: untuk membuat implementasi Gimli yang dapat digunakan menjadi lebih kecil dalam bahasa pilihan Anda.

Seharusnya dapat mengambil 384 bit input (atau 48 byte, atau 12 int unsigned ...) dan mengembalikan (dapat memodifikasi di tempat jika Anda menggunakan pointer) hasil Gimli diterapkan pada 384 bit ini.

Konversi input dari desimal, heksadesimal, oktal atau biner diperbolehkan.

Kasing sudut potensial

Encoding integer diasumsikan sebagai little-endian (mis. Apa yang mungkin sudah Anda miliki).

Anda dapat mengubah nama Gimlimenjadi Gtetapi masih harus berupa panggilan fungsi.

Yang menang?

Ini adalah kode-golf sehingga jawaban tersingkat dalam byte menang! Aturan standar berlaku tentu saja.

Implementasi referensi disediakan di bawah ini.

Catatan

Beberapa keprihatinan telah dikemukakan:

"hei geng, tolong implementasikan program saya secara gratis dalam bahasa lain jadi saya tidak perlu" (thx to @jstnthms)

Jawaban saya adalah sebagai berikut:

Saya dapat dengan mudah melakukannya di Java, C #, JS, Ocaml ... Ini lebih untuk bersenang-senang. Saat ini Kami (tim Gimli) menerapkannya (dan dioptimalkan) pada AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, SSE-unrolled, AVX, AVX2, VHDL dan Python3. :)

Tentang Gimli

Negara

Gimli menerapkan urutan putaran ke keadaan 384-bit. Negara direpresentasikan sebagai paralelepiped dengan dimensi 3 × 4 × 32 atau, setara, sebagai matriks 3 × 4 kata 32-bit.

Setiap putaran adalah urutan dari tiga operasi:

• lapisan non-linear, khususnya SP-box 96-bit yang diterapkan pada setiap kolom;
• di setiap putaran kedua, lapisan pencampuran linier;
• di setiap ronde keempat, tambahan konstan.

Lapisan non-linear.

Kotak-SP terdiri dari tiga sub-operasi: rotasi kata pertama dan kedua; fungsi-T non-linier 3-input; dan swap kata pertama dan ketiga.

Lapisan linier.

Lapisan linier terdiri dari dua operasi swap, yaitu Small-Swap dan Big-Swap. Small-Swap terjadi setiap 4 ronde mulai dari ronde 1. Big-Swap terjadi setiap 4 putaran mulai dari putaran ke-3.

Konstanta bulat.

Ada 24 putaran di Gimli, bernomor 24,23, ..., 1. Ketika bilangan bulat r adalah 24,20,16,12,8,4 kita XOR konstanta putaran (0x9e377900 XOR r) ke kata keadaan pertama.

sumber referensi dalam 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);
    }
  }
}

Versi Tweetable dalam C

Ini mungkin bukan implementasi terkecil yang dapat digunakan tetapi kami ingin memiliki versi standar C (sehingga tidak ada UB, dan "dapat digunakan" di perpustakaan).

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

Tes vektor

Input berikut dihasilkan oleh

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

dan nilai "dicetak" oleh

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

demikian:

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

harus kembali:

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

CJam (114 karakter)

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

Ini adalah blok anonim (fungsi): jika Anda ingin memberi nama Gmaka tambahkan :G. Dalam CJam, nama yang diberikan hanya bisa berupa huruf besar tunggal. Ada ruang untuk menambahkan komentar e# Gimli in CJamdan membiarkan karakter tersisa dalam satu tweet.

Tes online

Pembedahan

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

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

Saya mungkin mendapatkan byte dengan metode swapping saya, tetapi terlalu manis untuk tidak digunakan.

C, 268 karakter (268 byte) menggunakan uint32_t

NB Karena kode penggunaan asli <stdint.h>dan jenis Sseperti uint32_t *, saya pikir penggunaan longadalah cheat untuk masuk ke 280 karakter pada biaya portabilitas yang merupakan alasan untuk menggunakan uint32_tdi tempat pertama. Jika untuk keadilan perbandingan kami membutuhkan penggunaan konsisten uint32_tdan tanda tangan eksplisit void gimli(uint32_t *), kode asli benar-benar 284 karakter, dan kode orlp adalah 276 karakter.

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

Ini dapat dibagi menjadi dua tweet dengan penanda kelanjutan sebagai

#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

dan

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

Hanya dekat 1: 1 dari referensi untuk mulai bermain 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;}}}

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

Assembler x86 32-bit (112 byte)

(__cdlelepon konvensi)

            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

Versi Tweetable (pengkodean base85 format-z85):

v7vb1h> C} HbQuA91y51A: oWYw48G)? I = H /] rGf9Na> sA.DWu06 {6f # TEC ^ CM: # IeA-cstx7:>! VfVf # u * YB & mP (tuCl * + 7eENP) $ :) } t $ ^ wM51j% LDf $ HMAg2bB ^ MQP