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" ... ]]