Not available / text

Thesis (Ph. D.)--Virginia Polytechnic Institute and State University, 1993. / Vita. Abstract. Includes bibliographical references (leaves 133-136). Also available via the Internet.

Thesis (M.S.)--Oregon State University, 2005. / Printout. Includes bibliographical references (leaves 37-38). Also available on the World Wide Web.

Thesis (Ph. D.)--University of Texas at Austin, 2005. / Supervisor: Brian L. Evans. Vita. Includes bibliographical references.

Thesis (Honors)--College of William and Mary, 2009. / Includes bibliographical references (leaves 27-28).

Thesis (M.S.)--Rochester Institute of Technology, 2008. / Typescript. Includes bibliographical references (leaves 84-85).

This research explores the problem of finding a preimage — an input that, when passed through a particular function, will result in a pre-specified output — for the compression function of the SHA-1 cryptographic hash. This problem is much more difficult than the problem of finding a collision for a hash function, and preimage attacks for very few popular hash functions are known. The research begins by introducing the field and giving an overview of the existing work in the area. A thorough analysis of the compression function is made, resulting in alternative formulations for both parts of the function, and both statistical and theoretical tools to determine the difficulty of the SHA-1 preimage problem. Different representations (And- Inverter Graph, Binary Decision Diagram, Conjunctive Normal Form, Constraint Satisfaction form, and Disjunctive Normal Form) and associated tools to manipulate and/or analyse these representations are then applied and explored, and results are collected and interpreted. In conclusion, the SHA-1 preimage problem remains unsolved and insoluble for the foreseeable future. The primary issue is one of efficient representation; despite a promising theoretical difficulty, both the diffusion characteristics and the depth of the tree stand in the way of efficient search. Despite this, the research served to confirm and quantify the difficulty of the problem both theoretically, using Schaefer's Theorem, and practically, in the context of different representations.

One of the most common tasks in many computer applications is the maintenance of a dictionary of words. The three most basic operations on the dictionary are find, insert, and delete. An important data structure that supports these operations is a hash table. On a hash table, a basic operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case, where n is the number of words in the dictionary. While an ordinary hash function maps the words in a dictionary to a hash table with collisions, a perfect hash function maps the words in a dictionary to a hash table with no collisions. Thus, perfect hashing is a special case of hashing, in which a find operation takes 𝑂(1) time in the worst case, and an insert or a delete operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case. This thesis addresses the following issues: Mapping, ordering and searching (MOS) is a successful algorithmic approach to finding perfect hash functions for static dictionaries. Previously, no analysis has been given for the running time of the MOS algorithm. In this thesis, a lower bound is proved on the tradeoff between the time required to find a perfect hash function and the space required to represent the perfect hash function . A new algorithm for static dictionaries called the musical chairs(MC) algorithm is developed that is based on ordering the hyperedges of a graph. It is found experimentally that the MC algorithm runs faster than the MOS algorithm in all cases for which the MC algorithm is capable of finding a perfect hash function. A new perfect hashing algorithm is developed for dynamic dictionaries. In this algorithm, an insert or a delete operation takes 𝑂(1) time in the average case, and a find operation takes 𝑂(1) time in the worst case. The algorithm is modeled using results from queueing theory . An ordering problem from graph theory, motivated by the hypergraph ordering problem in the Me algorithm, is proved to be NP-complete. / Ph. D.

Thesis (M.S.)--Rochester Institute of Technology, 1987. / Includes bibliographical references.

Thesis (M.C.S.) - Carleton University, 2005. / Includes bibliographical references (p. 107-115). Also available in electronic format on the Internet.