|
|
Cryptographic schemes based on the discrete logarithm problem
Kadlček, Tomáš ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
In the paper we try to give a view of the discrete logarithm problem, especially of related problems that appear in literature since 2001. These problems are based on a computation of Weil and Tate pairing on eliptic curves. We give a view of these problems including some reductions. We mention some chosen schemes based on these problems that are iteresting because of their practical parametrs, primaci of security proofs or because these schemes introduced the new problem. We try to cover precisely the most important definitions in this sector of cryptography because these definition are omitted in the literature and it is often left up to reader to presume details by himself.
|
|
|
Algorithm for word morphisms fixed points
Matocha, Vojtěch ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In the present work we study the first polynomial algorithm, which tests if the given word is a fixed point of a nontrivial morphism. This work contains an improved worst-case complexity estimate O(m · n) where n denotes the word length and m denotes the size of the alphabet. In the second part of this work we study the union-find problem, which is the crucial part of the described algorithm, and the Ackermann function, which is closely linked to the union-find complexity. We summarize several common methods and their time complexity proofs. We also present a solution for a special case of the union-find problem which appears in the studied algorithm. The rest of the work focuses on a Java implementation, whose time tests correspond to improved upper bound, and a visualization useful for particular entries.
|
|
|
Application of ACO to simple subsitution ciphers
Turek, Luboš ; Tůma, Jiří (advisor) ; Holub, Štěpán (referee)
Název práce: Použití ACO algoritmu na řešení jednoduché substituční šifry Autor: Luboš Turek Katedra (ústav): Katedra algebry Vedoucí bakalářské práce: doc. RNDr. Jiří Tůma, DrSc. e-mail vedoucího: jiri.tuma@mff.cuni.cz Abstrakt: V předložené práci studujeme kombinatorickou metaheuristiku Ant Colony Optimization a zkoumáme možné způsoby jejího použití k pro- lomení jednoduché substituční šifry. Součástí práce je návrh a implementace programu. Klíčová slova: jednoduchá substituční šifra, ant colony optimization, ACO, kryptologie, kryptografie Title: Application of ACO to simple subsitution ciphers Author: Luboš Turek Department: Department of Algebra Supervisor: doc. RNDr. Jiří Tůma, DrSc. Supervisor's e-mail address: jiri.tuma@mff.cuni.cz Abstract: In the present work we study combinatorial metaheuristic Ant Colony Optimization and we search for its application to the problem of cracking simple subtitution cipher. Functional implementation is a part of the thesis. Keywords: simple substitution cipher, ant colony optimization, ACO, cryp- tology, cryptography 5
|
|
| |
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
Title: Structure of equality sets Author: Jana Hadravová Department: Department of Algebra Supervisor: doc. Mgr. Štěpán Holub, Ph.D., Dept. of Algebra Abstract: Binary equality set of two morphisms g, h : ⌃⇤ ! A⇤ is a set of all words w over two-letter alphabet ⌃ satisfying g(w) = h(w). Elements of this set are called binary equality words. One of the important results of research on binary equality sets is the proof of the fact that each binary equality set is generated by at most two words provided that both morphisms g and h are non-periodic. Moreover, if a binary equality set is generated by exactly two words, then the structure of both generators, and therefore of the whole set, is uniquely given. This work presents the results of our research on the structure of binary equality sets with a single generator. Importantly, these generators can be decomposed into simpler structures. Generators which can not be further decomposed are called simple equality words. First part of the presented work describes the structure of simple equality words and introduces their detailed classification. The main result of the first part is a precise characterisation of su ciently large simple equality words. In the second part, the work describes the iterative process which transforms a general generator of a binary...
|
|
|
Fast algebraic attacks
Hána, Martin ; Holub, Štěpán (advisor) ; Hojsík, Michal (referee)
In the present work we study algebraic attacks and cascading fast algebraic attack on stream ciphers using in their construction linear feedback shift registers. For deeper understanding of attacks we present some facts which are needed to know from theory of linear recurrence sequences in rst chapter. We show their connection to formalized description of construction we attack. In second chapter we show algebraic attacks on both ciphers using memory or memoryless. We introduce denitions of annihilator and algebraic immunity of Boolean function and show their main properties. In third chapter we use knowledge from rst two chapters and show process and principle of fast algebraic attack.
|
|
|
Time-memory tradeoff útoky
Seidlová, Monika ; Hojsík, Michal (advisor) ; Holub, Štěpán (referee)
Martin Hellman proposed the first time-memory tradeoff attack on block ciphers. It is a chosen plaintext attack, in which the attacker precomputes a large amount of data for some block cipher and can then use it repeatedly in attacks on that block cipher. An improvement suggested by Ron Rivest speeds up the attack by reducing the number of memory accesses. Another modification of the original attack called rainbow tables speeds up the attack even more and brings other advantages. Time-memory tradeoff attacks can also be applied to stream ciphers as known plaintext attacks. This bachelor thesis describes in detail the original attack, its improvements and a modification to stream ciphers. As an example, we summarize an attack on A5/1, a stream cipher used in mobile phones. We also propose a new time-memory tradeoff attack on block ciphers called r-coloured rainbows. The new attack is a modification of Hellman's attack and shares similarities with the rainbow table attack. We give a comparison of the properties of the three attacks and conclude that, for certain block ciphers, our attack may be the most effective of the three.
|
|
| |
|
| |
|
|
Projective geometry codes
Požárková, Zuzana ; Drápal, Aleš (advisor) ; Holub, Štěpán (referee)
In the presented work we define a class of error-correcting codes based on incidence vectors of projective geometries, including the necessary basis of coding theory and projective geometries. A detailed calculation is performed to show the dimension of these codes. In conclusion we concern ourselves with majority decoding. This work is a summary of the results of some known authors engaged in this field. We continue on some of these results and we present evidence of some of the statements, which have been proven differently by other authors.
|
guest ::
