Czesław Kościelny

Uniwersytet Zielonogórski,

Instytut Sterowania i Systemów Informatycznych

Wyższa Szkoła Menedżerska w Legnicy

Zakład Informatyki

Metoda konstrukcji szyfrów blokowych

korygujących manipulacje na kryptogramach

Streszczenie

W referacie przedstawiono zasady ogólnej metody konstrukcji odpornych na złamanie szyfrów blokowych, posiadających cenną dla praktyki właściwość wykrywania i korygowania manipulacji na kryptogramach. Prezentowane szyfry są szyframi endomorficznymi, w których stosuje się ten sam alfabet dla zapisu tekstu jawnego, klucza i kryptogramu, a zdolność detekcji i korygowania celowo wprowadzonych zmian w kryptogramie przez oponenta lub zmian przypadkowych, powodowanych przez zakłócenia w kanale transmisyjnym, uzyskuje się dzięki dwustopniowym procedurom szyfrowania i deszyfrowania. Procedura szyfrowania polega bowiem na złożeniu przekształcenia, zamieniającego tekst jawny na wektor kodowy niesystematycznego kodu cyklicznego z podstawieniem, które każdemu znakowi tekstu jawnego przyporządkowuje inny znak.

1. Wstęp

Sprawne funkcjonowanie każdej instytucji lub organizacji zależy dużej mierze od właściwie zorganizowanej komunikacji między wszystkimi komórkami jej struktury. Chodzi tu nie tylko o efektywną realizację przesyłania poleceń, sprawozdań i różnego rodzaju innych komunikatów, ale też o zagwarantowanie, by przekazywane wiadomości trafiały do właściwych adresatów. Inaczej mówiąc, musi być zapewniona poufność korespondencji, polegająca na uniemożliwianiu odczytania jakiegokolwiek komunikatu przez osobę nieupoważnioną. W szczególności należy starać się o to, by instytucja lub organizacja konkurencyjna nie mogła odczytać żadnego dokumentu wewnętrznego danej firmy. Od tajemnicy korespondencji, związanej z działalnością różnego rodzaju instytucji, organizacji i firm, zależy bowiem ich istnienie na rynku, a jedynym ekonomicznie uzasadnionym środkiem, który tę tajemnicę gwarantuje, jest niezawodny system kryptograficzny.

„Szyfrowanie jest za poważne, aby zostawiać je jedynie rządom” napisał w przedmowie do swojej książki znany kryptolog amerykański [1]. Pisząc te słowa autor miał zapewne na myśli zagrożenia, towarzyszące stosowaniu kryptografii. Na pierwszym miejscu należy tu wymienić zaufanie do instytucji, oferujących usługi kryptograficzne. Ale w Internecie można znaleźć dokumenty z których niezbicie wynika, że nawet renomowane firmy, oferujące komercyjne produkty kryptograficzne, czyli aparaturę lub programy do szyfrowania wiadomości, dokonują celowo takiej degradacji swoich produktów, która pozwala osobie, znającej szczegóły tej degradacji, prawie natychmiast zdeszyfrować kryptogram [8]. Motywem tej nieetycznej działalności jest oczywiście chęć ogromnego zysku, jaki można czerpać ze szpiegostwa przemysłowego i nieuczciwej konkurencji. Dlatego też niezłym wyjściem jest zakup programu, realizującego algorytmy kryptograficzne, w postaci źródłowej. Program powinien być przed zakupem szczegółowo zbadany przez kompetentnego i zaufanego informatyka-kryptologa. Dopiero po dokonaniu transakcji zakupu program szyfrujący i deszyfrujący należałoby skompilować, uruchomić i wdrożyć. Kupowanie aparatury kryptograficznej jest bardziej ryzykowne, gdyż sprawdzenie zasady działania układów scalonych dużej skali integracji, realizujących procedury kryptograficzne jest o wiele trudniejsze niż sprawdzenie programów. Poza tym oprogramowanie kryptograficzne jest bardziej elastyczne niż wyspecjalizowany sprzęt, używany do kryptograficznej ochrony danych. Wyjściem najlepszym wydaje się jednak system kryptograficzny, opracowany przez kompetentnych i lojalnych fachowców, zatrudnionych przez firmę, która będzie ten system używać.

Mając to na uwadze, w referacie przedstawiono nową wersję metody konstrukcji trudnych do złamania blokowych szyfrów symetrycznych, opisywaną wcześnie w pracach [3, 5, 6], które posiadają zdolność wykrywania i korygowania manipulacji na kryptogramach. Ta właściwość szyfru jest szczególnie cenna, gdyż zatrudnieni przez konkurencję kryptoanalitycy często stosują tzw. podsłuch czynny i poprzez manipulacje na kryptogramach usiłują uzyskać dodatkową wiedzę o treści szyfrowanych komunikatów i o metodzie szyfrowania.

