Coding Theory and Cryptography

Posted on 2021/10/11 by wdjoyner

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory
(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
FISH and I, by W. T. Tutte pdf
Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
Number Theory and Cryptography (using Maple), by John Cosgrave pdf
A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.

This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

Ring theory, via coding theory and cryptography

Posted on 2018/04/01 by wdjoyner

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

Elizebeth Friedman and the Holmwood case

Posted on 2017/11/07 by wdjoyner

Elizebeth Smith Friedman was the top cryptographer for the Coast Guard (then the enforcement arm of the Department of the Treasury) during the Prohibition Era.

According to wrecksite.eu, the SS Holmewood (that ESF spelled as Holmwood), also registered as the SS Ara, was a Swedish refrigerated cargo steamer [edited 2021 – see comments below]. Read more at wrecksite: https://www.wrecksite.eu/wreck.aspx?31920

The Holmwood case is a prohibition-era legal investigation concerning events up to and including the seizure of the SS Holmwood in October 5, 1933, in the Hudson River, and the subsequent trial of the smugglers. The New York Intelligence Office (of the Coast Guard, as part of the Treasury Department) used Elizebeth Friedman’s cryptanalysis of telegraph messages between the Holmwood and shore-based agents.

The best source of information from the ESF collection at the Marshall library, Box 6, File 24, “Notes on the solution of cipher and code used by the Holmwood” (14 pages), dated October 11, 1934. This document describes the investigation of the liquor smuggling operations of the Holmwood from 1930 to 1934. The first interception was November, 1930, by the New York Intelligence Office of the Treasury Department. The Coast Guard operated radio stations which monitored rum-runner telegraph stations. Usually these were in a telegraph cipher-code but sometimes they were in plain English. For example, it was reported that at 1505 on October 3, 1933, Radioman First Class B. E. Howell, of the New York Intelligence Unit, intercepted the following message

Anchor the boat in good place immediately. Take all men off in one of life boats. Hide the life boat if possible. Come ashore on New York side. Call [undecoded phone number] when you come ashore. PA code.

This message was preceded by a telegraph cipher-code

JDSLE 2221 1612 WJJE …. DEMPY.

which was decoded (by the office of ESF) as

Heave your anchor immediately and get underway. Stand up the river towards Albany.

This led to the seizure of the Holmwood. ESF wrote a strong commendation letter for Radioman Howell for his hard work and dedication to service.

For more on the life of Elizebeth Friedman, see [1], [2], or the (to be published?) book Divine Fire, by Katie Letcher Lyle, with significant additional material by myself.

[1] Smith, G. Stuart, A Life in Code: Pioneer Cryptanalyst Elizebeth Smith Friedman, McFarland & Company, Jefferson, NC, 2017.

[2] Fagone, Jason, The Woman Who Smashed Codes: A True Story of Love, Spies, and the Unlikely Heroine Who Outwitted America’s Enemies, Dey Street Books, New York, 2017

Problem of the week, 137

Posted on 2016/09/18 by wdjoyner

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

Hill verses Hamming

Posted on 2016/08/05 by wdjoyner

It’s easy to imagine the 19th century Philadelphia wool dealer Frank J. Primrose as a happy man. I envision him shearing sheep during the day, while in the evening he brings his wife flowers and plays games with his little children until bedtime. However, in 1887 Frank J. Primrose was not a happy man. This is because in June of that year, he had telegraphed his agent in Kansas instructions to buy a certain amount of wool. However, the telegraph operator made a single mistake in transmitting his message and Primrose unintentionally bought far more wool than he could possibly sell. Ordinarily, such a small error has little consequence, because errors can often be detected from the context of the message. However, this was an unusual case and the mistake cost him about a half-million dollars in today’s money. He promptly sued and his case eventually made its way to the Supreme Court. The famous 1894 United States Supreme Court case Primrose v. Western Union Telegraph Company decided that the telegraph company was not liable for the error in transmission of a message.

Thus was born the need for error-correcting codes.

Introduction

Lester Hill is most famously known for the Hill cipher, frequently taught in linear algebra courses today. We describe this cryptosystem in more detail in one of the sections below, but here is the rough idea. In this system, developed and published in the 1920’s, we take a $k\times k$ matrix K, composed of integers between 0 and 25, and encipher plaintext p by $p\longmapsto c=Kp$ , where the arithmetical operations are performed mod 26. Here K is the key, which should be known only to the sender and the intended receiver, and c is the ciphertext transmitted to the receiver.

On the other hand, Richard Hamming is known for the Hamming codes, also frequently taught in a linear algebra course. This will be describes in more detail in one of the sections below, be here is the basic idea. In this scheme, developed in the 1940’s, we take a $k\times k$ matrix G over a finite field F, constructed in a very particular way, and encode a message m by $m\longmapsto c=mG$ , where the arithmetical operations are performed in F. The matrix G is called the generator matrix and c is the codeword transmitted to the receiver.

Here, in a nutshell, is the mystery at the heart of this post.

These schemes of Hill and Hamming, while algebraically very similar, have quite different aims. One is intended for secure communication, the other for reliable communication. However, in an unpublished paper [H5], Hill developed a hybrid encryption/error-detection scheme, what we shall call “Hill codes” (described in more detail below).

Why wasn’t Hill’s result published and therefore Hill, more than Hamming, known as a pioneer of error-correcting codes?

Perhaps Hill himself hinted at the answer. In an overly optimistic statement, Hill wrote (italics mine):

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements $c_1,\dots,c_q$ according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution.

– Lester Hill, [H5]

By my interpretation, this suggests Hill wanted to answer the question below before moving on. As simple looking as it is, this problem is still, as far as I know, unsolved at the time of this writing.

Question 1 (Hill’s Problem):
Given k and q, find the largest r such that there exists a $k\times r$ van der Monde matrix with the property that every square submatrix is non-singular.

Indeed, this is closely related to the following related question from MacWilliams-Sloane [MS77], also still unsolved at this time. (Since Cauchy matrices do give a large family of matrices with the desired property, I’m guessing Hill was not aware of them.)

Question 2: Research Problem (11.1d)
Given k and q, find the largest r such that there exists a $k\times r$ matrix having entries in GF(q) with the property that every square submatrix is non-singular.

In this post, after brief biographies, an even more brief description of the Hill cipher and Hamming codes is given, with examples. Finally, we reference previous blog posts where the above-mentioned unpublished paper, in which Hill discovered error-correcting codes, is discussed in more detail.

Short biographies

Who is Hill? Recent short biographies have been published by C. Christensen and his co-authors. Modified slightly from [C14] and [CJT12] is the following information.

Lester Sanders Hill was born on January 19, 1890 in New York. He graduated from Columbia University in 1911 with a B. A. in Mathematics and earned his Master’s Degree in 1913. He taught mathematics for a few years at Montana University, then at Princeton University. He served in the United States Navy Reserves during World War I. After the WWI, he taught at the University of Maine and then at Yale, from which he earned his Ph.D. in mathematics in 1926. His Ph.D. advisor is not definitely known at this writing but I think a reasonable guess is Wallace Alvin Wilson.

In 1927, he accepted a position with the faculty of Hunter College in New York City, and he remained there, with one exception, until his resignation in 1960 due to illness. The one exception was for teaching at the G.I. University in Biarritz in 1946, during which time he may have been reactivated as a Naval Reserves officer. Hill died January 9, 1961.

Thanks to an interview that David Kahn had with Hill’s widow reported in [C14], we know that Hill loved to read detective stories, to tell jokes and, while not shy, enjoyed small gatherings as opposed to large parties.

Who is Hamming? His life is much better known and details can be readily found in several sources.

Richard Wesley Hamming was born on February 11, 1915, in Chicago. Hamming earned a B.S. in mathematics from the University of Chicago in 1937, a masters from the University of Nebraska in 1939, and a PhD in mathematics (with a thesis on differential equations)
from the University of Illinois at Urbana-Champaign in 1942. In April 1945 he joined the Manhattan Project at the Los Alamos Laboratory, then left to join the Bell Telephone Laboratories in 1946. In 1976, he retired from Bell Labs and moved to the Naval Postgraduate School in Monterey, California, where he worked as an Adjunct Professor
and senior lecturer in computer science until his death on January 7, 1998.

Hill’s cipher

The Hill cipher is a polygraphic cipher invented by Lester S. Hill in 1920’s. Hill and his colleague Wisner from Hunter College filed a patent for a telegraphic device encryption and error-detection device which was roughly based on ideas arising from the Hill cipher. It appears nothing concrete became of their efforts to market the device to the military, banks or the telegraph company (see Christensen, Joyner and Torres [CJT12] for more details). Incidently, Standage’s excellent book [St98] tells the amusing story of the telegraph company’s failed attempt to add a relatively simplistic error-detection to telegraph codes during that time period.

Some books state that the Hill cipher never saw any practical use in the real world. However, research by historians F. L. Bauer and David Kahn uncovered the fact that the Hill cipher saw some use during World War II encrypting three-letter groups of radio call signs [C14]. Perhaps insignificant, at least compared to the practical value of Hamming codes, none-the-less, it was a real-world use.

The following discussion assumes an elementary knowledge of matrices. First, each letter is first encoded as a number, namely

$A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25$ . The subset of the integers $\{0, 1, \dots , 25\}$ will be denoted by Z/26Z. This is closed under addition and multiplication (mod 26), and sums and products (mod 26) satisfy the usual associative and distributive properties. For R = Z/26Z, let GL(k,R) denote the set of invertible matrix transformations $T:R^k\to R^k$ (that is, one-to-one and onto linear functions).

The construction

Suppose your message m consists of n capital letters, with no spaces. This may be regarded an n-tuple M with elements in R = Z/26Z. Identify the message M as a sequence of column vectors ${\bf p}\in R^k$ . A key in the Hill cipher is a $k\times k$ matrix K, all of whose entries are in R, such that the matrix K is invertible. It is important to keep K and k secret.

The encryption is performed by computing ${\bf c} = K{\bf p},$ and rewriting the resulting vector as a string over the same alphabet. Decryption is performed similarly by computing ${\bf p} = K^{-1} {\bf c}.$ .

Example 1: Suppose m is the message “BWGN”. Transcoding into numbers, the plaintext is rewritten $p_0=1, p_1=22, p_2=6, p_3=13$ . Suppose the key is
$K=\left(\begin{array}{rr} 1 & 3 \\ 5 & 12 \end{array}\right).$
Using Hill’s encryption above gives $c_0=7,c_1=3,c_2=24,c_3=3$ . (Verification is left to the reader as an exercise.)

Security concerns: For example, this cipher is linear and can be broken by a known plaintext attack.

Hamming codes

Richard Hamming is a pioneer of coding theory, introducing the binary
Hamming codes in the late 1940’s. In the days when an computer error could crash the computer and force the programmer to retype his punch cards, Hamming, out of frustration, designed a system whereby the computer could automatically correct certain errors. The family of codes named after him can easily correct one error.

Hill’s unpublished paper

While he was a student at Yale, Hill published three papers in Telegraph and Telephone Age [H1], [H2], [H3]. In these papers Hill described a mathematical method for checking the accuracy of telegraph communications. There is some overlap with these papers and [H5], so it seems likely to me that Hill’s unpublished paper [H5] dates from this time (that is, during his later years at Yale or early years at Hunter).

In [H5], Hill describes a family of linear block codes over a finite field and an algorithm for error-detection (which can be easily extended to error-correction). In it, he states the construction of what I’ll call the “Hill codes,” (defined below), gives numerous computational examples, and concludes by recording Hill’s Problem (stated above as Question 1). It is quite possibly Hill’s best work.

Here is how Hill describes his set-up.

Our problem is to provide convenient and practical accuracy checks upon
a sequence of n elements $f_1, f_2, \dots, f_r$ in a finite algebraic
field F. We send, in place of the simple sequence $f_1, f_2, \dots, f_r$ , the amplified sequence $f_1, f_2, \dots, f_r, c_1, c_2, \dots, c_k$
consisting of the “operand” sequence and the “checking” sequence.

– Lester Hill, [H5]

Then Hill continues as follows. Let F=GF(p) denote the finite field having p elements, where $p>2$ is a prime number. The checking sequence contains k elements of F as follows:
$c_j = \sum_{i=1}^r a_{i}^jf_i,$
for $j = 1, 2, \dots, k$ . The checks are to be determined by means of a
fixed matrix
$A = \left( \begin{array}{cccc} a_{1} & a_{2} & \dots & a_{r} \\ a_{1}^2 & a_{2}^2 & \dots & a_{r}^2 \\ \vdots & & & \vdots \\ a_{1}^k & a_{2}^k & \dots & a_{r}^k \\ \end{array} \right)$
of elements of F, the matrix having been constructed according to the criteria in Hill’s Problem above. In other words, if the operand sequence (i.e., the message) is the vector ${\bf f} = (f_1, f_2, \dots, f_r)$ , then the amplified sequence (or codeword in the Hill code) to be transmitted is

${\bf c} = {\bf f}G,$
where $G = \left( I_r, A \right)$ and where $I_r$ denotes the
$r\times r$ identity matrix. The Hill code is the row space of G.

We conclude with one more open question.

Question 3:
What is the minimum distance of a Hill code?

The minimum distance of any Hamming code is 3.

Do all sufficiently long Hill codes have minimum distance greater than 3?

Summary

Most books today (for example, the excellent MAA publication written by Thompson [T83]) date the origins of the theory of error-correcting codes to the late 1940s, due to Richard Hamming. However, this paper argues that the actual birth is in the 1920s due to Lester Hill. Topics discussed include why Hill’s discoveries weren’t publicly known until relatively recently, what Hill actually did that trumps Hamming, and some open (mathematical) questions connected with Hill’s work.

For more details, see these previous blog posts.

Acknowledgements: Many thanks to Chris Christensen and Alexander Barg for
helpful and encouraging conversations. I’d like to explicitly credit Chris Christensen, as well as historian David Kahn, for the original discoveries of the source material.

Bibliography

[C14] C. Christensen, Lester Hill revisited, Cryptologia 38(2014)293-332.

[CJT12] ——, D. Joyner and J. Torres, Lester Hill’s error-detecting codes, Cryptologia 36(2012)88-103.

[H1] L. Hill, A novel checking method for telegraphic sequences, Telegraph and
Telephone Age (October 1, 1926), 456 – 460.

[H2] ——, The role of prime numbers in the checking of telegraphic communications, I, Telegraph and Telephone Age (April 1, 1927), 151 – 154.

[H3] ——, The role of prime numbers in the checking of telegraphic
communications, II, Telegraph and Telephone Age (July, 16, 1927), 323 – 324.

[H4] ——, Lester S. Hill to Lloyd B. Wilson, November 21, 1925. Letter.

[H5] ——, Checking the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields, undated and unpublished notes, 40 pages.
(hill-error-checking-notes-unpublished)

[MS77] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[Sh] A. Shokrollahi, On cyclic MDS codes, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, (ed. D. Joyner), Springer-Verlag, 2000.

[St98] T. Standage, The Victorian Internet, Walker & Company, 1998.

[T83] T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983.

More odd examples of p-ary bent functions

Posted on 2014/05/21 by wdjoyner

In an earlier post I discussed bent functions $f:GF(3)^2\to GF(3)$ . In this post, I’d like to give some more examples, based on a recent paper with Caroline Melles, Charles Celerier, David Phillips, and Steven Walsh, based on computations using Sage/pythpn programs I wrote with Charles Celerier.

We start with any function $f:GF(p)^n\to GF(p)$ . The Cayley graph of $f$ is defined to be the edge-weighted digraph

$\Gamma_f = (GF(p)^n, E_f ),$
whose vertex set is $V=V(\Gamma_f)=GF(p)^n$ and the set of edges is defined by

$E_f =\{(u,v) \in GF(p)^n\ |\ f(u-v)\not= 0\},$
where the edge $(u,v)\in E_f$ has weight $f(u-v)$ . However, if $f$ is even then we can (and do) regard $\Gamma_f$ as an edge-weighted (undirected) graph.

We assume, unless stated otherwise, that $f$ is even.

For each $u\in V$ , define

$N(u)=N_{\Gamma_f}(u)$ to be the set of all neighbors of $u$ in $\Gamma_f$ ,
$N(u,a)=N_{\Gamma_f}(u,a)$ to be the set of all neighbors $v$ of $u$ in $\Gamma_f$ for which the edge $(u,v)\in E_f$ has weight $a$ (for each $a\in GF(p)^\times = GF(p)-\{0\}$ ),
$N(u,0)=N_{\Gamma_f}(u,0)$ to be the set of all non-neighbors $v$ of $u$ in $\Gamma_f$ (i.e., we have $(u,v)\notin E_f$ ),
the support of $f$ is
${\rm supp}(f)=\{v\in V\ |\ f(v)\not=0\}$

Let $\Gamma$ be a connected edge-weighted graph which is regular as a simple (unweighted) graph. The graph $\Gamma$ is called strongly regular with parameters $v$ , $k=(k_a)_{a\in W}$ , $\lambda=(\lambda_a)_{a\in W^3}$ , $\mu=(\mu_a)_{a\in W^2}$ , denoted $SRG_{W}(v,k,\lambda,\mu)$ , if it consists of $v$ vertices such that, for each $a=(a_1,a_2)\in W^2$

$|N(u_1,a_1) \cap N(u_2,a_2)| = \left\{ \begin{array}{ll} k_{a}, & u_1=u_2,\\ \lambda_{a_1,a_2,a_3}, & u_1\in N(u_2,a_3),\ u_1\not= u_2,\\ \mu_{a}, &u_1\notin N(u_2),\ u_1\not= u_2,\\ \end{array} \right.$
where $k$ , $\lambda$ , $\mu$ are as above. Here, $W= GF(p)$ is the set of weights, including $0$ (recall an “edge” has weight $0$ if the vertices are not neighbors).

This example is intended to illustrate the bent function $b_8$ listed in the table below
$\begin{array}{c|ccccccccc} GF(3)^2 & (0, 0) & (1, 0) & (2, 0) & (0, 1) & (1, 1) & (2, 1) & (0, 2) & (1, 2) & (2, 2) \\ \hline b_8 & 0 & 2 & 2 & 0 & 0 & 1 & 0 & 1 & 0 \\ \end{array}$

Consider the finite field
$GF(9) = GF(3)[x]/(x^2+1) = \{0,1,2,x,x+1,x+2,2x,2x+1,2x+2\}.$
The set of non-zero quadratic residues is given by
$D = \{1,2,x,2x\}.$
Let $\Gamma$ be the graph whose vertices are $GF(9)$ and whose edges $e=(a,b)$ are those pairs for which $a-b\in D$ .

The graph looks like the Cayley graph for $b_8$ in the Figure below

Bent function b_8 on GF(3)^2

except

$8\to 0, 0\to 2x+2, 1\to 2x+1, 2\to 2x,$
$3\to x+2, 4\to x+1, 5\to x, 6\to 2, 7\to 1, 8\to 0.$
This is a strongly regular graph with parameters $(9,4,1,2)$ .

$\begin{array}{c|ccccccccc} v & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline N(v,0) & 3,4,6,8 & 4,5,6,7 & 3,5,7,8 & 0,2,6,7 & 0,1,7,8 & 1,2,6,8 & 0,1,3,5 & 1,2,3,4 & 0,2,4,5 \\ N(v,1) & 5,7 & 3,8 & 4,6 & 1,8 & 2,6 & 0,7 & 2,4 & 0,5 & 1,3 \\ N(v,2) & 1,2 & 0,2 & 0,1 & 4,5 & 3,5 & 3,4 & 7,8 & 6,8 & 6,7 \\ \end{array}$

The axioms of an edge-weighted strongly regular graph can be directly verified using this table.

Let $S$ be a finite set and let $R_0, R_1, \dots, R_s$ denote binary relations on $S$ (subsets of $S\times S$ ). The dual of a relation $R$ is the set

$R^* = \{(x,y)\in S\times S\ |\ (y,x)\in R\}.$
Assume $R_0=\Delta_S= \{ (x,x)\in S\times S\ |\ x\in S\}$ . We say $(S,R_0,R_1,\dots,R_s)$ is an $s$ -class association scheme on $S$ if the following properties hold.

We have a disjoint union
$S\times S = R_0\cup R_1\cup \dots \cup R_s,$
with $R_i\cap R_j=\emptyset$ for all $i\not= j$.
For each $i$ there is a $j$ such that $R_i^*=R_j$ (and if $R_i^*=R_i$ for all $i$ then we say the association scheme is symmetric).
For all $i,j$ and all $(x,y)\in S\times S$ , define
$p_{ij}(x,y) = |\{z\in S\ |\ (x,z)\in R_i, (z,y)\in R_j\}|.$
For each $k$ , and for all $x,y\in R_k$ , the integer $p_{ij}(x,y)$ is a constant, denoted $p_{ij}^k$ .

These constants $p_{ij}^k$ are called the intersection numbers of the association scheme.

For this example of $b_8$ , we compute the adjacency matrix associated to the members $R_1$ and $R_2$ of the association scheme $(G,R_0,R_1,R_2,R_3)$ , where $G = GF(3)^2$ ,

$R_i = \{(g,h)\in G\times G\ |\ gh^{-1} \in D_i\},\ \ \ \ \ i=1,2,$
and $D_i = f^{-1}(i)$ .

Consider the following Sage computation:

sage: attach "/home/wdj/sagefiles/hadamard_transform2b.sage"
sage: FF = GF(3)
sage: V = FF^2
sage: Vlist = V.list()
sage: flist = [0,2,2,0,0,1,0,1,0]
sage: f = lambda x: GF(3)(flist[Vlist.index(x)])
sage: F = matrix(ZZ, [[f(x-y) for x in V] for y in V])
sage: F  ## weighted adjacency matrix
[0 2 2 0 0 1 0 1 0]
[2 0 2 1 0 0 0 0 1]
[2 2 0 0 1 0 1 0 0]
[0 1 0 0 2 2 0 0 1]
[0 0 1 2 0 2 1 0 0]
[1 0 0 2 2 0 0 1 0]
[0 0 1 0 1 0 0 2 2]
[1 0 0 0 0 1 2 0 2]
[0 1 0 1 0 0 2 2 0]
sage: eval1 = lambda x: int((x==1))
sage: eval2 = lambda x: int((x==2))
sage: F1 = matrix(ZZ, [[eval1(f(x-y)) for x in V] for y in V])
sage: F1
[0 0 0 0 0 1 0 1 0]
[0 0 0 1 0 0 0 0 1]
[0 0 0 0 1 0 1 0 0]
[0 1 0 0 0 0 0 0 1]
[0 0 1 0 0 0 1 0 0]
[1 0 0 0 0 0 0 1 0]
[0 0 1 0 1 0 0 0 0]
[1 0 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 0 0]
sage: F2 = matrix(ZZ, [[eval2(f(x-y)) for x in V] for y in V])
sage: F2
[0 1 1 0 0 0 0 0 0]
[1 0 1 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0 0]
[0 0 0 0 1 1 0 0 0]
[0 0 0 1 0 1 0 0 0]
[0 0 0 1 1 0 0 0 0]
[0 0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 1 0 1]
[0 0 0 0 0 0 1 1 0]
sage: F1*F2-F2*F1 == 0
True
sage: delta = lambda x: int((x[0]==x[1]))
sage: F3 = matrix(ZZ, [[(eval0(f(x-y))+delta([x,y]))%2 for x in V] for y in V])
sage: F3
[0 0 0 1 1 0 1 0 1]
[0 0 0 0 1 1 1 1 0]
[0 0 0 1 0 1 0 1 1]
[1 0 1 0 0 0 1 1 0]
[1 1 0 0 0 0 0 1 1]
[0 1 1 0 0 0 1 0 1]
[1 1 0 1 0 1 0 0 0]
[0 1 1 1 1 0 0 0 0]
[1 0 1 0 1 1 0 0 0]
sage: F3*F2-F2*F3==0
True
sage: F3*F1-F1*F3==0
True
sage: F0 = matrix(ZZ, [[delta([x,y]) for x in V] for y in V])
sage: F0
[1 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 1]
sage: F1*F3 == 2*F2 + F3
True

The Sage computation above tells us that the adjacency matrix of $R_1$ is

$A_1 = \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right),$
the adjacency matrix of $R_2$ is

$A_2 = \left(\begin{array}{rrrrrrrrr} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}\right),$
and the adjacency matrix of $R_3$ is

