|
|
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
|
|
|
Diffie and Hellman are exchanging matrices over group rings
Linkeová, Romana ; Příhoda, Pavel (advisor) ; El Bashir, Robert (referee)
Title: Diffie and Hellman are exchanging matrices over group rings Author: Romana Linkeová Department: Department of Algebra Supervisor: Mgr. Pavel Příhoda, Ph.D., Department of Algebra Abstract: The Diffie-Hellman key exchange protocol is not suitable for devices with limited computational power while computing over group Z∗ p (where p is at least a 300-digit number). This fact led to the research of other algebraic structures, which may help in reducing the computational and storage cost of the protocol. D. Kahrobaei et al. posted in 2013 a proposal for working over a structure of small matrices and claimed that this modification will not affect the security of the protocol. We will attempt to attack this modification of the Diffie- Hellman protocol with the help of the theory of symmetric group representations. Firstly, we mention the basics of the theory of representations together with both the classical and the modified Diffie-Hellman protocol. Next, we elaborate the attack step by step and complement some of the steps with examples. Then, we probed security of the modified protocol against the baby-step giant-step attack. Keywords: public key cryptography, symmetric group representations, Diffie-Hellman protocol 1
|
guest ::
