Теория Информации

Encryption Algorithms
Transposition Cipher
A lot of codes are simple in design. Just by changing the order of words, letters, or the way read them can turn the message into secret code. The simplest examples of the Transposition Ciphers are:
Lumping Words (Format)
Get rid of spaces and returns to lump words together. Use upper case to make the code harder to read and decode.
Ciphertext: THISISHARDCODEFORMANYPEOPLE Message: THIS IS HARD CODE FOR MANY PEOPLE
Character Bloks
Block letter of a message by 2,3 or more characters.
Ciphertext: TH IS IS HA RD CO DE FO RM AN YP EO PL E Message: THIS IS HARD CODE FOR MANY PEOPLE
Backwards English
Writing words, sentences, or entire message backwards can be very confusing!
Ciphertext: SIHT SI DRAH EDOC ROF YNAM ELPOEP Message: THIS IS HARD CODE FOR MANY PEOPLE
Reading SIHT backwards yields the answer THIS.

Encryption Algorithms
Transposition Cipher
Transposition cipher rearrange characters according to some scheme. This rearrangement was classically done with the aid of some type of geometric figure. Enciphering procedure consists of two steps as shown next:
Plaintext
Figure
Ciphertext
Write-in
Take-off
First, the plaintext was written into the figure according to some “Write-in” path, then the ciphertext was taken off the figure according to some “Take-off” path.
Example 2.1. Suppose that the plaintext CRYPTOGRAPHY is written into 3 rows by 4 columns matrix by rows as follows:
1 2 3 4
C R Y P
T O G R
A P H Y
If the columns are taken off in the order 3-1-4-2, the
resulting ciphertext is YGHCTAPRYROP.

Encryption Algorithms
Transposition Cipher
Many transposition ciphers permute the characters of the plaintext with a fixed period d. The key for the cipher is given by the pair K=(d,f), where d is the number of characters within the block and f is function of permutation. Thus, a plaintext message
M=m1 ,..., md md+1,..., m2d ,...
is enciphered as
EK(M)=mf(1) ,..., mf(d) mf(d+1),..., mf(2d) ,...
Decipherment uses the inverse permutation.
Example. Suppose that d=4 and the function of permutation f is
i 1 2 3 4
f(i) 3 1 4 2
thus, the plaintext is divide into the blocks with 4 bits each, then for every block first plaintext character is moved to the second position, the second character to the fourth position and so forth.
M=CRYP TOGR APHY
Ek(M)=YCPR GTRO HAYP

Encryption Algorithms
Transposition Cipher
Like columnar transposition, periodic permutation cipher can be viewed as transpositions of the columns of a matrix in which the plaintext is written in by rows.
Example. Suppose that d=12 and the geometric figure is matrix 4 column by 3 rows and function of columns permutation f has a form
i 1 2 3 4
f(i) 3 1 4 2
M= HERE IS A SECRET MESSAGE ENCIPHERED BY TRANSPOSITION⇒
Ek(M)=RAR HIE ESE ESC EGC TSE SEI MAN EBA PET RYN HDR OI SIN SO PT

Encryption Algorithms
Transposition Cipher
Using a key word or phrase, such as, for example CONVENIENCE, assign a number to each letter in the word using this rule: the numbers are assigned starting with 1, and they are assigned first by alphabetical order, and second, where the same letter appears twice, by position in the word.
Example. Thus: the plaintext message M=HERE IS A SECRET MESSAGE ENCIPHERED BY TRANSPOSITION
Produces next ciphertext C=HECRN CEYI ISEP SGDI RNTO AAES RMPN SSRO EEBT ETIA EEHS

Encryption Algorithms
Transposition Cipher
Example. Another method of transposition is a Variant of column transposition that produces a different cipher:
C=HEESPNI RR SSEES EIY A SCBT EMGEPN ANDI CT RTAHSO IEERO
This method has the advantage of dividing the text being transposed in a more irregular fashion than ordinary columnar transposition.

