Coding Theory and Cryptography

Many books have now been published about the work of the Bletchley Park codebreakers during World War II. Outstanding among these are Alan Turing: The Enigma, by Andrew Hodges [Ho], a sensitive and enormously informative biography of a genius who made a unique contribution to winning the war while he was simultaneously inventing the computer; and Codebreakers, edited by F. H. Hinsley and Alan Stripp [Hin], a series of articles providing detailed information on the methods employed by the codebreakers of Bletchley Park. Particularly to be commended among the latter is the article by Professor I. J. (Jack) Good, entitled “Enigma and Fish”, in which Jack, one of the key members of the teams working first on Naval Enigma and then on the even more sophisticated Geheimschreiber code (which we called Fish!), describes the machines employed by the Germans and the machines we developed to help to read messages encrypted by these machines. It is a great advantage, of course, for those able, like Jack Good, to provide precise descriptions of these machines and of our methods, that much of the necessary information has now, at long last, been declassified.

I have been asked to speak today about some cryptographic work I was engaged in at Bletchley Park, during the Forties. I was concerned mainly with a German machine-cipher known in Bletchley as “FISH”. The network using this system grew to have many links and each link was given the name of a kind of fish. Thus the first link to be intercepted was called “Tunny” and I recall such names as “Bream”, “Herring” and “Mackerel” for later links.

Cryptology consists of two aspects: Signals Intelligence (SIGINT), which seeks to exploit the encrypted communications of enemies or potential enemies, and Information Systems Security, which seeks to protect American communications from those who might wish to exploit them. Americans utilized cryptology even before the foundation of the United States, particularly in the American Revolution and the Civil War. However, it was not until the Twentieth Century that the United States began sustained Communications Intelligence (COMINT) activities.

The present paper appears under joint authorship, however, the responsibilities of the two authors are divided and well defined. Lars Ulfving is the sole author of the original Swedish version of The Geheimschreiber Secret ¹, while Frode Weierud alone is responsible for the translation into English, the translator’s notes, and postscript, as well as the bibliography and the appendixes.

The RSA (Rivest, Shamir, Adleman) cipher algorithm has captured the imagination of many mathematicians by its elegance and basic simplicity ever since it was introduced in 1978. Numerous descriptions of the algorithm have been published. Readers with a knowledge of a little basic number theory will find the original paper [RSA] by the inventors of the algorithm, Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman, quite readable. Perhaps the most famous description is Martin Gardner’s expository article [G], which is written for readers of Scientific American. Martin E. Hellman [H] wrote another good Scientific American article describing the RSA algorithm and the knapsack cipher algorithm. The goal of this paper is to lead the reader who has some mathematical maturity but no knowledge of number theory, say a first year calculus student, a clever high school student, or an interested engineer, through the basic results needed to understand the RSA algorithm. The prerequisites are only a knowledge of the elementary school arithmetic of the integers, high school algebra, some familiarity with the notions of sets and of functions, and, most importantly, a real desire to understand how the RSA algorithm works. We begin with a discussion of general crypto systems and the differences between classical systems and public key systems. Then the treatment will give an informal but fairly rigorous introduction to the division algorithm, divisibility properties, greatest common divisors, the Euclidean algorithm, modular arithmetic, repeated squaring algorithm for b ^a (mod m), time estimates for these algorithms, Euler’s totient function, Euler’s Theorem, and, as a corollary, Fermat’s Little Theorem.

Since 1995–96 I have taught, using Maple, a yearly course on Number Theory and Cryptography to my undergraduate students¹. In this paper I outline some basic number theoretical topics related to cryptography, based on my experience as a teacher of those topics. I am omitting all reference to practical teaching details, but will happily forward all teaching materials (notes, examination papers, etc.) to any interested readers. Finally, several of my NT and Cryptography course Maple worksheets² are available on the internet [Cos].

Alice and Bob wish to communicate without the archvillainess Eve eavesdropping on their conversation. Alice, decides to take two college courses, one in cryptography, the other in quantum mechanics. During the courses, she discovers she can use what she has just learned to devise a cryptographic communication system that automatically detects whether or not Eve is up to her villainous eavesdropping. Some of the topics discussed are Heisenberg’s Uncertainty Principle, the Vernan cipher, the BB84 and B92 cryptographic protocols. The talk ends with a discussion of some of Eve’s possible eavesdropping strategies, opaque eavesdropping, translucent eavesdropping, and translucent eavesdropping with entanglement.

Short Abstract. This is a story about how Alice ingeniously devises two different quantum cryptographic communication protocols (i.e., BB84 and B92) that prevent archvillainess Eve from eavesdropping on Alice’s communications with Bob. How does Alice do this? Also, how does she implement her ideas in optics?

This talk is based on the paper: Lomonaco, Samuel J., A Quick Glance at Quan­tum Cryptography, Cryptologia, Vol. 23, No.1, January, 1999, pp1–41. (Quant­ph/9811056)

Let A be a (0,1)-matrix of size b by v with b ≥ v. Suppose that all rows (columns) of A are nonzero and distinct. We show that the rank of A over a field of characteristic 2 satisfies with equality if and only if A is the incidence matrix of a point-hyperplane Hadamard design. This generalizes a rigidity theorem of Hamada and Ohmori, who assumed that v + 1 is a power of 2 and that A is already known to be the incidence matrix of a Hadamard design. Our results follow from a generalization of a rank inequality of Wallis.

Let K/F _q be an elliptic function field. For every natural number n we determine the number of prime divisors of degree n of K/F _q which lie in a given divisor class of K.

We investigate the question when a cyclic code is maximum distance separable (MDS). For codes of (co-)dimension 3, this question is related to permutation properties of the polynomial (x ^b -1)/(x-1) for a certain b. Using results on these polynomials we prove that over fields of odd characteristic the only MDS cyclic codes of dimension 3 are the Reed-Solomon codes. For codes of dimension \(0(\sqrt q )\) we prove the same result using techniques from algebraic geometry and finite geometry. Further, we exhibit a complete q-arc over the field F _q , for even q. In the last section we discuss a connection between modular representations of the general linear group over F _q and the question of whether a given cyclic code is MDS.

We design algorithms for finding roots of polynomials over function fields of curves. Such algorithms are useful for list decoding of Reed-Solomon and algebraic-geometric codes. In the first half of the paper we will focus on bivariate polynomials, i.e., polynomials over the coordinate ring of the affine line. In the second half we will design algorithms for computing roots of polynomials over the function field of a nonsingular absolutely irreducible plane algebraic curve. Several examples are included.

This paper is an exposition of some aspects of geometric coding theory and Goppa codes on modular curves.