Implementierung eines verbandstheoretischen Chiffrierverfahrens

Abstract

In dieser Diplomarbeit geht es um die Entwicklung, Implementierung und Analyse eines symmetrischen Chiffrierverfahrens, welches auf einer hier für unsere Zwecke adaptierten algebraischen Struktur, den sogenannten *-Verbänden, basiert. Das Ziel der Arbeit ist es, ausgehend von den algebraischen Grundlagen des Chiffrierverfahrens, welche der Arbeit "Polynomial permutations on finite lattices related to cryptography" von D. Dorninger und H. Länger entnommen sind, das Verfahren im Detail zu formulieren, zu implementieren und dessen Stärken und Schwächen hervorzuheben.<br />Zu Beginn werden, basierend auf der Arbeit von D. Dorninger und H.<br />Länger, algebraische Strukturen und Abhängigkeiten dargestellt und weiterentwickelt, mit deren Hilfe Polynome auf Verbänden konstruiert werden, welche die Elemente des Verbands permutieren. Da alle Polynome auf Verbänden ordnungserhaltend sind und sich daher im Allgemeinen nicht für die Darstellung von Permutationen eignen, wird eine weitere Verbandsoperation * eingeführt, die eine antitone Involution darstellt.<br />Die dadurch entstehende algebraische Struktur heißt ein *-Verband und wird von uns mit V bezeichnet. Wir zeichnen Elemente a aus V mit einer bestimmten Eigenschaft aus und nennen diese zentrale Elemente. Über diese zentralen Elemente definieren wir in weiterer Folge Polynome pa, die Permutationen auf den *-Verbänden darstellen, sogenannte Polynompermutationen. Jede Polynompermutation pa steht in bijektiver Beziehung zu genau einem zentralen Element.<br />Es stellt sich heraus, dass diese speziell konstruierten Polynompermutationen bezüglich der Hintereinanderausführung eine Untergruppe der Ordnung 2 aller bijektiven Polynomfunktionen auf V bilden, die wiederum selbst eine Untergruppe der symmetrischen Gruppe des *-Verbands ist.<br />Mit den gewonnenen Polynompermutationen wird nun ein symmetrisches, verbandstheoretisches Chiffrierverfahren definiert. Um Aussagen über die Qualität der Verschlüsselung treffen zu können, wurde das Chiffrierverfahren als interaktives Programm implementiert.<br />Anhand mehrerer Methoden der Kryptoanalyse wird argumentiert, inwiefern das entwickelte verbandstheoretische Verfahren diesen Angriffen trotzen kann. Am Ende der Arbeit werden entdeckte Stärken und Schwächen zusammengefasst, sowie Ideen vorgestellt, das Chiffrierverfahren gegen einige dieser Schwächen resistent zu machen.<br />Zu guter Letzt stellen wir noch in Aussicht, wie ein asymmetrisches Verfahren, das ebenfalls auf *-Verbänden basiert, entwickelt werden könnte.<br />

The subject of this thesis is the development, implementation and analysis of a symmetric cipher based on an algebraic structure called *-lattice. On the basis of the algebraic principles of the encryption algorithm shown in the paper "Polynomial permutations on finite lattices related to cryptography" from D. Dorninger and H.<br />Länger, we formulate and implement the cipher and point out strengths and weaknesses.<br />First we illustrate and enhance the algebraic structures and dependencies developed in the paper from D. Dorninger and H. Länger and construct functions on lattices which permute the elements of those lattices.<br />In order to do the calculations by means of polynomials a further operation * on a lattice is introduced as an antitone involution of the lattice (Because all polynomial functions on a lattice are order preserving, this further operation * is introduced.). The resulting algebraic structure V is called a *-lattice. We define elements a in V with certain properties as central elements and select corresponding polynomial functions that are permutations on V. These polynomial functions are bijectively related to the central elements of the *-lattice and are referred to as polynomial permutations. These polynomial permutations form a subgroup of all bijective polynomial functions on V.<br />By means of these polynomial permutations a symmetric, lattice-based cipher is defined: Blocks of plaintext with elements xk in *-lattices Vk are encoded to pa(xk) in Vk by polynomial permutations pa. To decode the ciphertext the same polynomial permutation pa can be used: xk = pa(pa(xk)).<br />After an extensive analysis of the parameters of the cipher, further details of the encryption algorithm are presented and a possibility for a secure key exchange is given. Also a summary of the whole cipher for a computer scientiest is provided.<br />To examine the quality of the cipher, the procedure is implemented as an interactive program. Some relevant established techniques in the field of cryptoanalysis are discussed and applied. We point out strengths and weaknesses of the encryption algorithm and suggest approaches such as Cipher Block Chaining to compensate disadvantages.<br />Finally we provide a possibility for the development of an asymmetric cipher based on *-lattices.