Friedman test (cryptology)

In the cryptology is Friedman test is a method for analysis of a text by polyalphabetic substitution (z. B. algorithm of Vigen'ere ) was encrypted. It can be used to determine the length of the key. It was developed by William Frederick Friedman .

application

Let there be a Vigenère cipher text of length divided into blocks of length . We now calculate the coincidence index of such a text. There are two types of letter pairs: ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle \ kappa}$

A both are in the same block position,
B they are in different block positions.

The probability that two letters of type A are the same is : = 0.0762 (corresponds to the coincidence index for longer German texts). Furthermore, the probability that two letters of type B are the same is equal : = 0.0385 (= 1/26 and corresponds to the uniform distribution). ${\ displaystyle \ mu}$ ${\ displaystyle \ phi}$

In every block position there are letters and thus pairs. So the number of pairs of type A is the same ${\ displaystyle m / n}$ ${\ displaystyle {m / n \ choose 2}}$

${\ displaystyle n \ cdot {\ frac {m / n \ cdot (m / n-1)} {2}} = {\ frac {m (mn)} {2n}}}$ .

The remaining

${\ displaystyle {m \ choose 2} - {\ frac {m (mn)} {2n}} = {\ frac {m ^ {2} (n-1)} {2n}}}$

Pairs are of the type B . This gives for the coincidence index

${\ displaystyle \ kappa = {\ frac {{\ frac {m (mn)} {2n}} \ cdot \ mu + {\ frac {m ^ {2} (n-1)} {2n}} \ cdot \ phi} {m (m-1) / 2}} = {\ frac {(mn) \ cdot \ mu + m (n-1) \ cdot \ phi} {n (m-1)}}}$ .

If one now solves for n, the result is

${\ displaystyle n = {\ frac {m (\ mu - \ phi)} {\ kappa (m-1) + \ mu -m \ cdot \ phi}}}$ .

The presumed key length of the code word is then an integer that is close to this estimate .

Other procedures

The Kasiski test is used to find out the key length based on repeated groups of characters.

literature

Albrecht Beutelspacher : Cryptology. An introduction to the science of encryption, concealment, and concealment. Without any secrecy, but not without deceitful rogue, presented for the benefit and delight of the general public. 2nd considerably expanded and hopefully improved edition. Vieweg, Braunschweig 1991, ISBN 3-528-18990-8 .