FRIEDERICH JOHANN BUCK: ARITHMETIC PUZZLES IN CRYPTOGRAPHY

Cryptologia, Oct 2004 by Gathen, Joachim von zur

ABSTRACT: Much of modern cryptography relies on arithmetic-from RSA and elliptic curves to the AES. A little-known book by Comiers, published in 1690, seems to be the first recorded systematic use of arithmetic in cryptography. David Kahn's authoritative The Codebreakers mentions another work whose title links algebra and cryptography"by a German, F. J. Buck, as far back as 1772". It turns out to deal with mathematical puzzles. Buck uses such brain teasers to encode numbers, and thus letters and whole messages. For decoding, one has to be clever enough to solve those puzzles. There is no secret key involved. Other well-known examples of such "keyless" cryptography are mentioned.

KEYWORDS: algebraic cryptography, arithmetic puzzles, keyless cryptography, Prussia, 18th century

1 INTRODUCTION

This paper discusses a 15-page work from 1772 by Buck whose title brings together cryptography and algebra. Kahn [12, p. 405] writes about Lester S. Hill, who introduced linear algebra into cryptography: "Hill successfully used algebra as a process for cryptography. Probably many mathematicians had toyed with this idea; two proposals had even reached print-one by a German, F. J. Buck, as far back as 1772, the other by the young mathematician Jack Levine in a 1926 issue of a detective magazine." Buck's work was available to Kahn only as a citation in a bibliography by Maurits de Vries. The present analysis will show that it does not represent cryptography in the usual sense: there is no secret key, and the legitimate recipient has no advantage over an interceptor. Rather it is a game of hiding messages inside algebraical puzzles.

In the usual cryptographic scenario, someone sends an encrypted message to a correspondent who can decrypt it easily with the help of a secret key, and an interceptor cannot (easily) determine the plaintext from just the ciphertext. In Buck's setting, the secret key is replaced by the general ability to solve certain types of mathematical puzzles. Thus, if used for secret communication, it is secure against any interceptor who lacks this ability (and the funds to hire someone with the required ability). This might be called "keyless cryptography". In Section 5, we put some other well-known cryptographic systems into this framework.

The core of Buck's text consists of two sets of five puzzles, each set encrypting some plaintext. The first set is literally taken from Schwarzer's 1762 Arithmetic, with acknowledgement. The second set is made up by Buck himself. The solution to each puzzle yields some (one to six) numbers. Each such number in turn provides some (up to six) letters in specified positions in specified words of the plaintext. This happens via lengthy but straightforward instructions and the usual conversion of the numbers from 1 to 24 into the 24 letters of the alphabet of his times.

For use as a system of secret communication, the sender has to devise a set of numerical puzzles plus instructions that specify each letter of his message. This is easy to do for a "doctor of world wisdom" like Buck, at least in principle. The puzzles and instructions are sent as the ciphertext. The recipient must solve the brain teasers and follow the instructions to recover the plaintext, letter by letter. The design of such puzzles is simple in principle, but not in practice. Schwarzer's examples, faithfully reproduced by Buck, contain several misprints which make them unsolvable if taken literally. The challenge is to find reasonable solutions to an unknown problem which differs from the given one by as little as possible.

There is no secret key, and the intended recipient has no advantage over an undesired interceptor. This could work in a circle of doctors of world wisdom, where any interceptor may be assumed to lack the necessary amount of world wisdom. It could not be considered as a general system of secure communication, not even in Buck's times.

The present paper proceeds as follows. Section 2 lays out Buck's story as told by him. In Section 3, a sample puzzle is solved. It turns out that both the puzzles and the instructions contain numerous errors, and their solution indeed requires a modicum of world wisdom. Section 4 describes Buck's life and his university, with his famous colleague Immanuel Kant, and the works that he quoted, by Schwarzer and by Lindner. Section 5 briefly mentions other examples of such keyless cryptography throughout history.

The full text of Buck's book is available at

http : //www.math.upb.de/~aggathen/Publications/

with kind permission of the Martin-Luther-Universität at Halle-Wittenberg.

2 BUCK'S BOOK

The title page of the work by Buck is shown in Figure 1 and translates as:

Mathematical proof that algebra can comfortably be used to disclose some ways of secret writing. By Friederich Johann Buck, doctor of philosophy ("Weltweißheit" = "world wisdom") and jurisprudence, as well as professor of mathematics at the University of Königsberg. Königsberg, 1772. Published by the widow of J. D. Zeisen and the heirs of J. H. Härtung.