$A_3 = \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}\right)$
Of course, the adjacency matrix of $R_0$ is the identity matrix. In the above computation, Sage has also verified that they commute and satisfy

$A_1A_3 = 2A_2+A_3$
in the adjacency ring of the association scheme.

Conjecture:
Let $f:GF(p)^n\to GF(p)$ be a bent function, with $p>2$ . If the level curves of $f$ give rise to a weighted partial difference set then $f$ is weakly regular, and the corresponding (unweighted) partial difference set is of (positive or negative) Latin square type.

For more details, see the paper [CJMPW] with Caroline Melles, Charles Celerier, David Phillips, and Steven Walsh.

Another example of a Prohibition era cipher message

Posted on 2013/08/05 by wdjoyner

The following message, with Elizebeth Friedman‘s decryption, is a message from “Consolidated Exporters” (a Vancouver Canada company illegally importing liquor into the US) to one of its fleet of about 50 “black ships”, the SS Noble. (They are called “black ships” because they “rum run” without lights at night to avoid detection.)

Many thanks to the George C. Marshall Foundation, Lexington, Virginia, for providing this reproduction!

A 1932 memorandum on rum-runner’s cryptosystems

Posted on 2013/07/12 by wdjoyner

During the prohibition era, organized crime made phenomenal amounts of money through illegal smuggling. Eventually, their messages were enciphered. By the late 1920s and early 1930s, these cryptosystems became rather sophisticated. Here is a memorandum form Elizebeth Friedman to CMDR Gorman in January or 1932 which gives an indication of this sophistication.

