Autokey Cipher | Sahithyan's Notes

A classical, poly-alphabetic cipher. Created by Blaise de Vigenère. Provides higher security than the Bellaso variant. This was NOT covered in the class; only included here for the sake of completeness.

You may find an implementation of Autokey cipher in sahithyandev/ciphers.

Encryption

A short secret key is used to encrypt only the first few characters of the plaintext. From there, the keystream continues with the plaintext itself, shifted by the key length, rather than repeating the short key.

Each position adds its keystream letter modulo $26$ .

Since the keystream is never a short repeating sequence, the Kasiski test cannot be used to find a key length, making this cipher more secure than the repeating-key (Bellaso) variant.

Decryption

Only the short primer key is known at the start. Each position subtracts its keystream letter modulo $26$ . Every recovered plaintext letter is appended to the keystream and used to decrypt a later position, so the keystream is rebuilt as decryption proceeds.

Attacking

Still vulnerable to statistical attacks, since the key length is typically much shorter than the message, so most of the keystream is plaintext of the same language, whose letter frequencies are known.

The primer is short, so its length $L$ is guessed and each value tried.

For a fixed $L$ , every position past the primer has keystream equal to the plaintext $L$ places earlier, so

C_i = P_i + P_{i - L} \pmod{26}

Here $C_i$ is the numeric value of the $i$ -th ciphertext letter and $P_i$ likewise for plaintext. $A = 0$ to $Z = 25$ .

Applying $P_i = C_i - P_{i - L}$ repeatedly walks back in steps of $L$ until it hits the primer:

P_i = C_i - C_{i - L} + C_{i - 2L} - \dots \pm k_r

where $k_r$ is the one primer letter in residue class $r = i \bmod L$ . Each of the $L$ classes is then fixed by a single unknown letter. Its 26 values are tried and the one whose column matches the language’s letter frequencies is kept. The correct $L$ makes all $L$ columns come out as the language. No probable word is needed.

Worked Example

Plaintext imakemyownluck under primer key PATRIC, with $A = 0$ to $Z = 25$ .

The keystream is the primer key followed by the plaintext itself, truncated to the plaintext length.

plaintext:   i m a k e m y o w n l u c k
keystream:   P A T R I C I M A K E M Y O
ciphertext:  X M T B M O G A W X P G A Y

Each position adds the keystream letter modulo $26$ .

$i (8) + P (15) = 23 = X$
$m (12) + A (0) = 12 = M$

Ciphertext is XMTBMOGAWXPGAY.

For decryption, only the primer key PATRIC is known at the start. Each recovered plaintext letter is appended to the keystream and used to decrypt later positions.

$X (23) - P (15) = 8 = i$
$M (12) - A (0) = 12 = m$

After 6 positions the primer key is exhausted and the keystream continues with the recovered plaintext imakem.

$G (6) - i (8) = -2 \equiv 24 = y$
$A (0) - m (12) = -12 \equiv 14 = o$

Plaintext is imakemyownluck.

For the attack, take ciphertext UIHGTQANBLIGBBRBPRB with $L = 3$ . Class $r = 1$ holds positions $1, 4, 7, 10$ with ciphertext values $20, 6, 0, 11$ . As a function of the unknown primer letter $x$ , the class decrypts to

$20 - x, \quad 12 + x, \quad 14 - x, \quad 23 + x$

Only $x = 1$ (B) gives language: t n n y. The other 2 classes resolve the same way, giving primer BUZ and plaintext toinfinityandbeyond.