W tym zadaniu zajmiemy się uproszczoną wersją pewnego bardzo powszechnie stosowanego szyfru strumieniowego. Zarówno użytkownicy jak i łamacze szyfrów chcą posiadać jego możliwie najszybszą implementację. Pierwsi chcą szyfrować w czasie rzeczywistym dane przesyłane szybkimi łączami. Drudzy próbują brutalnego ataku i chcą sprawdzać jego skuteczność w możliwie najkrótszym czasie.
Rozważany szyfr posiada efektywną implementację sprzętową, która umożliwia
szyfrowanie/deszyfrowanie jednego bitu w jednym takcie zegara.
Niestety nie dysponujemy sprzętowym szyfratorem i musimy go zaimplementować
na dostępnym pececie.
W książce "Kryptografia dla praktyków" Bruce'a Schneiera znaleźliśmy
implementację w języku C.
Niestety bliższe przyjrzenie się pokazało, że kod ten jest napisany
badziewiasto i nie jest wolny od błędów.
Na szczęście udało się go odpluskwić i uruchomić.
Efekt nas rozczarował.
Szyfrowanie 1 bitu zajmuje 195 taktów zegara.
Próbujemy zmusić gcc do agresywnej optymalizacji.
Najlepsza okazuje się kombinacja opcji
-O3 -mcpu=pentium2 -fomit-frame-pointer.
Nasz kompilator potrafi czynić cuda - szyfrowanie 1 bitu zajmuje już tylko
71 takty zegara.
Jednak naszym celem jest zejście poniżej 32 taktów zegara.
Spróbujmy użyć asemblera.
I tu zaczyna się właściwe zadanie.
Plik cipher.c zawiera wzorcową
implementację (odpluskwioną ale nadal badziewiastą) rozważanego szyfru w języku C.
Główną procedurą jest encrypt_dectrypt_c.
Oprócz tego plik ten zawiera procedury do porównywania wydajności implementacji.
Plik cipher.asm zawiera asemblerową
procedurę encrypt_dectrypt_asm, która aktualnie wywołuje swoją
odpowiedniczkę w C.
Należy wstawić do tego pliku, wykonaną w asemblerze NASM, własną implementację.
Plik makefile umożliwia skompilowanie
całości.
Program oczekuje jednego 9-cio znakowego argumentu, który jest kluczem szyfrowania.
Program wykonuje trzy testy, porównujące implementację w C z implementacją w asemblerze.
Dla każdego testu program wypisuje wartość improvement,
określającą ile razy implementacja asemblerowa jest szybsza.
Liczba punktów za zadanie będzie wyliczana jako średnia z kilku testów za pomocą
formuły
Prawdopodobnie niezłą strategią rozwiązywania tego zadania będzie:
dobre zrozumienie działania algorytmu szyfrującego,
wykonanie jego efektywnej implementacji w języku C,
przetłumaczenie na asembler za pomocą gcc z ustawioną optymalizacją i opcjami
-S -masm=intel i na koniec ręczne podrasowanie kodu asemblerowego.
Należy założyć, że adres wskazujący na dane do zaszyfrowania lub odszyfrowania jest
wielokrotnością 4.
Można też założyć, że długość tych danych jest wielokrotnością 4 lub nawet 16,
jeśli komuś będzie tak wygodniej.