|
|
Application of Multilinear Forms in Cryptography
Rabas, Tomáš ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.
|
|
|
Elliptic curves over finite fields
Beran, Adam ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis, we study the theory of elliptic curves, with the main focus on elliptic curves over finite fields. We present basic theory, taking several technical aspects into consideration (singularity of the curve, effect of field characteristic on the form of the equation of elliptic curve). We algebraically deduce and formulate the group law, that is the definition of addition on a set of points on elliptic curve). We prove a known result saying that the set of points on elliptic curve under addition forms a group. We present an elementary proof, some of the calculations will be carried out in computer program Mathematica due to their complexity. Finally, we study endomorphisms of elliptic curves over finite fields (homomorphisms on the set of points on elliptic curve that are defined by rational functions). Using obtained results, we prove the Hasse's theorem, which provides an estimate of the order of the group of points on elliptic curve over finite field. 1
|
|
|
Multilinear Maps Over the Integers
Havránek, František ; Žemlička, Jan (advisor) ; Šaroch, Jan (referee)
The thesis aims to describe the [CLT15] scheme, which is based on the Diffie- Hellman scheme and uses multilinear maps over integers. This scheme enables an exchange of a key among several participants. The level κ scheme (using a κ-linear map) enables the exchange of a key among κ + 1 participants. The thesis introduces the basic terms, describes the needed theory, the base of which is the Chinese Remainder Theorem, and also the preparation and usage of the scheme. The correctness of the scheme is proved as well and the related requirements on the basic parameters are discussed.
|
|
|
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
|
guest ::
RSS feed.