Skip to main content
main-content

Über dieses Buch

This book is intended as a text for a course on cryptography with emphasis on algebraic methods. It is written so as to be accessible to graduate or advanced undergraduate students, as well as to scientists in other fields. The first three chapters form a self-contained introduction to basic concepts and techniques. Here my approach is intuitive and informal. For example, the treatment of computational complexity in Chapter 2, while lacking formalistic rigor, emphasizes the aspects of the subject that are most important in cryptography. Chapters 4-6 and the Appendix contain material that for the most part has not previously appeared in textbook form. A novel feature is the inclusion of three types of cryptography - "hidden monomial" systems, combinatorial-algebraic sys­ tems, and hyperelliptic systems - that are at an early stage of development. It is too soon to know which, if any, of these cryptosystems will ultimately be of practical use. But in the rapidly growing field of cryptography it is worthwhile to continually explore new one-way constructions coming from different areas of mathematics. Perhaps some of the readers will contribute to the research that still needs to be done. This book is designed not as a comprehensive reference work, but rather as a selective textbook. The many exercises (with answers at the back of the book) make it suitable for use in a math or computer science course or in a program of independent study.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Cryptography

Abstract
Broadly speaking, the term cryptography refers to a wide range of security issues in the transmission and safeguarding of information. Most of the applications of algebra and number theory have arisen since 1976 as a result of the development of public key cryptography.
Neal Koblitz

Chapter 2. Complexity of Computations

Abstract
Suppose that f(n) and g(n) are functions of the positive integers n which take positive (but not necessarily integer) values for all n. We say that f(n) = 0(g(n)) (or simply f = 0(g)) if there exists a constant C such that f(n) is always less than C · g(n). For example, 2n2 + 3n − 3 = 0(n2) (namely, it is not hard to prove that the left side is always less than 3n2, so 3 can be chosen as the constant C in the definition).
Neal Koblitz

Chapter 3. Algebra

Abstract
We start out by recalling the basic definitions and properties of a field.
Neal Koblitz

Chapter 4. Hidden Monomial Cryptosystems

Abstract
Let K be an extension of degree n of the finite field F q , where q is a power of 2, and let β1, β2,..., β n ∈ K be a basis of K as an F q -vector space. Alice will be using the Imai-Matsumoto system in K. She regards each element of K as an n-tuple over F q . Alice may choose to keep her basis secret, in which case we cannot assume that a cryptanalyst (whom we shall name “Catherine”) knows what basis she is using.
Neal Koblitz

Chapter 5. Combinatorial-Algebraic Cryptosystems

Abstract
About twenty years ago, a combinatorial cryptosystem called the Merkle-Hellman Knapsack met with a great deal of enthusiastic acclaim [Hellman and Merkle 1978]. For message transmission it was much more efficient than its main competitor at the time, which was RSA. Moreover, it was thought to be almost provably secure. Whereas the security of RSA is based on the difficulty of factoring large integers, that of Merkle-Hellman is based on the conjecturally more difficult Subset Sum problem, which is known to be NP-complete (see Definition 4.6 of Chapter 2).
Neal Koblitz

Chapter 6. Elliptic and Hyperelliptic Cryptosystems

Abstract
Starting in about 1985, the theory of elliptic and hyperelliptic curves over finite fields has been applied to various problems in cryptography: factorization of integers, primality testing, and construction of cryptosystems. In this chapter we shall discuss the last of these. One of the main reasons for interest in cryptosystems based on elliptic and hyperelliptic curves is that these curves are a source of a tremendous number of finite abelian groups having a rich algebraic structure.
Neal Koblitz

Backmatter

Weitere Informationen