Encryption Algorithms
Transposition Cipher
Another interesting form of transposition is the "turning grille", used by Germany during the First World War.
A square grille, divided into a grid of squares, one-quarter of which are punched with holes, is placed over a sheet of paper. The message is written on the paper through the holes, and then the grille is rotated by 90 degrees, and then the message continues to be written, as the grille is turned through all four possible positions.
The trick to designing such a grille is to divide the grille into quarters, numbering the squares in each quarter so that as the grille is rotated, corresponding squares have the same number. Then, choose one square with each number for punching.
Example. Example of a turning grille and its use:
Layout:
Grid numbering:

Encryption Algorithms
Transposition Cipher
Example. Example of a turning grille and its use for message: M=HERE IS A SECRET MESSAGE WRITE
First Round
Second Round

Encryption Algorithms
Transposition Cipher
Example. M=HERE IS A SECRET MESSAGE WRITE
Third Round
Fourth Round
C=HEEMS ECWER RSEIR SSEIR SSEIT EAATG

Encryption Algorithms
Simple Substitution Ciphers
Simple substitution cipher replace each character of plaintext with a corresponding character of ciphertext; a single one-to-one mapping from plaintext to ciphertext characters is used.
A simple substitution cipher replace each character of an ordered plaintext alphabet, denoted as Α, with the corresponding character of an ordered cipher alphabet, denoted of C. Suppose A is an n-character alphabet {a0,a1,...,an}, then C is an n-character alphabet {f(a0),f(a1,)...,f(an)}, where f:A-->C is a one-to-one mapping of each character of A to the corresponding character of C. The key K to the cipher is given by C or, equivalently, by the function f.
To encipher, a plaintext message M=m1m2... is written as the ciphertext message EK(M)=f(m1)f(m2)...
Example 2.7. Suppose that f maps English alphabet A={a0,a1,...,an} into the cipher alphabet C as:
A:ABCDEFGHIJKLMNOPQRSTUVWXYZ
C:YARMOLIKBCDEFGHJNPQSTUVWXZ
then the plaintext CRYPTOGRAPHY is enciphered as: EK(M)=RPXJSHIPYJKX

Encryption Algorithms
Simple Substitution Ciphers
Compass Cipher-A Method for Alphabet Substitution
There are lots of ways to create a compass cipher key.
The arrows show the direction used to fill in the compass lines. Once you have all the letters written into your compass write out the letters, from outside in and then combine all of the letters into a long line. Copass Key: YUQMEAZVRNJFBWSOKGCXTPLHD

Encryption Algorithms
Simple Substitution Ciphers
Letter Spokes Cipher Clock
It’s another way of making up a random alphabet substitution wheel. The letter spokes cipher clock, developed by Angie Wimer, resemble the spokes of a wheel. According to his idea you have to simply take each letter in the wheel and line it up with another letter somewhere else in the wheel.
See if you can decipher the encrypted message “ROT” by making the use of the Letter Spokes clock below the answer is “BAD”.

Encryption Algorithms
Simple Substitution Ciphers
Alphabet & Word Correlated Ciphers.
Sometimes keywords are used to help encipher a message. By writing out a sentence(s) that contains all the letters of the alphabet you can correlate plain alphabet letters within a word found in the keyword phase to make the cipherring a bit more difficult to decipher.
The keyword phrase “The quick brown fox jumps over the lazy dog” contains all the letters of the alphabet. Even though some letters appear more than once it shall serve as a keyword phrase because it still contains all the letters of the alphabet. To get started, write out your keyword phrase and number each word:
Plaintext: Johnson is a spy
Ciphertext:

Encryption Algorithms
Simple Substitution Ciphers
Cipher based on shifted alphabet (“direct standard alphabets”) shift the letters of the alphabet to the right by k positions, modulo the size of the alphabet according to the equation
f(a)=(a+k) mod n,
where n is the size of the alphabet and a denotes letter and its position in A.
For the English alphabet
0-A, 1-B, 2-C, 3-D, 4-E, 5-F, 6-G, 7-H, 8-I, 9-J, 10-K, 11-L, 12-M, 13-N, 14-O, 15-P, 16-Q, 17-R, 18-S, 19-T, 20-U, 21-V, 22-W, 23-X, 24-Y, 25-Z.
Under the Caesar cipher, our plaintext CRYPTOGRAPHY is enciphered by
f(a)=(a+3) mod 26,
then EK(M)=FUBSWRJUDSKB.
There are more complex transformation of the plaintext alphabet. Ciphers based on multiplications (“decimations”) are shown below
f(a)=ka mod n,
where k and n are relatively prime so that the letter of the alphabet produce a complete set of residues. For the plaintext CRYPTOGRAPHY and k=3 we will get f(a)=3a mod 26, and EK(M)=GZUTFQSZATVU.

