Running key cipher: Difference between revisions

Revision as of 14:37, 16 November 2009

Revision as of 12:18, 26 March 2010

Line 52:

== Variants ==

Modern variants of the running key cipher often replace the traditional ''tabula recta'' with bitwise [[exclusive or]], operate on whole [[byte]]s rather than alphabetic letters, and derive their running keys from large files. Apart from possibly greater entropy density of the files, and the ease of automation, there is little practical difference between such variants and traditional methods. If the running key is random, never reused, and kept secret, the result is a [[one-time pad]], a method that provides perfect secrecy (reveals no information about the plaintext).

== Security ==

If the running key is truly random, never reused, and kept secret, the result is a [[one-time pad]], a method that provides perfect secrecy (reveals no information about the plaintext). However, if (as usual) the running key is a block of text in a [[natural language]], security actually becomes fairly poor, since that text will have non-random characteristics which can be used to aid cryptanalysis. As a result, the [[information entropy|entropy]] per character of both plaintext and running key is low, and the combining operation is easily inverted.

Perhaps surprisingly, the security is usually fairly poor. This is because the [[information entropy|entropy]] per character of both plaintext and running key is low, and the combining operation is easily inverted. This means a [[cryptanalysis|cryptanalyst]] can run guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext - which can in turn be extended, and so on. Eventually it is likely that the running key will be recognised, and the jig is up. This process is sometimes performed as a simple puzzle, for recreation.

PerhapsTo surprisingly,attack the security is usually fairly poor. This is because the [[information entropy|entropy]] per character of both plaintext and running key is lowcipher, and the combining operation is easily inverted. This means a [[cryptanalysis|cryptanalyst]] can runruns guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext - which can in turn be extended, and so on. Eventually it is likely that the source of the running key will be recognisedidentified, and the jig is up. This process is sometimes performed as a simple puzzle, for recreation.

There are several ways to improve the security. The first and most obvious is to use a secret mixed alphabet tableau instead of a ''tabula recta''. This does indeed greatly complicate matters but it is not a complete solution. Pairs of plaintext and running key characters are far more likely to be high frequency pairs such as 'EE' rather than, say, 'QQ'. The skew this causes to the output [[frequency distribution]] is smeared by the fact that it is quite possible that 'EE' and 'QQ' map to the same ciphertext character, but nevertheless the distribution is not flat. This may enable the cryptanalyst to deduce part of the tableau, then proceed as before (but with gaps where there are sections missing from the reconstructed tableau).