EverCrack Open Source Cryptanalysis

Transposition is a method of changing the position (while

retaining the identity) of each unit of clear text. A simple (albeit pseudo)

example is a jumble. The word "attack" is transposed to "takact". However, this

is not a strict transposition method since there isn't a system (key) to the

re-arrangement, thus, the intended receiver possesses no greater chance of

recovering the original word than the cryptanalytic attacker. In other words,

from a security viewpoint, the cipher is not secure since the cryptanalytic

attacker possesses *no lesser* chance of recovering the original word than the

intended receiver.

The simplest form of a transposition cipher is the rail cipher.

A rail cipher is implemented by taking a message ("this is a secret message")

and dropping every other letter, as so;

T

I

A

E

R

E

M

S

A

E

H

S

S

C

E

T

E

S

G

and then writing the top and then the bottom row to produce the ciphertext

message:

T I I A E R T E S G H S S S C E M S A E

As will be demonstrated later, like the casear cipher, this is

simply an implementation of the matrix transposition cipher with a single key

- divide the message into a matrix of two rows and n-columns. If the cipher

system is known (in this case, the secrecy of the message was dependent on the

secrecy of the method, not the secrecy of a key) the clear text is easily re-

coverable (in fact, it is weaker than the Caesar Cipher since there are only two

possible translations, and only one is ciphered!).

The matrix, or columnar, cipher is more complex and therefore

more secure. The matrix cipher works by first enumerating the number of clear-

text units [spaces and / or punctuation may or may not be included] and then

figuring out factor-sets [number pairs that when multiplied equal the number of

clear-text units]. If this number is prime, the clear-text may be padded ac-

cordingly. Next, a factor set is chosen and the factors are used to create a

grid or matrix of rows and columns. The message is input row by row (or column

by column) and output column by column (or row by row, if input column by

column).

Clear-Text: T H I S I S A S E C R E T M E S S A G E

Characters: 20

Factor Sets: {2, 10}, {4, 5}, {5, 4}, {10, 2}

Chosen Set: {4, 5}

Matrix:

T	H	I	S	I
S	A	S	E	C
R	E	T	M	E
S	S	A	G	E

Cipher Text: T S R S H A E S I S T A S E M G I C E E

When determining the exact matrix to use it is generally best

to use one that most closely resembles a square. This is because a squared

matrix tends to diffuse the letters more [letters that are adjacent in the

plain text message and also in the cipher text message can make the transposed

message easier to decipher]. For example, if the {2, 10} matrix were chosen:

T

H

I

S

I

S

A

S

E

C

R

E

T

M

E

S

S

A

G

E

Cipher Text: T R H E I T S M I E S S A S S A E G C E

Here, "SS" appears together as it does in the original mes-

sage. This particular matrix is the same as a Rail Cipher - if we had input the

message column-by-column then output row-by-row, we would have the exact en-

cipherment as the Rail Cipher example!

Next in level of complexity, within the class of "simple trans-

position" ciphers, (ciphers without a key to the input-output but a key to the

matrix used) is the route transposition cipher.

Again: THIS IS A SECRET MESSAGE

T

H

I

S

I

S

A

S

E

C

R

E

T

M

E

S

S

A

G

E

Now, instead of output going column by column, your may go down

the first column up the second column, down the third, then up the fourth, then

down the fifth. yielding:

Cipher-Text: TSRS SEAH ISTA GMES ICEE

That is just one method of output. Here, the general method or

algorithm is the zigzag route. The key to the method is the specific starting

point and path you follow. You could have started in the lower-right corner

and went up, or did any combination of routes that produced the ciphertext.

Doing so, produces a *complex* route transposition cipher.

Instead of having to just figure out the possible different matrices for a

simple route, you have to figure out the particular route as well (including

the starting point!).

Lastly, in complexity of the simple transpositions, is the

spiral cipher. Once again: this is a secret message

T

H

I

S

I

S

A

S

E

C

R

E

T

M

E

S

S

A

G

E

Now follow along... start at the 't' in the upper-left corner.

Go down to the 's', across to the 'e', up to the 'i', across (left) to the 'h',

down to the 'e', across (right) to 'm', up to 'e', then left to 's'.

Cipher-Text: TSRS SAGE ECIS IHAE TMES

Like the zigzag cipher, other routes can be incorporated (based

on a key) for the starting point and specific path (you could start from an

inner letter and spiral outwards). Again, that elevates the cipher to a complex

route transposition. A generalized cryptanalzer against all the above forms of

simple transposition ciphers would have to yield many, many permutations.

EverCrack will use such a generalized approach but avoid the

"brute" force approach. Brute force just ain't in the design of EverCrack...

and design is everything.