|
|
Recovering daily keys for Enigma
Kubániová, Dominika ; Tůma, Jiří (advisor) ; Žemlička, Jan (referee)
During the second world war the ability to read enemy's encrypted messages was important to defence own territory and even to quicken the end of the war. One of the encrypting machines was german Enigma, whose seizing did not yet mean any success of decryption since the number of all possible settings for one day was a number exceeding trillions. In the pre-war and war years the breaking of Enigma was led by the best polish and british mathematicians, while they had to strictly keep their achievements secret, even decades years after the war. The aim of my bachelor thesis is to create a mathematical model of Enigma and to reconstruct its procedures for discovering daily keys with emphasis on their mathematical substantiation. 1
|
|
|
Groups the order of which is the fourth power of a prime greater than three
Prokop, Jakub ; Drápal, Aleš (advisor) ; Žemlička, Jan (referee)
The primary objective of this thesis is the classification of groups the order of which is the fourth power of a prime greater than three. First, concepts such as the Frattini subgroup are introduced, and some of their general properties are shown. These properties are then used to seperate the groups of order p4 for p > 3 into distinct cases, and these cases are then described in more detail. In the final chapter semihomomorphisms are introduced, and some properties of the group of semiautomorphisms are shown. In particular, a method of embedding semiautomorphisms of a group is shown, and the group of semiautomorphisms of a group of nilpotence class two is described in more detail. 1
|
|
|
Bubble Blast 2
Vaňková, Petra ; Tůma, Jiří (advisor) ; Žemlička, Jan (referee)
Title: Bubble Blast 2 Author: Petra Vaňková Department: Department of Algebra Supervisor: Doc. RNDr. Jiří Tůma, DrSc., Department of Algebra Abstract: This thesis deals with mathematical analysis and solvability of the Bubble Blast 2 game. The first part introduces rules of the game, and a matrix representation of the game. The second part at first describes the two-dimensional game dynamics, and also important terms such as agent, time, and state matrix are defined. It is explained why dealing with solvability of the two-dimensional game is difficult and an easier straight line version of the game is introduced. The main part consists of several theorems about the one-dimensional game that eventually lead to the necessary and sufficient condition of the game solvability with only one click given. All results of this thesis are original, only a minor part is based on the game source code. Keywords: model of the game, state matrix, state transformation, agent
|
|
|
Fast multiplication in the field GF(2n)
Bajtoš, Marek ; Žemlička, Jan (advisor) ; Šaroch, Jan (referee)
Title: Fast multiplication in the field GF(2n ) Author: Marek Bajtoš Department: Department of Algebra Supervisor: doc. Mgr. et Mgr. Žemlička Jan, Ph.D., Department of Algebra Abstract: In this bachelor thesis we research how to optimize multiplication with a fixed element of finite field which can be useful for implementation of crypto- graphic algorithms in lightweight cryptography. We will represent effectivity of multiplication by number of XOR operation needed for implementation of matrix which represent some fixed element of finite field. We prove that some matrix re- presents multiplication with some element of finite field if and only if the minimal polynomial of matrix is irreducible. We also prove theorems describing conditi- ons which matrix must satisfy so matrix can be implemented with only 1 or 2 XOR operations. At the end of the thesis we show construction of circulant MDS matrices which uses elements of finite field with low XOR count so they can be easily implemented. Keywords: lightweight cryptography, finite field, XOR, MDS matrix
|
|
|
GPS and how it works
Štumpf, Daniel ; Tůma, Jiří (advisor) ; Žemlička, Jan (referee)
In this bachelor thesis we provide information about algorithms for GPS po- sitioning and about the accuracy of the estimated position. We describe two algorithms that lead to a position of a receiver. They both measure pseudoran- ges to the satellites but in two different ways. Pseudorange is an observed value, which we get from the received signal, that include distance to the satellite and errors like atmospheric delay and clock offset. The first algorithm uses pseudo- ranges based on the travel time of the broadcasted satellite signal and leads to a meter position accuracy. The second algorithm uses phase observations of pseu- doranges and results in much higher accuracy. Using dual frequency receivers and differential GPS we get to a mm accuracy. Then we describe a Kalman filter that is used for estimating position of a moving receiver and improving the estimated position of a static receiver. 1
|
|
|
Star height
Svoboda, Tomáš ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
We present a certain family of languages and show that for those languages infinite hierarchy of star heights exists. The proof was first devised by Dejean and Schützenberger. More recently it was reformulated by Sakarovitch, who left some of the parts of the proof the the reader for more careful consideration. This thesis expands on those parts and provides more detailed proofs. We mainly focus on construction of rational expression with the star height of the given language. We also compare the star height and generalised star height and the difference in achieved results for those two similar concepts.
|
|
|
The knapsack and its applications
Linkeová, Romana ; Příhoda, Pavel (advisor) ; Žemlička, Jan (referee)
Title: The knapsack and its applications Author: Romana Linkeová Department: Department of Algebra Supervisor: doc. Mgr. Pavel Příhoda, Ph.D., Department of Algebra Abstract: This thesis is focused on various aspects of cryptosystems based on NP (non-deterministic polynomial) complete knapsack problem. From the theory of complexity point of view, the less known parts of the proof of knapsack problem NP completeness are shown in detail. From the cryptographical point of view, a demonstration of breaking of the Merkle-Hellman cryptosystem (the basic de- sign of knapsack-type cryptosystems) is provided, showing that poor parameters choice can lead to easy obtaining of the whole private key. Another contribution of this thesis consists in a presented proposal of a new cryptosystem concept based on the matrix 0-1 knapsack problem. This concept was developed in order to prevent known attacks, however, in the thesis we provide a proof analogous to J. C. Lagarias and A. M. Odlyzko, 1985, which shows that an attack based on the LLL algorithm will be successful on the majority of the matrix 0-1 kna- psack problem cryptosystems. Finally, a list of modern cryptosystems based on the knapsack problem is provided and a cryptanalysis thereof is given. Keywords: knapsack problem, NP complete problems, LLL algorithm 1
|
|
|
Decidability of the theory of commutative groups
Čech, František ; Šaroch, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis will be demonstrated proof of decidability of theory of commu- tative groups. This result was already shown in year 1955 by author W.Szmielew. However proof shown here takes different path. Result will by shown with use of results from theory of modules and theory of modeles prooved in article by M. Ziegler Model theory of modules. Final part of proof follows proof shown in article The elementary theory of Abelian groups by P. C. Eklofa and E. R. Fishera. 1
|
|
|
Semilinear sets
Bouška, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In this thesis we examine a part of the mathematical side of the theory of context free languages, namely semilinear sets. We prove that the semilinear sets are closed under set intersection and difference in a mathematically better digestible and possibly easier way than how it is presented as a non-central result in the referenced literature. Then we introduce the notion of a context-free language and present a result that relates semilinear sets and context-free languages without a proof. 1
|
|
|
Binary codes based on (2,3)-representation
Sternwaldová, Anetta ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
A new class of prefix codes is introduced in this thesis. These codes are based on an integer representation in mixed base with the radices 2 and 3. The goal is to describe (2,3)-representation and its properties with regard to utilization for encoding. The thesis also deals with construction of (2,3)-codes and proves that (2,3)-codes prevent error propagation over many codewords during data transmission. Upper bound of codeword length is obtained and estimate of average expected codeword length is also presented. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.