S-box Rijndaela jest często stosowaną operacją w szyfrowaniu i deszyfrowaniu AES . Zwykle jest implementowany jako 256-bajtowa tabela odnośników. Jest to szybkie, ale oznacza, że ​​musisz wyliczyć 256-bajtową tabelę wyszukiwania w kodzie. Założę się, że ktoś w tym tłumie mógłby to zrobić z mniejszym kodem, biorąc pod uwagę podstawową strukturę matematyczną.

Napisz funkcję w swoim ulubionym języku, która implementuje S-box Rijndaela. Najkrótszy kod wygrywa.

Ruby, 161 znaków

R=0..255
S=R.map{|t|t=b=R.select{|y|x=t;z=0;8.times{z^=y*(x&1);x/=2;y*=2};r=283<<8;8.times{r/=2;z^r<z/2&&z^=r};z==1}[0]||0;4.times{|r|t^=b<<1+r^b>>4+r};t&255^99}

Aby sprawdzić wynik, możesz użyć następującego kodu, aby wydrukować go w formie tabeli:

S.map{|x|"%02x"%x}.each_slice(16){|l|puts l*' '}

GolfScript, 60 znaków

{[[0 1{.283{1$2*.255>@*^}:r~^}255*].@?~)={257r}4*99]{^}*}:S;

Ten kod definiuje nazwaną funkcję, Sktóra pobiera bajt i stosuje do niego S-box Rijndael. (Używa także wewnętrznej funkcji pomocnika o nazwie, raby zapisać kilka znaków).

Ta implementacja wykorzystuje tabelę logarytmiczną do obliczania odwrotności GF ( ²⁸ ), jak zasugerował Thomas Pornin . Aby zapisać kilka znaków, cała tabela logarytmiczna jest ponownie obliczana dla każdego bajtu wejściowego; mimo to i mimo że GolfScript jest ogólnie bardzo wolnym językiem, ten kod zajmuje tylko około 10 ms na przetworzenie bajtu na moim starym laptopie. Wstępne obliczenie tabeli logarytmicznej (as L) przyspiesza ją do około 0,5 ms na bajt, przy skromnym koszcie jeszcze trzech znaków:

[0 1{.283{1$2*.255>@*^}:r~^}255*]:L;{[L?~)L={257r}4*99]{^}*}:S;

Dla wygody oto prosta uprząż testowa, która wywołuje funkcję S, jak zdefiniowano powyżej, w celu obliczenia i wydrukowania całego S-boxa szesnastkowo jak na Wikipedii :

"0123456789abcdef"1/:h; 256, {S .16/h= \16%h= " "++ }% 16/ n*

Wypróbuj ten kod online.

^{(Wersja demonstracyjna online wstępnie oblicza tabelę logarytmiczną, aby uniknąć zbyt długiego czasu. Mimo to strona internetowa GolfScript może czasami losowo upłynąć limit czasu; jest to znany problem z witryną, a przeładowanie zwykle ją rozwiązuje).}

Wyjaśnienie:

Zacznijmy od obliczenia tabeli logarytmicznej, a konkretnie od funkcji pomocniczej r:

{1$2*.255>@*^}:r

Ta funkcja przyjmuje na wejściu dwa wejścia: bajt i maskę bitów redukcyjnych (stała między 256 a 511). Duplikuje bajt wejściowy, mnoży kopię przez 2, a jeśli wynik przekracza 255, XORs ją z maską bitową, aby sprowadzić ją z powrotem poniżej 256.

W kodzie generującym tablicę logów funkcja rjest wywoływana z maską bitową redukcji 283 = 0x11b (co odpowiada wielomianowi redukcyjnemu Rijndael GF ( ²⁸ ) x ⁸ + x ⁴ + x ³ + x + 1), a wynik jest XORed z oryginalnym bajtem, skutecznie mnożąc go przez 3 (= x + 1, jako wielomian) w skończonym polu Rijndaela. To zwielokrotnienie powtarza się 255 razy, zaczynając od bajtu 1, a wyniki (plus początkowy bajt zerowy) są gromadzone w 257-elementowej tablicy, Lktóra wygląda następująco (pominięta część środkowa):

[0 1 3 5 15 17 51 85 255 26 46 ... 180 199 82 246 1]

Powodem, dla którego istnieje 257 elementów, jest to, że przy wstawionym 0 i 1 występującym dwukrotnie, możemy znaleźć modułową odwrotność dowolnego danego bajtu, po prostu patrząc na jego (zerowy) indeks w tej tablicy, negując go i patrząc w górę bajtu przy zanegowanym indeksie w tej samej tablicy. (W GolfScript, podobnie jak w wielu innych językach programowania, ujemne indeksy tablic liczą się wstecz od końca tablicy.) Rzeczywiście, dokładnie to robi kod L?~)L=na początku funkcji S.

