Planet Scheme

January 30, 2015

Programming Praxis

M4 Macros

I’ve always had a love/hate relationship with m4 macros. For programming languages that don’t offer macros, or have only a limited form of macros (like C), m4 can be a godsend. Used to their fullest potential, m4 macros enable programmers to write programs that write programs, which can lead to extremely high productivity. And m4 macros aren’t limited to use in programming; I used m4 macros recently when writing my security camera essay (which is what inspired me to write this exercise).

If you’re interested in learning about m4, the original tutorial by Brian Kernighan and Dennis Ritchie is a fine introduction for casual use, the manual for Gnu m4 is complete and definitive, and this short essay by Ken Turner is a little bit insane.

Your task is to use m4 to write some program or transform some text; the purpose is to introduce you to m4 (or re-introduce you if it’s been a long time since your last use), so any task will do. When you are finished, you are welcome to read or run a suggested solution or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 30, 2015 09:00 AM

January 28, 2015

GNU Guix

GNU Guix 0.8.1 released

We are pleased to announce the next alpha release of GNU Guix, version 0.8.1.

The release comes both with a source tarball, which allows you to install it on top of a running GNU/Linux system, and a USB installation image to install the standalone Guix System Distribution.

The highlights for this release include:

See the original announcement for details.

About GNU Guix

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution is an advanced distribution of the GNU system.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language.

At this stage the Guix System Distribution can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armv7.

by Ludovic Courtès at January 28, 2015 11:58 PM

January 27, 2015

GNU Guix

GNU Guix at FOSDEM

Guix will be present at FOSDEM in Brussels, Belgium, with a talk entitled "The Emacs of Distros" this Saturday, at 3PM, in room H.1302.

The talk will give an update on developments in Guix and the Guix System Distribution since last year, and will explain and demo the overall philosophy behind its design---how Guix seeks to empower users.

Hope to see you there!

by Ludovic Courtès at January 27, 2015 09:33 AM

Programming Praxis

Sum Of Four Primes

Today’s exercise comes from one of those competitive programming websites. I never participate in the coding frenzy at those sites, because the competitiveness at extracting every last millisecond from the run time or deleting every unneeded character from the program text ruins the pleasure, but some of the problems are fun:

Given a positive integer 7 < n ≤ 10000000, find four prime numbers with sum n. For instance, 46 = 11 + 11 + 17 + 7.

Your task is to write a program to find four primes that sum to n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 27, 2015 09:00 AM

January 23, 2015

Programming Praxis

Fibonacci Conjecture

The sequence of Fibonacci numbers is defined as F0 = 0, F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.

Your task is to either prove the conjecture to be true or find a counter-example that demonstrates it is false (hint: this is not a blog about proving math theorems). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 23, 2015 09:00 AM

January 20, 2015

Programming Praxis

Largest Forward Difference

In an array of integers, the forward difference between any two elements is the rightmost integer less the leftmost integer. The largest forward difference is the greatest value of all forward differences between elements of the array. If there are no positive forward differences, the largest forward difference is taken to be zero, as if an integer is subtracted from itself.

For instance, in the array [1,5,7,2,9] the largest forward difference is 9 – 1 = 8, and in the array [4, 3, 2, 1] the largest forward difference is 0.

Your task is to write a program that finds the largest forward difference in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 20, 2015 09:00 AM

January 16, 2015

Programming Praxis

Gödel Numbering

Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =

83838469305478699942290773046821079668485703984645720358854000640

The process is reversible; factor the Gödel number and decode the exponents.

Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 16, 2015 09:00 AM

January 13, 2015

Programming Praxis

Essay: Building A Security Camera With A Raspberry Pi

We have today our fourth essay: Building a Security Camera with a Raspberry Pi. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

My daughter recently had a thief enter her apartment and steal her laptop computer. Later, when I asked her what she wanted for Christmas, her answer was immediate: a security camera, so in case she is robbed again she will have pictures of the thief to give to the police. But commercial security cameras are expensive, often several hundred dollars, and many are tied to security services with expensive monthly fees, which she wasn’t interested in paying. So I built a security camera using a Raspberry Pi, and wrote this essay describing how I did it.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.


