Running key cipher: Difference between revisions

Content deleted Content added
AnomieBOT (talk | contribs)
m Dating maintenance tags: {{Clarify}}
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.