The Kryptos Sculpture, Langley, VA.
In 1606 the alchemist Trithemius published a book on cryptography called Steganographia. Alchemists that knowlege was a matter of private, spiritual transformation, and they believed that nature could be influenced by our attitudes.
The first Harry Potter book referenced the alchemist Nicolas Flamel 1330–1418 who lived in France. The Harry Potter books picked up on the esoteric viewpoint where magic depends on the development of personal qualities. (Or correct pronunciation: levi-o-sa). Since nature was locked behind a spiritual enlightenment, the alchemical works should also be locked away from the non-adept (the muggles). Cryptography reflected their understanding of truth as a riddle hidden behind a personal insight.
The invention of new means of communication meant that hiding messages was important for more than alchemy. In business, diplomacy, wars and private affairs, private messages could be sent over a public channel only if it is protected with encryption.
Classical encryption depended on a shared secret that could unlock the message. The method of the lock should resist attempts by those without the secret to unlock the message. Before computers, those methods were limited in complexity. The simplest encryptions often work by changing a message letter by letter, according to a fixed or rotating pattern. In a fixed pattern it might be be moving each letter forward by one in the alphabet, as in this example,
A very simple cipher: rotate the letter one forward in the alphabet. plain text: w o l f s o n cipher text: x p m g t p o
Certain simple machines came about to help calculate these hand ciphers. One such tool was the Jefferson Wheel Cipher invented by Thomas Jefferson in 1795, see to the right.
Each wheel had the letters in a different order. So rather than a going to b, it could could to c. Then b would go to d, and so on. But these wheels had the letters all jumbled so it was harder to break the cipher.
There were 36 wheels, and the key was the order in which they where placed in the spindle. Encryption was by 36 letters at a time.
In honor or these classical hand ciphers, the CIA has put the Kryptos sculture, by artist Jim Sanbornand pictured in the upper right hand corner of this page, in the courtyard of their complex in Langley, Virginia. There are four sections to the sculpture. Sections one and two use a sort of Vignere, and the third uses a transposition cipher. The fourth section remains a mystery.
How do you break a cipher? For simple simple ciphers the method of frequency counting is used.
Although the substitution of one letter for another disguises the letter, it does not disguise the frequency of the letter. Statistics can be made and a first approximation of the substitution derived by letter statistics.
For the python code, please look at my:
The Jefferson Wheel Cipher provides a bit more challenge, but once the number of wheels used is known (William Friedman, the first famous American cryptographer, taught us how to do this mathematically, using the Index of Coincidence), each column is broken separately.
The Playfair Cipher attempts to be resistant to this frequency analysis by encoding pairs of letters at a time. It uses a keyword to fill in a 5 by 5 grid. The message is broken into letter pairs, after using X to separate double letters and possibly a final X to make the message of even length.
(Note: We need a 25 letter alphabet. Traditionally the cipher made I and J the same letter.)
Taking the message two letters at a time, the two letters are found in the grid and replaced by a different two letters according to three rules:
| W | O | L | F | S |
| N | C | A | M | P |
| U | B | D | E | G |
| H | IJ | K | Q | R |
| T | V | X | Y | Z |
The keyword is Wolfson Campus. T O M O R R O W -> T O M O R X R O W X -> V W C F R Z L T T H E B I R D -> T H E B I R D X -> W T G D K H K L
| W | O | L | F | S |
| N | C | A | M | P |
| U | B | D | E | G |
| H | IJ | K | Q | R |
| T | V | X | Y | Z |
| W | O | L | F | S |
| N | C | A | M | P |
| U | B | D | E | G |
| H | IJ | K | Q | R |
| T | V | X | Y | Z |
| W | O | L | F | S |
| N | C | A | M | P |
| U | B | D | E | G |
| H | IJ | K | Q | R |
| T | V | X | Y | Z |
your chance to try! decode the message: W T M C Q X W B P F K D K H D Y
And mathematicians were the most involved participant in the making and breaking of codes from that moment forward.
The very famous cipher machine of the war is the Enigma. It was one of the two main German ciphers. As war approached, Polish mathematicians, including Marian Rejewski, took an interest in Enigma-like machines and made a great deal of progress in understanding how to defeat its encryption.
Poland was invaded in September of 1939, and the Polish code-breakers we taken to France and their knowledge shared with the French and British. France was soon also overrun, although code-breaking continued in southern France, but the center of Enigma code breaking was then at Bletchley Park in England.
It was at Bletchley Park that Alan Turing worked on breaking the Enigma. The film The Imitation Game tells some of the story of Alan Turing's work on the Enigma.
These where times without all the technology
we have today, so the Enigma was largely mechanical.
The Enigma was a type of rotor machine.
It consisted of disks, called rotors, with
criss-crossing wires connecting 26 electrical contacts on one side of the rotor with
26 electrical contacts on the other side of the rotor.
The contacts could be lettered A through Z, so that is a wire ran from the A contact on one side of the rotor to the E contact of the other side of the rotor, this would mean that the letter A becomes the letter E by the encryption.
But the disks would turn with every letter encrypted. Mechanically this was done by the rotor being pushed on a keyboard, that would also move the first rotor by one place. Eventually the first rotor would move the second rotor, and the second a third. These means the Enigma used many different substitutions patterns that effectively did not repeat.
To understand this, the mathematicians understood that this substitution pattern was a permutation. That is, a general and mathematical study of shuffling. Understanding permutations, the code breakers were able to exploit errors made by the operators, and use cribs, text that they guessed would be found in the message, to break the keys and decrypt the messages.
A -+ +----- A A B C D E F
\ / C B F E D A
B -- \ -------- / ------ B
\ /
C --+ +----------------- C A -> C -> F -> A
\ / B -> B
D --- \ --- / --+ +- D D -> E -> D
\ / | /
E ----- \ -/ --- | -+ (A C F) (D E) (B) cycle notation
\ |
/ \ +------- E
/ \
F ----+ +------------ F
THE GROUP AXIOMS
A group is a mathematical structure with elements E, and an
operation ∘ such that,
- for e1 and e2 in E, e1 ∘ e2 is in E.
- the operation is associative, for e1, e2 and e2 in E,
(e1 ∘ e2) ∘ e3 = e1 ∘ (e2 ∘ e3)
- there is always a unique solution of x for the equation,
e1 ∘ x = e2
for any given e1 and e2 in E.
These axioms imply the existence of a unique identity element I in E, which always solves,
e1 ∘ x = e1 for any e1 in E
and the existence of unique inverses, an uniqe (1/e1) in element of E which solves,
e1 ∘ (1/e1) = I
EXAMPLE: The group of permutations.
Let P3 be the group of permutations on 3 letter. It has these 6 elements,
(1)(2)(3), (1 2)(3), (1 3)(2), (1)(2 3), (1 2 3), (1 3 2)
The identity is (1)(2)(3), and the inverses are in this table
ELEMENT 1/ELEMENT NOTES
--------- --------- ----------
(1)(2)(3) (1)(2)(3) The identity is its own inverse
(1 2)(3) (1 2)(3) Fixes the number 3, swaps 1 and 2
(1 3)(2) (1 3)(2) Fixes the number 2, swaps 1 and 3
(1)(2 3) (1)(2 3) Fixes the number 1, swaps 2 and 3
(1 2 3) (1 3 2) Rotate i -> i+1 % 3
(1 3 2) (1 2 3) Rotate i -> i-1 % 3
For the group of permutations on n letters, I = (1)(2)...(n).
APPLY THE GROUP OF PERMUTATIONS TO ENIMGA
We described a wheel W on a reduced Enigma of 6 letters,
W = (A C F) (D E) (B)
The Enigma had three wheels, and they are rotated with each letter
encrypted. This means the permutation changed with each letter.
We will continue with just a reduced Enigma of 6 letters and only one wheel.
We can account for the rotation with another permutation, but we do not do that now.
The Enigma worked by sending the electricity from the key pushed on a
keyboard, to the rotor, followed by a REFLECTOR R that was wired in
criss-crosses back through the rotor in the opposite direction, to a light board.
KEY PRESS ----> W ---> R ---> W backwards ----> LIGHT BOARD
The result is the key is permuted by,
W ∘ R ∘ (1/W)
A typical reflector R is R = (1 2)(3 4)(5 6). It is all criss-crosses.
☆ Decryption is encrypting again.
Proof:
(W ∘ R ∘ (1/W)) ∘ (W ∘ R ∘ (1/W))
= W ∘ R ∘ ((1/W)) ∘ W) ∘ R ∘ (1/W)
= W ∘ R ∘ I ∘ R ∘ (1/W)
= W ∘ (R ∘ R) ∘ (1/W)
= W ∘ I ∘ (1/W)
= W ∘ (1/W)
= I
☆ The encryption permutation has only one cycles and two cycles.
Proof:
Since E = (W ∘ R ∘ (1/W)) has E ∘ E = I,
E ∘ E (x) = x,
(1/E) ∘ E ∘ E (x) = (1/E)(x)
( (1/E) ∘ E) ∘ E (x)
= I ∘ E (x) = E(x)
So E(x) = (1/E)(x) for any x.
Either
- E(x) = (1/E)(x) = x, and E has the one cycle (x)
- or E(x)=y and (1/E)(y) = x, and E has the two cycle (x y)
☆ The encryption permutation has only two cycles.
Proof:
This is a harder more general proof, that for any permutation W,
W ∘ E ∘ (1/W) has the same cycle structure as E.
In this case, since E is a product of 2-cycles, W ∘ E ∘ (1/W) is a product of 2-cycles.
CONSEQUENCES:
The Enigma never encrypts a letter to itself. This is a great help to cryptanalysis
to eliminate possibilities in sample text.
The Enigma encrypts and decrypts with the same key.
Going backwards through this rotor would work backwards through at permutation.
So the permutation (A C F) (D E) (B) backards is (F C A)(E D)(B).
The identity permutation is (1)(2)(3)(4)(5)(6). So W &comfn; (1/W)
should calculate to that permutation,
(A C F) (D E) (B) ∘ (F C A)(E D)(B) = (1)(2)(3)(4)(5)(6)
For the reflector R = (A B) (C D) (E F), the encryption at this wheel position is,
W ∘ R ∘ (1/W) = (A C F) (D E) (B) ∘ (A B) (C D) (E F) ∘ (F C A)(E D)(B)
= (A D F B)(C E) ∘ (F C A)(E D)(B)
= (A E) (B F) (C D)
The Details:
Composing the leftmost two permutations,
A goes to C then C goes to D
D goes to E then E goes to F
F goes to A then A goes to B
B goes to B then B goes to A
making cycle (A D F B)
C goes to F then F goes to E
E goes to D then D goes to charset
making cycle (C E)
result - (A D F B)(C E)
Composing with the rightmost permutation
A goes to D then D goes to E
E goes to C then C goes to A
making cycle (A E)
B goes to A then A goes to F
F goes to B then B goes to B
making cycle (B F)
C goes to E then E goes to D
D goes to F then F goes to C
making cycle (C D)
results = (A E)(B F)(C D)
Cryptography now has techniques for many problems in information hiding, disclosure, authenticity and fairness. Here is an example of the interesting problems now solved with cryptography. No computer required.
Suppose Alice and Bob have a friend Yenta who decides that maybe Alice and Bob should date, and says so publicly. Actually, maybe Alice and Bob should date. The situation is socially delicate, however. Maybe Alice does not want to show interest unless Bob shows interest, and likewise for Bob. Both would rather disclose nothing unless they already knew they were in agreement.
Meanwhile, onlookers should learn only what becomes obvious. If Alice and Bob date, then they must of both wanted to. If not, then the onlooker should not learn whether it was because one, the other, or neither, wished to.
Each party is entitled to only the inferences that are unavoidable. Can we hide all over information?
If both are interested, then Alice and Bob go on a date and everyone knows that both are interested. Because everyone sees them go on a date.
If not both are interested, everyone knows this too, because they do not go on a date. But there are three possibilites:
All three give the reasons give same outcome, so that will be the least that can be inferred by the public, but it also should be the most that can be inferred by the public.
The participants also observe the date/no-date outcome, but they also know their own interest and would rather keep that secret.
In the case Alice wants to go on a date, the the outcome reveals Bob's choice. If they go on a date it is because Bob also wanted to go on a date, else he did not.
In the case Alice does not want to go on a date, there are two possibilities:
Both of these lead to no date, and Alice should not learn which of the two cases it was.
Same for Bob learning Alice's choice.
THE FIVE CARD TRICK ------------------- The five cards that are used: ♠ ♠ ♥ ♥ ♥ Alice gets one of each, and Bob gets one of each. The public retains a red heart. Alice and Bob in secret either palce the spade on top of the heart or the heart on top of the spade. Because it is hard to draw onto, I will draw the top card left of the bottom card. Yes(date!): ♥ ♠ No (nope!): ♠ ♥ The public then collects the cards this way, - reverse the order of Alice's cards - place the retained red hard under - place Bob's cards in their order under that. Four possibilities: (but we don't know which because no one looks): Yes Yes: ♠ ♥ ♥ ♥ ♠ No Yes: ♥ ♠ ♥ ♥ ♠ Yes No : ♠ ♥ ♥ ♠ ♥ No No : ♥ ♠ ♥ ♠ ♥ The cards are now cut at a random location. This has the effect of creating just two outcomes. The Yes–Yes outcome, and all others. The process of randomly cutting cards makes it impossible, when the cut deck is revealed, to distinguish between the three non-Yes–Yes cases.To make this clearer, randomly cutting the cards is equivalent to taking the sequence of five cards and turning them into a circular pattern of cards, by joining the ends into a circle. Then forgetting about where they were joined, picking a random card as a starting point an naming the cards in order from that randomly picked card.
Make into a circule parttern leaves us with just two possible patterns,
Only Yes–Yes is in the first case. All the other situations as in the second case. Hence become absolutely indistinguishable. HOW THE 4 OUTCOMES LOOK IN A CIRCULAR ORDERING (A NECKLACE) YES-YES ♥ / \ / \ / \ ♥ ♥ \ / \ / ♠ - ♠ The other 3 cases ♥ / \ / \ / \ ♠ ♠ \ / \ / ♥ - ♥
- Either the two black cards are next to each other,
- or they are not.
author: burton rosenberg
created: 24 may 2021
update: 26 may 2021
