S-box Rijndael adalah operasi yang sering digunakan di AES enkripsi dan dekripsi . Ini biasanya diimplementasikan sebagai tabel pencarian 256-byte. Itu cepat, tetapi berarti Anda perlu menghitung tabel pencarian 256-byte dalam kode Anda. Saya yakin seseorang dalam kerumunan ini bisa melakukannya dengan kode lebih sedikit, mengingat struktur matematika yang mendasarinya.

Tulis fungsi dalam bahasa favorit Anda yang mengimplementasikan S-box Rijndael. Kode terpendek menang.

Ruby, 161 karakter

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}

Untuk memeriksa output, Anda dapat menggunakan kode berikut untuk mencetaknya dalam bentuk tabel:

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

GolfScript, 60 karakter

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

Kode ini mendefinisikan fungsi bernama Syang mengambil dalam byte dan menerapkan Rijndael S-box untuk itu. (Ini juga menggunakan fungsi pembantu internal bernama runtuk menyimpan beberapa karakter.)

Implementasi ini menggunakan tabel logaritma untuk menghitung invers GF (2 ⁸ ), seperti yang disarankan oleh Thomas Pornin . Untuk menyimpan beberapa karakter, seluruh tabel logaritma dihitung ulang untuk setiap byte input; Meski begitu, dan meskipun GolfScript menjadi bahasa yang sangat lambat secara umum, kode ini hanya membutuhkan sekitar 10 ms untuk memproses byte pada laptop lama saya. Pra-perhitungan tabel logaritma (as L) mempercepatnya hingga sekitar 0,5 ms per byte, dengan biaya sederhana dari tiga karakter lagi:

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

Untuk kenyamanan, berikut ini adalah test harness sederhana yang memanggil fungsi S, sebagaimana didefinisikan di atas, untuk menghitung dan mencetak seluruh S-box dalam hex seperti di Wikipedia :

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

Coba kode ini secara online.

^{(Demo online menghitung ulang tabel logaritma untuk menghindari mengambil terlalu banyak waktu. Meski begitu, situs GolfScript online kadang-kadang secara acak waktu habis; ini adalah masalah yang diketahui dengan situs, dan memuat ulang biasanya memperbaikinya.)}

Penjelasan:

Mari kita mulai dengan perhitungan tabel logaritma, dan secara khusus dengan fungsi helper r:

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

Fungsi ini mengambil dua input pada stack: satu byte dan bitmask reduksi (sebuah konstanta antara 256 dan 511). Ini menggandakan byte input, mengalikan salinan dengan 2 dan, jika hasilnya melebihi 255, XOR dengan bitmask untuk mengembalikannya di bawah 256.

Di dalam kode penghasil log-tabel, fungsinya rdisebut dengan bitmask reduksi 283 = 0x11b (yang sesuai dengan Rijndael GF (2 ⁸ ) polinomial reduksi x ⁸ + x ⁴ + x ³ + x + 1), dan hasilnya XORed dengan byte asli, secara efektif mengalikannya dengan 3 (= x + 1, sebagai polinomial) dalam bidang hingga Rijndael. Perkalian ini diulang 255 kali, mulai dari byte 1, dan hasilnya (ditambah byte nol awal) dikumpulkan ke dalam array 257-elemen Lyang terlihat seperti ini (bagian tengah dihilangkan):

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

Alasan mengapa ada 257 elemen adalah bahwa, dengan 0 yang diawali dan dengan 1 terjadi dua kali, kita dapat menemukan invers modular dari byte yang diberikan hanya dengan melihat indeks (berbasis-nol) dalam array ini, meniadakannya, dan mencari naik byte pada indeks yang dinegasikan dalam array yang sama. (Dalam GolfScript, seperti dalam banyak bahasa pemrograman lainnya, indeks array negatif dihitung mundur dari akhir array.) Memang, inilah yang dilakukan oleh kode L?~)L=pada awal fungsi S.

Sisa kode memanggil fungsi helper rempat kali dengan bitmask reduksi 257 = 2 ⁸ + 1 untuk membuat empat bit-rotated copy dari byte input terbalik. Ini semua dikumpulkan ke dalam array, bersama dengan konstanta 99 = 0x63, dan XOR bersama-sama untuk menghasilkan hasil akhir.

x86-64 Kode mesin - 23 22 20 19 byte

Menggunakan set instruksi 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

Menggunakan konvensi pemanggilan Windows, mengambil byte dan menghasilkan byte. Tidak perlu membalikkan ShiftRowskarena tidak mempengaruhi byte pertama.

Tabel dapat dihasilkan tanpa menghitung invers di bidang terbatas GF (256), dengan menggunakan logaritma. Akan terlihat seperti ini (kode Java, gunakan intuntuk menghindari masalah dengan bytetipe yang ditandatangani ):

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

Idenya adalah bahwa 3 adalah generator multiplikasi GF (256) *. Tabelnya t[]sedemikian sehingga t[x]sama dengan 3 ^x ; karena 3 ²⁵⁵ = 1, kita mendapatkan bahwa 1 / (3 ^x ) = 3 ^255-x .

GolfScript (82 karakter)

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

Menggunakan variabel global Adan B, dan menciptakan fungsi sebagai variabel global S.

Inversi Galois adalah kekerasan; Saya bereksperimen dengan memiliki mulfungsi terpisah yang dapat digunakan kembali untuk transformasi affine pasca-inversi, tetapi ternyata lebih mahal karena perilaku luapan yang berbeda.

Ini terlalu lambat untuk demo online - itu akan habis bahkan pada dua baris pertama dari tabel.

Python, 176 karakter

Jawaban ini untuk komentar-komentar Paŭlo Ebermann tentang membuat fungsi waktu konstan. Kode ini sesuai dengan tagihan.

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

d

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;

}

ini dapat menghasilkan tabel pencarian pada waktu kompilasi, saya bisa menghemat beberapa dengan membuat ubyte sebagai param generik

sunting langsung ubyteke ubytetanpa pencarian array, tidak ada percabangan dan loop sepenuhnya tidak bisa dikendalikan

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 menggunakan @Thomas 'algo untuk membuat tabel pencarian

Stax , 53 byte

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

Jalankan dan debug itu

Saya tidak memiliki pemahaman khusus tentang S-box. Ini adalah konversi dari solusi Thomas Pornin (8 tahun!) .