3
$\begingroup$

I have been been studying some basic ciphers, and learnt about the affine cipher where the encryption function is given by $ax+b \pmod{26}$ for an alphabet with 26 characters. This is a very insecure cipher, so if it was used it must have been a long time ago. I am aware that the Caesar cipher and the Atbash cipher are special cases of the affine cipher (with $a=1$ and $a=b=25$, respectively). However, when these two ciphers were used, the encryption was not performed mathematically using the affine function, but with a shifted alphabet.

So, my question is: Has the affine cipher ever been used in practice (with $a\ne1$ and $a\ne b\ne25$), where the encryption was performed mathematically using the affine function?

$\endgroup$
  • $\begingroup$ Nice question, I wasn't able to find the answer just googling until I ended here. $\endgroup$ – Leopoldo Sanczyk Oct 27 at 3:00
2
$\begingroup$

While it's hard to prove that something has not been done, I'm fairly confident in asserting that affine ciphers (with $a \not\equiv \pm1$) are purely educational toys and have never been used for serious encryption (i.e. something not deliberately designed to be broken), except perhaps arguably as parts of a more complex cipher.

For one thing, affine ciphers of this type aren't really particularly good for anything in practice. Their keyspace is not that much larger than that of simple Caesar shift ciphers, and in any case they are just as vulnerable to attacks via frequency analysis as any other simple monoalphabetic substitution cipher.

As hand ciphers, affine ciphers are too complex to be practically applied without the aid of an explicit lookup table. And while one could indeed construct an encryption table using an affine map, doing so would not seem to offer any particular advantage over e.g. the various keyword-based methods actually used in practice.

Meanwhile, for a machine cipher, affine maps offer no obvious advantage over the combination of shifts and (fixed) non-linear permutations, as used e.g. famously by the Enigma machines, and they have the obvious disadvantage that modular multiplication is far harder to implement mechanically than simple shifting. That's not to say that it could not be done, as exemplified e.g. by Weisner & Hill's patented mechanical implementation of the Hill cipher. That said, it's worth keeping in mind that, although proposed as (a component of) a practical real-world cryptosystem, the Hill cipher was never really adopted as such, is large part due to its cumbersomeness. Presumably, any attempts to employ affine ciphers via mechanical means would have encountered similar difficulties.


I tried to see if I could determine when and where the concept of affine ciphers was first introduced, but I'm not sure if I've really found it. In any case, the earliest mention of the term "affine cipher" that I could find in the literature is from 1983, in a book chapter titled "Elements of Cryptology" by M. Davio and J.-M. Goethals, included in the book Secure Digital Communications by G. Longo (ed).

However, while the chapter indeed briefly discusses classical monoalphabetic substitution ciphers (of which affine ciphers as you define them are a subset) on page 3, the phrase "affine cipher" only occurs on page 14, in the context of block ciphers, and only as an example of an insecure class of ciphers to be avoided:

2.4 Combining building blocks.

Individually, each of the above building blocks [i.e. bit permutations, translations, linear transformations, addition mod $2^n$ and substitutions (S-boxes)] is a poor cipher. However, by combining them (as suggested by Shannon) in a product cipher, we may obtain much stronger ciphers.

Some of the combinations, however, are weak. For example, by combining translations and linear transformations we obtain an affine cipher: $$m \to Am + b$$ which can be broken in much the same way as a linear cipher. Thus affine substitutions should be avoided.

(emphasis original; [editorial note] mine)

In particular, in the context where the quote above appears, $m$ in fact denotes a block of $n$ bits, $A$ is an $n \times n$ matrix over GF(2), and the operator $+$ (which really should have been written as $\oplus$, to stay consistent with the usage on the previous page) clearly denotes bitwise XOR. Thus, while the "affine cipher" described in this text is indeed clearly an affine transformation, the elements being transformed in this case are $n$-bit vectors over GF(2) rather than integers modulo 26 (or any other modulus).


Meanwhile, the earlier mention that I could find of the "educational" form of the affine cipher you describe above is from Douglas R. Stinson's book Cryptography: Theory and Practice, first published in 1995:

1.1.3 The Affine Cipher

The Shift Cipher is a special case of the Substitution Cipher which includes only 26 of the 26! possible permutations of 26 elements. Another special case of the Substitution Cipher is the Affine Cipher, which we describe now. In the Affine Cipher, we restrict the encryption functions to functions of the form $$e(x) = ax + b \bmod 26,$$ $a, b \in \mathbb Z_{26}$. These functions are called affine functions, hence the name Affine Cipher. (Observe that when $a = 1$, we have a Shift Cipher.)

There's no mention in the rest of Stinson's book of any historical usage of affine ciphers, and indeed the text seems to present them merely as a particular mathematically interesting class of simple ciphers. If a historical source for affine ciphers existed, one would expect it to be mentioned in section 1.3 ("Notes"), which e.g. cites Lester S. Hill's original 1929 paper on his eponymous cipher, as well as David Kahn's The Codebreakers for general history of cryptography (with a special mention of the historical misattribution of what's nowadays known as the Vigenère cipher to Blaise de Vigenère rather than to its actual author, Giovan Battista Bellaso). But no such reference is given there, or anywhere else as far as I can tell.

It thus seems possible that Stinson may have invented the affine cipher in its modern form, perhaps inspired by earlier uses of the term in contexts like Davio's & Goethal's mention of affine block ciphers. However, without additional sources, I cannot be sure of this. Perhaps someone ought to contact him and ask.

$\endgroup$
  • 1
    $\begingroup$ The same shape works as a secure one-time authenticator by virtue of being a universal hash, which is how it is more often used. (Not to mention, of course, LCGs!) $\endgroup$ – Squeamish Ossifrage Mar 22 at 1:08
  • $\begingroup$ @Squeamish Ossifrage Could you please describe what the secure one-time authenticator looks like? How can I change the Affine Cipher into a secure authenticator? $\endgroup$ – Patriot Jul 7 at 10:49
  • 1
    $\begingroup$ @Patriot Lots of material out there on universal hash families for (one-time) authenticators/authentication. (Those are all searchable keywords!) Here's a quick description with some references: crypto.stackexchange.com/a/71090 $\endgroup$ – Squeamish Ossifrage Aug 5 at 1:15
  • $\begingroup$ Thanks for the research you added to the answer. The year this term was introduced is still a open question. At least you limited it. $\endgroup$ – Leopoldo Sanczyk Oct 27 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.