Implementiere Rijndaels S-Box

15

Die S-Box von Rijndael wird häufig bei der AES- Verschlüsselung und -Entschlüsselung eingesetzt. Es wird normalerweise als 256-Byte-Nachschlagetabelle implementiert. Das ist schnell, bedeutet aber, dass Sie eine 256-Byte-Nachschlagetabelle in Ihrem Code aufzählen müssen. Ich wette, jemand in dieser Menge könnte es mit weniger Code tun, angesichts der zugrunde liegenden mathematischen Struktur.

Schreiben Sie eine Funktion in Ihrer Lieblingssprache, die Rijndaels S-Box implementiert. Kürzester Code gewinnt.

Keith Randall
quelle
1
Bonuspunkte (Upvotes von mir), wenn die resultierende Funktion zeitlich konstant ist (dh keine datenabhängigen Codepfade oder Arrayzugriffe oder was auch immer Ihre Sprache unterstützt).
Paŭlo Ebermann
@ PaŭloEbermann Array-Zugriffe sind in vielen Sprachen eine konstante Zeit (es wird ein (skalierter) Wert zu einem Zeiger hinzugefügt und dereferenziert, deshalb ist eine Nachschlagetabelle so schnell)
Ratschenfreak
@ratchetfreak Array-Zugriffe sind O (1), aber die tatsächliche Zugriffszeit hängt beispielsweise von Cache-Treffern oder -Fehlern ab, was zu Seitenkanalangriffen auf AES führt.
Paŭlo Ebermann
@ PaŭloEbermann, aber Sie können den kürzeren Code verwenden, um eine Nachschlagetabelle zu füllen, die dann gut unter eine Speicherseite passt.
Peter Taylor
@ PaŭloEbermann und wenn die 256-Länge-Tabelle zusammen mit dem Code gespeichert wird (wie bei der Kompilierung generiert), haben Sie fast einen Cache-Hit garantiert
Ratschenfreak

Antworten:

6

Ruby, 161 Zeichen

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}

Um die Ausgabe zu überprüfen, können Sie den folgenden Code verwenden, um sie in tabellarischer Form auszudrucken:

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

GolfScript, 60 Zeichen

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

Dieser Code definiert eine benannte Funktion S, die ein Byte einnimmt und die Rijndael S-Box darauf anwendet. (Es wird auch eine interne Hilfsfunktion verwendet r, um ein paar Zeichen zu speichern.)

Diese Implementierung verwendet eine Logarithmentabelle, um die GF (2 8 ) -Inversen zu berechnen , wie von Thomas Pornin vorgeschlagen . Um einige Zeichen zu sparen, wird die gesamte Logarithmentabelle für jedes Eingangsbyte neu berechnet. Trotzdem, und obwohl GolfScript im Allgemeinen eine sehr langsame Sprache ist, benötigt dieser Code nur etwa 10 ms, um ein Byte auf meinem alten Laptop zu verarbeiten. Durch Vorberechnung der Logarithmentabelle (as L) wird eine Geschwindigkeit von bis zu 0,5 ms pro Byte erreicht, und dies zu moderaten Kosten von drei weiteren Zeichen:

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

Der Einfachheit halber hier ein einfaches Testkabel, das Sdie oben definierte Funktion zum Berechnen und Ausdrucken der gesamten S-Box in hexadezimaler Form wie bei Wikipedia aufruft :

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

Versuchen Sie diesen Code online.

(Die Online-Demo berechnet die Logarithmus-Tabelle vorab, um zu vermeiden, dass zu viel Zeit benötigt wird. Trotzdem kann es vorkommen, dass die Online-GolfScript-Site eine willkürliche Zeitüberschreitung aufweist. Dies ist ein bekanntes Problem, das in der Regel durch ein erneutes Laden behoben wird.)

Erläuterung:

Beginnen wir mit der Berechnung der Logarithmentabelle und speziell mit der Hilfsfunktion r:

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

Diese Funktion belegt zwei Eingänge im Stack: ein Byte und eine Reduktionsbitmaske (eine Konstante zwischen 256 und 511). Es dupliziert das Eingangsbyte, multipliziert die Kopie mit 2 und wenn das Ergebnis 255 überschreitet, wird es mit der Bitmaske XOR-verknüpft, um es wieder unter 256 zu bringen.

Innerhalb des Protokolltabellen-Erzeugungscodes wird die Funktion rmit der Reduktionsbitmaske 283 = 0x11b (die dem Rijndael GF (2 8 ) -Reduktionspolynom x 8 + x 4 + x 3 + x + 1 entspricht) aufgerufen, und das Ergebnis ist XOR-verknüpft Multiplizieren Sie das ursprüngliche Byte mit 3 (= x + 1, als Polynom) im endlichen Rijndael-Feld. Diese Multiplikation wird ab Byte 1 255-mal wiederholt, und die Ergebnisse (plus ein anfängliches Null-Byte) werden in einem Array mit 257 Elementen gesammelt L, das wie folgt aussieht (mittlerer Teil weggelassen):

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

