Patterson's Cipher for Jefferson -- Challenge Solved After 200 Years
In 1803, President Thomas Jefferson sent Robert R. Livingston, minister in Paris, a cipher based on new principles which he found "the easiest to use" and "the most indecypherable". It was originally designed by Robert Patterson, a mathematician of an age with Jefferson and Jefferson's colleague in the American Philosophical Society.
In modern terminology, a cipher is a cryptographic scheme that operates on each letter of plaintext and is distinguished from a code that translates plaintext to code by words or syllables, though, in Jefferson's time, the word "cipher" (or "cypher" as was the preferred spelling at the time) encompassed both concepts. When Jefferson became the third president of the United States, a code with some 1700 elements had become the standard form of secret communication means rather than a cipher (see here). A simple substitution cipher was too vulnerable to cryptanalysis and more secure polyalphabetic substitution cipher advocated by James Lovell during the Revolutionary War created much confusion for his correspondents. Jefferson himself had similar experience with William Short (PTJ Code No.4/WE062; see here).
Patterson's cipher did not use such substitution. It was a transposition cipher, in which the plaintext letters are not changed to other letters but put into a mixed order.
In the following, Patterson's cipher is first explained with reference to his original letter, which includes the challenge Patterson thought undecipherable without knowing the key. Then, improvements or modifications proposed thereafter by Jefferson and Patterson are described. At the end of the article, recent solution of Patterson's challenge is summarized.
Patterson told Jefferson of his idea in a letter of 19 December 1802.
He began with axiomatic observations.
The art of secret writing, or, as it is usually termed,
writing in cypher, has occasionally engaged the attention both of the
statesmen & philosophers for many ages; and yet I believe it will be
acknowledged, by all who are acquainted with the present state of
this art, that it is still far short of perfection. A perfect cypher,
as it appears to me, should possess the following properties --
1. It should be equally adapted to all languages.
2. It should be easily learned & retained in memory.
3. It should be written and read with facility & dispatch.
4. (which is the most essential property) it should be absolutely
inscrutable to all unacquainted with the particular key or
secret for decyphering.
I shall not enter into a tedious detail of the various systems of
secret writing that have been or are still in use, or point out their several defects; but shall immediately
proceed to lay before you a system which, I flatter myself, will be
found to possess the above requisites, in as great a degree as
can reasonably be desired. For 1st. it is equally applicable to all
alphabetical languages. 2d. it may be learned by any person of
moderate capacity in ten minutes; so that he shall be as expert in
the use of it, as one who may have practised it for many years.
3d. it may be written and read with nearly the same facility
and dispatch as common writing. & 4th it will be absolutely
impossible, even for one perfectly acquainted with the general
system, ever to decypher the writing of another without his key.
Patterson to Jefferson, 19 December 1802
Before detailing the scheme, Patterson stressed that it was not a substitution cipher.
In this system, there is no substitution of one letter or character
for another; but every word is to be written at large, in its proper alphabetical
characters, as in common writing: only that there need be
no use of capitals, pointing, nor spaces between words; since any
piece of writing may be easily read without these distractions.
Patterson explained his scheme as follows.
The method is simply this -- Let the writer rule on his paper as
many pencil lines as will be sufficient to contain the whole writing.
Then, instead of placing the letters one after the other, as in common
writing, let them be placed one under the other, in the Chinese manner,
namely, the first letter at the beginning of the first line, the second
letter at the beginning of the second line, and so on, writing column
after column, from left to right, till the whole is written.
This writing is then to be distributed into sections of not more than
nine lines in each section, and these are to be numbered 1. 2. 3. &c 1. 2. 3. &c. (from top to bottom).
At the end of this draft stage, the writer would have written as follows, where the plaintext "Buonaparte has at last given peace to Europe! ..." is written from top to bottom, from left to right. In this example, one section contains 8 lines.
Then, this is transcribed to get the cipher text.
The whole is then to be transcribed, section after section, taking the
lines of each section in any order at pleasure, inserting at the
beginning of each line respectively any number of arbitrary or
insignificant letters, not exceeding nine; & also filling up the
vacant spaces at the end of the lines with like letters.
The transcribed cipher would look as shown below. In each of the three sections in the cipher, lines are transcribed in the order 5-7-3-4-8-1-6-2. (As noted below, this ordering is specified by a key, which is to be termed a "key of lines" by Jefferson.) In each line, 0 to 9 insignificant letters (nulls) are inserted at the beginning. The number of such nulls in each line forms another key, a "key of letters", which is 8-1-3-9-3-4-2-0 in the example used. Nulls are also appended at the end of the lines. The nulls are shaded in the image below.
Now the key or secret for decyphering will consist in knowing --
the number of lines in each section, the order in which these are
transcribed, and the number of insignificant letters at the beginning
of each line -- all which may be briefly, and intelligibly
expressed in figures, thus--
The first rank of figures expressing the number and order of the lines in each
section, and the 2d rank, the number of arbitrary letters at the
beginning of each respective line.
To decipher, one would number the lines according to the key of lines (5-7-3-4-8-1-6-2), delete the nulls at the beginning of the lines, that is, a number of letters specified by the key of letters (8-1-3-9-3-4-2-0), cut the lines apart, and stick them on another piece of paper in the order of the line number (1-2-3-4-5-6-7-8). Then, the plaintext could be read from top to bottom, from left to right.
Patterson added that the frequency of the letters used in the nulls should be the same as in the ciphered text.
It will be proper that the supplementary letters used at the
beginning and end of the lines, should be nearly in the
same relative proportion to each other in which they occur in
the cypher itself, so that no clue may be afforded for distinguishing
between them and the significant letters.
Finally, Patterson provided simple analysis of the strength of his scheme.
On calculating the number of changes, and combinations, of
which the above cypher is susceptible, even supposing that
neither the number of lines in a section, nor the number
of arbitrary letters at the beginning of the lines, should ever
exceed nine, it will be found to amount to upwards of
ninety millions of millions*, nearly equal to the number
of seconds in three millions of years! Hence I presume
the utter impossibility of decyphering will be readily
*equal to the sum of all the changes on any number of quantities not
exceeding nine, multiplied by the ninth power of nine.
Patterson included a specimen enciphered with his scheme, which he said would not be deciphered, without necessary keys, even with "the united ingenuity of the whole human race" till the end of time.
I shall conclude this paper with a specimen of such
writing, which I may safely defy the united ingenuity of
the whole human race to decypher, to the end of time -- but
which, however, by the help of the key, consisting of not
more than eighteen figures, might be read, with the utmost
ease, in less than fifteen minutes--
The image of the cipher Patterson considered so secure will be presented at the end of this article with the keys to the cipher. Below is its transcription, in which some of Patterson's errors have been corrected, while omission of "a", another omission of "w", and one superfluous "w" have been retained.
Jefferson liked Patterson's scheme and he even thought of employing it in the State Department. He proposed one change in the scheme. In Patterson's original idea, a message is first written vertically and then transcribed horizontally to produce cipher text. Jefferson changed this such that a message is first written horizontally, with the letters in each line aligned vertically, and the vertical sequence of letters are transcribed horizontally to produce cipher text.
I have thoroughly considered your cypher, and
find it is much more convenient in practice than my wheel
cypher, that I am proposing it to the Secretary of State for use in his
office. I vary it in a slight circumstance only. I write the lines in the
original draught horizontally & not vertically, placing the letters of the different
lines very exactly under each other. I do this for the convenience of the
principal whose time is to be economised, tho' it increases the labor of a copying
clerk. The copying clerk transcribes the vertical lines horizontally. The clerk
of our correspondent restores them to their horizontal position ready for the reading of the principal.
Jefferson to Patterson, 22 March 1802
Jefferson's Description of the Patterson Cipher
Having "thoroughly considered" Patterson's cipher, Jefferson described his own adaptation of the cipher as follows.
As explained to Patterson, in Jefferson's version, the writer first drafts a message horizontally instead of vertically.
In writing the original paper which is to be cyphered, use no capitals, write the letters disjoined, equidistant,
and those of each line vertically under those of the one next above. This will be greatly
facilitated by using common black-lines, chequered by black-lines drawn vertically, so that you
may place a letter between every two vertical black lines. The letters on your paper will
thus be formed into vertical rows as distinct as the horizontal lines.
The second operation was to transcribe the message to produce cipher text. Note that the term "column" (vertical) corresponds to Patterson's "section" (horizontal), whereas a "column" in Patterson's description referred to a vertical line, which was called a "vertical row" by Jefferson.
To Cypher. Divide the vertical rows of the page into vertical columns of 9 letters or rows in
breadth each, as far as the letters or rows of the line will hold out. The last will probably be
a fractional part of a column. Number the vertical rows of each column from 1 to 9 in
In the example of Jefferson, the writer would now have written as follows:
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
w h e n a n a t i o n l e d t o g r e a t n e s s b y t h e
h a n d o f l i b e r t y a n d p o s s e s s e d o f a l l
t h e g l o r y t h a t h e r o i s m m u n i f i c e n s e
a n d h u m a n i t y c a n b e s t o w d e s c e n d s t o
Jefferson prescribes writing of nulls on the second paper before actually transcribing the message.
Then, on the paper to be sent to your correspondent, begin as many horizontal lines
as there are vertical rows in your original, by writing in the beginning of each of every 9 horizontal
lines as many insignificant letters from 1 to 9 as you please; not in regular order
from 1 to 9 but interverting the order of the numbers arbitrarily. Suppose e.g. you write 8 insignificant
letters in the 1st line, 2 in the 2d, 1 in the 3d, 6 in the 4th, etc. You will thus have the horizontal lines of
your 2d paper formed into horizontal bands of 9 lines each, of which this, for instance, will be the
key, or key of insignificant letters as it may be called. 220.127.116.11.18.104.22.168.5. | 22.214.171.124.126.96.36.199.5. | 188.8.131.52.184.108.40.206.1. | 2.1.3.
Then copy the vertical lines of the 1st paper, or original, horizontally, line for line, on the 2d [paper], the columns
in regular succession, but the vertical lines of each [column] arbitrarily; as suppose you copy first the 1st
vertical line of the 1st column, the 5th next, then the 2d, then the 8th, etc. according to this, which
may be called the key of lines 220.127.116.11.18.104.22.168.4. | 22.214.171.124.126.96.36.199.9. | 188.8.131.52.184.108.40.206.6. | 3.2.1.
Then fill up the
ends of the lines with insignificant letters so as to make them appear of even lengths, & the work is done.
Your correspondent is to be furnished with the keys thus:
key of letters 220.127.116.11.18.104.22.168.5. | 22.214.171.124.126.96.36.199.5. | 188.8.131.52.184.108.40.206.1. | 2.1.3.
key of lines 220.127.116.11.18.104.22.168.4. | 22.214.171.124.126.96.36.199.9. | 188.8.131.52.184.108.40.206.6. | 3.2.1.
While Patterson's idea was to use a single key to each section, Jefferson assigned different keys for each column.
The ciphered text can be deciphered by deleting the nulls, copying horizontal lines vertically in the order specified by the key of lines, and reading horizontally.
To decypher. Your correspondent takes the cyphered paper you have sent him, & first, by the key
of letters, he dashes his pen through all the insignificant letters, at the beginning of every line.
Then he prefixes
to the lines the numbers taken from the key of lines in the order in which they are arranged in the key.
Then he copies the 1st line of the 1st horizontal band, writing on a separate paper, the letters vertically one under
another (but no exactness is necessary as in the original operation). He proceeds next to copy line No. 2
vertically also, placing its letters by the side of those of his first vertical line; then No. 3 & so on to No. 9 of
the 1st horizontal band.
Then he copies line No. 1 of the 2d horizontal band, No. 2, No. 3, etc. in the regular order
of the lines & bands.
When he comes to the insignificant letters at the ends of the lines they will betray
themselves at once by their incoherence, & he proceeds no further.
This 3d paper will then
in its letters and lines be the true counterpart of the 1st original.
The plaintext thus obtained reads "When a nation led to greatness by the hand of liberty, and possessed of all the glory that heroism, munificense, and humanity can bestow, ...." This was taken from an appeal to the people of Great Britain, adopted by the Continental Congress in September 1774.
Patterson's Keyword System
In responding to Jefferson's appreciating letter of 22 March, Patterson made an additional proposal of a keyword system, which will be easier to memorize than numerical keys.
I am not a little flattered
with the notice you have taken of my cypher -- your alteration
will certainly very much facilitate the labour of the principal
without greatly increasing that of the copyist. There is yet another
alteration, relative to the key, which, I conceive, would be of
considerable advantage -- Instead of expressing it by figures
which are so liable to be forgotten, it may be expressed by a
single word or name which may always be remembered, without
committing it to writing. For example, suppose the key-word
Montecello [sic] -- the letters of this word are to be numbered according
to their places in the alphabet, any letter repeated being referr'd
to a second, or third alphabet -- then the letters in the above
word be numbered as follows
M o n t e c e l l o
e, l, and o being referr'd to a second alphabet, and according[ly] numbered
8, 9, 10.
This key-word will then signify that there are
ten vertical lines in the section, which are to be transcribed
in horizontal lines in the order of the above figures viz. 4th 6th 5th &c.
The same word may also be used to signify the number
of supplementary or insignificant letters at the beginning of
the respective lines, as 4 at the beginning of the first, 6, at that
of the second &c. Or two key-words may be used; the first
to signify the number and order of lines in the section, and
the second, the supplementary letters.
When the two words do not
consist of an equal number of letters, then so many of the
first letters of the least word may be subjoined to the end of it,
as to make their number equal. Thus James Maddison [sic], as
a key, would be written and numbered in this manner.
J a m e s j a m M a d d i s o n
Patterson to Jefferson, 12 April 1802
Proposal to Livingston
Jefferson liked Patterson's idea of using keywords. When he told Livingston of this scheme, he provided his own explanation of the keyword system.
A favorable and a confidential opportunity offering by Mr. Dupont de Nemours, who is revisiting his native country gives me an opportunity of sending you a cipher to be used between us, which will give you some trouble to understand, but, once understood, is the easiest to use, the most indecipherable, and varied by a new key with the greatest facility of any one I have ever known. I am in hopes the explanation inclosed will be sufficient.
Let our key of letters be 651279843|923178546|314285769
and the key of lines be 947618523|218965734|769312458
and lest we should happen to lose our key or be absent from it, it is so formed as to be kept in the memory and put upon paper at pleasure; being produced by writing our names and residences at full length, each of which containing 27 letters is divided into 3 parts of 9 letters each; and each of the 9 letters is then numbered according to the place it would hold if the 9 were arranged alphabetically. Thus
robertrli alphabetically arranged would be
The numbers over the letters being then arranged as the letters to which they belong stand in our names, we can always construct our key.
Jefferson to Livingston, 18 April 1803
It is noted that here again Jefferson slightly modified Patterson's idea in the case the same letter occurs more than once in a keyword. For example, in assigning numbers to "onticello", Jefferson assigned successive numbers 1-9 to the alphabetically arranged sequence "ceillnoo", while Patterson's original idea was to assign numbers 1-7 to "ceilno" and extra "n" and "o" were to be assigned 8 and 9.
As of 22 March, Jefferson considered using this new cipher in the State Department. However, in providing Livingston with this cipher, Jefferson intended to limit its use to private matters.
But why a cipher between us, when official things go naturally to the Secretary of State, and things not political need no cipher.
1. matters of a public nature, and proper to go on our records, should go to the secretary of state.
2. matters of a public nature not proper to be placed on our records may still go to the secretary of state, headed by the word "private." But
3. there may be matters merely personal to ourselves, and which require the cover of a cipher more than those of any other character.
This last purpose and others which we cannot foresee may render it convenient and advantageous to have at hand a mask for whatever may need it. But writing by Mr. Dupont I need no cipher. I require from him to put this into your own and no other hand, let the delay occasioned by that be what it will.
Although Jefferson thought highly of this cipher, there is no evidence that this scheme was ever used between them.
Enciphering a Single Word
Having used codes and ciphers for many years in practice, Jefferson realized that Patterson's cipher might not be well suited to encipher short plaintext such as a single word.
We are introducing your cypher into our foreign correspondence, but it often happens that we wish only to cypher 2 or 3 lines, or one line, or half a line, or a single word. It does not answer for this. Can you remedy it.
Jefferson to Patterson, 17 April 1802
Patterson replied that even a single word can be enciphered with exactly the same procedure if each letter in a word was considered as a line of plaintext.
With respect to the cyphers when applied to a
single word or line, I would observe, that in strict conformity
with the general system, each letter must, in this case, be considered
as a column or vertical line; and, with its [supplementary]
letters prefixed, must be transcribed into a horizontal line. Thus,
if the word Louisiana were to be written in cypher, and the
it would, with its supplementary letters prefixed, and a few adjoined, stand thus, --
Patterson to Jefferson, 24 April 1802
The keyword "Benjamin" specifies the key of lines 23751648 when each letter is assigned a number in the alphabetical order and "Franklin" specifies the key of letters 27164538. Using the key of letters, the first two letters of the first row are insignificant or supplementary letters, the seven letters of the second row are insignificant letters, and so on. After deleting such insignificant letters, reading each letter in the order specified by the key of lines recovers the plaintext "louisiana".
Patterson realized that the "great proportion" of insignificant letters made this scheme unwieldy. But he had a solution for that. The number of the nulls can be reduced by grouping several letters in a line instead of treating each letter as a line.
remedy is easy, and that without deviating in the least from the
general use of the system -- it is only for the Principal to
write the word or part to be cyphered in short horizontal
lines one under the other, each counting of about 3, 4, or 5
letters, for then the copy or cypher will consist of as many lines
only as the number of letters in each line of the original. For example,
if we take the same word and key as before, the Principal
would write it thus
and the copyist thus--
Here the labour of the copying clerk is sufficiently diminished
while that of the Principal is no way increased, and yet the
difficulty or impossibility of decyphering, without the key, completely preserved.
In this case, the plaintext has only three lines and the key of lines "23751648" is reduced to "231". Thus, the first vertical line "lia" goes to the third row of the cipher, the second vertical line "osn" goes to the first row of the cipher, and the third vertical line "uia" goes to the second row of the cipher. The key of letters "27164538" is truncated to "271", which dictates the first row of the cipher should have two insignificant letters or nulls, the second row seven, and the third row one.
To decipher, the first two letters of the first row, the first seven letters of the second row, and the first one letter of the third row should be deleted according to the key of letters. After deleting these nulls, arranging the rows in the order specified by the key of lines gives:
Reading from top to bottom, left to right would recover the plaintext "louisiana".
Patterson's Challenge Solved After 200 Years
Patterson thought his cipher could not be deciphered without keys. The challenge included in his first letter was taken two centuries after his time by a mathematician Lawren M. Smithline.
His method was based on probability of digraphs (e.g., qu is a "favorable" digraph, ls "unfavorable", dx nonexistent). Further, instead of recovering the original ordering of the lines in a section at a time, he first focused on identifying two rows that should be adjacent to each other. More specifically, for a particular assumed value of the number of lines in one section (K) and particular two lines assumed to be adjacent to each other (R, S), the most favorable values of the number of nulls (C, D) at the beginning of those particular two lines were determined. The process also gave a score, based on which the best scoring K, R, and S can be determined. (For details, see Lawren M. Smithlilne, 'A Cipher to Thomas Jefferson: A collection of decryption techniques and the analysis of various texts combine in the breaking of a 200-year old code', American Scientist, 97 (2009), 142-149)
Use of digraphs is a usual measure for solving transposition ciphers. (See, for example, David Kahn, The Codebreakers, p.302 ff; Fletcher Pratt, Secret and Urgent, p.97 ff.) By introducing a quantitative measure of how favorable a digraph is, Smithline could construct a robust algorithm that could accommodate nulls and even transcription errors. His algorithm is so flexible to allow transcription errors such as copying "w" as "ui". His iterative strategy to find adjacent rows one by one reduced the computational cost to a feasible level.
The reconstructed keys were 1-3-5-6-2-7-4 (the key for lines) and 3-4-7-5-2-8-9 (the key for letters). Thus, the cipher revealed the preamble of the Declaration of Independence: "In Congress, July fourth, one thousand seven hundred and seventy six. A declaration by the Representatives of the United States of America in Congress assembled. When in the course of human events,...."
First posted on 18 April 2009. Last modified on 19 July 2009.
Articles on Historical Cryptography