PROBABILISTIC CRYPTANALYTIC ALGORITHMS (DISCRETE LOGARITHMS)

This work evaluates the security threats posed to cryptographic systems by certain probabilistic cryptanalytic methods, including attacks against specific cryptographic systems and the effectiveness of a generalized attack against block ciphers, particularly when used to cryptanalyze the national Data Encryption Standard (DES). Much of the material is of interest in a more general mathematical context. As examples, we consider the structure of directed graphs derived from DES and in doing so derive new results in graph theory in evaluating other cryptosystems we show that fast computation of discrete logarithms is possible in more cases than previously known.The second part of the thesis extends a fast algorithm for computing discrete logarithms to a larger class of finite fields than the original algorithm. We give a rigorous proof of the effectiveness of the extended algorithm the proof also applies to the original algorithm and is the first rigorous treatment of its behavior. As a result of this work, cryptographic systems which rely for their security on the difficulty of computing discrete logarithms are now seen to be much less secure.Additional contributions of this thesis include a new application of discrete logarithms (to "coin flipping"), analysis of a proposed algorithm for integer factoring and its relationship to factoring-based cryptosystems, and a study of circumstances under which cryptanalysis is equivalent in difficulty to exhaustive search.The first part of the thesis concerns the effectiveness of a generalized attack when used to cryptanalyze DES. Since the performance of the attack depends critically on the graph structure of the cryptosystem, we study DES graphs to determine if they contain structures which would make them more or less vulnerable to the attack. In doing so we define a new statistic, "drainage", for graphs, characterize its behavior for random graphs and give an effective algorithm for estimating drainage for surprisingly large graphs. By using the new algorithm with DES graphs and comparing the results with our theoretical predictions, we obtain evidence for the effectiveness of the generalized attack against DES.