by programmingpraxis at January 13, 2015 09:00 AM

Ben Simon

The Most Powerful Computer You'll Never Own

Inspired by the movie the Imitation Game, I just had build my own Turing Machine (I know, I should have built one of these! Some day). While folks have built actual physical machines, I took the programmer's way out and made mine strictly virtual.

A Turing Machine is the theortical device Alan Turing devised in his 1936 paper on computability. To this day, Computer Science students are made to do battle with this machine and the theories that stem from it.

While it's been years since I've done any CS homework that involved Turing Machines, I can't recall actually ever implementing one. What a shame.

The web is filled with such simulators including: here, here and here. These were invaluable for refreshing my memory as to how a Turing Machine operates.

Implementing a Turing Machine was oddly satisfying. One has to contend with the fact that a program handed to a Turing Machine may never complete. I dealt with this by allowing the user to execute the machine in terms of blocks of cycles. So you create the machine, run it for 100 cycles, and if you want, run it 100 more.

Here's the code to create a machine. The program is actually Alan Turing's first example:

(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

The rules specified by r1 are in the format:

 (((current-state current-symbol) (new-state new-symbol new-direction))
  ...)

Invoking make-tm creates the new Turing Machine. You provide as arguments the initial state, initial tape-contents, list of halting states and the transition rules.

Once you've got the machine (tm1, above), you can invoke it with an integer to say how many cycles of the machine should execute (e.g., (tm1 10)).

Scheme truly shined as a host language: I was trivially able to make the machine operate on arbitrary states and tape contents. Also sexpr's were ideal for defining the state transition rules.

All of this may seem fairly unimpressive until you ponder this thought:

However odd it may sound for so simple a machine, the Turing Machine is the most powerful computing model known to computer scientists. In this context, "powerful" refers only to what it is capable of doing, not to how fast or efficiently it does it. It has been proven that a TM is capable of performing any computation that a modern computer can, given enough time. Infact, it is technically MORE powerful than modern computers, since it has no storage limitations.

Here's the complete source code for my simulator.

Update: Programming Praxis tackled the Turing Machine almost 5 years ago. I've updated my code below with their example.

; A Turing Machine Impl

(define (range lower upper)
 (if (>= lower upper) '()
     (cons lower (range (+ 1 lower) upper)))) 

(define (show . words)
 (for-each display words))

(define tape-cell '#(_))
(define tape-padding '#(_ _ _ _ _))

(define (make-tape contents)
 (cons 0 (vector-append (list->vector contents) tape-padding)))

(define (tape-head t)
 (car t)) 
(define (tape-items t)
 (cdr t))
 
(define (tape-read t)
 (vector-ref (tape-items t) (tape-head t)))
 
(define (tape-write t x)
 (vector-set! (tape-items t) (tape-head t) x)
 t)
 
(define (tape-move t direction)
 (let ((index (+ (tape-head t)
                 (case direction
                  ((< L) -1)
                  ((> R) 1)
                  ((- N) 0)
                  (else (error "Unknown tape movement: " direction))))))
  (cond ((= index -1)
         (set-cdr! t (vector-append tape-cell (tape-items t)))
         (set! index 0))
        ((= index (vector-length (tape-items t)))
         (set-cdr! t (vector-append (tape-items t) tape-padding))))
  (set-car! t index)
  t))

(define (display-tape t)
 (for-each (lambda (i)
            (let ((v (vector-ref (tape-items t) i)))
              (cond ((= i (tape-head t))
                     (show "[" v "]"))
                    (else (show v)))
              (show " ")))
           (range 0 (vector-length (tape-items t)))))

(define (tm-find state tape rules)
 (let ((needle (list state (tape-read tape))))
  (let loop ((rules rules))
   (cond ((null? rules) #f)
         ((equal? needle (caar rules)) (cadar rules))
         (else
          (loop (cdr rules))))))) 
            
(define (make-tm initial-state initial-tape halting-states rules)
 (let ((state initial-state)
       (tape (make-tape initial-tape)))
 (lambda (cycles)
  (let loop ((cycle 0))
   (show state ": ")
   (display-tape tape)
   (newline)
   (cond ((= cycle cycles) #t)
         ((member state halting-states) state)
         ((tm-find state tape rules) =>
          (lambda (dest)
           (let* ((new-state (car dest))
                  (new-symbol (cadr dest))
                  (new-direction (caddr dest)))
             (set! state new-state)
             (tape-write tape new-symbol)
             (tape-move tape new-direction)
             (loop (+ 1 cycle)))))
          (else 'no-matching-rules))))))

; Binary Counting - http://aturingmachine.com/examples.php
(define r0 '(((walk  0) (walk  0 >))
             ((walk  1) (walk  1 >))
             ((walk  _) (count _ <))
             ((count 0) (walk  1 >))
             ((count 1) (count 0 <))
             ((count _) (walk  1 >))))
             
(define tm0 (make-tm 'walk '(0) '() r0))

; Turing's First Example 
;  http://en.m.wikipedia.org/wiki/Turing_machine_examples
(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

; http://programmingpraxis.com/2009/3/27/a-turing-machine-simulator/
(define r2 '(((0 1) (0 1 R))
             ((0 +) (1 1 R))
             ((1 1) (1 1 R))
             ((1 _) (2 _ L))
             ((2 1) (H 1 N))))
(define tm2
 (make-tm 0
         '(1 1 1 + 1 1 1 1)
         '(H)
         r2))

by Ben Simon (noreply@blogger.com) at January 13, 2015 01:24 AM

January 09, 2015

Programming Praxis

One-Time Pad

In a previous exercise Ben Simon showed us how to use a trigraph for secret communication. For illustration, he used a one-time pad based on a simple random number generator, but that is not sufficient for proper cryptographic secrecy. In today’s exercise we build a secure one-time pad.

We need two things. One is a cryptographically-secure source of random bits. Solutions include counting the clicks of a geiger counter or reading the background radiation, but being a software guy rather than a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive bits from the Blub-Blub-Shum generator, form them into a number, and take the result mod 26, discarding the four largest numbers from the set in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired size.

Your task is to write a program to generate one-time pads. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 09, 2015 09:00 AM

GNU Guix

GNU Guix ported to ARM and other niceties of the new year

A new port of GNU Guix to ARM using the "hard float" ABI has just landed, thanks to the hard work of Mark H Weaver and John Darrington. This makes it the fourth supported architecture after x86_64, i686, and mips64el. We are looking for ARM hardware donations that would allow us to add this architecture to our continuous integration build farm; your help is welcome!

In other news, there has been work to improve Linux module handling, the addition of session support in the login manager, more tooling in 'guix lint', an nscd configuration interface, many new packages (Xfce, NumPy, SciPy, and Clang, to name a few), and many bug fixes. Getting closer to a new release!

About GNU Guix

GNU Guix is the functional package manager for the GNU system, and a distribution thereof.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language.

At this stage the distribution can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armhf.

by Ludovic Courtès at January 09, 2015 08:18 AM

January 06, 2015

Programming Praxis

Lucas-Carmichael Numbers

We start the new year with a simple task from number theory. A Lucas-Carmichael number is a positive composite integer n, odd and square-free, such that p + 1 divides n + 1 for all prime factors p of n. For instance, 2015 is a Lucas-Carmichael number because 2015 = 5 × 13 × 31 and 5 + 1 = 6, 13 + 1 = 14, and 31 + 2 = 32 all divide 2015 + 1 = 2016. The restriction that n be square-free prevents the cubes of prime numbers, such as 8 or 27, from being considered as Lucas-Carmichael numbers.

Your task is to write a program to find all the Lucas-Carmichael numbers less than a million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at January 06, 2015 09:00 AM

December 30, 2014

Ben Simon

Forth in Racket, Mind-bending and Beautiful

Jay McCarthy's efficient implementation of Forth in 85 lines of Racket is beautiful. It demonstrates how you can integrate two different programming paradigms in one environment, and it does so with some impressive macro-fu. Consider his goals:

  1. We must be able to define functions in Forth that are callable from Forth, always.
  2. We must be able to give functions stack effect annotations to enable them to be called from Racket.
  3. We must be able to lift Racket functions to Forth so they are oblivious to the stack, like turning + into :+.
  4. We must be able to lower Racket functions to Forth so they can directly affect the stack, like writing :over.
  5. We must be able to enter Forth from Racket arbitrarily, such as to write testing forms like check-forth.

Meeting all those goals is an impressive feat.

As a functional tool, I'm not sure I see much of a use for it (yet). As a novel case study and series of examples, it's fantastic.

by Ben Simon (noreply@blogger.com) at December 30, 2014 06:28 PM

December 23, 2014

Programming Praxis

Ancient Algorithms

[ Today’s exercise is a Christmas stocking stuffed with six little exercises. I wish all my readers a Merry Christmas and a Happy New Year! I’ll be taking a few days with family, so the next exercise will appear on January 6, 2015. ]

We tend to think of algorithms as procedures used by computers, but algorithms actually have a long and distinguished history. Today’s exercise discusses six algorithms that pre-date the Christian era, arranged roughly in chronological order. Despite their antiquity, all these algorithms are still in use today.

Peasant Multiplication: This algorithm has been independently invented by most societies as they progress to numeracy, so it is called the Egyptian method, the Ethiopian method, the Russian method, the Ukranian method, and so on for many different peoples; we simply call it the Peasant method. It is known that the Egyptians used this algorithm during the construction of the pyramids.

The algorithm starts by writing the two numbers to be multiplied at the heads of two columns. Then, on successive rows, the number in the left column is halved, discarding any remainder, and the number in the right column is doubled, until the left column is reduced to one. Then the sum of the numbers in the right column that correspond to odd numbers in the left column is the desired product. The ancients use pairs of pebbles to halve numbers and determine parity; we find it simpler to sum the odds as we go along.

function product(left, right)
    prod := 0
    while left > 0
        if left is odd
            prod := prod + right
        left := halve(left)
        right := double(right)
    return prod

In the United States we torment eight-year-old kids with the times tables, but school children in the rest of the world learn this method, which is simpler and, if you’ve ever taught third-grade math, more likely to be done correctly. Additionally, all computers do arithmetic in binary, and use this algorithm deep in the microcode that is stamped into the silicon chip that runs them, shifting bits to perform the halving and doubling operations. The only improvement is that computers nowadays process multiple bits at the same time, instead of just a single bit, reducing the number of steps in the loop.

Babylonian Square Roots: Mathematical historians know that the Babylonians invented a method of calculating square roots because a clay tablet with the calculations etched into it (ancient “scrap paper”) exists, but the method was first described by Hero of Alexandria in the first century after Christ. Hero (his name is sometimes spelled Heron) invented the jet engine (a hollow metal ball filled with water, heated over a fire to convert the water to steam, which exited by two nozzles on opposite sides of the globe; the rotational motion could be captured by gears or belts), the windmill (he used it to power a variety of machines, including a grain grinder), and the vending machine (you dropped a coin into a slot, which caused a balance beam to rise, opening a valve and filling a small vessel with holy water; when the vessel was full, it tipped to deliver the holy water, the coin was tipped into the safe, the balance beam fell, the valve closed, and the machine reset for the next purchase).

Hero observed that if x is an approximation of the square root of n, a better approximation is given by the average of x and n /x; we say x ′ = (x + n /x) / 2. The initial value of x can be anything on the range 1 ≤ xn, though the process converges more quickly if x is somewhat closer to n. In the version of the function given below, we bound n on the range 1 ≤ n < 4 so we can fix the number of iterations required for double-precision accuracy; an alternative is to iterate until the difference between two successive approximations is less than some desired epsilon.

function sqrt(n)
    if n < 1 return sqrt(n * 4) / 2
    if 4 <= n return sqrt(n / 4) * 2
    x = (n + 1) / 2
    repeat 5 times
        x = (x + n / x) / 2
    return x

The only improvement since the Babylonians is the initialization of x, which nowadays is done by some kind of black magic operating on the internal representation of the number (for integers, it’s generally one less than the number of bits in the binary representation of the number, for floating point it’s generally half the mantissa of the number with the exponent reduced by one), usually reducing the number of iterative steps to two or three.

Pythagorean Triples: Pythagoras, who lived about five centures before Christ, was a mathematician, philosopher and mystic. When he discovered that the square root of 2 could not be expressed as the ratio of two integers (we now say that it is irrational), he thought he had discovered some impossible flaw in the perfection of the World, and swore his followers to secrecy; legend tells us that one of his disciples, Hippasus, was murdered when he divulged the secret (another legend has it that Hippasus, not Pythagoras, who discovered the irrationality of the square root of 2).

Pythagoras proved that for any right triangle the square of the length of the hypotenuse is equal to the sum of the squares of the other two sides. He also discovered that given any coprime m and n, a primitive right triangle (all sides coprime to each other) has sides m2n2, 2mn, m2 + n2; for instance, with m = 2 and n = 1, the triangle is 22 − 12 = 2, 2 × 2 × 1 = 4, and 22 + 12 = 5.

function triple(m, n)
    return m*m - n*n, 2*m*n, m*m + n*n

An alternative method is to take any primitive Pythagorean triple {a, b, c} and generate three new primitive Pythagorean triples as {a-2b+2c, 2a-b+2c, 2a-2b+3c}, {a+2b+2c, 2a+b+2c, 2a+2b+3c}, {−a+2b+2c, −2a+2b+3c}; the process starts from {3, 4, 5}. Of course, non-primitive triples can be generated by multiplying all three elements of a primitive triple by some constant k.

Greatest Common Divisor: Euclid was either a Greek mathematician of the third century before Christ or, as some historians suggest, the conglomerate name of several mathematicians. Euclid wrote Elements, a textbook of geometry and number theory which has been in continuous publication since it was written, which is famous for its method of starting with five axioms and deriving all of geometry from them.

Euclid’s Elements, Book VII, Proposition 2, gives an algorithm for computing the greatest common divisor of two integers. Euclid’s algorithm works by repeatedly subtracting the smaller number from the larger, which reduces the magnitude of the numbers, thus guaranteeing termination of the algorithm, without affecting the greatest common divisor, since both the smaller number and the difference between the two numbers must be multiples of the greatest common divisor.

function gcd(m, n) # ancient
    if m < n return gcd(m, n-m)
    if n < m return gcd(m-n, n)
    return m
function gcd(m, n) # modern
    if n == 0 return m
    return gcd(n, m % n)

Euclid used repeated subtraction; nowadays we use modular arithmetic. Knuth calls this the “grand-daddy” of all algorithms, even though it isn’t the oldest, because it was the first to be written in rigorous form.

Approximation of Pi: Archimedes of Syracuse (on the island of Sicily) was a famous inventor of the third century before Christ: the screw pump, block-and-tackle pulley, odometer (it dropped a ball every time the wheel completed a turn), and numerous devices of war were among his inventions. He didn’t invent the lever, but was the first to explain how it worked, and he famously stated “Give me a lever and a place to stand, and I can move the world.” His most famous discovery was that objects float when they weigh less than the water they displace, which he used to prove that the king’s crown, thought to be pure gold, was actually an amalgam with silver; it is said that he discovered the principle while bathing, whereupon he ran naked through the street shouting “Eureka!”

The ratio of the circumference of a circle to its diameter is the mathematical constant known as π, which is approximately 3.141592654. Archimedes bounded the value of π in the range 223/71 < π < 22/7 by calculating the perimeters of two hexagons, one inscribed inside a circle and one circumscribing it, then successively doubling the number of sides of the inscribed and circumscribed regular polygons through the series 6, 12, 24, 48, and 96.

function pi(n) # archimedes used 6
    outer := 3 * sqrt(3)
    inner := outer / 2
    for i from 1 to n
        outer = 2 / (1/outer + 1/inner)
        inner = sqrt(outer * inner)
    return inner, outer

Archimedes’ approximation 22/7 is still frequently used today, but his method of computing the approximation has been replaced by a series expansion due to Srinivasa Ramanujan, or some similar series expansion, which converges in just a few steps; by contrast, Archimedes’ algorithm requires 27 steps for double-precision accuracy.

Prime Numbers: Eratosthenes, who measured the circumference of Earth, the distance from Earth to Sun, and the tilt of Earth’s axis, devised a system of latitude and longitude and was third chief librarian of the great library at Alexandria, succeeding Ptolemy and Apollonius, invented a method of enumerating prime numbers about 200BC; his writing has been lost, but we know of his invention through the writings of Nicomachus two centuries later.

The Sieve of Eratosthenes identifies primes by striking out multiples and keeping what’s left; the image is that composites fall through the sieve but primes remain. Initialize a list of numbers, from 2 to the desired limit n all marked as prime, then consider each number in turn; if it has not been marked as composite, report it as prime, then mark all its multiples as composite, starting from the square of the prime (since all smaller multiples will have already been marked composite by smaller primes).

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] = False

Modern mathematicians have optimized the basic Sieve of Eratosthenes shown above by eliminating the small primes that, because they have so many multiples, take most of the time; eliminating multiples of 2 is easy, and “wheels” can be used to eliminate multiples of 3, 5, 7, and so on, though increasingly large wheels quickly become cumbersome to operate. Still, an optimized Sieve of Eratosthenes is faster than any of its many modern alternatives.

Your task it to translate these seven programs into your favorite programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at December 23, 2014 09:00 AM

December 19, 2014

Programming Praxis

Diana Cryptosystem

[ Today’s exercise comes from the blog of long-time reader Ben Simon, after he declined my offer to guest-author the exercise and told me to steal it. The code and most of the text is his, so he gets the credit, not me. ]

It’s been a while since we had an exercise from our cryptography topic. Today’s exercise is the Diana Cryptosystem, also known as the trigraph cipher, which was used militarily by US forces during the Vietnam War and is theoretically unbreakable when used properly.

There are two pieces to the system: the trigraph itself, which is pictured at right, and a one-time pad, like this:

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK
GORWY WETFR COYET OOWHY
ZPDDA CMMXT VYTJI RRQGU

To use the cipher, a section of the one-time pad is chosen and the two five-character groups that begin the section are transmitted unchanged. Thereafter, the key character is looked up on the trigraph, the next plaintext character is on the top row, and the corresponding ciphertext character is read off the bottom row. Decryption is the inverse operation. For instance, the message ATTACK AT DAWN is encoded like this, starting from the third group on the second row of the one-time pad:

UKVTF WZHOK GORWY WETFR COYET
            ATTAC KATDA WNXYZ
UKVTF WZHOK TSPDZ TVNRI BYEXH

Then UKVTF WZHOK TSPDZ TVNRI BYEXH is transmitted by Morse code. The recipient looks up the first two groups on the one-time pad then decrypts as follows:

UKVTF WZHOK GORWY WETFR COYET
UKVTF WZHOK TSPDZ TVNRI BYEXH
            ATTAC KATDA WNXYZ

The cipher is unbreakable without the one-time pad.

We said earlier that the cipher was used militarily. Ben points to this description of its use:

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.

Your task is to write a program that implements the trigraph cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at December 19, 2014 09:00 AM