Diana Cryptosystem
December 19, 2014
[ 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.
Find Two Added Integers
December 16, 2014
I saw this question at a popular interview-question site and got mad at the suggested answer:
You are given two lists containing identical sets of integers except that the first list contains two additional integers not present in the second set. For instance, with a = {1 4 9 2 7 3} and b = {9 7 4 1}, the two additional integers are 2 and 3. Write a program to find the two additional integers.
Your task is to write the requested program. 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.
Magic Squares
December 12, 2014
Magic squares are an arrangement of consecutive counting numbers starting from 1 into rows and columns in which every row, column and the two main diagonals all sum to the same number. Magic squares are an important element of recreational mathematics, and have been known since antiquity; this magic square of order 3, with magic sum 15, was published in China in 650BC:
4 | 9 | 2 |
3 | 5 | 7 |
8 | 1 | 6 |
That magic square was constructed by the “start bottom, move down and right, else up” rule: Starting from either of the center cells on the bottom row, enter a 1, then move to the next square diagonally down and right (wrapping around the sides of the square if necessary), then enter the next number in sequence, 2, and so on. However, if the next square is occupied, move instead to the next square up from the current square, then continue the sequence. Various rules like “start left, move down and right, else up” and “start top, move up and right, else down” also work, but rules like “start top, move down and left, else up” don’t; I’ll let you have the pleasure of figuring out which rules work and which don’t. This method works only for odd orders; there are other methods for even orders, which we may examine at some other time.
In the example square, the starting cell is the center cell on the bottom edge, where you see 1. Moving down and right and wrapping to the top of the next column, enter 2. Then moving down and right and wrapping to the left of the next row, enter 3. The next cell down and right already contains 1, so instead move up from the current cell and enter 4. Then moving down and right, enter 5. Then moving down and right, enter 6. The next cell down and right, wrapping both the row and column, already contains 4, so instead move up from the current cell and enter 7. Then moving down and right and wrapping to the left of the next row, enter 8. Finally, moving down and right and wrapping to the top of the next column, enter 9.
Your task is to write a program that takes an odd order n, one of the four starting cells and a rule and generates the indicated magic square. 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.
Every Possible Fraction
December 9, 2014
When I saw this web page a few days ago, I knew it would make a great exercise, simple but fascinating. Starting with x = 1, every fraction in lowest terms is generated by x ′ = 1 / (n − y + 1), where n = ⌊ x ⌋ and y = x − n. The underlying math is known as the Stern-Brocot tree, and has been known since the ancient Greeks, who used terms of the Stern-Brocot tree to design the gear ratios in the Antikythera mechanism.
Your task is to write a program that generates the fractions in lowest terms. 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.
Free Time
December 5, 2014
We have a very practical task today: Given the set of busy-time intervals of two people, as in a calendar, find the free-time intervals of both people so they can arrange a meeting.
Your task is to write a program to find free time. 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.
Gray Code Neighbors
December 2, 2014
Our exercise today is based on Gray code sequences, where each number in the sequence differs from its predecessor in only one bit. We studied Gray code sequences in a previous exercise. Here is an interview question base on Gray code sequences:
Given two integers, determine if they are two consecutive numbers in a Gray code sequence.
Your task is to write a program that determines if two numbers appear consecutively in a Gray code sequence. 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.
A Prime Number Puzzle
November 28, 2014
Today’s exercise comes from the world of recreational mathematics.
For each number n from 1 to 9 inclusive, find a number m that begins with the digit n, has n digits, has each two-digit sequence within m a different prime number, and is as small as possible.
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.
Thou Impertinent Urchin-Faced Miscreant!
November 25, 2014
In 1968, Newsweek published an article “How to Win at Wordsmanship” by Philip Broughton. You pick a random number from 000 to 999, then look up a three word phrase in a table coded by the three digits of the random number:
Column 1 | Column 2 | Column 3 |
0. integrated | 0. management | 0. options |
1. total | 1. organizational | 1. flexibility |
2. systematized | 2. monitored | 2. capability |
3. parallel | 3. reciprocal | 3. mobility |
4. functional | 4. digital | 4. programming |
5. responsive | 5. logistical | 5. concept |
6. optional | 6. transitional | 6. time-phase |
7. synchronized | 7. incremental | 7. projection |
8. compatible | 8. third-generation | 8. hardware |
9. balanced | 9. policy | 9. contingency |
For instance, the random number 031 leads to the phrase “integrated reciprocal flexibility,” which you can use in a technical conversation or report. Broughton said “No one will have the remotest idea of what you are talking about, but the important thing is that they’re not about to admit it.”
Since then, many buzz-phrase generators have been developed, including corporate-speak “holistically embrace customer-directed imperatives” and the Shakespearean insult generator that gave us the title of our exercise. We have a couple of word lists on the next page, or you can Google for “buzz-phrase generator” to find lots of them on the web, but it’s most fun to build your own.
Your task is to write a program that generates random buzz-phrases. 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.
An Array Of Zeroes
November 21, 2014
Beware! Today’s exercise, which derives from an interview question asked at Facebook, is trickier than it looks:
You are given an array of integers. Write a program that moves all non-zero integers to the left end of the array, and all zeroes to the right end of the array. Your program should operate in place. The order of the non-zero integers doesn’t matter. As an example, given the input array [1,0,2,0,0,3,4], your program should permute the array to [1,4,2,3,0,0,0] or something similar, and return the value 4.
Your task is to write the indicated program. 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.
Damm’s Algorithm
November 18, 2014
We studied Hans Peter Luhn’s algorithm for generating check digits in a previous exercise. Today, we look at an alternate check digit algorithm developed by H. Michael Damm. Both algorithms are useful for creating checked identification numbers, suitable for credit cards or other identity numbers.
Damm’s algorithm is based on table lookup. It is initialized with a current check digit of 0. Then, each digit of the number, from left to right (most-significant to least-significant) is looked up in a two-dimensional table with the current check digit pointing to the row and the digit of the number pointing to the column, using this table:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 9 |
9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
For instance, given the input 572, the check digit is 4 and the output is 5724. The check digit is computed starting with 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, and row 7 and column 2 gives a final check digit of 4. Notice that leading zeroes do not affect the check digit.
Checking goes the same way, and is successful if the final check digit is 0. Given the input 5724, the initial check digit is 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, row 7 and column 2 gives a new check digit of 4, and row 4 and column 4 gives a final check digit of 0.
Your task is to write functions that add a check digit to a number and validate a number to which a check digit has been added. 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.