Many thanks to the George C. Marshall Foundation, Lexington, Virginia, for providing this reproduction!

A 1926 message from “I Am Alone”

Posted on 2013/07/04 by wdjoyner

The I Am Alone, flying a Canadian flag, was a rumrunner sunk by Coast Guard patrol boats in the Gulf of Mexico in March, 1929. The USCG knew that the ship was not a Canadian owned-and-controlled vessel but the proof went down to the bottom of the ocean when it was sunk. The Canadian Government sued the United States for $365,000 and the ensuing legal battle brought world-wide attention. Elizebeth Friedman decoded the messages transmitted by the I Am Alone, and those messages proved that the boat was, in fact, not a Canadian owned-and-controlled vessel. The case actually went to a Commission, whose final report was issued in 1935. They found, thanks in part to Elizebeth Friedman, that the owners and controllers of the vessel were not Canadian and used the boat primarily for illegal purposes.

The image below is a scan of an intercepted message, dated 1926-02-15, from the I Am Alone.

The writing is that of EF and you can make out her (mostly) deciphered message.

For more information, see, for example,
“All Necessary Force”: The Coast Guard And The Sinking of the Rum Runner “I’m Alone” by Joseph Anthony Ricci, 2011, or
“Listening to the rumrunners” by David Mowry, 2001.