2. Metoda konstrukcji nadmiarowego symetrycznego szyfru blokowego korygującego manipulacje na kryptogramach

Cechą charakterystyczną prezentowanej metody konstrukcji szyfru jest sposób likwidowania nadmiarowości tekstu jawnego i usuwania zależności statystycznych między tekstem jawnym i kryptogramem. Zamiast zalecanej przez Shannona techniki mieszania i rozpraszania, polegającej na naprzemiennym stosowaniu podstawień i przestawień, proponowana metoda wmontowuje do procedur szyfrowania i deszyfrowania procedury kodowania i dekodowania kodów cyklicznych, w których występują m. in. nieliniowe operacje mnożenia wielomianów, oraz jedną permutację
, za pomocą której każdy znak tekstu jawnego zastępuje się innym znakiem. Uzyskano dzięki temu zadowalający efekt usuwania nadmiarowości i bardzo dużą przestrzeń klucza, gwarantującą odporność szyfru na złamanie. Jak wspomniano wcześniej, rozpatrywany szyfr jest szyfrem endomorficznym, w którym tekst jawny i kryptogram zapisuje się za pomocą znaków tego samego alfabetu. Znakami alfabetu w rozważanym szyfrze są elementy ciała skończonego GF(q).

Niech system algebraiczny

(1)

złożony ze zbioru liczb całkowitych
i z operacji dodawania i mnożenia elementów tego zbioru reprezentuje q-elementowe ciało skończone i niech

(2)

będzie wielomianem generującym kodu cyklicznego
nad
, korygującego
błędów. Niech też

(3)

będzie dowolną permutacją elementów ciała
. Jeśli sekwencja elementów ciała
w postaci wektora

(4)

stowarzyszonego z wielomianem

oznacza k-elementowy blok tekstu jawnego, i jeśli wektor

(5)

będzie wraz z permutacją
tajnym kluczem, to następujące przekształcenie szyfrujące służy do generowania szyfru blokowego korygującego manipulacje na kryptogramach

(6)

Przekształcenie (6) jest opisane przy pomocy funkcji trzech zmiennych

(7)

gdzie g,
, m, K jak we wzorach (2), (3), (4) i (5), zaś

oznacza odpowiednio procedurę konwersji wielomianu
stopnia
na wektor o m składowych i wektora o m składowych na wielomian stopnia
Operacja mnożenia wielomianów i operacja dodawania, występujące w zależności (7) należy wykonywać zgodnie z arytmetyką ciała GF(q).

Z definicji funkcji E wynika, że odpowiadający blokowi tekstu jawnego m blok kryptogramu c jest sumą nad
n-znakowego bloku klucza K i n-znakowego zmodyfikowanego wektora kodowego niesystematycznego kodu (n, k), w którym każdą składową zastąpiono stosownym elementem ciała
zgodnie z permutacją
.

Przekształcenie deszyfrujące będzie zatem miało postać

(8)

czyli

(9)

gdzie
oznacza kryptogram, w którym dokonano manipulacji,
jest procedurą dekodowania wektora kodowego z korekcją błędów,
jest permutacją odwrotną permutacji (3), przy pozostałych oznaczeniach jak we wzorze (7). Procedura deszyfrowania działa poprawnie, jeśli liczba manipulacji, czyli liczba zmienionych znaków w kryptogramie, nie jest większa od parametru t, który zależy od zdolności korekcyjnej kodu cyklicznego, zastosowanego do konstrukcji szyfru. Jeśli przy tym założy się, że wszystkie szczegóły algorytmów szyfrowania i deszyfrowania są ogólnie znane, wówczas klucz szyfrujący ma dwie składowe: permutację
oraz klucz właściwy K. Wtedy liczba możliwych do zastosowania kluczy wyniesie

(10)

gdzie n jest długością wektora kodowego.

3. Przykład

Dla zilustrowania przedstawionej metody generowania szyfru pozwalającego korygować manipulacje na kryptogramach przyjęto, że stosuje się alfabet w postaci zbioru liczb

.

Wobec tego przy realizacji programowej algorytmów kryptograficznych trzeba zastosować ciało skończone o 8 elementach

w którym operacje dodawania i mnożenia zdefiniowano przy pomocy podanych niżej tabliczek:

Tabliczki dodawania i mnożenia w ciele GF(8)

+	0	1	2	3	4	5	6	7		0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7	0	0	0	0	0	0	0	0	0
1	1	0	3	2	5	4	7	6	1	0	1	2	3	4	5	6	7
2	2	3	0	1	6	7	4	5	2	0	2	4	6	3	1	7	5
3	3	2	1	0	7	6	5	4	3	0	3	6	5	7	4	1	2
4	4	5	6	7	0	1	2	3	4	0	4	3	7	6	2	5	1
5	5	4	7	6	1	0	3	2	5	0	5	1	4	2	7	3	6
6	6	7	4	5	3	2	1	0	6	0	6	7	1	5	3	2	4
7	7	6	5	4	3	2	1	0	7	0	7	5	2	1	6	4	3

