Applications of artificial intelligence and related techniques to selected elements of number theory and cryptology

Strong public-key cryptography can provide security for distributed applications across an insecure Internet. The number theory based RSA algorithm apparently provides such a cryptosystem yet its strength has never been proven. It is believed, but not known, that decrypting an RSA encrypted message without secret information is as difficult as factoring the modulo base, and factoring in turn is believed to be no easier than NP. We investigate the application of Artificial Intelligence techniques to the problem of decrypting an RSA encrypted message.; We prove obtaining an exponential period of an encrypted message allows the message to be decrypted without factoring. Then we cast the task of finding such an exponential period as an optimization problem to which genetic algorithms can be applied. An investigation into the various difficulties surrounding such an application leads to the proposal of a novel genetic operator. Empirical evidence demonstrates that the use of genetic search to find an exponential period exhibits exponential growth. An investigation into algebraic structure of the ring ZN shows finding the exponential period is as hard as factoring. As a corollary, we demonstrate a set of relationships between the difficulty of factoring, the RSA problem, the Diffie-Hellman key exchange problem, and the discrete log problem. Based on this we propose a public key system based on Diffie-Hellman that possesses interesting properties relating to its use in Web-based applications. Failing to find another property that may be used to replace exponential period, we look at the application of AI to factoring. We show how to cast factoring as a state space search problem. We construct a factoring tool based on these ideas.