The above image is courtesy of the Elizebeth S. Friedman Collection at the George C. Marshall Foundation, Lexington, Virginia. (If you make use of the image, please acknowledge the Marshall Foundation.)

Lester Hill’s “The checking of the accuracy …”, part 10

Posted on 2013/06/02 by wdjoyner

Construction of finite fields for use in checking

Let $F_\Gamma$ denote a finite algebraic field with $\Gamma$ elements. It is well-known that, for a given $\Gamma$ , all fields $F_\Gamma$ are “simply isomorphic”, and therewith, for our purposes, identical. We shall consequently refer, without restraint, to ”the field $F_\Gamma$ .”

If $p$ is a prime positive integer greater than $1$ , $F_p$ is called, according to the terminology of Section 8, Example 2, a ”primary” field. Explicit addition tables, as was noted in section 8, are hardly required in deal ing with primary fields. The most useful of these fields, in telegraphic checking, are probably $F_{23}$ , $F_{29}$ , $F_{31}$ , and $F_{101}$ . The field $F_{101}$ will be considered in detail in what follows.

The number of elements in a non-primary finite algebraic field
is a power of a prime. If we have

$q=p^k$
where $p$ and $k$ are positive integers greater than $1$ , and $p$ is prime, the non-primary field $F_q$ may be constructed very easily by algebraic extension of the field $F_p$ . Explicit addition table is needed when working with a non-primary field. Otherwise, checking operations are exactly the same as in primary fields.

