Bob, Thanks. I'll work through this. Marlin -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Adam P. Goucher Sent: Sunday, April 10, 2011 12:39 PM To: math-fun; uk-imo-squad@lists.maths.bath.ac.uk; Dave Greene Subject: [math-fun] A cipher challenge Dear all: I have developed a new cipher, which is an involution between strings. That is to say, the enciphering process is identical to the deciphering process. I designed the cipher to be relatively quick to encipher and decipher by a human (6 characters per minute), yet difficult to crack, even with the help of a computer. This makes it preferable over: * Vigenere and monoalphabetic ciphers, which are crackable. Certain monoalphabetic ciphers, such as Noah John Rondeau's code, can elude most people, including T. Rychlik (which is not the Linnaean name for a bacterium! : ). Nevertheless, Dave Greene cracked it in a couple of days, and I also managed it in a similar amount of time. Consequently, it is not secure enough to use for protecting secret information. * Enigma, Feistel etc., which require a machine to encipher. Moreover, the Feistel cipher only has 2^56 keys, so is within the reach of a brute-force computer search. Enigma also has inherent Achilles' heels, making it possible to decipher with computer assistance. -------- Anyway, here is a description of my crypto-system: To begin with, a key is required. The key can be any string with 32 or fewer characters; longer keys are more secure. For this example, we will use the key MATHFUN. Firstly, each alphabetic character in the key is converted into a number in the interval [1,26], like so: A = 1, B = 2, ... , Z = 26. Hence, MATHFUN = (13,1,20,8,6,21,14). This sequence is used to generate the encoding matrix. The encoding matrix is an 8 * 4 array of squares, like so: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The first number is 13, so we place 'A' in the 13th box: _ _ _ _ _ _ _ _ _ _ _ _ A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 1, so we place 'B' in the next box along: _ _ _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Then 20. 'C' goes in the box 20 spaces ahead, like so: (There is a helical-toroidal-style wrap-around effect.) _ C _ _ _ _ _ _ _ _ _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 8: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The next number is 6, so we move 6 *unoccupied* spaces ahead: _ C _ _ _ _ _ _ _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ And 21: _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ _ _ _ _ _ _ _ Finally, 14, so we move 14 unoccupied squares ahead and add 'G': _ C _ _ _ _ _ F _ D _ _ A B _ _ _ E _ _ _ _ _ _ _ G _ _ _ _ _ _ Now, we fill in with the rest of the alphabet, starting at the top-left, and moving *vertically* downwards: H C L P T W Z F I D M Q A B ! J E N R U X . ? K G O S V Y , - Note that the 'alphabet' is augmented with " .,!?-", to make the total of 32 characters necessary. Indeed, my cipher works for any power of two, but 32 is the next power of two above 26. With each element, associate a binary string, like so: H = 00000 C = 00001 L = 00010 ... F = 00111 I = 01000 D = 01001 ... A = 01100 ... G = 11001 ... , = 11110 - = 11111 To encode a string, we separate it into blocks of five characters. Each block is encoded with a 5*5 array of bits. For example, let's consider the string GAUSS. G = 11001, so fill in the first column of a 5*5 array with 11001: G 1 _ _ _ _ 1 _ _ _ _ 0 _ _ _ _ 0 _ _ _ _ 1 _ _ _ _ And the next column with A = 01100: G A 1 0 _ _ _ 1 1 _ _ _ 0 1 _ _ _ 0 0 _ _ _ 1 0 _ _ _ Eventually, we will have: G A U S S 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 The first row, 10111, corresponds to ?: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 And 11011 corresponds to S: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 Proceeding in this manner yields: G A U S S 1 0 1 1 1 ? 1 1 0 1 1 S 0 1 1 0 0 A 0 0 0 1 1 P 1 0 0 1 1 R So, GAUSS enciphers to ?SAPR. You can verify that ?SAPR enciphers to GAUSS, and indeed that encipherment is self-inverse in the general case. -------- Eight Enjoyable Exercises (in ascending order of difficulty): 1. Decipher CIHTXG ZYGRI BU with the key MATHFUN. (15 characters; the two spaces are important.) 2. How many possible encoding matrices are there? (Ignore the fact that certain matrices do not correspond to actual keys.) 3. Find the encoding matrix for the key FERMATSLASTTHEOREM. 4. Decipher Z?TQN with the key FERMATSLASTTHEOREM. 5. Of the 33554432 possible five-character strings, how many map to themselves? (This is irrespective of the key.) 6. Give an example of a five-character string which maps to itself with the key MATHFUN. 7. Decipher this with an unknown key: (420 characters; it is easiest to view in a monospaced font such as in Notepad.) BNXUHJIG!RFSKRDQBBFI KIOYCLOQS.SAMLPDV?UXHE,STV?IL?FVXBX.QHF N.I!RKZ?CO AFUKMIW!UKR,KYU,MVXS?E.XO,CVU?LCLI-TMXIX-K.FTVVWN C-WTI TASD!OQM ? KYYZWBN-Z-NACLGHMJYVQWSQCU GJBBOG MIOYFN?EJ U,MVXJCU.GZFFLQL.FHTOGIZUVFMORMVHCU-FBANWTJROO.I!QNTB ,.NIOC NDVZRCUNTJT,EM.FIJC-QVC!U -OA RMGOB!KMP-O!CZS,DEGMSCP VMRYAV RC,CM ?BU?IYQDSAOBLS-PAKMW!FFZCQPREY ,FU?ZWSWUP-WRDKNX,VBN- A-XPM,LKY!LRF,!I.HAIO !ILUVINO!ALEK!DLEZJ-UOQDFFGHTY DS?OCGE 8. What was the original key used for the message in exercise 7? -------- Have fun! Sincerely, Adam P. Goucher _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun