Although usage of the .NET Cryptographic classes does not absolutely require a knowledge of the history of cryptography, knowing their pedigree gives new insight into how they work.
(DOCUMENT GETTING THERE...WORK IN PROGRESS....BUT NOT FINISHED...ITS A BIG INTERESTING SUBJECT!)
Cryptography was about Life and Death
Now a days, with our Wifi, Hifi, and Segway, its hard to imagine the stark reality of what awaited the people who used these codes if they were cracked.
All of these codes were designed for non-trivial purposes: if deciphered, someone was going to die, and it probably wasn't going to be a nice death. If you were lucky and of high birth, you might be lucky enough to get your head cut off, but if you were anybody else, you generally were tortured for more information, and when you had spilt your guts a hundred times over and couldn't take anymore they would...continue.
Finally, after rotting in a dungeon, unable to move due to dislocated bones and broken feet, because you were accused and condemned as a spy or a traitor, you would end up being hung,quartered, burnt, branded, lynched, dismembered, or just impaled.
So it was a deadly serious business.
I just wanted to remind you of this before you just glance at the examples: they look so simple and its hard to imagine they worked (everything looks easy with hindsight) and its "just history"...but in some cases it was history that was not that long ago.
The full sentence passed upon those convicted of High Treason up to 1870 (140 years ago!) was as follows :
“That you be drawn on a hurdle to the place of execution where you shall be hanged by the neck and being (still) alive cut down, your privy members shall be cut off and your bowels taken out and burned before you, your head severed from your body and your body divided into four quarters to be disposed of at the King’s pleasure.”
(Although the last one was actually in 1820).
Img: Guy Fawkes being quartered, and disemboweled.
Before getting started, a little tour of the common words will be helpful - especially words like code and cipher, which are in interchangeable in the English language, but do have their distinct meanings.
- Cryptology/Cryptography is the science of secret writing.
- Cryptographer is a person who uses codes and ciphers to communicate with each other.
- A Cryptoanalyst is a person who uses logic and intuition to unravel the secrets and convert the ciphertext back into plaintext.
- Plaintext is the text that is to be encrypted.
- Ciphertext is the encrypted plaintext.
- An encryption algorithm is a general method of encryption used to convert plaintext into ciphertext.
- A key is the parameter used by the encryption algorithm to convert plaintext into ciphertext.
- Together, an algorithm and a key transform plaintext into ciphertext – or ciphers, for short.
- Codes are loosely applied to all forms of encryption, but technically there is a difference:
Code operate at the level of meaning; that is, words or phrases are converted into something else.
They do not work with algorithms, but work with code books instead. - Ciphers are distinct from codes, as they work at the level of individual letters, or small groups of letters, or even, in modern ciphers, with individual bits. Another way of stating this is that code works on the meaning, whereas ciphers transform elements below the semantic level, ie, below the level of meaning.
- A homophone is a ciphertext symbol that always represents the same plaintext symbol.
- A A polyphone is a ciphertext symbol that always represents the same set of plaintext symbols (generally at most 3).
- A PolyAlphabetic cipher is one that uses more than one cipher alphabet.
- A Substitution Cipher is one where the identity of an homophone (character) is kept the same, but its index within an alphabet is changed.
- A Transposition Cipher is one where the position of the original characters all retain their idenities (ie, ‘a’ still means ‘a’) but change there positions.
An example would be the word god, which can be transposed to odg, dgo, dog, ogd. - A MonoAlphabetic Cipher is a cipher that uses only one alphabet for its cipher text. Most ciphers up to Alberti's Cipher were MonoAlphabetic.
- An Alphabet is a standardized set of characters, or letters, each roughly representing a phoneme.
- But Syllabaries (see Rossignol's Great Cipher) represent syllables,
- And Logographies are sets where each symbol/character represents a word.
- Autokey Cipher
- Running Key Cipher
Cryptography has developed over several millennium, but not always linearly. With the vast distances between difference cultures, translations, etc. the dates at which various algorithms first appeared at not always linear in terms of time. Ideas were developed, then sometimes lost for centuries, only to pop up again, merged into new solutions.
Therefore, although I have tried to keep the ciphers linear in terms of dates, I have focused more on listing them by their type. That said, often a new cipher was actually a merge of two or more previous ideas -- classification in such instances is generally done by the newest part of the algorithm.
The Spartans invented the Scytale to encrypt military messages between military commanders on the field.
It consisted of a dowel of a specific diameter, around which would be wrapped a narrow strip of papyrus, parchment, or leather, and the message was written across the strips, in the axis of the stick itself, rather than the paper strips.
When unwound, the ribbon appeared to be covered by random characters.
The receiver would wrap the ribbon around his dowel -- of identical dimension -- in order to read the message.
PlainText:
Attack on the right flank tomorrow at dawn.
1000 of them 300 or us - fair odds. no?
CipherText written on
4 lines on sctale, wrapped 20 times:
[1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0]
|A|t|t|a|c|k| |o|n| |t|h|e| |r|i|g|h|t| |
|t|o|m|m|o|r|o|w| |a|t| |d|a|w|n|.| |1|0|
|0|0|0| |o|f| |t|h|e|m| |3|0|0| |o|f| |u|
|s| |-| |f|a|i|r| |o|d|d|s|,| |n|o|?| | |
Unwrapped, this ribbon would read as:
At0s to0 tm0 am coof krfa o i owtr n h ...etc.
Although first mentioned by Archilochus (7th Century BC), it was not until Apollonius of Rhodes (3rd Century BC) that it was described as a cryptographic device, and not until Plutarch (120 AD) did anyone describe how it was operated.
The key, if you will, is the diameter of the stick to use.
Another example of a MonoAlphabetic Transposition Cipher is the Rail Fence Cipher.
The oldest Rail Fence Ciphers laid out the plain text in a zigzap pattern to achieve the encryption:
Maybe Tom Sawyer Liked this cipher.
Zig Zagged Rail Fence on 3 lines:
M e S e k h i r
a b T m a y r i e t i c p e
y o w L d s h
Cipher Text (in blocks of 5):
MeSek hirab Tmayr ietic peyow Ldsh
Later, the zig zag pattern was dropped for a more straight forward vertical pattern that took less time to create and decrypt:
PlainText: Maybe Tom Sawyer Liked this cipher.
Columnar layout:
Mboaeidiie
aemwrktspr
yTSyLehch.
Cipher Text (in blocks of 5):
Mboae idiie aemwr ktspr yTSyL ehch.
The key, if you will, is the number of rows to write.
The columnar cipher takes the concept of a transposition cipher one step further, merging it with the concept of a keyed cipher (which we will expand on in a second).
First a keyword of non-repeating characters is chosen (eg: VICTORY) and then the message is written out in rows of a fixed length, equal to the length of the keyword. Once the plaintext message have been laid out, the letters are collected in the order determined by the keyword:
Keyword: V I C T O R Y
Order: 6 2 1 5 3 4 7
V I C T O R Y
6 2 1 5 3 4 7
- - - - - - -
PlainText:
T H E E N E M
Y I S M O V I
N G E A S T A
T D A W N A T
T A C K N O W
If each row is read, in the specified column order,
one now gets:
ETNEETM.SIOVMYI.EGSTANA.ADNAWTT.CANOKTW
Rearranged into blocks of 5 to
obfuscate the column count, the final cipher text is
as follows:
Cipher Text: ETNEE TMSIO VMYIE GSTAN AADNA WTTCA NOKTW
The key, if you will, is the keyword, which sets up the number of columns to use, and the order of the columns.
TODO
Substitution is a cryptographic technique where each letter of the plaintext message is replaced by a different letter. Each letter retains its original position in the message text, but the identity of the letter is changed. This type of technique was documented during Julius Caesar's Gallic Wars.
Just about the simplest MonoAlphabetic Substitution cipher is the Atbash Cipher, developed by the Hebrews about 500 BC, which simply reversed the alphabet:
Atbash :
Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher Alphabet: ZYXWVUTSRQPONMLKJIHGFEDCBA
So: 'HELLO' encrypts to 'SVOOL'
Many names of people and places are believed to have been deliberately obscured in the Hebrew Bible using this cipher.
ATBASH gets it's name from the fact that in the cipher, A becomes a letter than sounds like T, B becomes Sh: ATBSh.
A slightly more complicated example of a MonoAlphabetic substitution cipher is ROT13, a Caesar Cipher, which offsets the alphabet by a certain amount.
In the case of ROT13 case the offset is 13:
ROT13 (a Caesar Cipher):
Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher Alphabet: NOPQRSTUVWXYZABCDEFGHIJKLM
So: 'HELLO' encrypts to 'URYYB'
Since the offset could effectively be any number larger than or less than 0, it is a more powerful substitution cipher than the Atbash cipher (although admittedly not by much).
The key of the number of characters to offset the cipher alphabet (according to Suetonius, Julius Caesar used a key of of three).
A deranged alphabet cipher is any MonoAlphabetic substitution cipher whose cipher alphabet is out of order with its plaintext alphabet:
Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher Alphabet: FJYGKCTILHMSUBDVONRZWXAEPQ
PlainText: HELLO
CipherText: IKSSD
The problem with the basic deranged alphabet cipher is that you have to have a phenomenal memory to remember which letter goes with which. To solve that problem, the concept of a keyword is introduced.
This time, one starts by choosing a word that doesn’t have repeating letters, (‘eg: WORK’), and denoting it as the key.
The key is then written first, with then the rest of the alphabet following it, taking care to not use any letters already used within the key:
A Keyword based Deranged Alphabet, with key ='WORK':
Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher Alphabet: WORKABCDEFGHIJLMNPQSTUVXYZ
PlainText: 'HELLO'
CipherText: 'DAHHM'
Another way of creating a keyword based deranged cipher alphabet is to construct it as a square:
WORKA
BCDEF
GHILM
NPQST
UVXYZ
So that the alphabet becomes
ABCDE FGHIK LMNOP QRSTU VWXYZ
WBGPU OCHQV RDIQX KELSY AFMTZ
PlainText: HELLO
CipherText: HURRQ
In fact, this solution of using a keyword and square to lay out the cipher alphabet characters is the basis of several other systems, such as
The Greek scholar Polybius (203-120BC) (who also invented the wonderful concept of a balanced government) invented a signaling system that was intended to for torches and such, in order to communicate over large distances.
His system was to make a grid of letters and use their X and Y coordinates to communicate:
..12345
1 ABCDE
2 FGHIK
3 LMNOP
4 QRSTU
5 VWXYZ
A B C D E F G H...Z
11 12 13 14 15 21 22 23..55
One could communicate from shore to the ships and back with torches as the following example of the letter ‘Z’ demonstrates:
but once the concept of deranged alphabets was discovered, it wasn’t long before someone realized that Polybius' square could be combined with the concept of keyword based deranged alphabets to get something like the following:
..12345
1 NAVYB
2 CDEFG
3 HIKLM
4 OPQRS
5 TUWXZ
With the keyword ‘NAVY’ gives:
A B C D E F G H ...Z
21 51 12 22 32 42 52 13...55
So:
'HELLO' would be '13 32 43 43 14'
which packed into 5's would be:
13324 34313
This type of cipher has also been called the nock cipher has been used by several groups of prisoners to communicate across cells by tapping their drink mugs on the piping.and probably was used by Senator McCain while he was imprisoned (but since it is somewhat easy to crack, I doubt any communication was very secure).
Note: This became the basis for the ADFGVX cipher developed later.
In cryptology, when talking about substitution ciphers, the ciphers are described as converting from one ‘alphabet’ to another ‘alphabet’.
This usually is implied to be another alphabet of n (eg: 26 characters in English alphabet, or 24 in Latin, or other), just sorted in a different way.
In the following case the first character of the cipher alphabet is the letter ‘N’:
ROT13 (a Caesar Cipher):
Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher Alphabet: NOPQRSTUVWXYZABCDEFGHIJKLM
So: 'HELLO' encrypts to 'URYYB'
But a encryption algorithm’s output ciphertext alphabet doesn’t always have to be the same as the input plaintext’s alphabet: one could use any symbol as long as it was agreed upon by both parties.
During the Middle ages and later, several schemes were invented, and they are collectively known as PigPen Ciphers.
According to http://templis.free.fr/crypthog.htm the Templars had the following alternate alphabet, with which they were able to transfer credits between the 9000 Templar branches, without having to actually transfer funds (which was dangerous) – in essence the first banking system:
The above alternate alphabet was based on their cross of the 8 beatitudes.
There were many alphabets based on alternate alphabets: the following is one used by Heinrich Cornelius Agrippa von Nettelsheim (c: 1530 AD)
Here’s another variant of the alternate alphabet system, this one proposed by Gustavus Selenus (c: 1620 AD)
The PigPen Cipher (so named because the characters look somewhat like open pig pens) is a MonoAlphabetic substitution cipher, that uses alternate symbols to for its cipher alphabet, and was used by the Freemasons in the 1700’s for record keeping and correspondence.
Its primary characteristic is that letters were replaced by alternate alphabet symbols, chosen from a grid:
M E E T M E A F T E R S C H O O L B E H I N D T H E G Y M
Morse Code is a series of dots and dashes used to represent plain text characters, and does not use a code book, so is actually a cipher and not a code.
The Telegraph Code, which was transmitted using Morse Code, was a Code.
Trivia:
“In speed contests between expert Morse code operators and expert cellphone SMS text messaging users, Morse code has consistently won, leading to speculation that cellphone manufacturers might someday build interfaces for Morse code input[citation needed]. This interface would translate the Morse code input into text, so that it could be sent to any SMS-capable cellphone, thus the recipient would not need to know Morse code in order to read it.”
When typesetting came out one could get quite creative with all the various characters available, as this cipher, published by Edgar Allan Poe’s The Gold Bug short story):
53‡‡†305))6*;4826)4‡.)4‡);806*;48†8
¶60))85;1‡(;:‡*8†83(88)5*†;46(;88*96
...
The actual symbols can be quite fanciful, as the following set of dancing men (used by Sherlock Holmes in The Adventure of the Dancing Men) demonstrate:
The cipher alphabet can be numbers, or pairs of numbers, such as the following ASCII table, which encodes every plaintext character as a number:
ASCII Hex Encoding:
PlainText: H E L L O
CipherText: 48 45 4C 4C 4F
The only criteria really is that the symbols are understood on both ends of the communication.
The problem with all these kind of simple MonoAlphabetic substitution ciphers, whether based on the same alphabet as the plaintext alphabet, or whether based on an alternate alphabet such as the pigpen ciphers, there is a fundamental weakness, which was first noticed and expressed 1200 years ago by
Abu Yusuf Yaqub ibn Ishaq ibn as-Sabbah ibn 'Omran ibn Ismail al-Kindi. He suggested that these types of substitution encryped messages could be cracked by applying Frequency analysis.
His observation, and therefore suggestion on how to crack these types of messages, was that in every language, certain letters (such as e, t, a, etc. in English ) show up far more often than others. Once you know that, finding the most often used character in a substitution cipher is usually enough to crack several letter (e, maybe t’s). And it doesn’t stop there: with the vast amounts of other frequency statistics that can be found (eg: at letterfrequency.org), and knowing the context of the message, you can basically decrypt any simple substitution encrypted message.
Here’s a link to a very short and easy to understand example on how to use Frequency Analysis to solve the Sherlock Holmes’ dancing men message.
Note:
Frequency Analysis, in practice, is actually more not as clear cut as the above pseudo-rules: the frequencies change depending on the trade of the communication (ie, certain combinations of letters are seen more in medical texts than military texts, and vice versa.)
In a homophonic substitution cipher, each plaintext letter is replaced with several different ciphertext letters. Generally speaking, as the frequency of the letter increases, the number of potential ciphertext letters would increase proportionately. For example the letter "E" may have a frequency of 12% for most communications and would potentially have 12 different ciphertext letters representing it. This would complicate simple attempts at frequency analysis because an encrypted message would represent a single letter "E" with 12 distinct ciphertext letters.
To counter attacks using Frequency Analysis the next significant development was the idea of using two or more cipher characters for each plaintext (ie: source) character.
For example, the letter ‘'T’ could be represented by ‘S’, and ‘@’ , using more characters for the higher frequency characters (eg: t, e, a, etc.), and less characters for the lower frequency plaintext characters. In this way, the frequency distribution is flattened, making analysis more difficult.
In addition, certain symbols were used to represent words.
Wikipedia states that the first mention of such a system was by Ahmad Abd Allah al-Qalqashandi (1355-1418) in 1412 – although this appears to be contradicted by the appearance of a the Michele Steno document (see below). Possibly the distinction is that 1412 was the first publication (not the first use).
One of the first examples we have of a homophonic substitution in Europe is by the Doge of Venice, Michele Steno, who used a system that introduced several characters for vowels.
His system not only used several randomly chosen cipher characters to represent a single vowel in the plaintext, but his system also included null characters for purely obfuscation reasons, as well as characters to represent complete, common, words.
the 1500’s saw many examples of homophonic substitution ciphers, with fanciful characters, used to counter frequency analysis to varying degrees, and sometimes the inclusion of other concepts such as null characters, as well characters for complete common words.
Philibert Babou’s Cipher is a very good example of these concepts:
Trivia:
Unfortunately for Babou, while he was working day and night as cryptographer for his king, his king decided to take his wife as his lover
One direction that homophonic substitution ciphers led to was very fanciful and pretty alphabets, since they had to now have more than just 26 characters, such as the one most probably (not solved yet) used in this message sent to the San Francisco Examiner on November 8, 1969 by the Zodiac Killer:
Some Book Ciphers can be homophonic substitution ciphers.
Note that when dealing with book ciphers its important to distinguish between book codes and book ciphers: if the numbers refer to words (codewords), then they are codes, but if the numbers refer to letters, then they are ciphers.
And if they are ciphers, they are either plain substitution ciphers, (numbers replacing the characters), or homophonic substitution ciphers if the numbers are constantly shifting (ie, if ‘a’ can be represented by an ‘a’ on page 10 as well as page 16, 21, etc.)
An interesting variant on Book Codes and Book Ciphers is the Nomenclatur Code.
Named after the public official who announced the titles of visiting dignitaries, the first Nomenclature Codes worked from a Codebook containing only the names of these visiting dignitaries:
1 Snoopy
2 Charlie Brown
3 The Wizard of Id
4 The King of Siam
PlainText: Today, Charlie Brown and the Wizard of Id stopped in on the king king.
CipherText: Today, 2 and 3 stopped in on 4.
Later versions of Nomenclatur codes referred to not only names of dignitaries, but included many common words and places as well.
But some of the solutions classified as Nomenclatur Codes went far beyond this, and became homophonic substitution ciphers instead -- and not all of them were based on alphabets either: Rossignol's Great Cipher, used by Louis XIV of France, used a large 'codebook' which was actually a table of 587 syllables (so this would technically not be a homophonic or MonoAlphabetic substitution cipher).
The Straddling Checkerboard Cipher is a MonoAlphabetic substitution cipher that builds on concepts introduced by Polybius' Square Cipher, adding fractionalization.
The first row is set up with the eight highest frequency letters (mnemonic ESTONIA-R), leaving two blank spots. It has no row label.
The second and third rows are labeled with whichever two digits didn't get a letter in the top row, and then filled out with the rest of the alphabet (this can be scrambled by a key word, or simply done in order - relying on another stage of the cipher for security).
Since there are 30 slots in our grid, and we missed two letters in the first row, there will end up being two spare in the other rows. It doesn't matter where these spares go, so long as sender and receiver use the same system.
0 1 2 3 4 5 6 7 8 9
E T A O N R I S
2 B C D F G H J K L M
6 P Q U V W X Y Z .
PlainText: H E L L O
CipherText: 3 0 28 28 4 : 30282 84 (rearranged into blocks of 5)
Note: why its classified as a homophonic cipher, I'm not sure.
Although homophonic ciphers go a long way towards providing a robust defense against Cryptoanalysts using intuition and frequency analysis to crack the cipher, more can be done.
A powerful solution is to not just use one cipher ‘alphabet’ (the set of characters to use when encrypting), but more than one. This actually sounds more complicated, than it is.
The Alberti cipher by Leon Battista Alberti was basically two rings of letters connected together by a central spindle: you chose the letter you wanted to encrypt (eg: A) on the outer alphabet,which aligned with a letter on the inner letter (eg: N, if we are offset by 13 letters), but at arbitrary moments (eg after two sentences worth), you rotate the disk to a new offset. Although the code was trivial to break (the offset was indicated to the receiver by Capitalization of the letter which somewhat gave the game away) the idea of changing the offset was radical and ground breaking.
In fact, the Alberti Cipher was the first ever PolyAlphabetic substitution cipher, and it was the peak of cryptography at that time.
The Alberti Cipher initially consisted of two Caesar Shift ciphers performed on the plain text, alternating at random between the two shifts. The change between ciphers was marked by the Capitalization of the first letter of the section of text to be encrypted with the new shift. The action of a Caesar cipher is to move each letter a number of places down the alphabet. ...
The cipher was later made more complicated by using 3 or 4 different Caesar shifts alternating between them in alphabetical order, again highlighted by a Capital Letter.
Finally, Alberti started using more random substitutions - Affine Shifts and Keyword shifts, but the substitution cipher would be shifted about, once again denoted by the presence of a capital. The Affine cipher is a special case of the more general substitution cipher. ...
PlainText Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Alphabet used for the first (eg) 2 characters:
Cipher Alphabet: DEFGHIJKLMNOPQRSTUVWXYZABC
Alphabet used for the next (eg) 2 characters:
Cipher Alphabet: FGHIJKLMNOPQRSTUVWXYZABCDE
Alphabet used for the next (eg) 2 characters:
Cipher Alphabet: JKLMNOPQRSTUVWXYZABCDEFGHI
PlainText: 'HE LL O'
CipherText: KH QQ X
The first publication in Latin dealing with cryptography (Polygraphiae libri sex, Ioannis Trithemii abbatis Peapolitani, quondam Spanheimensis, ad Maximilianum Ceasarem) was published posthumously in 1518 by Johannes Trimethius (1462-1516).
One of the systems demonstrated was based on a matrix of 24 by 24 characters (he was using an alphabet that didn’t use a j or v).
To use it, one starts off with plaintext message to encrypt (eg: 'ALCHEMY') and finds its first character ('A') on the first row (the 'a' row, which also happens to be the reference line). Therefore, ‘A’=’a’.
For the next plaintext character ('L'), the equivalent ciphertext character will be the character at the intersection of the the next row down (the 'b' row) and the 'L' on the reference line. This will be the cipher character 'm'.
For the next plaintext character ('C'), the equivalent ciphertext character will be the character at the intersection of the the next row down (the 'c' row) and the 'C' on the reference line. This will be the cipher character 'e'.
And so on:
PlainText: ALCHEMY
RowUsed: abcdefg
CipherText: amelird
Notice how each row in the matrix is incrementing the offset of the alphabet -- in essence a Caesar Shift of n.
What is apparent from this system is that it is a substitution cipher that for each character being encrypted, a new alphabet is selected.
This is similar to the Alberti Cipher, except that instead of spinning the disk by a random amount after a random amount of characters, this one's offset is incremented by 1, after every character.
This is called a key progression.
Notice as well that it is obviously easier to crack than Alberti’s Cipher, once the shift by 1 system is figured out, but Trimesthius’ Cipher is historically significant as it not only introduced for the first time the concept of an auto-incrementing key progression, but also formed the basis on which Giovan Battista Bellaso (1553) formed his cipher (which is incorrectly known as the Vigenère Cipher).
sss
Encryption is performed by using an agreed-upon phrase called countersign, placed over the plaintext.
Then, working with the table, one finds the row whose title contains the letter in the countersign.
Once the row is found, one uses the letter above or below the one identified by the cipher text.
In other words, in the following example, for the first letter of the Countersign ('S') we look for the row whose label is 'ST'.
Once the row is found, we search for the letter 'M'. It is above the letter 'o', so 'o' is our first cipher character.
For the next character, we find the row whose title contains the letter 'K' ...(since K is in between I and L, I'm going to use the 'IL' row).
Once the row found, we search for the letter 'E' on it. It is above the letter 'p', so 'p' is our next cipher character.
For our third character, we find the row whose title contains the letter 'Y' ...and find the 'YZ' row.
Once the row found, we search for the letter 'E' again, and this time find it is above the letter 's'.
Countersign: SKYSIGALSKYSIGALSKY
Plaintext: MeetMeAtTheFountain
CipherText: opsexyniessudcaiptm
Note how even though the plaintext character is the same for both the 2nd and 3rd characters (e) of the plaintext, their equivalent cipher text is different.
“in combining the best of his two predecessors – the mixed alphabet of Alberti and the letter-by-letter encryption of Trimethius – with his own brilliant idea of a literal key, he created the modern concept of PolyAlphabetic substitution” [Kahn, 1973].
Trivia:
This cipher is that it is perfectly compliant with Kerckhoffs’ principle.
Vigenère's Cipher is almost identical in concept to Bellaso's cipher, except that uses a grid of alphabets, each shifted by one more on each row.
The strength of the cipher lies in the fact that a single letter can be represented in several different ways because 26 distinct alphabets are used and this poses a challenge to traditional frequency analysis techniques.
For a while it was considered as le chiffre indéchiffrable (French for 'the unbreakable cipher') -- which turned out to be totally false: Charles Babbage crached it in 1854, but Friedrich Kasiski was the first to publish a successful attack, in 1863.
a b c d e f g h i j k l m n o p q r s t u v w x y z
a A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
b B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
c C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
d D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
e E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
f F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
g G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
h H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
i I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
j J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
k K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
l L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
m M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
n N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
o O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
p P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
r R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
s S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
t T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
u U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
v V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
w W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
x X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Countersign: FISHFISHFISHF
PlainText: MeetMeTonight
CipherText: QLVAQLKURPXNX
In these, the plaintext letters are encrypted in groups not by themselves. This partly helps to flatten the frequency distribution of the letters - 'e' being far more common than 'z' for example. If the letters are paired, there are less distinct common groups, although they do still appear - 'st' is more likely to appear than 'df' in English.
In a Polygraphic substitution cipher, plaintext letters are substituted in larger groups, instead of substituting letters individually. The first advantage is that the frequency distribution is much flatter than that of individual letters (though not actually flat in real languages; for example, 'TH' is much more common than 'XQ' in English). Second, the larger number of symbols requires correspondingly more ciphertext to productively analyze letter frequencies.
della Porta proposed a 20 x 20 tableau (for the 20 letters of the Italian/Latin alphabet he was using) filled with 400 unique glyphs representing pairs of characters.
The system was impractical and probably never actually used.
If both letters are the same, add an X between them. Encrypt the new pair, re-pair the remaining letters and continue.
If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively, wrapping around to the left side of the row if necessary. For example, using the table above, the letter pair GJ would be encoded as HF.
If the letters appear on the same column of your table, replace them with the letters immediately below, wrapping around to the top if necessary. For example, using the table above, the letter pair MD would be encoded as UG.
If the letters are on different rows and columns, replace them with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important - the first letter of the pair should be replaced first. For example, using the table above, the letter pair EB would be encoded as WD.
The Playfair cipher uses a 5 by 5 table containing a key word or phrase:
K E Y W O
R D A B C
F G H I J
L M N P S
T U V X Z
Plaintext: HELLO
CipherText: HE LL OX (split into 2s, append filler 'X')
HE LX LO (oops 2 are the same...insert an 'X')
GY PT SK (for each line, find the perpendiculars)
Trivia:
Playfair was in military use from the Boer War through World War II.
Several other practical polygraphics were introduced in 1901 by Felix Delastelle, including the bifid and four-square ciphers (both digraphic) and the trifid cipher (probably the first practical trigraphic).
The Hill cipher, invented in 1929 by Lester S. Hill, is a Polygraphic substitution which can combine much larger groups of letters simultaneously using linear algebra.
Each letter is treated as a digit in base 26: A = 0, B =1, and so on. (In a variation, 3 extra symbols are added to make the basis prime.) A block of n letters is then considered as a vector of n dimensions, and multiplied by a n x n matrix, modulo 26. The components of the matrix are the key, and should be random provided that the matrix is invertible in 
(to ensure decryption is possible). Astonishingly, a Hill cipher of dimension 6 was once implemented mechanically!
Unfortunately, the Hill cipher is vulnerable to a known-plaintext attack because it is completely linear, so it must be combined with some non-linear step to defeat this attack. The combination of wider and wider weak, linear diffusive steps like a Hill cipher, with non-linear substitution steps, ultimately leads to a substitution-permutation network (e.g., a Feistel cipher), so it is possible—from this extreme perspective—to consider modern block ciphers as a type of polygraphic substitution.
Kerchoff was a Dutchman who lived in Paris who published two essay in the Journal of Military Science.
suggested an encryption pattern that assumes that all parts of the system are known -- except the secret key.
The law was one of six design principles laid down by Kerckhoffs for military ciphers :
- The system should be, if not theoretically unbreakable, unbreakable in practice.
- Compromise of the system should not inconvenience the correspondents ("There is no secrecy in the algorithm - It is all in the key.")
- The key should be memorable without notes and should be easily changeable
- The cryptograms should be transmittable by telegraph
- The apparatus or documents should be portable and operable by a single person
- The system should be easy, neither requiring knowledge of a long list of rules nor involving mental strain
Until well past WWII his concepts were considered theoretical at best.
The Zimmerman telegram was a secret telegram which included proposals for a German alliance with Mexico. The telegram was intercepted and decrypted by the British Government.
The German ADFGVX cipher was the first cipher used by the German Army during World War I. This was a fractioning transposition cipher which combined a modified Polybius square with a single columnar transposition used to encode a 36 letter alphabet (26 letters plus 10 digits).
1919 - 1945 AD: Mechanical PolyAlphabetic Substitution Ciphers (Enigma, etc.)
Because Kerchoff's Principles were considered un obtainable, things didn't change very rapidly, and cryptography basically remained based on PolyAlphabetic substitution ciphers -- only much more complicated now that they could be mechanized.
In 1919 4 patents for rotor cipher machines were applied for. The most important of the resulting machines was the Enigma, especially in the versions used by the German military from approximately 1930. The Allies also developed and used rotor machines (eg, SIGABA and Typex).
All of these were similar in that the substituted letter was chosen electrically from amongst the huge number of possible combinations resulting from the rotation of several letter disks. Since one or more of the disk rotated mechanically with each plaintext letter enciphered, the number of alphabets used was substantially more than astronomical. Early versions of these machine were, nevertheless, breakable. William F. Friedman of the US Army's SIS early found vulnerabilities in Hebern's rotor machine, and GC&CS's Dillwyn Knox solved versions of the Enigma machine (those without the "plugboard") well before WWII began. Traffic protected by essentially all of the German military Enigmas was broken by Allied cryptanalysts, most notably those at Bletchley Park, beginning with the German Army variant used in the early 1930s. This version was broken by inspired mathematical insight by Marian Rejewski in Poland.
Trivia:
No messages protected by the SIGABA and Typex machines were ever, so far as is publicly known, broken.
<<<Invented by Arthur Scherbius, Enigma was Germany's main cryptographic technology during WW II. Following the decryption of the Zimmerman note during World War I and the effects that weak ciphers had on the war's outcome, Germany was looking for "the unbreakable cipher" and was interested in leveraging automation and the use of machinery to replace traditional paper and pencil techniques. The Enigma machine consisted of a basic keyboard, a display that would reveal the cipher text letter, and a scrambling mechanism such that each plain text letter entered as input via the keyboard was transcribed to its corresponding cipher text letter. The machine was modular in design and multiple scrambling disks were employed to thwart attempts at frequency analysis and these scrambling disks and there particular positioning inside enigma emulated many different cipher alphabets. To decipher a message, the receiver require a code book (shared by both the sender and receiver) detailing all the specific scrambler settings for the day and would also have an identical enigma machine. Breaking Enigma was crucial to ending World War II and it was eventually broken due in large part to the work of Marian Rejewski, a polish statistician, mathematician, and code breaker. Although Rejewski never broke the Enigma, he transferred all his research to the English and the French weeks before Germany invaded Poland. Eventually, Alan Turing and the code breakers at Bletchley used Rejewski's work to build Bombes which were electromechanical machines that were designed specifically to break Enigma.
>>>
Good tutorial on how Enigma worked: printable and http://www.howstuffworks.com/framed.htm?parent=code-breakers.htm&url=http://www.codesandciphers.org.uk/enigma/index.htm
We always hear about the allies at Bletchley Park cracking Enigma, the German encoding device, but they probably wouldn’t have gotten anywhere without this humble talents of Marian Rejewski, the story of how he and a couple of other polish cryptographers did all the hard work before the war even started, is a fun quick read.
Just to put it in context:
"The solution", historian David Kahn writes, "was Rejewski's own stunning achievement, one that elevates him to the pantheon of the greatest cryptanalysts of all time". Rejewski used a mathematical theorem that one mathematics professor has since described as "the theorem that won World War II"
1953: The VIC Cipher
http://www.answers.com/topic/vic-cipher
<<<
The VIC cipher was a pencil and paper cipher used by the Soviet spy Reino Häyhänen, codenamed "VICTOR".
It was arguably the most complex hand-operated cipher ever seen. Although certainly not as complex or secure as modern computer operated stream ciphers or block ciphers, in practice messages protected by it resisted all attempts at cryptanalysis by at least NSA (and perhaps other organizations such as GCHQ) from its discovery in 1953 until Häyhänen's defection in 1957.
The VIC cipher can be regarded as the evolutionary pinnacle of the Nihilist cipher family. It has several components, including mod 10 chain addition (a lagged Fibonacci generator, a recursive formula used to generate a sequence of pseudorandom digits), a straddling checkerboard, and a disrupted double transposition. Until the discovery of VIC, it was generally thought that a double transposition alone was the most complex cipher an agent, as a practical matter, could use as a field cipher.
Link to demonstration of the math involved: http://www.quadibloc.com/crypto/pp1324.htm
And then there was Claude Shannon. In 1949 he published the paper Communication Theory of Secrecy Systems in These, in addition to his other works on information and communication theory established a solid theoretical basis for cryptography and for cryptanalysis. And with that, cryptography more or less disappeared into secret government communications organizations such as the NSA, GCHQ, and equivalents elsewhere. Very little work was again made public until the mid '70s, when everything changed.
Claude Shannon proved, using information theory considerations, that any theoretically unbreakable cipher must have keys which are at least as long as the plaintext, and used only once: one-time pad.
One Time Pad
The One Time Pad is a technique that offers 'perfect theoretical secrecy' by using a truly random key only once per communication. Imagine a sender and receiver, each having matching pads filled with hundreds of pages of unique keys composed of truly random letters. The sender would encrypt a message using a Vigenère square and the first key in his pad and the receiver would decrypt it in the same way. At this point, both the sender and receiver would discard the first page of their pads (destroy the last used key) and continue using new keys for future messages. This offers perfect secrecy because even if a single key is compromised, it does not reveal anything about future or past transmissions. The strength of the technique lies in randomness and one time use of the keys.
Claude Shannon described how if the ciphertext, key, and plaintext are changing at a consistent rate, you are have achieved perfect secrecy in his 1949 paper Communication Theory of Secrecy Systems.
Lucifer was a symmetric encryption algorithm created by Horst Feistel in the 1970's while working at IBM. The scrambling technique of Lucifer was quite involved and begins with translating the plain text string to binary format. Next, the binary string is shuffled and divided into 64 bit blocks and encryption happens on a per block basis. Each of these 'blocks' are split into 2 32 bit blocks and they are named "Left(0)" and "Right(0)". The "Right(0)" block is put through a mangle function which rearranges the binary numbers using a fairly complex substitution cipher. The "Right(0)" block is then added to the "Left(0)" block to create a new half block called "Right(1)" and the original "Right(0)" block is renamed Left(1). This series of steps is called a "Fiestel Round" and is repeated 16 times in total. The mangler function can change and is determined by a key the sender and the receiver agree upon. A modified version of Lucifer was adopted as the American standard for encryption known as DES or the Data Encryption Standard. The main difference between Lucifer and DES was that the NSA limited DES to 56 bit keys to balance national security interests against personal and corporate privacy needs.
British Intelligence inventors of PKC
James Ellis, Clifford Cocks, Malcolm Williamson stated as the original inventors of public key cryptography. This fact was originally kept secret until after 1976 when Diffie and Hellman take credit for discovering PKC.
Whitfield Diffie and Martin Hellman were pioneers in the fields of asymmetric cryptographic techniques. Prior to their work, most encryption was symmetric and involved the send and receiver sharing a key to secure communications. They focused on one-way functions which is simple to run and very difficult to undo. The Diffie-Hellman key exchange enables sender and receiver to establish a secret key publicly without any prior key sharing. This asymmetric key system is one in that the encryption and decryption keys are not identical and revolutionized cryptography for years to come. For the first time in history, Alice and Bob could secure communications without any prior interaction. This idea was later incorporated into RSA named after Rivest, Shamir, and Adleman and is a common cryptographic technique on the Internet today.
Further Reading:
Pyramid (Magic Square) Cipher
Atbash (Hebrew) Cipher
Christian Cross (Greek) Cipher
Futhark (Runic) Cipher
Templar Cipher
Rosicrucian Cipher
Freemason Cipher
Knight's Tour Cipher
Dice Cipher
EXCELLENT FOR MODERN PART:
http://www.jproc.ca/crypto/crypto_hist.html GREAT
History_of_Cryptography
http://en.wikipedia.org/wiki/History_of_cryptography
Essential to show XOR: ttcodep.html *http://www.vectorsite.net/ttcodep.html
https://www.securetrust.com/resources/crypto-uni/
http://books.google.com/books?id=N11_m8SJGCMC
&pg=PT34&lpg=PT34&dq=Polybius+cipher+invented&source=web
&ots=_yCnMmz77Z&sig=tPJ_65vDW_rwpwlMa107_rP_Ihw
&hl=en&sa=X&oi=book_result&resnum=7&ct=result#PPT88,M1
http://www.apprendre-en-ligne.net/crypto/menu/index.html