Running key cipher: Difference between revisions

Revision as of 17:24, 2 November 2023

Latest revision as of 08:50, 11 November 2024

(4 intermediate revisions by 3 users not shown)

Line 1:

{{short description|Type of polyalphabetic substitution cipher}}

{{refimprove|date=March 2016}}

In classical [[cryptography]], the '''running key cipher''' is a type of [[polyalphabetic substitution]] [[cipher]] in which a text, typically from a book, is used to provide a very long [[keystream]]. The earliest description of such a cipher was given in 1892 by French mathematician Arthur Joseph Hermann (better known for founding [[Éditions Hermann]]). Usually, the book to be used would be agreed ahead of time, while the passage to be used would be chosen [[random]]ly for each message and secretly indicated somewhere in the message.

== Example ==

The key text used is a portion of ''[[The C Programming Language]]'' (1978 edition), and the ''[[tabula recta]]'' is the tableau. The plaintext here is "Flee at once".

Page 63, line 1 is selected as the running key:

Line 25:

|}

The message is then sent as "JCVSR LQNPS". However, unlike a [[Vigenère cipher]], if the message is extended, the key is not repeated; the key text itself (the text from the ''[[The C Programming Language]]'') is used as the key.{{Clarify|date=November 2023}}and can be extended for any arbitrary length. If the message is extended, such as, "Flee at once. We are discovered", then the running key continues as before:

{| class="wikitable" style="text-align:center"

Line 64:

The [[VIC cipher]] uses a similar [[lagged Fibonacci generator]].

== Security and cryptanalysis ==

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: for example, [[William F. Friedman]] suggested a [[ciphertext-only attack]] during WWI against most frequent letters encoded by other most frequent letters.<ref>{{Cite web |title=Cryptology: Running-Text Ciphers – Cryptanalysis According to Friedman |url=https://www.staff.uni-mainz.de/pommeren/Cryptology/Classic/7_Aperiodic/AnalFR.html |access-date=2024-01-10 |website=www.staff.uni-mainz.de}}</ref> As a result, the [[information entropy|entropy]] per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a [[cryptanalysis|cryptanalyst]] runsmay run [[Known-plaintext attack|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 (for more detailed explanation refer to [[Autokey cipher#Cryptanalysis|Autokey cipher]]). Eventually it is likely that the source of the running key will be identified, and the jig is up.

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. PairsAs exploited in Friedman's method, 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).

Another possibility is to use a key text that has more entropy per character than typical English. For this purpose, the [[KGB]] advised agents to use documents like [[almanac]]s and trade reports, which often contain long lists of random-looking numbers.