Example: The field $F_3$ with the elements (marks) $0,1,2$ , has the tables

$\begin{array}{r|*{3}{r}} \multicolumn{1}{c|} +&0&1&2\\\hline {}0&0&1&2\\ {}1&1&2&0\\ {}2&2&0&1\\ \end{array}$
$\begin{array}{r|*{3}{r}} \multicolumn{1}{c|} \cdot &0&1&2\\\hline {}0&0&0&0\\ {}1&0&1&2\\ {}2&0&2&1\\ \end{array}$

By adjoining a root of the equation $x^2=2$ , an equation which is irreducible in $F_3$ , we easily obtain the field $F_9$ with marks

$\alpha j+\beta$
where $\alpha$ and $\beta$ denote elements of $F_3$ . The marks of $F_9$ are thus

$0,1,2,j,j+1,j+2,2j,2j+1,2j+2.$
These marks (elements) are combined, in the rational field operations of $F_9$ , according to the reduction formula $j^2=2$ . If we label the marks of $F_9$ as follows

$\begin{array}{ccccccccc} 0 & 1 & 2 & j & j+1& j+2& 2j& 2j+1& 2j+2\\ 0 & 1 & a & b & c & d & e & f & g\\ \end{array}$
the addition and multiplication tables of the field are given as in
Section 8, Example 1.