Encryption Algorithms
Simple Substitution Ciphers
Addition (shifting) and multiplication can be combined to give an affine transformation
f(a)=(ak1+k0) mod n,
where k1 and n are relatively prime.
Higher-order transformations are obtained with polynomial transformations of degree t:
f(a)=(atkt+at-1kt-1+...+ak1+k0) mod n,
Some substitution cipher use nonstandard ciphertext alphabet. The Churchyard cipher shown below was engraved on a tombstone in Trinity Churchyard, New York, in 1794.
A* B* C* K** L** M** T U V
D* E* F* N** O** P** W X Y
G* H* I-J* Q** R** S** Z
What is the plaintext corresponding to the next ciphertext?
** * ** * ** * * **
* * * *

Encryption Algorithms Single-Letter Frequency Analysis
Simple substitution cipher are generally easy to break in a ciphertext-only attack using single-letter frequency distributions. The letters of English alphabet can be divided into subsets of high, medium, low, and rare frequency as shown below:
high: E T A O N I R S H
medium: D L U C M
low: P F Y W G B V
rare: J K Q X Z
By comparing the letter frequencies in a given ciphertext with the expected frequencies, a cryptoanalyst can match the ciphertext letter with the plaintext letters. Diagram and trigram distributions are also helpful.
Ciphers based on shifted alphabets are usually easy to solve, because each ciphertext letter is a constant distance from its corresponding plaintext letter. Cipher based on affine transformations
f(a)=(ak1+k0) mod n,
are somewhat trickier. To determine the values of k1 and k0 the system of two linear equations have to be solved. So, for the two pairs of (f(a),a): (10,4), (19,9) we have two equations
10=(4k1+k0) mod 26,
19=(9k1+k0) mod 26,
then subtracting (1) from (2) we get 9=5k1 mod 26. The last equation can be solved to determine k1 =7. Substituting in (1) value of k1 gives (28+k1 ) mod 26=10.

Encryption Algorithms Homophonic Substitution cipher
A homophonic substitution cipher maps each character a of the plaintext alphabet into a set of ciphertext elements f(a) called homophones. A plaintext message M=m1m2... is enciphered as C=c1c2..., where each ci is picked at random from the set of homophones f(mi).
Example. Let the English letters are enciphered as integers between 00 and 99, where the number of integers assigned to a letter is proportional to the relative frequency of the letter, and no integer is assigned to more than one letter. A possible assignment of integers to the letters in the message CRYPTOGRAPHY are show below (integer assignment for the remaining letters of the alphabet are not given)
letter Homophones
A 23, 25, 97, 95, 81, 33, 12, 11
C 44, 77, 34, 51
G 87, 41
H 59, 90, 00, 26
O 66, 87, 02, 15, 22, 09, 83, 54
P 04, 58
R 38, 07, 94, 30, 56, 67
T 55, 71, 72, 80, 01, 12, 29, 50, 68
Y 88
One possible encipherment of the message is:
C= 77 07 88 58 72 54 41 30 97 04 00 88

1.Single letter frequency distributions.
Encryption Algorithms Homophonic Substitution cipher

Encryption Algorithms Beale Ciphers
The Beale cipher is an example of a homophonic substitution cipher. The key is the Declaration of Independence. The words of the Declaration are numbered consecutively as shown below
Declaration of Independence (first 100 words)
01 When, in the course of human events, it becomes necessary
11 for one people to dissolve the political bands which have
21 connected them with another, and to assume among the Powers
31 of the earth the separate and equal station to which
41 the Laws of Nature and of Nature’s God entitle them,
51 a decent respect to the opinions of mankind requires that
61 they should declare the causes which impel them to the
71 separation. We hold these truths to be self-evident; that
81 all men are created equal, that they are endowed by
91 their Creator with certain unalienable rights; that among
Beale enciphered each letter in the plaintext message by substituting the number of some word which started with that letter. The letter W, for example, was enciphered with the number 1, 19, 40, 66, 72, ... . As an example let consider the word PLAIN. The result of enciphering are shown below:
M = P L A I N
C = 13 42 81 08 44