Der Grund, warum es 257 Elemente gibt, ist, dass wir mit der vorangestellten 0 und 1, die zweimal vorkommen, die modulare Inverse jedes gegebenen Bytes finden können, indem wir einfach seinen (nullbasierten) Index in diesem Array nachschlagen, ihn negieren und suchen up das Byte am negierten Index im gleichen Array. (In GolfScript, wie in vielen anderen Programmiersprachen, werden negative Array-Indizes vom Ende des Arrays an rückwärts gezählt.) In der Tat ist dies genau das, was der Code L?~)L=am Anfang der Funktion Stut.

Der Rest des Codes ruft die Hilfsfunktion rviermal mit der Reduzierungsbitmaske 257 = 2 8 + 1 auf, um vier bitgedrehte Kopien des invertierten Eingangsbytes zu erstellen. Diese werden zusammen mit der Konstanten 99 = 0x63 zu einem Array zusammengefasst und zusammen mit XOR-Verknüpfungen versehen, um die endgültige Ausgabe zu erhalten.

Ilmari Karonen
quelle
7

x86-64 Maschinencode - 23 22 20 19 Bytes

Verwendet den AES-NI-Befehlssatz

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

Verwendet Windows-Aufrufkonventionen, nimmt ein Byte auf und gibt ein Byte aus. Es ist nicht notwendig, das umzukehren, ShiftRowsda es das erste Byte nicht beeinflusst.

mir'
quelle
2
X86_64 zieht einmal ein Mathematica und hat ein eingebautes dafür.
Moonheart08
6

Die Tabelle kann ohne Berechnung von Inversen im endlichen Feld GF (256) unter Verwendung von Logarithmen erzeugt werden. Es würde so aussehen (Java-Code, intum Probleme mit dem signierten byteTyp zu vermeiden ):

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

Die Idee ist, dass 3 ein multiplikativer Generator von GF (256) * ist. Die Tabelle t[]ist so, dass t[x]sie 3 x entspricht . da 3 255 = 1, erhalten wir das 1 / (3 x ) = 3 255-x .

Thomas Pornin
quelle
sollte es nicht sein 0x1B(eine 1 im Hex-Literal) anstatt0x11B
Ratschenfreak
@ratchetfreak: nein, es muss 0x11B sein (ich habe es versucht). Der intTyp ist in Java 32-Bit. Ich muss das höhere Bit streichen.
Thomas Pornin
ah wusste nicht, dass
Ratschenfreak
Ist das ein >>> statt eines >> in Zeile 4?
Joe Z.
@ JoeZeng: beide würden funktionieren. In Java ist ">>>" die "vorzeichenlose Schicht", ">>" die "vorzeichenbehaftete Schicht". Sie unterscheiden sich dadurch, wie sie mit dem Vorzeichenbit umgehen. In diesem Fall werden die Werte niemals breit genug sein, damit das Vorzeichenbit ungleich Null ist, sodass es keinen wirklichen Unterschied macht.
Thomas Pornin
6

GolfScript (82 Zeichen)

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

Verwendet globale Variablen Aund Bund erstellt die Funktion als globale Variable S.

Die Galois-Inversion ist rohe Gewalt; Ich experimentierte mit einer separaten mulFunktion, die für die affine Transformation nach der Inversion wiederverwendet werden konnte, die sich jedoch aufgrund des unterschiedlichen Überlaufverhaltens als teurer herausstellte.

Dies ist zu langsam für eine Online-Demo - es würde sogar in den ersten beiden Zeilen der Tabelle eine Zeitüberschreitung auftreten.

Peter Taylor
quelle
Meins ist schneller (und kürzer;). Trotzdem +1.
Ilmari Karonen
4

Python, 176 Zeichen

Diese Antwort ist für Paŭlo Ebermanns Frage nach der Konstanthaltung der Zeit. Dieser Code passt zur Rechnung.

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
Keith Randall
quelle
Die zeitkonstante Multiplikation ist plattformabhängig (auch auf 32-Bit-Plattformen, z. B. ARM Cortex M0). Siehe diese verwandte Frage
fgrieu
1
@fgrieu Sicher, aber das sind alles Multiplikationen mit Konstanten, die einfach mit Shifts und Additions in konstanter Zeit implementiert werden können.
Keith Randall
2

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;

}

Dies kann die Nachschlagetabelle zur Kompilierungszeit generieren. Ich könnte einige einsparen, indem ich ubyte zu einem generischen Parameter mache

Bearbeiten direkt ubytean , ubyteohne Array - Lookups, keine Verzweigung und vollständig abrollbares Schlaufen

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 hat @Thomas 'Algo zum Erstellen der Nachschlagetabelle verwendet

Ratschenfreak
quelle