Enigmatic Code
Programming Enigma Puzzles
Enigma 1764: Secret passages
Posted by on 28 August 2013
From New Scientist #2932, 31st August 2013 [link] [link]
Kathryn and her school friends have been using a Lorenz-type code to pass covert messages to each other. Each letter is expressed as a five-digit binary number such that A = 1 = 00001, M = 13 = 01101 and so on, but other symbols are represented by 00000 and by 11011 upwards. A fixed letter, say M, is chosen as a “coder”, known only to the sender and receiver. To transmit a letter, say D, it is added to the coder by the “exclusive-NOR” rule:
1 + 1 = 1,
1 + 0 = 0,
0 + 1 = 0,
0 + 0 = 1.So, for example, D + M = 00100 + 01101 = 10110 = V. When the sent letter V is added by the recipient to the coder M, the original letter reappears: 10110 + 01101 = 00100.
She has sent her name to her friends as seven letters. KATHRYN and its coded version together consist of 14 different letters, so what was the coded version?
[enigma1764]
Enigmatic Code 
This Python program runs in 32ms.
from enigma import irange, printf # maps: letters -> code, code -> letters (l2c, c2l) = (dict(), dict()) for c in irange(1, 26): l = chr(64 + c) l2c[l] = c c2l[c] = l # encode/decode a message with the given key def code(k, text): return ''.join(c2l.get((l2c[l] ^ k) ^ 0b11111, '?') for l in text) # message plaintext text = 'KATHRYN' # choose a coding letter for (k, v) in c2l.items(): # encode the message msg = code(k, text) # skip encodings with non-letters if '?' in msg: continue # no shared letters in the text and the message if set(text).intersection(msg): continue printf("message={msg} [key={v}]")Solution: The coded version of KATHRYN is PZOSIBU.
And here’s a different approach. Instead of considering each coding key letter and looking at what the encoded message is, it considers each letter of the plaintext and eliminates coding letters that won’t work for that letter. So it only needs to encode 47 letters rather than 26×7 = 182 letters (not that it makes much difference on a problem of this size).
from enigma import printf # encode/decode a letter l with the key k def encode(k, l): e = (ord(k) - 64) ^ (ord(l) - 64) ^ 0b11111 return chr(e + 64) if 0 < e < 27 else '?' # plaintext text = 'KATHRYN' # encoded strings by k enc = dict((k, '') for k in 'BCDEFGIJLMOPQSUVWXZ') # consider each letter of the plaintext for l in text: # keep keys that encode to a valid unused letter for k in list(enc.keys()): e = encode(k, l) # remove encodings that have non-letters or share letters with the plaintext if e == '?' or e in text: del enc[k] else: enc[k] += e printf("[{l}] {n} keys, {ks}", n=len(enc), ks=' '.join(k + ':' + enc[k] for k in sorted(enc.keys()))) for k in sorted(enc.keys()): printf("encoded={v} key={k}", v=enc[k])# convert KATHRYN to its letter code form text = [ord(c) - ord('A') + 1 for c in 'KATHRYN'] # now try all code values as the coder for key in range(1, 27): # form the cipher text cipher = [~(c ^ key) & 0x1f for c in text] # check that its elements are in the code range for letters if all(0 < c < 27 for c in cipher): # now covert it to its letter form code_word = ''.join(chr(c + ord('A') - 1) for c in cipher) # and check that it shares no letters with KATHRYN if not (set('KATHRYN') & set(code_word)): # output the code letter and the encoded version of KATHRYN letter = chr(key + ord('A') - 1) print('{:s} codes KATHRYN as {:s}.'.format(letter, code_word))def encode(x,y): return chr( ((ord(x)-64)^(ord(y)-64))^31 +64) alphabet=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ') remainder=alphabet-set('KATHRYN') for key in alphabet: if all(encode(x,key) in remainder for x in 'KATHRYN'): print "key :",key ,", ", ''.join([encode(c,key) for c in 'KATHRYN'])