Applications of algebraic number theory to cryptography.

摘要

If two communication partners wish to engage in a private conversation across a public channel, they need to encrypt their messages to prevent an eavesdropper from discovering the contents of their conversation. To achieve this, the two parties must first agree on a common cryptographic key. Such a key cannot be distributed across an open channel, as this would enable an adversary to obtain the key and thus decrypt all communicated information. The problem of key exchange can be overcome in two ways. The partners can employ a public-key cryptosystem, i.e. use different keys for encryption and decryption, where the encryption key is publicly known and the decryption key is known only to the decrypter. Alternatively, they can communicate a sequence of messages according to a specific protocol that allow them to agree on a common key without revealing it to an opponent. This dissertation offers solutions to both approaches.;The first part of this thesis presents a generalization of several existing public-key cryptosystems. The difficulty of breaking the new scheme is equivalent to the problem of factoring a large integer, a task believed to be very difficult. This information regarding the security of the scheme represents an improvement over the well-known RSA public-key system. We describe the number theoretic fundamentals, present the algorithms required for the system together with their computational complexity, analyze the scheme's security, and finally discuss an implementation.;All conventional protocols for key exchange rely strongly on the structure of a group. Recently, for the first time, a modification of the standard protocol was suggested which does not use a group, but is based instead on the infrastructure of a real quadratic field. This loss of structure in the underlying set may increase the security of the scheme over that of previously known protocols. Part II of this thesis introduces the specifics of the new protocol. As before, we give the necessary number theoretic background, describe the algorithms and their complexity, present a complete approximation and error analysis, briefly discuss the security, and conclude with some computational results.