Wyniki 1-2 spośród 2 dla zapytania: authorDesc:"Marcin Dawiec"

Porównanie algorytmów mnożenia funkcji boolowskich DOI:10.15199/59.2018.4.4


  Wstęp Niech Vn będzie n-wymiarową przestrzenią wektorową nad ciałem dwuelementowym F2. Każdą funkcję boolowską n-zmiennych f: Vn  {0,1} można przedstawić w postaci: f(x) = S faxa = S f a1 , ..., an x1 a1 ... xn an (1) aÎVn a = (a1, ..., an)ÎVn gdzie fa = fa1 , ..., an Î{0,1}, zaś symbol sumy dotyczy dodawania modulo 2. Przedstawioną powyżej postać nazywa się algebraiczną postacią normalną funkcji f - ANF (Algebraic Normal Form). Z punktu widzenia struktury algebraicznej funkcje boolowskie tworzą pierścień z operacjami dodawania i mnożenia, które cechuje nierówna złożoność obliczeniowa. Dodawanie funkcji boolowskich jest operacją prostą, natomiast mnożenie w ogólnym przypadku operacją bardzo złożoną, która decyduje o efektywności algorytmów wykorzystujących działania arytmetyczne na funkcjach boolowskich. Funkcje boolowskie znajdują szerokie zastosowanie w inżynierii, m.in. obecnie stosowane cyfrowe układy elektroniczne realizują swoje funkcje na podstawie funkcji boolowskich. Arytmetyka funkcji boolowskich, a dokładnie jej złożoność obliczeniowa, ma istotne znaczenie w procesie projektowania układów cyfrowych, matematyce oraz w szczególności w kryptologii. Tam jest nadzwyczaj ważna, gdyż im szybsze metody mnożenia, tym większe możliwości badania własności funkcji kryptograficznych (np. algorytmów blokowych i strumieniowych). Jedną z gałęzi kryptologii, w której szczególne znaczenie ma złożoność arytmetyki funkcji boolowskich, jest kryptoanaliza algebraiczna. Przykładem, gdzie szybkie mnożenie funkcji boolowskich odgrywa ważną rolę, może być wyznaczanie baz Gröbnera z wykorzystaniem algorytmu Buchbergera [1, 2] oraz algorytmów F4 i F5 [3, 4], gdzie występuje mnożenie wielomianów boolowskich w postaci ANF. Istotnym zastosowaniem mnożenia funkcji boolowskich jest znajdowanie ich odporności algebraicznej, która z kolei jest ważna dla bezpieczeństwa szyfrów blokowych i strumieniowych. Zgodnie z definicją, odporno[...]

ATAK ZA POMOCĄ KOSTEK NA SZYFR BLOKOWY CTC DOI:


  1. MOTYWACJA Atak za pomocą kostek, w postaci zaproponowanej przez I. Dinura i A. Shamira w [1] ma zastosowanie dla algorytmów o nieznanej konstrukcji (w postaci tzw. czarnej skrzynki, ang. black box). W fazie wstępnej ataku typowane są 𝑘-elementowe podzbiory zmiennych boolowskich, opisujących działanie szyfru, a następnie generowane 2𝑘-elementowe podzbiory ich wartości, zwane kostkami. Autorzy tego ataku proponują losowe przeszukiwanie kostek. W tym kontekście pojawia się naturalne pytanie, czy wiedza na temat konstrukcji atakowanego algorytmu szyfrowania może zmniejszyć przestrzeń poszukiwania kostek, a zatem zwiększyć skuteczność ataku? Praca udziela pozytywnej odpowiedzi na postawione pytanie. Ponadto, wskazuje możliwość wykorzystania przedstawionego algorytmu do wyszukiwania kostek użytecznych pod kątem innych zastosowań np. cube testers. 2. WSTĘP Atak za pomocą kostek jest atakiem na symetryczne algorytmy kryptograficzne, którego celem jest odzyskanie klucza (ang. key recovery attack). Atak stanowi rozszerzenie ataku AIDA (ang. algebraic IV differential attack), przedstawionego w [2] i ataku różniczek wyższego rzędu [3]. Przy pomocy ataku za pomocą kostek przeprowadzone zostały ataki na 4-rundowy algorytm CTC [4] i 767 rundowy szyfr strumieniowy Trivium [1]. Ponadto, koncepcja kostek została wykorzystana do badania pewnych własności funkcji boolowskich (ang. cube testers) oraz do zdefiniowania dynamicznego ataku kostkami (ang. dynamic cube attack). Ten ostatni umożliwił zaatakowanie 250 rund szyfru strumieniowego Grain [5], zredukowanego do 3 rund szyfru blokowego Serpent [6] oraz zredukowane wersje funkcji skrótu MD6 [7] i Keccak [8]. 2.1. Atak za pomocą kostek Prawie w każdym systemie kryptograficznym bity wyjścia mogą być opisane za pomocą wielomianu wielu zmiennych 𝑝(𝑥1, … , 𝑥𝑛, 𝑘1, … , 𝑘𝑚) nad ciałem 𝐺𝐹 (2) [...]

 Strona 1