W FIPS-197 ( Advanced Encryption Standard , znany jako AES), jest często używany SubBytes
, który można zaimplementować jako
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];}
Ta funkcja nie jest arbitralna; jest odwracalnym odwzorowaniem, polegającym na odwróceniu w polu Galois, po którym następuje afiniczna transformacja. Wszystkie szczegóły znajdują się w FIPS-197 sekcja 5.1.1 lub tutaj sekcja 4.2.1 (pod nieco inną nazwą).
Jednym problemem z implementacją jako tabelą jest to, że otwiera się ona na tak zwane ataki synchronizacji pamięci podręcznej .
Zatem waszą misją jest wymyślenie dokładnego zamiennika powyższej SubBytes()
funkcji, która przejawia zachowanie w czasie stałym; będziemy zakładać, że to przypadek, gdy nic w zależności od wejścia x
w SubBytes
służy albo:
- jako indeks tablicowy
- jako kontrola operandu
if
,while
,for
,case
lub operator?:
; - jak każdy operand operatorów
&&
,||
,!
,==
,!=
,<
,>
,<=
,>=
,*
,/
,%
; - jako prawy operand operatorów
>>
,<<
,*=
,/=
,%=
,<<=
,>>=
.
Zwycięski projekt będzie jednym z najniższych kosztach, uzyskane od liczby wykonawców zawartych w ścieżce danych wejściowych zależne, o wadze 5 dla operatorów jednoargumentowych -
i ~
jak również <<1
, >>1
, +1
, -1
; waga 7 dla wszystkich innych operatorów, zmiany z innymi liczbami lub dodawanie / dodawanie innych stałych (rzutowania typu i promocje są bezpłatne). Zasadniczo koszt ten pozostaje niezmieniony przez rozwinięcie pętli (jeśli występują) i jest niezależny od danych wejściowych x
. Jako remis wygrywa odpowiedź z najkrótszym kodem po usunięciu białych znaków i komentarzy.
Planuję wyznaczyć wpis jako odpowiedź tak wcześnie, jak to możliwe w roku 2013, UTC. Rozważę odpowiedzi w językach, o których wiem trochę, uszeregowując je jako proste tłumaczenie na C niezoptymalizowane pod względem wielkości.
Przeprosiny dla początkowej zaniechania +1
i -1
na uprzywilejowanych operatorów, wolnych odlewów i promocjach oraz rankingu wielkości. Należy pamiętać, że *
jest to zabronione zarówno w przypadku jedności, jak i mnożenia.
źródło
Odpowiedzi:
Wynik:
940 933 926910, podejście do wieży polowejStruktura jest zasadniczo taka sama jak implementacja Boyara i Peralty - zmniejsz inwersję w GF (2 ^ 8) do inwersji w GF (2 ^ 4), podziel ją na liniowy prolog, nieliniowy korpus i liniowy epilog, a następnie zminimalizować je osobno. Płacę pewne kary za ekstrakcję bitów, ale rekompensuję to, że mogę wykonywać operacje równolegle (z pewnym rozsądnym dopełnianiem bitów
fwd
). Bardziej szczegółowo...tło
Jak wspomniano w opisie problemu, S-box składa się z inwersji w konkretnej implementacji pola Galois GF (2 ^ 8), po której następuje transformacja afiniczna. Jeśli wiesz, co oba oznaczają, pomiń tę sekcję.
Transformacja afiniczna (lub liniowa) jest funkcją,
f(x)
która szanujef(x + y) = f(x) + f(y)
if(a*x) = a*f(x)
.Pole to zestaw
F
elementów z dwoma specjalnymi elementami, które nazwiemy0
i1
oraz dwoma operatorami, które wywołamy+
i*
które szanują różne właściwości. W tej części zakładamy, żex
,y
iz
są elementamiF
.F
tworzą Abelowych grupą zgodnie+
z0
jak tożsamość IEx + y
jest elementemF
;x + 0 = 0 + x = x
; każdyx
ma odpowiedni-x
taki, żex + (-x) = (-x) + x = 0
;x + (y + z) = (x + y) + z
; ix + y
=y + x
.F
inne niż0
tworzą Abelowych grupą zgodnie*
z1
jak tożsamość.x * (y + z) = (x * y) + (x * z)
.Okazuje się, że istnieją pewne dość poważne ograniczenia pól skończonych:
p
jest liczbą pierwszą ik
jest mocą) .F\{0}
pod*
cykliczny; tzn. istnieje co najmniej jeden elementg
taki, że każdy element ma mocg
.k
pola pierwszego rzędu. Np. GF (2 ^ 8) ma reprezentację w postaci wielomianówx
ponad GF (2). W rzeczywistości jest zwykle więcej niż jedna reprezentacja. Rozważx^7 * x
w GF (2 ^ 8); musi to być odpowiednik jakiegoś wielomianu rzędu 7, ale który? Istnieje wiele wyborów, które dają odpowiednią strukturę; AES decyduje się na wykonaniex^8 = x^4 + x^3 + x + 1
(leksykograficznie najmniejszy wielomian, który działa).Jak więc obliczyć odwrotność w tej konkretnej reprezentacji GF (2 ^ 8)? Jest to zbyt masywny problem, aby go rozwiązać bezpośrednio, więc musimy go rozwiązać.
Wieże polowe: reprezentujące GF (2 ^ 8) pod względem GF (2 ^ 4)
Zamiast reprezentować GF (2 ^ 8) z wielomianami 8 terminów nad GF (2), możemy przedstawić go wielomianami 2 terminów nad GF (2 ^ 4). Tym razem musimy wybrać liniowy wielomian dla
x^2
. Załóżmy, że wybieramyx^2 = px + q
. Potem(ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq)
.Czy łatwiej jest znaleźć odwrotność w tej reprezentacji? Jeśli
(cx + d) = (ax + b)^-1
otrzymamy równoczesne równaniaad + (b + ap)c = 0
bd + (aq)c = 1
Pozwól
D = [b(b+ap) + a^2 q]
i ustawc = a * D^-1
;d = (b + ap) * D^-1
. Możemy więc wykonać odwrotność w GF (2 ^ 8) dla kosztu konwersji na GF (2 ^ 4), odwrotność oraz kilka dodatków i mnożenia w GF (2 ^ 4) i powrót z powrotem. Nawet jeśli wykonujemy odwrotność za pomocą tabeli, zmniejszyliśmy rozmiar tabeli z 256 do 16.Szczegóły dotyczące wdrożenia
Aby skonstruować reprezentację GF (4), możemy wybrać jeden z trzech wielomianów w celu zmniejszenia
x^4
:x^4 = x + 1
x^4 = x^3 + 1
x^4 = x^3 + x^2 + x + 1
Najważniejszą różnicą jest implementacja mnożenia. Dla każdego z trzech (odpowiadających
poly
3, 9, f) będą działać następujące:Jeśli jednak wybierzemy,
poly = 3
możemy znacznie wydajniej obsłużyć przepełnienie, ponieważ ma ładną strukturę: nie ma podwójnego przepełnienia, ponieważ oba wejścia są zarówno sześcienne, jak ix^6 = x^2 (x + 1)
sześcienne. Ponadto możemy zapisać zmianyb
: ponieważ pozostawiamy przepełnienie do końca,a0 x^2
nie ma żadnych ustawionych bitów odpowiadającychx
lub 1, więc możemy zamaskować go za pomocą -4 zamiast -1. Wynik toNadal musimy wybrać wartości
p
iq
dla reprezentacji GF (2 ^ 8) zamiast GF (2 ^ 4), ale nie mamy na nich wielu ograniczeń. Liczy się tylko to, że możemy uzyskać funkcję liniową od bitów naszej oryginalnej reprezentacji do bitów reprezentacji roboczej. Jest to ważne z dwóch powodów: po pierwsze, łatwo jest wykonać transformacje liniowe, podczas gdy transformacja nieliniowa wymagałaby optymalizacji równoważnej z trudnością do optymalizacji całej S-box; po drugie, ponieważ możemy uzyskać dodatkowe korzyści. Aby podsumować strukturę:Jeśli bity
x
są,x7 x6 ... x0
ponieważ transformacja jest liniowa, otrzymujemya = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0})
. Kwadrat to i dostajemy sięa^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2
tam, gdzie krzyżują się terminy (ponieważ w GF (2),1 + 1 = 0
).a^2
Można więc również obliczyć jako funkcję liniowąx
. Możemy rozszerzyć przednią transformację liniową, aby uzyskać:i jesteśmy zredukowani do trzech mnożeń i jednego dodatku. Możemy również rozszerzyć kod mnożenia, aby wykonać dwa mnożenia
Dinv
równolegle. Zatem nasz całkowity koszt to transformacja liniowa do przodu, suma, dwa mnożenia, odwrotność w GF (2 ^ 4) i wsteczna transformacja liniowa. Możemy przetoczyć post-odwrotną transformację liniową S-boxa i uzyskać ją zasadniczo za darmo.Obliczanie współczynników transformacji liniowych nie jest zbyt interesujące, podobnie jak mikrooptymalizacja w celu zapisania tutaj maski i przesunięcia. Pozostała interesująca część to optymalizacja
inverse_GF16
. Istnieją 2 ^ 64 różnych funkcji od 4 do 4 bitów, więc bezpośrednia optymalizacja wymaga dużej ilości pamięci i czasu. To, co zrobiłem, to rozważenie 4 funkcji od 4 bitów do 1 bitu, nałożenie limitu na całkowity dopuszczalny koszt każdej funkcji (przy maksymalnym koszcie 63 na funkcję mogę wyliczyć wszystkie odpowiednie wyrażenia w mniej niż minutę), i dla każdej krotki funkcji wykonaj wspólną eliminację podwyrażeń. Po 25 minutach chrupania stwierdzam, że najlepszy możliwy odwrotność z tym ograniczeniem ma całkowity koszt 133 (średnio 33,25 na bit wyjścia, co nie jest złe, biorąc pod uwagę, że najtańszym wyrażeniem dla każdego pojedynczego bitu jest 35) .Wciąż eksperymentuję z innymi podejściami, aby zminimalizować inwersję w GF (2 ^ 4), a podejście, które opiera się na podejściu oddolnym, a nie odgórnym, przyniosło poprawę z 133 do 126.
źródło
& 1
można przyciąć (szczególnie jeślix
jestunsigned char
;CHAR_BIT
ma 8 w codegolf).Wynik: 980 = 7 * 5 + 115 * 7 + 7 * 5 + 15 * 7, minimalizacja Boyara i Peralty
Znalazłem nową kombinacyjną technikę minimalizacji logiki z aplikacjami do kryptologii autorstwa Joan Boyar i René Peralta, która (z wyjątkiem formalizmu C) robi to, co jest wymagane. Technika wykorzystywana do wyprowadzania ich równań jest opatentowana przez nie mniej niż USA. Właśnie wykonałem proste tłumaczenie ich równań w języku C , uprzejmie tutaj połączone .
źródło
Wynik: 10965
Korzysta z tej samej zasady rozwijania wyszukiwania tablicy. Może wymagać dodatkowych rzutów.
Dzięki ugoren za wskazanie, jak poprawić
is_zero
.źródło
(c|-c)>>31
wynosi 0 dla 0 i -1 w przeciwnym razie.c >> 4
wydaje mi się, że masz podpisaną prawą zmianę do mnie. A jeśli naprawdę nalegasz -((unsigned int)(c|-c))>>31
jestc?1:0
.c >>4
Współpracuje z lub bez rozszerzenia migowego. Ale dobrze złap się na używaniu niepodpisanej zmiany: edytuję, kiedy wrócę do domu i mogę korzystać z odpowiedniego komputera, a nie telefonu. Dzięki.Wynik: 9109, podejście algebraiczne
Opuszczę podejście do wyszukiwania na wypadek, gdyby ktoś mógł go znacznie poprawić, ale okazuje się, że możliwe jest dobre podejście algebraiczne. Ta implementacja znajduje multiplikatywną odwrotność za pomocą algorytmu Euclid . Napisałem go w Javie, ale w zasadzie można go przenieść do C - skomentowałem części, które zmieniłyby się, gdybyś chciał przerobić go tylko przy użyciu typów 8-bitowych.
Dzięki ugoren za wskazanie, jak skrócić
is_nonzero
czek w komentarzu do mojej drugiej odpowiedzi.źródło
Wynik: 256 * (7+ (8 * (7 + 7 + 7) - (2 + 2)) + 5 + 7 + 7) = 48640 (przy założeniu rozwinięcia pętli)
Wyjaśnienie:
Zasadniczo wyszukiwanie tablicy zostało ponownie zaimplementowane przy użyciu operatorów bitowych i zawsze przetwarza całą tablicę. Pętlimy przez tablicę i xor
x
z każdym indeksem, a następnie używamy operatorów bitowych, aby logicznie negować wynik, więc otrzymujemy 255 kiedyx=i
i 0 w przeciwnym razie. Bitowo - i to z wartością tablicową, tak że wybrana wartość pozostaje niezmieniona, a pozostałe stają się 0. Następnie bierzemy bitową - lub tej tablicy, wyciągając w ten sposób tylko wybraną wartość.Dwie
1 << j
operacje znikną w ramach rozwijania pętli, zastępując je mocami 2 od 1 do 128.źródło
-(2+2)
bierze się twoje obliczenie punktacji? Edycja: ah, wstawianie tworzy a<<1
i a>>1
.Ocena
19681692 za pomocą tabeli odnośnikówUwaga: To rozwiązanie nie spełnia kryteriów z powodu
w >> b
.Korzystanie z tabeli odnośników, ale czytanie 8 bajtów jednocześnie.
3 * 7 + 32 * (6 * 7 + 2 * 5) + 7 = 692
źródło
w>>b
RHS obliczono na podstawiex
w >> b
gdzieb
zależy od danych wejściowych; równieżx/8
,x%8
i*= (1-badi)
. Pierwszy z nich najprawdopodobniej przerodzi się w zależność czasową od niskiej klasy procesorów. Jednak pomysł użycia szerokich zmiennych z pewnością ma potencjał.w >> b
jest to bardzo istotne (muszę sprawdzić, czy można to naprawić bez przepisywania wszystkiego.Wyszukiwanie i maska tabeli, wynik = 256 * (5 * 7 + 1 * 5) = 10240
Używa wyszukiwania tabeli z maską, aby wybrać tylko pożądany wynik. Wykorzystuje fakt, że
j|-j
jest on ujemny (gdy i! = X) lub zero (gdy i == x). Przesunięcie tworzy maskę „wszystko jedno” lub „zero”, która służy do wybrania tylko pożądanego wpisu.źródło