Encryption Algorithms Polygram Substitution Cipher
All of the preceding substitution cipher encipher a single letter of plaintext at a time. By enciphering larger blocks of letters, polygram substitution ciphers make cryptoanalysis harder by destroying the significance of single-letter frequencies.
The Playfair cipher is a diagram substitution cipher named after the English scientist Lyon Playfair; the cipher was actually invented in 1854 by Playfair’s friend, Charls Wheatstone, and was used the British during World War I. The key of this cipher is given by a 5 by 5 matrix of 25 letters (J was not used), such as the one shown below.
Key for Playfair cipher
Y A R M O
L I K B C
D E F G H
V N P Q S
T U W X Z
Playfair cipher enciphering rule
Each pair of plaintext letters m1m2 is enciphering according to the following rules: 1. If m1 and m2 are in the same row, then c1 and c2 are the two characters to the right of m1 and m2, respectively, where the first column is considered to be to the right of the last column. 2. If m1 and m2 are in the same column, then c1 and c2 are the two characters below m1 and m2,
respectively, where the first row is considered to be below last row. 3. If m1 and m2 are in different rows and columns, then c1 and c2 are the other two corner of the rectangle having m1 and m2, as corners, where c1 is m1 ‘s row and c2 is in m2 ‘s row. 4. If m1 =m2 a null letter (e.g., X) is inserted into the plaintext between m1 and m2 to eliminate the double. 5. If the plaintext has an odd number of characters, a null letter is appended to the end of the plaintext.

Playfair has inspired some related bigraphic ciphers that, on the one hand, improve security by involving multiple, unrelated alphabets, but on the other hand, are simpler in that they use fewer rules than Playfair.
In the Four-Square cipher, two squares are used to find the two plaintext letters, and two others are used to find the two ciphertext letters:
2. Encryption Algorithms 2.6. Polygram Substitution Cipher
Thus, the diagram m1m2=HW becomes c1c2= MN.

The first of the three rules for Playfair encipherment changes one two-letter group, or digraph, to another by exchanging column co-ordinates. This suggests using row and column co-ordinates in a more general fashion. Let's take the 5 by 5 square above, but number the rows and the columns, like this:
Encryption Algorithms Bifid Cipher
Then, another method of encipherment would be as follows: Divide a message into groups of letters of a fixed length, say five letters, and write the row and then the column co-ordinate of each letter beneath it, like this:
and then, going across within each group, read the numbers in order, and turn them, in pairs, into letters: that is, read 11555 14535 52453 33435... and turn them into the letters corresponding to 11, 55, 51, 45, 35, 52, and so on.

Encryption Algorithms Trifid Cipher
This is the Bifid cipher of Delastelle, and the general principle of this form of cipher is called seriation. This is one of the most secure pencil-and-paper ciphers that is still used by hobbyists as a puzzle. It isn't hard to make this kind of cipher just a little bit more complicated, and thereby obtain one that is genuinely secure. It belongs to the class of cipher methods known as fractionation, where letters are divided into smaller pieces, or "fractions". Just as two symbols from 1 to 5 give 25 letters, three symbols from 1 to 3 give 27 letters; and five binary bits provide a 32-character alphabet.
The Trifid, also due to Delastelle, is the analogous cipher using a 27-letter alphabet represented by three symbols from 1 to 3:
to encipher a message by seriation like this:
which again is read off horizontally after being written in vertically, yielding a cipher message like this:313-I, 232-P, 123-B, 131-Z, 321-T, 333-D, 331-U, 122-&, 322-J, 333-D, 112-A 122-&, 321-T, 321-T, 122-&, 213-Q, 221-O, 331-U, 311-C, 233-S, 222-V.