In FIPS-197 (dem Advanced Encryption Standard , bekannt als AES) wird er stark genutzt SubBytes, was als implementiert werden könnte
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};
return t[x];}
Diese Funktion ist nicht beliebig. es ist eine reversible Abbildung, bestehend aus einer Inversion in einem Galoisfeld, gefolgt von einer affinen Transformation. Alle Details finden Sie in FIPS-197, Abschnitt 5.1.1 oder hier Abschnitt 4.2.1 (unter einem etwas anderen Namen).
Ein Problem bei der Implementierung als Tabelle besteht darin, dass so genannte Cache-Timing-Angriffe möglich sind .
Ihre Mission ist es daher, einen genauen Ersatz für die obige SubBytes()Funktion zu finden, der ein zeitlich konstantes Verhalten aufweist. Wir gehen davon aus, dass dies der Fall ist, wenn entweder nichts abhängig von der Eingabe xvon SubBytesverwendet wird:
- als Array-Index,
- da der Steueroperanden
if,while,for,case, oder Betreiber?:; - wie jeder Operand von Operatoren
&&,||,!,==,!=,<,>,<=,>=,*,/,%; - als rechter Operand der Operatoren
>>,<<,*=,/=,%=,<<=,>>=.
Der Gewinner wird eines mit den niedrigsten Kosten, aus der Anzahl der Operatoren in dem Eingangsabhängigen Datenweg ausgeführt erhalten wurde, mit einem Gewicht von 5 für unäre Operatoren -und ~sowie für <<1, >>1, +1, -1; Ein Gewicht von 7 für alle anderen Operatoren, Verschiebungen mit anderen Zählungen oder Hinzufügungen / Untersetzungen anderer Konstanten (Typumwandlungen und Werbeaktionen sind kostenlos). Im Prinzip bleiben diese Kosten durch das Abrollen von Schleifen (falls vorhanden) unverändert und sind von der Eingabe unabhängig x. Als Tie-Breaker gewinnt die Antwort mit dem kürzesten Code nach dem Entfernen von Leerzeichen und Kommentaren.
Ich plane, einen Eintrag so früh wie möglich als Antwort zu kennzeichnen, und zwar in Jahr 2013, UTC. Ich werde Antworten in Sprachen berücksichtigen, die ich kenne, und sie als direkte Übersetzung in C einstufen, die nicht für die Größe optimiert ist.
Entschuldigung für das anfängliche Auslassen von +1und -1in den bevorzugten Betreibern, für freie Besetzungen und Werbeaktionen sowie für die Rangfolge der Größe. Beachten Sie, dass *dies sowohl bei Einzahl als auch bei Multiplikation verboten ist.
quelle
Antworten:
Spielergebnis:
940 933 926910, FeldturmannäherungDie Struktur entspricht im Wesentlichen der Implementierung von Boyar und Peralta - reduzieren Sie die Inversion in GF (2 ^ 8) auf die Inversion in GF (2 ^ 4), zerlegen Sie sie in einen linearen Prolog, einen nichtlinearen Körper und einen linearen Epilog. und minimieren Sie sie dann separat. Ich zahle einige Strafen für die Bit-Extraktion, aber ich kompensiere dies, indem ich in der Lage bin, Operationen parallel auszuführen (mit einigem vernünftigen Auffüllen der Bits von
fwd). Ausführlicher...Hintergrund
Wie in der Problembeschreibung erwähnt, besteht die S-Box aus einer Inversion in einer bestimmten Implementierung des Galois-Feldes GF (2 ^ 8), gefolgt von einer affinen Transformation. Wenn Sie wissen, was beide bedeuten, überspringen Sie diesen Abschnitt.
Eine affine (oder lineare) Transformation ist eine Funktion,
f(x)dief(x + y) = f(x) + f(y)und respektiertf(a*x) = a*f(x).Ein Feld ist eine Reihe
Fvon Elementen mit zwei speziellen Elementen, die wir nennen wollen0und1und zwei Operatoren, die wir nennen wollen+und*, die verschiedenen Eigenschaften respektieren. In diesem Abschnitt wird angenommen , dassx,yundzsind ElementeF.Fbilden eine abelsche Gruppe+mit0als Identität: dhx + yist ein Element vonF;x + 0 = 0 + x = x; jederxhat ein entsprechendes-xsolchesx + (-x) = (-x) + x = 0;x + (y + z) = (x + y) + z; undx + y=y + x.Fanderer als0bilden eine abelsche Gruppe*mit1als Identität.x * (y + z) = (x * y) + (x * z).Es stellt sich heraus, dass es für endliche Felder einige ziemlich strenge Einschränkungen gibt:
pdas Prim und istkdie Potenz ist). .F\{0}unter*ist zyklisch; dh es gibt mindestens ein Elementg, von dem jedes Element eine Potenz istg.kdes Feldes der Primordnung. ZB hat GF (2 ^ 8) eine Darstellung in Form von Polynomen vonxüber GF (2). Tatsächlich gibt es normalerweise mehr als eine Darstellung. Betrachten Siex^7 * xin GF (2 ^ 8); es muss einem Polynom der Ordnung 7 entsprechen, aber welches? Es gibt viele Möglichkeiten, die die richtige Struktur ergeben. AES wähltx^8 = x^4 + x^3 + x + 1(das lexikographisch kleinste Polynom, das funktioniert).Wie berechnen wir also eine Inverse in dieser bestimmten Darstellung von GF (2 ^ 8)? Es ist ein zu großes Problem, um es direkt anzugehen, also müssen wir es auflösen.
Feldtürme: repräsentieren GF (2 ^ 8) in Bezug auf GF (2 ^ 4)
Anstatt GF (2 ^ 8) mit Polynomen von 8 Termen über GF (2) darzustellen, können wir es mit Polynomen von 2 Termen über GF (2 ^ 4) darstellen. Diesmal müssen wir ein lineares Polynom für wählen
x^2. Angenommen, wir wählenx^2 = px + q. Dann(ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq).Ist es einfacher, eine Inverse in dieser Darstellung zu finden? Wenn
(cx + d) = (ax + b)^-1wir die simultanen Gleichungen erhaltenad + (b + ap)c = 0bd + (aq)c = 1Lass
D = [b(b+ap) + a^2 q]und setzec = a * D^-1;d = (b + ap) * D^-1. Wir können also eine Inverse in GF (2 ^ 8) für die Kosten einer Konvertierung in GF (2 ^ 4), eine Inverse und einige Additionen und Multiplikationen in GF (2 ^ 4) und eine Konvertierung zurück durchführen. Auch wenn wir das Inverse mit einer Tabelle machen, haben wir die Tabellengröße von 256 auf 16 reduziert.Implementierungsdetails
Um eine Darstellung von GF (4) zu konstruieren, können wir zwischen drei zu reduzierenden Polynomen wählen
x^4:x^4 = x + 1x^4 = x^3 + 1x^4 = x^3 + x^2 + x + 1Der wichtigste Unterschied besteht in der Implementierung der Multiplikation. Für alle drei (die
poly3, 9, f entsprechen) funktioniert Folgendes:Wenn wir
poly = 3uns jedoch dafür entscheiden , können wir den Überlauf viel effizienter handhaben, da er eine schöne Struktur hat: Es gibt keinen doppelten Überlauf, da die beiden Eingänge beidex^6 = x^2 (x + 1)kubisch und auch kubisch sind. Außerdem können wir die Verschiebungen von speichernb: Da wir den Überlauf als letztes verlassen,a0 x^2habenxwir keine gesetzten Bits entsprechend oder 1 und können es daher mit -4 anstelle von -1 maskieren. Das Ergebnis istWir müssen immer noch die Werte von
pundqfür die Darstellung von GF (2 ^ 8) vor GF (2 ^ 4) wählen , aber wir haben nicht viele Einschränkungen. Was zählt, ist, dass wir eine lineare Funktion von den Bits unserer ursprünglichen Darstellung zu den Bits der Arbeitsdarstellung erhalten können. Dies ist aus zwei Gründen von Bedeutung: Erstens ist es einfach, lineare Transformationen durchzuführen, während für eine nichtlineare Transformation eine Optimierung erforderlich ist, die der Optimierung der gesamten S-Box entspricht. zweitens, weil wir einige nebenleistungen erhalten können. So rekapitulieren Sie die Struktur:Wenn die Bits
xsindx7 x6 ... x0dann da die Transformation linear wir bekommena = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Quadrieren Sie es und wir erhalten,a^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2wo die Kreuzbegriffe aufheben (weil in GF (2),1 + 1 = 0). Soa^2kann auch als lineare Funktion von berechnet werdenx. Wir können die lineare Vorwärtstransformation erweitern, um Folgendes zu erhalten:und wir sind auf drei Multiplikationen und eine Addition. Wir können den Multiplikationscode auch erweitern, um die beiden Multiplikationen
Dinvparallel durchzuführen. Unsere Gesamtkosten sind also eine lineare Vorwärtstransformation, eine Addition, zwei Multiplikationen, eine Inverse in GF (2 ^ 4) und eine lineare Rückwärtstransformation. Wir können in der post-inversen linearen Transformation der S-Box rollen und diese im Wesentlichen kostenlos erhalten.Die Berechnung der Koeffizienten für die linearen Transformationen ist nicht sehr interessant, ebenso wenig wie die Mikrooptimierung, um eine Maske hier und eine Verschiebung dort zu speichern. Der verbleibende interessante Teil ist die Optimierung von
inverse_GF16. Es gibt 2 ^ 64 verschiedene Funktionen von 4 Bit bis 4 Bit, daher erfordert eine direkte Optimierung viel Speicher und Zeit. Was ich getan habe, ist, 4 Funktionen von 4 Bit bis 1 Bit zu betrachten, die zulässigen Gesamtkosten für eine Funktion zu begrenzen (mit einem Maximalpreis von 63 pro Funktion kann ich alle geeigneten Ausdrücke in weniger als einer Minute aufzählen). und für jedes Tupel von Funktionen werden gemeinsame Unterausdrücke eliminiert. Nach 25 Minuten Knirschen stelle ich fest, dass die bestmögliche Inverse mit dieser Obergrenze insgesamt 133 kostet (durchschnittlich 33,25 pro Bit der Ausgabe, was nicht schlecht ist, wenn man bedenkt, dass der billigste Ausdruck für ein einzelnes Bit 35 ist). .Ich experimentiere immer noch mit anderen Ansätzen, um die Inversion in GF (2 ^ 4) zu minimieren, und ein Ansatz, der Bottom-Up statt Top-Down erstellt, hat eine Verbesserung von 133 auf 126 ergeben.
quelle
& 1kann getrimmt werden ( va wennxistunsigned char;CHAR_BITist 8 im Codegolf).Ergebnis: 980 = 7 * 5 + 115 * 7 + 7 * 5 + 15 * 7, Minimierung von Boyar und Peralta
Ich fand eine neue Technik zur Minimierung der kombinatorischen Logik mit Anwendungen auf die Kryptologie von Joan Boyar und René Peralta, die (abgesehen vom C-Formalismus) das tut, was erforderlich ist. Die Technik zur Ableitung ihrer Gleichungen ist von nicht weniger als den USA patentiert . Ich habe gerade eine C-Übersetzung ihrer Gleichungen gemacht , die freundlicherweise hier verlinkt sind .
quelle
Ergebnis: 10965
Dies verwendet dasselbe Prinzip wie das Aufrollen der Array-Suche. Erfordert möglicherweise zusätzliche Würfe.
Vielen Dank an ugoren für den Hinweis, wie man sich verbessern kann
is_zero.quelle
(c|-c)>>31ist 0 für 0 und -1 ansonsten.c >> 4scheint deine Rechtsverschiebung für mich signiert zu sein. Und wenn Sie wirklich darauf bestehen -((unsigned int)(c|-c))>>31istc?1:0.c >>4funktioniert mit oder ohne Vorzeichenerweiterung. Aber ein guter Haken bei der Verwendung einer Schicht ohne Vorzeichen: Wird bearbeitet, wenn ich zu Hause bin und einen richtigen Computer anstelle eines Telefons verwenden kann. Vielen Dank.Ergebnis: 9109, algebraischer Ansatz
Ich werde den Lookup-Ansatz verlassen, falls jemand ihn drastisch verbessern kann, aber es stellt sich heraus, dass ein guter algebraischer Ansatz möglich ist. Diese Implementierung findet die multiplikative Inverse unter Verwendung des Euclid-Algorithmus . Ich habe es in Java geschrieben, aber im Prinzip kann es nach C portiert werden. Ich habe die Teile kommentiert, die sich ändern würden, wenn Sie es nur mit 8-Bit-Typen überarbeiten möchten.
Vielen Dank an ugoren für den Hinweis, wie
is_nonzeroich das Einchecken in einem Kommentar zu meiner anderen Antwort verkürzen kann .quelle
Ergebnis: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (unter der Annahme, dass die Schleifen ausgerollt sind)
Erläuterung:
Im Wesentlichen eine Array-Suche, die mit bitweisen Operatoren neu implementiert und immer das gesamte Array verarbeitet wird. Wir durchlaufen das Array und xor
xmit jedem Index und verwenden dann bitweise Operatoren, um das Ergebnis logisch zu negierenx=i. Ansonsten erhalten wir 255 when und 0. Wir bitweise - und dies mit dem Array-Wert, so dass der gewählte Wert unverändert ist und die anderen 0 werden. Dann nehmen wir das bitweise-oder dieses Arrays und ziehen dabei nur den gewählten Wert heraus.Die zwei
1 << jOperationen würden als Teil des Abrollens der Schleife verschwinden und sie durch die Potenzen von 2 von 1 bis 128 ersetzen.quelle
-(2+2)in Ihrer Punkteberechnung? Edit: ah, Inlining schafft ein<<1und ein>>1.Kerbe
19681692, unter Verwendung der NachschlagetabelleHinweis: Diese Lösung erfüllt die Kriterien aufgrund von nicht
w >> b.Verwenden der Nachschlagetabelle, aber gleichzeitiges Lesen von 8 Bytes.
3 · 7 + 32 · (6 · 7 + 2 · 5) + 7 = 692
quelle
w>>bRHS vonxw >> bWobhängt von der Eingabe ab; auchx/8,x%8und*= (1-badi). Der erste degeneriert besonders wahrscheinlich in eine Zeitabhängigkeit von Low-End-CPUs. Die Idee, breite Variablen zu verwenden, hat jedoch durchaus Potenzial.w >> bist sehr wichtig (ich muss sehen, ob es behoben werden kann, ohne alles neu zu schreiben.Tabellensuche und Maske, Punktzahl = 256 * (5 * 7 + 1 * 5) = 10240
Verwendet die Tabellensuche mit einer Maske, um nur das gewünschte Ergebnis auszuwählen. Verwendet die Tatsache, dass
j|-jentweder negativ (wenn i! = X) oder null (wenn i == x) ist. Durch Verschieben wird eine All-One- oder All-Zero-Maske erstellt, mit der nur der gewünschte Eintrag ausgewählt wird.quelle