Autokey cypher: Difference between revisions

Browse history interactively ← Previous editContent deleted Content addedVisual WikitextInline

Revision as of 04:43, 17 July 2012 editDavidCary (talk \| contribs)Extended confirmed users7,117 edits suggest merge to autokey cipher ← Previous edit		Latest revision as of 03:51, 4 May 2017 edit undoAnomieBOT (talk \| contribs)Bots6,569,039 editsm Substing templates: {{This is a redirect}}. See User:AnomieBOT/docs/TemplateSubster for info.
(7 intermediate revisions by 6 users not shown)
Line 1:		Line 1:
			#REDIRECT ]
	] for use with an autokey cypher]]
	{{merge to \| autokey cipher }}

			{{redirect category shell\|{{R from other spelling}}{{R with history}}}}
	An '''autokey cypher''' (also known as the '''autoclave cypher''') is a ] which incorporates the message (the ]) into the ]. There are two forms of autokey cypher: ''key autokey'' and ''text autokey'' cyphers. A key-autokey cypher uses previous members of the ] to determine the next element in the keystream. A text-autokey uses the previous message text to determine the next element in the keystream.

	In modern cryptography, self-synchronizing ]s are autokey cyphers.

	==History==

	The first autokey cypher was invented by ], and contained a fatal defect. Like many autokey cyphers it used the plaintext to encrypt itself; however, since there was no additional key, it is no easier for the intended recipient to read the message than anyone else who knows that the cypher is being used.<ref>Kahn, David, ''The Codebreakers'', revised edition, 1996, p. 144.</ref> A number of attempts were made by other cryptographers to produce a system that was neither trivial to break nor too difficult for the intended recipient to decypher. Eventually one was invented in 1564 by ] using a "reciprocal table" with five alphabets of his invention and another form was described in 1586 by ] with a similar reciprocal table of ten alphabets. This system is now known as the ].

	One popular form of autokey starts with a ], a square with 26 copies of the alphabet, the first line starting with 'A', the next line starting with 'B', etc., like the one above. In order to encrypt a plaintext, one locates the row with the first letter to be encrypted, and the column with the first letter of the key. The letter where the line and column cross is the cyphertext letter.

	] used the first letter of each word as a primer to start his text autokey. ] used as a primer an agreed-upon single letter of the alphabet.

	The autokey cypher as used by the members of the ] differs in the way the key is generated. It starts with a relatively short keyword, and appends the message to it. So if the keyword is "QUEENLY", and the message is "ATTACK AT DAWN", the key would be "QUEENLYATTACKATDAWN".

	Plaintext: ATTACK AT DAWN...
	Key: QUEENL YA TTACK AT DAWN....
	cyphertext: QNXEPV YT WTWP...

	The cyphertext message would therefore be "QNXEPVYTWTWP".

	==Cryptanalysis==

	Using an example message "meet at the fountain" encrypted with the keyword "KILT":

	plaintext: MEETATTHEFOUNTAIN (unknown)
	key: KILTMEETATTHEFOUN (unknown)
	cyphertext: WMPMMXXAEYHBRYOCA (known)

	We try ] words, ]s, ]s etc. in all possible positions in the key. For example, "THE":

	cyphertext: WMP MMX XAE YHB RYO CA
	key: THE THE THE THE THE ..
	plaintext: DFL TFT ETA FAX YRK ..

	cyphertext: W MPM MXX AEY HBR YOC A
	key: . THE THE THE THE THE .
	plaintext: . TII TQT HXU OUN FHY .

	cyphertext: WM PMM XXA EYH BRY OCA
	key: .. THE THE THE THE THE
	plaintext: .. WFI EQW LRD IKU VVW

	We sort the plaintext fragments in order of likelihood:

	unlikely <------------------> promising
	EQW DFL TFT ... ... ... ... ETA OUN FAX

	We know that a correct plaintext fragment will also appear in the key, shifted right by the length of the keyword. Similarly our guessed key fragment ("THE") will also appear in the plaintext shifted left. So by guessing keyword lengths (probably between 3 and 12) we can reveal more plaintext and key.

	Trying this with "OUN" (possibly after wasting some time with the others):

	shift by 4:
	cyphertext: WMPMMXXAEYHBRYOCA
	key: ......ETA.THE.OUN
	plaintext: ......THE.OUN.AIN

	by 5:
	cyphertext: WMPMMXXAEYHBRYOCA
	key: .....EQW..THE..OU
	plaintext: .....THE..OUN..OG

	by 6:
	cyphertext: WMPMMXXAEYHBRYOCA
	key: ....TQT...THE...O
	plaintext: ....THE...OUN...M

	We see that a shift of 4 looks good (both of the others have unlikely Qs), so we shift the revealed "ETA" back by 4 into the plaintext:

	cyphertext: WMPMMXXAEYHBRYOCA
	key: ..LTM.ETA.THE.OUN
	plaintext: ..ETA.THE.OUN.AIN

	We have a lot to work with now. The keyword is probably 4 characters long ("..LT"), and we have some of the message:

	M.ETA.THE.OUN.AIN

	Because our plaintext guesses have an effect on the key 4 characters to the left, we get feedback on correct/incorrect guesses, so we can quickly fill in the gaps:

	MEETATTHEFOUNTAIN

	The ease of cryptanalysis is thanks to the feedback from the relationship between plaintext and key. A 3-character guess reveals 6 more characters, which then reveal further characters, creating a cascade effect, allowing us to rule out incorrect guesses quickly.

	==Autokey in modern cyphers==
	Modern autokey cyphers use very different encryption methods, but they follow the same approach of using either key bytes or plaintext bytes to generate more key bytes. Most modern ]s are based on ]s: the key is used to initialize the generator, and either key bytes or plaintext bytes are fed back into the generator to produce more bytes.

	Some ]s are said to be "self-synchronizing", because the next key byte usually depends only on the previous N bytes of the message. If a byte in the message is lost or corrupted, therefore, the key-stream will also be corrupted—but only until N bytes have been processed. At that point the keystream goes back to normal, and the rest of the message will decrypt correctly.

	== See also ==
	* ]

	== References ==
	{{reflist}}
	{{refbegin}}
	*Bellaso, Giovan Battista, ''Il vero modo di scrivere in cifra con facilità, prestezza, et securezza di Misser Giovan Battista Bellaso, gentil’huomo bresciano'', Iacobo Britannico, Bressa 1564.
	*Vigenère, Blaise de, ''Traicté des chiffres ou secrètes manières d’escrire'', Abel l’Angelier, Paris 1586. ff. 46r-49v.
	*LABRONICUS (Buonafalce, A), ''Early Forms of the Porta Table'', “The Cryptogram”, vol. LX n. 2, Wilbraham 1994.
	*Buonafalce, Augusto, ''Bellaso’s Reciprocal cyphers'', “Cryptologia” 30 (1):39-51, 2006.
	*LABRONICUS (Buonafalce, A), ''Vigenère and Autokey. An Update'', “The Cryptogram”, vol. LXXIV n. 3, Plano 2008.
	{{refend}}

	{{Cryptography navbox \| classical}}

	]
	]
	]

	]
	]

Latest revision as of 03:51, 4 May 2017

Redirect to:

Autokey cipher

This page is a redirect. The following categories are used to track and monitor this redirect:

From an alternative spelling: This is a redirect from a title with an alternative spelling of the target name. Pages that link to this redirect may be updated to link directly to the target page if that results in an improvement of the text. Do not "fix" such links if they are not broken. Also, these links should not be replaced with piped links.
- There are many more specific templates such as {{R from alternative hyphenation}}, {{R from alternative punctuation}} and {{R from alternative spacing}}. Also see subcategories of Category:Redirects from modifications for other options (capitals, abbreviations, diacritics, plurals, stylizations, transliteration, ligatures, different parts of speech, etc.)

With history: This is a redirect from a page containing substantive page history. This page is kept as a redirect to preserve its former content and attributions. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated), nor delete this page.
- This template should not be used for redirects having some edit history but no meaningful content in their previous versions, nor for redirects created as a result of a page merge (use {{R from merge}} instead), nor for redirects from a title that forms a historic part of Misplaced Pages (use {{R with old history}} instead).

When appropriate, protection levels are automatically sensed, described and categorized.