Jak wiadomo, jest to ciało charakterystyki 2, więc operacja dodawania jest taka sama, jak odejmowanie. Przyjęto też, że zastosowana będzie permutacja

i jej permutacja odwrotna

oraz cykliczny rozszerzony kod Reeda-Solomona [4] (9, 5), korygujący dwa błędy, o wielomianie generującym, stowarzyszonym z wektorem

,

co oznacza, że

Kod powyższy generuje wektory kodowe o długości 9, składające się z 5 symboli informacyjnych i 4 symboli nadmiarowych. Niech wektory

,

reprezentują odpowiednio tekst jawny i drugą składową klucza. Wobec tego trzeba wyznaczyć

Oto kolejne etapy obliczania kryptogramu

i ostatecznie

.

Jeśli zostanie odebrany kryptogram w postaci

,

w którym zmieniono 3. i 6. symbol, to procedura deszyfrowania ma przebieg:

Przestrzeń klucza dla rozpatrywanego szyfru wyniesie

7. Wnioski

Pokazano stosunkowo prosty sposób generowania symetrycznych szyfrów blokowych, odpornych na złamanie i umożliwiających korekcję manipulacji na kryptogramach. Zaprezentowane szyfry nadają się zarówno do realizacji sprzętowej, pozwalającej na duże szybkości szyfrowania, oraz wolniejszej, ale bardziej elastycznej realizacji programowej. Szyfry można konstruować nad dowolnym alfabetem o liczbie elementów, równej potędze liczby pierwszej. Najbardziej praktycznym sposobem jest jednak zastosowanie uniwersalnego kodu ASCII, kiedy procedury szyfrowania i deszyfrowania można realizować w ciele GF(256). Wówczas przestrzeń klucza, przy stosowaniu rozszerzonego kodu Reeda-Solomona nad GF(256) będzie zawierać
elementów. Procedury szyfrowania i deszyfrowania można także konstruować w oparciu o skrócone kody cykliczne. Warto też wspomnieć, że opisany szyfr może pracować w trybie elektronicznej książki kodowej, trybie łączenia bloków zaszyfrowanych i w trybach sprzężenia zwrotnego kryptogramu. Szyfr jest szczególnie przydatny do szyfrowania dużych plików, rzędu 10 i więcej megabajtów.

Literatura

[1]	B. Schneier, Applied Cryptography, John Wiley & Sons, 1996, second edition
[2]	Cz. Kościelny, Programowa realizacja działań w ciałach skończonych do zastosowań w technice kodowania korekcyjnego i kryptografii, Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej nr 61, seria monografie nr 11 , 115 s., 1983.
[3]	Cz. Kościelny, W. Mochnacki, Kryptografia z zastosowaniem kodów cyklicznych, II Krajowa Konferencja Naukowo-Techniczna Przetwarzanie sygnałów w telekomunikacji, sterowaniu i kontroli, Tom 1: transmisja informacji s. 20-23, Bydgoszcz, 23-25 września 1986.
[4]	Cz. Kościelny, Constructing a Better Cyclic Code than Cyclic Reed-Solomon Code, IEEE Trans. on Information Theory, vol. 41 No. 4, July 1995, s. 1191 - 1194
[5]	Cz. Kościelny, T. Hebisz, Metoda konstrukcji szyfru blokowego wykrywającego manipulacje na kryptogramach, Materiały II Krajowej Konferencji Zastosowań Kryptografii ENIGMA'98, Warszawa, 26 - 28 maja 1998, str. KII-WOC-29 - KII-WOC-42.
[6]	Cz. Kościelny, T. Hebisz, Kod Reeda-Solomona jako symetryczny szyfr blokowy wykrywający manipulacje na kryptogramach, Prace V Krajowej Konferencji Naukowo-Technicznej Diagnostyka Procesów Przemysłowych, str. 343 - 346, Łagów Lubuski, 17 - 19 września 2001
[7]	Cz. Kościelny, T. Hebisz, More Secure Computing in Finite Fields for Cryptographic Applications, Proceedings C. D. of Fourteenth International Symposium on Mathematical Theory of Networks and Systems MNTS 2000, Perpignan, France, June 19 - 23, 2000
[8]	Cz. Kościelny, Polityczne i prawne uwarunkowania techniki ochrony poufności informacji w Internecie, materiały Ogólnopolskiej Konferencji Naukowej Funkcjonowanie i rozwój organizacji w zmiennym otoczeniu, Legnica, 11 września 2001.

.

Metoda konstrukcji szyfrów blokowych korygujących manipulacje na kryptogramach

1

---