Trigraphs, Diana Pads and Zombies

I'm browsing this guy's zombie response kit when I noticed this item here:

This naturally raises the questions: (a) what's a tri-graph and (b) how does it help with "clandestine" communications?

Of course, the Internet explains: a tri-graph (or is it trigraph?) is a lookup table used in One Time Pad (OTP) encryption. One example of an OTP are pages and pages of random text. If you and I have copies of the same one time pad, then we can use a tri-graph as follows:

1. Pick a line in the OTP (known as our key text). Say:

  VAXPM IPIXU QUXIP MAXIU

2. Write the clear text below it:

  VAXPM IPIXU QUXIP MAXIU
  MEETA TTENT ONIGH TXXXX

(that's: meet at 10 tonight)

3. For each letter, look up the key text and plain text character in the trigraph and find the resulting encrypted text.

  VAXPM IPIXU QUXIP MAXIU
  MEETA TTENT ONIGH TXXXX
  SVYRN YRNPM VSULD UCFUI

Because of the symmetric nature of the tri-graph, I can decode the text using the same procedure. That is, if I look up a key and encrypted letter, I will arrive and the decoded letter.

That may seem like a neat parlor trick, but the fact is, the above encryption is actually quite strong. In fact, assuming that the pads are truly randomly generated, never reused and never compromised the system is unbreakable.

One use case for the above system was during the Vietnam War:

Special Forces were one of (if not the only) units in Vietnam to utilize Morse code on a regular basis. We used a method of encryption called the Diana Cryptosystem.

The basis of these "One-Time Pads", is that there were only two matching pads in existence, and they would only be used one time. They were booklets that contained randomly generated groups of 5-letter "words;” 30 words to a page. The person sending a message would first write the letters to the message, over these random groups of words. Included in the front of each one-time pad was a one-page encryption table. If I wanted to send the letter "P", and the letter under the "P" was an "A", then I would send a "K". The person listening on the frequency at the other end, would have the other matching pad. They would write the letter they received (a "K") over the letter in their one-time pad (an "A"), and decipher it based on the table, yielding the original letter "P".

Each communication site in Vietnam (we had over 100 A-Camps along the Cambodian / Laotian border, and some 20 B-detachment sites spread over the country) had a different pad, depending on the location they were having the commo-check with. It obviously was very important that both people were using the appropriate matching pads, or the deciphered messages would not make any sense.

After a while, most of us became so proficient with the system, that we actually learned the deciphering matrix by heart. No matter what pads anyone had, the combinations always were the same. i.e. Any 3 letters always went together, regardless of the order; "BKO"/"KOB"/"OBK"/"BOK". After listening to thousands and thousands of transmissions, it really got quite simple. If I was listening to code, and a letter "B" was sent (now remember, we usually sent around 20-25 "words" (5 letters per word) a minute, hence the importance of the "speed" keys!), and the letter it was associated with was an "O", most of us would decipher as we heard it, and just write the "K". That may sound like quite a yarn, but it is absolutely true.

That's my kind of solution: simple enough that a a soldier can manually execute the encryption and send it over Morse Code, yet sophisticated enough that the code was effectively unbreakable.

Naturally, I had to experiment with this encryption, and of course, write some code to make it easier to play with. You can find the code here, or copied below. The code provides two top level function: make-pad which generates characters for a one time pad and tri-lookup which does the tri-graph lookup:

(In the session above, k is the key text and p is the plain text)

Thinking more about this form of encryption, it's remarkable how practical it could be. For example, if both my wife and I had a business card sized piece of paper packed with random characters, we could send dozens of short messages to each other using the above technique. Furthermore, any stream of text that we agree upon could be used as a key. While random text would be ideal, technically any string of characters would work. We could use song lyrics, the 5th paragraph from the 2nd story on the 3rd page of the New York Times, street names from a map, ingredients on a shampoo bottle, etc. Heck, you could even incorporate the clue to the key in the messages. For example:

 K541 8151 Z781 0742 AI06 PU72 EBXBH HGOXU

Where K541 8151 Z781 0742 AI06 PU72 corresponds to tweet 541815178107420672 (the spaces and letters are meant to throw off attackers).

Of course, straying from randomized text definitely weakens the setup. I wouldn't want to protect state secrets or call in an air strike using these short-cuts. But, this would work for leaving a romantic note to my wife or other less than sensitive message.

At the end of the day, I suppose the most important question is: does a tri-graph belong in your zombie fighting kit? Heck yeah! It also belongs in your kids play fort setup, and teenager's clandestine communication kit.

---

;;
;; Implement a version of One Time Pad encryption.
;; Use a trigraph / diana pad method
;; http://danmorgan76.wordpress.com/2013/09/30/encryption-via-a-one-time-pad/
;; http://home.earthlink.net/~specforces/spdiana.htm
;; 

(define (a->i letter)
 (- (char->integer letter) 65))
  
(define (i->a index)
 (integer->char (+ 65 index)))
 
(define (rand-char)
 (i->a (random-integer 26)))

(define (range low high)
 (if (> low high) '() (cons low (range (+ 1 low) high))))
 
(define (head items)
 (let loop ((i 0) (items items) (accum '()))
  (cond ((or (null? items) (= i 5)) (reverse accum))
        (else
         (loop (+ i 1) (cdr items) (cons (car items) accum))))))

(define (tail items)
 (reverse (head (reverse items))))
 
(define (make-pad rows cols)
 (define (make-block)
  (apply string (map (lambda (i) (rand-char)) (range 1 5))))
 (define (make-row)
  (for-each (lambda (i)
             (if (> i 1) (display " ")) 
             (display (make-block)))
            (range 1 cols)))
 (for-each (lambda (i)
             (make-row) (newline))
           (range 1 rows)))

(define (tri-row i)
 (reverse (map (lambda (pos)
                 (i->a (modulo (- pos i) 26)))
          (range 0 25))))

(define (tri-lookup key plain)
 (let loop ((key (string->list key))
            (plain (string->list plain))
            (coded '()))
  (cond ((null? plain) (apply string (reverse coded)))
        ((equal? #\space (car plain))
         (loop (cdr key) (cdr plain)
               (cons #\space coded)))
        (else
         (let ((row (a->i (car plain)))
               (col (a->i (car key))))
           (loop (cdr key) (cdr plain) 
                 (cons (list-ref (tri-row row) col) coded)))))))          
(define k "ASDFA POUYK")
(define p "HELLO WORLD")