In a like manner, $F_{27}$ can be obtained from $F_3$ by adjunction of a root of the equation $x^3=x+1$ , which is irreducible in $F_3$ and $F_9$ . The marks (elements) of $F_{27}$ are

$\alpha j^2+\beta j+\gamma,$
where $\alpha,\beta,\gamma$ are elements of $F_3$ . They are combined, in the rational operations of $F_{27}$ according to the reduction formula $j^3=j+1$ .

Example: The field $F_2$ with the elements (marks) $0,1$ , has the tables

$\begin{array}{r|*{2}{r}} \multicolumn{1}{c|} + &0&1\\ \hline {}0&0&1\\ {}1&1&0\\ \end{array}$
$\begin{array}{r|*{2}{r}} \multicolumn{1}{c|} \cdot &0&1\\ \hline {}0&0&0\\ {}1&0&1\\ \end{array}$

By adjunction of a root of the equation $x^5=x^2+1$ , which is irreducible in the fields $F_2$ , $F_4$ , $F_8$ and $F_{16}$ , we easily obtain the field $F_{32}$ . The marks of $F_{32}$ are

$\alpha j^4+\beta j^3+\gamma j^2+\delta j+\epsilon,$
where $\alpha,\beta,\gamma, \delta,\epsilon$ are elements of $F_2$ ; and these $32$ marks are combined, in the rational operations of $F_{32}$ , according to the reduction formula $j^5=j^2+1$ .

Example: The field $F_5$ with the elements (marks) $0,1,2,3,4$ , has the tables

$\begin{array}{r|*{5}{r}} \multicolumn{1}{c|} +&0&1&2&3&4\\\hline {}0&0&1&2&3&4\\ {}1&1&2&3&4&0\\ {}2&2&3&4&0&1\\ {}3&3&4&0&1&2\\ {}4&4&0&1&2&3\\ \end{array}$
$\begin{array}{r|*{5}{r}} \multicolumn{1}{c|} \cdot &0&1&2&3&4\\\hline {}0&0&0&0&0&0\\ {}1&0&1&2&3&4\\ {}2&0&2&4&1&3\\ {}3&0&3&1&4&2\\ {}4&0&4&3&2&1\\ \end{array}$

By adjoining a root of the equation $x^2=2$ , which is irreducible in $F_{5}$ , we readily obtain the field $F_{25}$ . The marks of $F_{25}$ are

$\alpha j+\beta ,$
where $\alpha,\beta$ are elements of $F_5$ ; and these $25$ marks are combined, in the rational operations of $F_{25}$ , according to the reduction formula $j^2=2$ .

Of the non-primary fields, $F_{25}$ , $F_{27}$ , $F_{32}$ are probably those which are most amenable to practical application in telegraphic checking.

Yet Another Mathblog

Category Archives: cryptography