Dans FIPS-197 ( Advanced Encryption Standard , connu sous le nom d'AES), il est largement utilisé SubBytes, qui pourrait être implémenté comme
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];}
Cette fonction n'est pas arbitraire; c'est une cartographie réversible, consistant en une inversion dans un champ de Galois suivie d'une transformation affine. Tous les détails se trouvent dans FIPS-197 section 5.1.1 ou ici section 4.2.1 (sous un nom légèrement différent).
Un problème avec l'implémentation en tant que table est qu'elle s'ouvre aux attaques dites de synchronisation de cache .
Ainsi, votre mission est de concevoir un remplacement exact pour la SubBytes()fonction ci-dessus , qui présente un comportement à temps constant; nous supposerons que c'est le cas lorsque rien en fonction de l'entrée xde SubBytesn'est utilisé:
- comme un index de tableau,
- que le contrôle de l' opérande
if,while,for,case, ou de l' opérateur?:; - comme l' un des opérandes d'opérateurs
&&,||,!,==,!=,<,>,<=,>=,*,/,%; - comme le droit opérande des opérateurs
>>,<<,*=,/=,%=,<<=,>>=.
Le gagnant sera celui avec le plus faible coût, obtenu à partir du nombre d'opérateurs exécutées dans le chemin de données dépendant de l' entrée, avec un poids de 5 pour les opérateurs unaires -et ~ainsi que pour <<1, >>1, +1, -1; poids de 7 pour tous les autres opérateurs, quarts avec d'autres nombres ou ajouts / sous-ensembles d'autres constantes (les transformations de type et les promotions sont gratuites). En principe, ce coût est inchangé par les boucles de déroulement (le cas échéant) et indépendant de l'entrée x. En tant que bris d'égalité, la réponse avec le code le plus court après la suppression des espaces et des commentaires l'emporte.
J'ai l'intention de désigner une entrée comme réponse dès que possible en 2013, UTC. Je considérerai les réponses dans les langues que je connais, en les classant comme une traduction directe en C non optimisée pour la taille.
Toutes mes excuses pour l'omission initiale +1et -1dans les opérateurs favorisés, de lancers et promotions gratuits, et le classement de la taille. Notez que cela *est interdit à la fois lorsqu'il est unaire et comme multiplication.
la source
Réponses:
Score:
940 933 926910, approche de la tour sur le terrainLa structure est essentiellement la même que celle de Boyar et Peralta - réduire l'inversion dans GF (2 ^ 8) en inversion dans GF (2 ^ 4), la décomposer en un prologue linéaire, un corps non linéaire et un épilogue linéaire, puis les minimiser séparément. Je paye quelques pénalités pour l'extraction de bits, mais je compense en pouvant faire des opérations en parallèle (avec un bourrage judicieux des bits de
fwd). Plus en détail...Contexte
Comme mentionné dans la description du problème, la S-box consiste en une inversion dans une implémentation particulière du champ de Galois GF (2 ^ 8) suivie d'une transformation affine. Si vous savez ce que ces deux signifient, ignorez cette section.
Une transformation affine (ou linéaire) est une fonction
f(x)qui respectef(x + y) = f(x) + f(y)etf(a*x) = a*f(x).Un champ est un ensemble
Fd'éléments avec deux éléments spéciaux, que nous appellerons0et1, et deux opérateurs, que nous appellerons+et*, qui respectent diverses propriétés. Dans cette section, on suppose quex,yetzsont des éléments deF.Fforment un groupe abélien sous+avec0comme identité: iex + yest un élément deF;x + 0 = 0 + x = x; chacunxa un correspondant-xtel quex + (-x) = (-x) + x = 0;x + (y + z) = (x + y) + z; etx + y=y + x.Fautre que0forment un groupe abélien sous*avec1comme identité.x * (y + z) = (x * y) + (x * z).Il s'avère qu'il existe des limitations assez sévères sur les champs finis:
pest le premier etkest la puissance) .F\{0}sous*est cyclique; c'est-à-dire qu'il y a au moins un élémentgtel que chaque élément est une puissance deg.kdu champ de l'ordre premier. Par exemple, GF (2 ^ 8) a une représentation en termes de polynômes dexplus de GF (2). En fait, il y a généralement plus d'une représentation. Considérezx^7 * xdans GF (2 ^ 8); il doit être équivalent à un polynôme d'ordre 7, mais lequel? Il y a beaucoup de choix qui donnent la bonne structure; AES choisit de fairex^8 = x^4 + x^3 + x + 1(le polynôme lexicographiquement le plus petit qui fonctionne).Alors, comment calculer un inverse dans cette représentation particulière de GF (2 ^ 8)? C'est un problème trop volumineux pour être abordé directement, nous devons donc le décomposer.
Tours de campagne: représentant GF (2 ^ 8) en termes de GF (2 ^ 4)
Au lieu de représenter GF (2 ^ 8) avec des polynômes de 8 termes sur GF (2), nous pouvons le représenter avec des polynômes de 2 termes sur GF (2 ^ 4). Cette fois, nous devons choisir un polynôme linéaire pour
x^2. Supposons que nous choisissionsx^2 = px + q. Alors(ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq).Est-il plus facile de trouver un inverse dans cette représentation? Si
(cx + d) = (ax + b)^-1nous obtenons les équations simultanéesad + (b + ap)c = 0bd + (aq)c = 1Let
D = [b(b+ap) + a^2 q]and setc = a * D^-1;d = (b + ap) * D^-1. On peut donc faire un inverse en GF (2 ^ 8) pour le coût d'une conversion en GF (2 ^ 4), un inverse et quelques additions et multiplications en GF (2 ^ 4), et une reconversion. Même si nous faisons l'inverse au moyen d'un tableau, nous avons réduit la taille du tableau de 256 à 16.Détails d'implémentation
Pour construire une représentation de GF (4) on peut choisir entre trois polynômes pour réduire
x^4:x^4 = x + 1x^4 = x^3 + 1x^4 = x^3 + x^2 + x + 1La différence la plus importante réside dans la mise en œuvre de la multiplication. Pour l'un des trois (qui correspondent à
poly3, 9, f), les éléments suivants fonctionneront:Cependant, si nous choisissons,
poly = 3nous pouvons gérer le débordement beaucoup plus efficacement car il a une belle structure: il n'y a pas de double débordement, car les deux entrées sont à la fois cubiques etx^6 = x^2 (x + 1)cubiques. De plus, nous pouvons enregistrer les décalages deb: puisque nous laissons le débordement durer, ila0 x^2n'y a pas de bits définis correspondant àxou 1 et nous pouvons donc le masquer avec -4 au lieu de -1. Le résultat estNous devons encore choisir les valeurs de
petqpour la représentation de GF (2 ^ 8) sur GF (2 ^ 4), mais nous n'avons pas beaucoup de contraintes sur elles. La seule chose qui compte, c'est que nous pouvons obtenir une fonction linéaire des bits de notre représentation d'origine aux bits de la représentation de travail. Cela compte pour deux raisons: premièrement, il est facile de faire des transformations linéaires, alors qu'une transformation non linéaire nécessiterait une optimisation équivalente en difficulté à une optimisation complète de la S-box entière; deuxièmement, parce que nous pouvons obtenir des avantages secondaires. Pour récapituler la structure:Si les bits de
xsontx7 x6 ... x0alors puisque la transformée est linéaire, nous obtenonsa = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Carré et nous obtenonsa^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2où les termes croisés s'annulent (car dans GF (2),1 + 1 = 0). Ila^2peut donc aussi être calculé en fonction linéaire dex. Nous pouvons augmenter la transformation linéaire directe pour obtenir:et nous en sommes à trois multiplications et un ajout. Nous pouvons également étendre le code de multiplication pour effectuer les deux multiplications
Dinven parallèle. Notre coût total est donc une transformation linéaire en avant, une addition, deux multiplications, une inverse en GF (2 ^ 4) et une transformation linéaire en arrière. Nous pouvons rouler dans la transformation linéaire post-inverse de la S-box et l'obtenir essentiellement gratuitement.Le calcul des coefficients pour les transformations linéaires n'est pas très intéressant, pas plus que la micro-optimisation pour sauvegarder un masque ici et un décalage là. La partie intéressante restante est l'optimisation de
inverse_GF16. Il y a 2 ^ 64 fonctions différentes de 4 bits à 4 bits, donc une optimisation directe nécessite beaucoup de mémoire et de temps. Ce que j'ai fait, c'est de considérer 4 fonctions de 4 bits à 1 bit, de plafonner le coût total autorisé pour une fonction (avec un coût maximum de 63 par fonction, je peux énumérer toutes les expressions appropriées en moins d'une minute), et pour chaque tuple de fonctions, éliminer la sous-expression commune. Après 25 minutes de resserrement, je trouve que le meilleur inverse possible avec cette casquette a un coût total de 133 (une moyenne de 33,25 par bit de sortie, ce qui n'est pas mal étant donné que l'expression la moins chère pour un bit individuel est de 35) .J'expérimente toujours avec d'autres approches pour minimiser l'inversion dans GF (2 ^ 4), et une approche qui construit de bas en haut plutôt que de haut en bas a produit une amélioration de 133 à 126.
la source
& 1peut être coupé (surtout s'il l'xestunsigned char;CHAR_BITest 8 en codegolf).Score: 980 = 7 * 5 + 115 * 7 + 7 * 5 + 15 * 7, minimisation de Boyar et Peralta
J'ai trouvé une nouvelle technique de minimisation de la logique combinatoire avec des applications à la cryptologie par Joan Boyar et René Peralta, qui (sauf pour le formalisme C) fait ce qui est nécessaire. La technique utilisée pour dériver leurs équations est brevetée par pas moins que les États-Unis. Je viens de faire une traduction directe en C de leurs équations , gentiment liées ici .
la source
Résultat: 10965
Cela utilise le même principe de déroulement de la recherche de tableau. Peut nécessiter des moulages supplémentaires.
Merci à ugoren d'avoir indiqué comment s'améliorer
is_zero.la source
(c|-c)>>31vaut 0 pour 0 et -1 sinon.c >> 4semblez avoir signé le bon changement pour moi. Et si vous insistez vraiment -((unsigned int)(c|-c))>>31c'estc?1:0.c >>4travaux avec ou sans extension de signe. Mais bonne prise sur l'utilisation d'un quart de travail non signé: modifiera quand je rentrerai à la maison et pourra utiliser un ordinateur approprié plutôt qu'un téléphone. Merci.Score: 9109, approche algébrique
Je laisserai l'approche de recherche au cas où quelqu'un pourrait l'améliorer considérablement, mais il s'avère qu'une bonne approche algébrique est possible. Cette implémentation trouve l'inverse multiplicatif en utilisant l'algorithme d'Euclide . Je l'ai écrit en Java mais en principe il peut être porté en C - j'ai commenté les parties qui changeraient si vous voulez le retravailler en utilisant uniquement des types 8 bits.
Merci à ugoren d'avoir indiqué comment raccourcir le
is_nonzerochèque dans un commentaire sur mon autre réponse.la source
Score: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (en supposant que les boucles soient déroulées)
Explication:
Essentiellement, une recherche de tableau est réimplémentée à l'aide d'opérateurs au niveau du bit et traite toujours l'ensemble du tableau. Nous parcourons le tableau et xor
xavec chaque index, puis utilisons des opérateurs au niveau du bit pour nier logiquement le résultat, nous obtenons donc 255 quandx=iet 0 sinon. Nous binaire-et ceci avec la valeur de tableau, de sorte que la valeur choisie est inchangée et les autres deviennent 0. Ensuite, nous prenons le binaire-ou de ce tableau, tirant ainsi uniquement la valeur choisie.Les deux
1 << jopérations disparaîtraient dans le cadre du déroulement de la boucle, en les remplaçant par les puissances de 2 de 1 à 128.la source
-(2+2)calcul de votre score? Edit: ah, l'incrustation crée un<<1et un>>1.Score
19681692, en utilisant la table de correspondanceRemarque: Cette solution ne répond pas aux critères, à cause de
w >> b.Utilisation de la table de recherche, mais lecture de 8 octets à la fois.
3 * 7 + 32 * (6 * 7 + 2 * 5) + 7 = 692
la source
w>>bRHS a-t-elle été calculée à partir dexw >> boùbdépend de l'entrée; aussix/8,x%8et*= (1-badi). Le premier est particulièrement susceptible de dégénérer en une dépendance temporelle sur les processeurs bas de gamme. Cependant, l'idée d'utiliser des variables larges a certainement du potentiel.w >> bc'est assez essentiel (j'ai besoin de voir si cela peut être résolu sans tout réécrire.Recherche de table et masque, score = 256 * (5 * 7 + 1 * 5) = 10240
Utilise la recherche de table avec un masque pour sélectionner uniquement le résultat souhaité. Utilise le fait qui
j|-jest soit négatif (quand i! = X) soit nul (quand i == x). Le décalage crée un masque tout-un ou tout-zéro qui est utilisé pour sélectionner uniquement l'entrée que nous voulons.la source