Contact analysis (cryptanalysis)

In cryptanalysis, contact analysis is the study of the frequency with which certain symbols precede or follow other symbols. The method is used as an aid to breaking classical ciphers.

Contact analysis is based on the fact that, in any sample of any written language, certain symbols appear adjacent to other symbols with varying frequencies. Moreover, these frequencies are roughly the same for almost all samples of that language, even when the distribution of the symbols themselves differs significantly from normal. This is true regardless of whether the symbols being used are words or letters.

In some ciphers, these properties of the natural language plaintext are preserved in the ciphertext, and have the potential to be exploited in a ciphertext-only attack.

Although in a sense contact analysis can be considered a type of frequency analysis, most discussions of frequency analysis concern themselves with the simple probabilities of the symbols in the text: $P(X_{i}=a)$ or $P(X_{i}=a\cap X_{i+1}=b)$

Contact analysis is based on the conditional probability that certain letters will precede or succeed other letters: $P(X_{i}=b\mid X_{i-1}=a)$ , or $P(X_{i}=c\mid X_{i-2}=a\cap X_{i-1}=b)$ , or even $P(X_{i}\subset S\mid X_{i-1}\subset T\cap X_{i+1}\subset T)$ , where $S$ and $T$ are subsets of the alphabet being used.

Where frequency analysis is based on first-order statistics, contact analysis is based on second or third-order statistics.

External links

Statistical Distributions of English Text

Classical cryptography

Ciphers
by family

Caesar	Affine (Atbash) ROT13

Null	Null cipher (Null encryption)

One time pad	Book One-time pad

Polybius square	ADFGVX Bifid Tap code 3D (Trifid: Nihilist and VIC cipher)

Square	Two-square Four-square

Substitution cipher	Autokey Chaocipher Great Hill Keyword Running key

Transposition cipher	Rail fence cipher

Other	Alberti BATCO (Slidex) Beaufort Dvorak Enigma Kama Sutra Navajo code Pigpen Playfair Polyalphabetic Rasterschlüssel 44 Reihenschieber Reservehandverfahren Scytale Smithy code Solitaire Straddling checkerboard Tabula recta Transposition Trithemius Vigenère

Cryptanalysis

Frequency analysis
Index of coincidence (Units: Ban and Nat)
Information leakage
Kasiski examination

Miscellaneous

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 3/29/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.