Reszta kodu wywołuje funkcję pomocniczą rcztery razy z redukcyjną maską bitową 257 = 2 ⁸ + 1, aby utworzyć cztery obrócone bity kopie odwróconego bajtu wejściowego. Wszystkie są zebrane w tablicę wraz ze stałą 99 = 0x63 i razem XOR, aby uzyskać końcowy wynik.

x86-64 Kod maszynowy - 23 22 20 19 bajtów

Korzysta z zestawu instrukcji AES-NI

66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1  
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

Używając konwencji wywoływania systemu Windows, pobiera bajt i wysyła bajt. Nie ma potrzeby odwracania, ShiftRowsponieważ nie wpływa to na pierwszy bajt.

Tabelę można wygenerować bez obliczania odwrotności w polu skończonym GF (256), używając logarytmów. Wyglądałoby to tak (kod Java, używany w intcelu uniknięcia problemów z podpisanym bytetypem):

int[] t = new int[256];
for (int i = 0, x = 1; i < 256; i ++) {
    t[i] = x;
    x ^= (x << 1) ^ ((x >>> 7) * 0x11B);
}
int[] S = new int[256];
S[0] = 0x63;
for (int i = 0; i < 255; i ++) {
    int x = t[255 - i];
    x |= x << 8;
    x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
    S[t[i]] = (x ^ 0x63) & 0xFF;
}

Chodzi o to, że 3 jest multiplikatywnym generatorem GF (256) *. Tabela t[]jest taka, że t[x]jest równa 3 ^x ; ponieważ 3 ²⁵⁵ = 1, otrzymujemy to 1 / (3 ^x ) = 3 ^255-x .

GolfScript (82 znaków)

{256:B,{0\2${@1$3$1&*^@2/@2*.B/283*^}8*;;1=},\+0=B)*:A.2*^4A*^8A*^128/A^99^B(&}:S;

Wykorzystuje zmienne globalne Ai Bi tworzy funkcję jako zmienną globalną S.

Inwersja Galois to brutalna siła; Eksperymentowałem z osobną mulfunkcją, która mogłaby zostać ponownie wykorzystana do transformacji afinicznej po inwersji, ale okazało się, że była droższa z powodu różnych zachowań przepełnienia.

Jest to zbyt wolne jak na demo online - przekroczyłoby limit czasu nawet w pierwszych dwóch rzędach tabeli.

Python, 176 znaków

Ta odpowiedź dotyczy pytania komentującego Paŭlo Ebermanna o ustawieniu funkcji na stały czas. Ten kod pasuje do rachunku.

def S(x):
 i=0
 for y in range(256):
  p,a,b=0,x,y
  for j in range(8):p^=b%2*a;a*=2;a^=a/256*283;b/=2
  m=(p^1)-1>>8;i=y&m|i&~m
 i|=i*256;return(i^i/16^i/32^i/64^i/128^99)&255

re

ubyte[256] getLookup(){

    ubyte[256] t=void;
    foreach(i;0..256){
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * 0x1B);
    }
    ubyte[256] S=void;
    S[0] = 0x63;
    foreach(i;0..255){
        int x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        S[t[i]] = cast(ubyte)(x & 0xFF) ^ 0x63 ;
    }
    return S;

}

to może wygenerować tablicę odnośników w czasie kompilacji, mógłbym trochę zaoszczędzić, zmieniając ubyte w ogólny parametr

edit kierować ubytesię ubytebez wyszukiwań tablicy, bez rozgałęzień i całkowicie unrollable pętle

B[256] S(B:ubyte)(B i){
    B mulInv(B x){
        B r;
        foreach(i;0..256){
            B p=0,h,a=i,b=x;
            foreach(c;0..8){
                p^=(b&1)*a;
                h=a>>>7;
                a<<=1;
                a^=h*0x1b;//h is 0 or 1
                b>>=1;
            }
            if(p==1)r=i;//happens 1 or less times over 256 iterations
        }
        return r;
    }
    B s= x=mulInv(i);
    foreach(j,0..4){
        x^=(s=s<<1|(s>>>7));
    }
    return x^99;
}

edit2 użył algo @Thomas do stworzenia tabeli odnośników

Stax , 53 bajty

ë■ÿÆ♂◄º5hUø√!«mr¿¡ƒR3Å←ç≥#/$taJkαn∩╓▒ÿ╔τy╫π§╪S♫╔┴H╔║Ö

Uruchom i debuguj

Nie mam szczególnego zrozumienia S-boxów. Jest to konwersja rozwiązania Thomasa Pornina (8 lat!) .