The Beer Bottle Cipher
Ron Rivest
6/30/99
Last week an MIT student hacker broke into the famous Yale University
secret drinking society known as "Skull and Bones". He made a
startling discovery that has implications for national security,
saloons, and camp counselors nationwide.
What he discovered gives a surprising explanation for the origin and
meaning of the well-known drinking song "99 Bottles of Beer on the
Wall." The song, familiar to many, starts with the verse:
99 bottles of beer on the wall,
99 bottles of beer.
Take one down,
Pass it around,
98 bottles of beer on the wall.
Successive verses are the same, with the numbers reduced by one each
time. The song ends (sadly, but in glorious harmony) with "No bottles
of beer on the wall".
Apparently, this drinking song describes an encryption procedure used
by Skull and Bones' members to protect sensitive information. The
procedure, called the "Beer Bottle Cipher," was devised in the early
1700's by a mathematically-inclined Skull and Bones member. The song
was crafted as a mnemonic for the procedure.
The MIT student discovered a yellowed manuscript in the S&B vault
describing the origin and meaning of the song. ("Lock-picking that
vault was a piece of cake," the student was reported as saying.)
The Skull and Bones society uses the Beer Bottle Cipher to protect
its most valuable information. For example, it protects embarassing
personal secrets revealed by new members at their initiation ceremony.
(Details of the initiation ceremony, such as whether it is actually
held in the nude, as has been reported, were not described in this
manuscript.)
The MIT student has anonymously posted a copy of the manuscript on the
Net. This note gives a technical overview of the cipher.
This discovery may have implications for the current congressional
debate about encryption policy, since current export policy would
now prohibit the singing of this song in the presence of foreigners.
(In recognition of this development, the U.S. Navy has just instructed
its sailors to begin the song with 56 bottles of beer rather than the
conventional 99 bottles of beer when they are in a foreign port, or in
the presence of foreigners. And Louis Freeh is rumored to be asking
Congress to pass a constitutional amendment banning the song altogether.)
We now give the encryption procedure itself.
Suppose we start with "n bottles of beer on the wall". Imagine that
this row of bottles holds an n-digit number---each bottle holds one
decimal digit. (Imagine the bottles lined up left to right, with the
left-most bottle holding the most-significant digit.)
The plaintext to be encrypted is first represented as a number, using
two bottles for each letter (A = 01, B = 02, and so on). A "space" is
represented as 00. Thus, the secret "BALD MOTHER" would be
represented by the number 0201120400131520080518, using 22 bottles.
If, as in this case, the plaintext needs fewer than 99 bottles, then
it uses just the right-most bottles, and the left-most bottles hold
zeros, so the total number of bottles is 99. (For longer secrets,
start out with more bottles, and sing more verses.)
There is also an encryption key, known as the "skull". The skull is a
long secret number known only to the president and vice-president of
the society. (George Bush (senior) is believed to have served as an
S&B president, which may help explain his later political successes.)
In addition, there is the "table", which is where the "empties" go.
That is, when you "take one down, pass it around", one bottle is taken
off the wall (from the right end) and put down at the right end of the
row of empties. In the encryption procedure the bottles on the table
are not really empties, since they still contain digits, and the
actual procedure is a bit more complicated.
Anyway, you start with n bottles of beer on the wall holding the
plaintext and end up when the song is over with n empties on the table
holding the ciphertext.
The procedure is complicated enough that you probably should not be
drinking beer when you try to do it. The song helps you keep on
track throughout.
Once you have got set up to encrypt, with the plaintext on the wall,
skull in hand, and table empty, you just sing the song. Each phrase
in the song tells you exactly what to do next. The four phrases are:
"k bottles of beer"
"on the wall"
"Take one down"
"Pass it around"
Each phrase has a meaning, instructing you how to encrypt, as follows:
"k bottles of beer"
-- First you take the left-most bottle of beer on
the wall and move it over to the right-most end.
The k bottles in a row on the wall represent a
k-digit number. As you sing "k bottles of beer"
you multiply that number by the quantity (10k+1),
discarding high-order bottles if necessary.
Example: number on the wall = 537
sing "3 bottles of beer"
move left-most bottle to right end
new number on wall = 375
multiply by 31 (which is 10*3+1)
result = 11625
new number on wall = 625
"on the wall"
-- As you sing "on the wall", you add the skull to the
number on the wall, keeping only the low-order k bottles.
Example: number on wall = 625
sing "on the wall"
skull = 7972340074652439987611087
sum = 7972340074652439987611712
new number on wall = 712
"Take one down"
-- As you sing "take one down", you remove the rightmost
bottle from the wall. Call the digit in that bottle the
"bone". Don't put the bone on the table just yet...
Example: number on wall = 712
sing "take one down"
new number on wall = 71
bone = 2
"Pass it around"
-- As you sing "pass it around", you do the following.
Suppose you start with t bottles on the table, representing
a t-digit number. Define the "big bone" to be a (t+1)-digit
number each of whose digits is the bone. Then you add the
big bone to the ten times the number on the table, and keep
only the low-order (t+1) digits of the result.
Example: number on table = 587623 (t = 6)
sing "pass it around"
bone = 2
big bone = 2222222
10 x table = 5876230
sum = 8098452 (now t = 7)
The output of the encryption procedure is the number remaining on the
table when you are done.
That's the entire encryption procedure---the "Beer Bottle Cipher".
The manuscript didn't give the decryption procedure, but merely
advised the president to consult a society member who knew some number
theory if he needed to decrypt something. [For the mathematically
inclined, the only somewhat subtle part is undoing the "k bottles of beer"
operation, which can use a precomputed table of the multiplicative inverses
of (10k+1) modulo 10^k, for k = 1, 2, ..., 99.]
The actual security of this cipher seems to be an open question... Can it
be broken?
Investigations are now underway concerning the true origins of the
song "On the Twelfth Day of Christmas"...
[[ Thanks to Ian Goldberg and David Wagner for some "beer review" ... ]]
