Enigmatic Code

Programming Enigma Puzzles

Enigma 1764: Secret passages

From New Scientist #2932, 31st August 2013 [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]

Advertisements

4 responses to “Enigma 1764: Secret passages

  1. Jim Randell 28 August 2013 at 6:25 pm

    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.

    • Jim Randell 28 August 2013 at 10:31 pm

      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.keys()), 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])
      
  2. Brian Gladman 28 August 2013 at 8:01 pm
    # 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))
    
  3. arthurvause 28 August 2013 at 8:57 pm
    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'])
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: