|
|
Sieving in factoring algorithms
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. Apart from several well-known variants, we present our own proposals of both quadratic and number field sieve and analyze their advantages and disadvantages in detail. 1
|
|
|
Sieving in factoring algorithms
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. In addition, we present our own variant of the quadratic sieve, which has relatively large advantages in some areas compared to other known suggestions. 1
|
|
|
On DSA
Čadová, Veronika ; Drápal, Aleš (advisor) ; Jedlička, Přemysl (referee)
This thesis deals with problems of comparing the safety and running time of digital signatures DSA and Schnorr. Digital signature is almost full, legally recognized alternative to physical sign, intended for use in a digital environment. Digital signature uses asymmetric codes and hash functions which are easily described, as well as other basic concepts such as discrete logarithm and cyclic groups. The thesis deals with the analysis of possible attacks on DSA and compares DSA and Schnorr algorithm. Digital signature history and its implementation is part of the thesis.
|
|
|
Side information based cryptanalysis
Primas, Martin ; Rosa, Tomáš (advisor) ; Jedlička, Přemysl (referee)
This thesis presents the side channel attack on implementation of RSA scheme where Montgomery multiplication and Chinese remainder theorem are used. The attack is based on already published Tomoeda`s attack that is studied more exactly in this thesis. Tomoeda`s attack is revised and especially the theoretical bound for probability of success of this attack is found. Next we provide new formal de nition used in searching for approximate greatest common divisors where well known LLL algorithm for searching for approximated shortest vector in lattices is used. Original connection between Tomoeda`s attack and algorithm for searching for approximate greatest common divisors is the main contribution of this work as the connection provide better attack on RSA scheme. In the last part we search for optimal connection of these algorithms and particular attacks are described.
|
|
|
Testing perfect powers
Straková, Hana ; Stanovský, David (advisor) ; Jedlička, Přemysl (referee)
A positive integer n is a perfect power if there exist integers x and k, both at least 2, such that n = x^k. Perfect power testing is important as preprocessing for number factorization and prime number testing, because many algorithms for that are not able to distinguish between prime number and power of prime number, so it is necessary to test it by perfect power tests. This thesis includes comparison of two algorithms for perfect power testing, one by Daniel J. Bernstein and the other by E. Bach & J. Sorenson. The goal is to implement described algorithms in C language with GMP library for multiple-precision arithmetics, to compare the theoretical results and running times of implemented algorithms.
|
|
| |
|
| |
|
|
Advanced techniques for calculations of discrete logarithm
Matocha, Vojtěch ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
Let G be a finite cyclic group. Solving the equation g^x = y for a given generator g and y is called the discrete logarithm problem. This problem is at the core of many modern cryptographic transformations. In this paper we provide a survey of algorithms to attack this problem, including the function field sieve, the fastest known algorithm applicable to the multiplicative group of a finite field. We also discuss the index calculus algorithm and some techniques improving its performance: the Coppersmith's algorithm and the polynomial sieving. The most important contribution of this paper is a C-language implementation of the function field sieve and its application to real inputs.
|
|
|
On DSA
Čadová, Veronika ; Drápal, Aleš (advisor) ; Jedlička, Přemysl (referee)
This thesis deals with problems of comparing the safety and running time of digital signatures DSA and Schnorr. Digital signature is almost full, legally recognized alternative to physical sign, intended for use in a digital environment. Digital signature uses asymmetric codes and hash functions which are easily described, as well as other basic concepts such as discrete logarithm and cyclic groups. The thesis deals with the analysis of possible attacks on DSA and compares DSA and Schnorr algorithm. Digital signature history and its implementation is part of the thesis.
|
|
|
Number Field Sieve for Discrete Logarithm
Godušová, Anna ; Jedlička, Přemysl (advisor) ; Příhoda, Pavel (referee)
Many of today's cryptographic systems are based on the discrete logarithm problem, e.g. the Diffie-Hellman protocol. The number field sieve algorithm (NFS) is the algorithm solving the problem of factorization of integers, but latest works show, it can be also applied to the discrete logarithm problem. In this work, we study the number field sieve algorithm for discrete logarithm and we also compare the NFS for discrete logarithm with the NFS for factoriza- tion. Even though these NFS algorithms are based on the same principle, many differences are found. 1
|
guest ::
RSS feed.