National and Kapodistrian University of Athens
Τεχνικές επεξεργασίας σήματος στην κρυπτογραφία
Abstract
dc:descriptionCryptography is the study of mathematical techniques concerning telecommunication security stream ciphers comprise an important class of cryptographic algorithms. Shift registers with linear (LFSR) or nonlinear (FSR) feedback are the basic building blocks in stream ciphers. The security of these systems is mainly attributed to pseudorandom characteristics of the keystreams. Amongst the cryptographic measures of a sequence is its complexity defined as the length of the shortest FSR that generates the sequence. Especially the linear complexity is important for assessing resistance to cryptanalytic attacks like the Berlekamp-Massey algorithm (BMA). Hence high linear complexity is prerequisite for keystreams. Such sequences are generated by applying nonlinear Boolean functions either as filters or combiners. However resistance of cryptosystems to various attacks is also associated with properties of the functions used. Determining the connections between several cryptographic criteria of sequences remains an open problem. In this thesis, pseudorandom properties of sequences are studied, by using system theoretic concepts. A new unified approach for analyzing the linear complexity is developed via controllability and observability conditions applied to sequence generators. A new generalized Fourier transform is introduced allowing the generation of sequences with prescribed linear complexity. Moreover new classes of nonlinear filters are constructed which guarantee high values of the linear complexity. Furthermore the nonlinear complexity of binary sequences and its connections to other cryptographic criteria is studied. A new efficient recursive algorithm is presented, which produces the minimal FSR of a given sequence, thus generalizing the BMA to the nonlinear case. Connections between nonlinear complexity and Lempel-Ziv complexity are also established. Moreover a lower bound for the Lempel-Ziv compression ratio of a sequence is proved which depends on its nonlinear complexity. Finally the problem of computing best quadratic approximations of Boolean functions is studied. Efficient formulas for computing such approximations for a class of functions with degree 3 and 4 are proved. The methodology is independent from the number of variables and reveals new design principles for cryptographic functions. An analysis of recently proposed cryptographic functions indicates potential weaknesses if construction parameters are not properly chosen.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2007
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Limniotis, Konstantinos
- Λιμνιώτης, Κωνσταντίνος
Subjects
dc:subject × 20- Κρυπτογραφία
- Ακολουθίες
- Αλγόριθμοι ροής
- Λογικές συναρτήσεις
- Πολυπλοκότητα ακολουθιών
- Μετασχηματισμός Fourier
- Καταστατικά συστήματα
- Καταχωρητές ολίσθησης με ανάδραση
- Cryptography
- Sequences
- Stream ciphers
- Boolean functions
- Complexity of sequences
- Fourier transforms
- State space systems
- Feedback shift registers
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23012