La S-box de Rijndael est une opération fréquemment utilisée dans le chiffrement et le déchiffrement AES . Il est généralement implémenté comme une table de recherche de 256 octets. C'est rapide, mais cela signifie que vous devez énumérer une table de recherche de 256 octets dans votre code. Je parie que quelqu'un dans cette foule pourrait le faire avec moins de code, étant donné la structure mathématique sous-jacente.

Écrivez une fonction dans votre langue préférée qui implémente la S-box de Rijndael. Le code le plus court gagne.

Ruby, 161 caractères

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}

Afin de vérifier la sortie, vous pouvez utiliser le code suivant pour l'imprimer sous forme de tableau:

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

GolfScript, 60 caractères

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

Ce code définit une fonction nommée Squi prend un octet et lui applique la S-box Rijndael. (Il utilise également une fonction d'assistance interne nommée rpour enregistrer quelques caractères.)

Cette implémentation utilise une table de logarithmes pour calculer les inverses GF (2 ⁸ ), comme suggéré par Thomas Pornin . Pour enregistrer quelques caractères, la table de logarithme entière est recalculée pour chaque octet d'entrée; malgré cela, et bien que GolfScript soit un langage très lent en général, ce code ne prend que 10 ms environ pour traiter un octet sur mon ancien ordinateur portable. Le précalcul de la table de logarithme (as L) l'accélère jusqu'à environ 0,5 ms par octet, au coût modeste de trois caractères supplémentaires:

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

Pour plus de commodité, voici un harnais de test simple qui appelle la fonction S, telle que définie ci-dessus, pour calculer et imprimer l'ensemble de la S-box en hexadécimal comme sur Wikipedia :

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

Essayez ce code en ligne.

^{(La démo en ligne précalcule la table de logarithme pour éviter de prendre trop de temps. Même ainsi, le site GolfScript en ligne peut parfois expirer de manière aléatoire; il s'agit d'un problème connu avec le site, et un rechargement le corrige généralement.)}

Explication:

Commençons par le calcul de la table de logarithme, et plus précisément avec la fonction d'assistance r:

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

Cette fonction prend deux entrées sur la pile: un octet et un masque de bits de réduction (une constante entre 256 et 511). Il duplique l'octet d'entrée, multiplie la copie par 2 et, si le résultat dépasse 255, le XOR avec le masque de bits pour le ramener sous 256.

Dans le code de génération de la table de journal, la fonction rest appelée avec le masque de réduction 283 = 0x11b (qui correspond au polynôme de réduction Rijndael GF (2 ⁸ ) x ⁸ + x ⁴ + x ³ + x + 1), et le résultat est XORed avec l'octet d'origine, en le multipliant effectivement par 3 (= x + 1, comme un polynôme) dans le champ fini de Rijndael. Cette multiplication est répétée 255 fois, à partir de l'octet 1, et les résultats (plus un zéro octet initial) sont collectés dans un tableau de 257 éléments Lqui ressemble à ceci (partie centrale omise):

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

La raison pour laquelle il y a 257 éléments est que, avec le 0 précédant et 1 se produisant deux fois, nous pouvons trouver l'inverse modulaire de tout octet donné simplement en recherchant son index (de base zéro) dans ce tableau, en le niant et en regardant jusqu'à l'octet à l'index négatif dans le même tableau. (Dans GolfScript, comme dans de nombreux autres langages de programmation, les index de tableau négatifs comptent à rebours à partir de la fin du tableau.) En effet, c'est exactement ce que fait le code L?~)L=au début de la fonction S.

Le reste du code appelle la fonction d'assistance rquatre fois avec le masque binaire de réduction 257 = 2 ⁸ + 1 pour créer quatre copies à rotation binaire de l'octet d'entrée inversé. Ceux-ci sont tous collectés dans un tableau, avec la constante 99 = 0x63, et XOR ensemble pour produire la sortie finale.

x86-64 Code machine - 23 22 20 19 octets

Utilise le jeu d'instructions 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

En utilisant les conventions d'appel Windows, prend un octet et sort un octet. Il n'est pas nécessaire d'inverser le ShiftRowscar cela n'affecte pas le premier octet.

La table peut être générée sans calculer les inverses dans le champ fini GF (256), en utilisant des logarithmes. Il ressemblerait à ceci (code Java, intpour éviter les problèmes avec le bytetype signé ):

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

L'idée est que 3 est un générateur multiplicatif de GF (256) *. Le tableau t[]est tel qu'il t[x]est égal à 3 ^x ; puisque 3 ²⁵⁵ = 1, nous obtenons que 1 / (3 ^x ) = 3 ^255-x .

GolfScript (82 caractères)

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

Utilise les variables globales Aet B, et crée la fonction comme variable globale S.

L'inversion de Galois est une force brute; J'ai expérimenté avec une mulfonction séparée qui pourrait être réutilisée pour la transformation affine post-inversion, mais elle s'est avérée plus coûteuse en raison du comportement de débordement différent.

C'est trop lent pour une démonstration en ligne - cela expirerait même sur les deux premières lignes du tableau.

Python, 176 caractères

Cette réponse est pour le commentaire-question de Paŭlo Ebermann sur la façon de rendre la fonction à temps constant. Ce code correspond à la facture.

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

ré

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;

}

cela peut générer la table de recherche au moment de la compilation, je pourrais en économiser en faisant ubyte un paramètre générique

éditez directement ubyteà ubytesans recherches de tableau, sans branchement et boucles entièrement déroulables

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 a utilisé l'algo de @Thomas pour créer la table de recherche

Stax , 53 octets

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

Exécuter et déboguer

Je n'ai aucune compréhension particulière des S-box. Il s'agit d'une conversion de la solution de Thomas Pornin (8 ans!) .