2
$\begingroup$

I know simple formulas like

$$E(x) = (ax+b)\pmod n$$

where $E(x)$ stands for encryption,

$$D(y)= z(y-b)\pmod n$$

where $D(y)$ stands for decryption,

and

$$ax==1\pmod n$$

Assuming someone gives us an encrypted string, is there a way to find $a$ and $b$ from that string? If not, what informations we should have to find $a$ and $b$ keywords from the encrypted string? Is there a way to find a and b keywords in an affine cipher when only ciphertext but no plaintext is known?


Note that this is not a duplicate of Affine cipher: calculate the key from a known plaintext/ciphertext pair. In that other question, the user knows beginning of both encrypted and decrypted message.

$\endgroup$
2
$\begingroup$

There are several ways to break an affine cipher without any known plaintext.

First of all, for the common case of $n = 26$, there are only $12$ possible values of $a$ (since $a$ and $n$ must be coprime) and $26$ possible values of $b$, for a total of $312$ possible keys. That's small enough that you can easily test all the keys and simply inspect the results to find the most plausible plaintext.

Even if the alphabet size is larger (say, $n = 256$) you can let a computer try all possible keys and use statistical frequency analysis to sort them by plausibility. Manual inspection should then let you pick out the correct plaintext from among the few dozen ones rated most likely by the statistical test. Of course, to set up the frequency model, you'll need to have some idea of what the plaintext might be (e.g. English text, executable binary code, base64-encoded data, etc.) and it must not be too random-looking.

More generally, an affine cipher is a type of monoalphabetic substitution cipher, and so any techniques that can break general monoalphabetic substitution ciphers (such as manual step-by-step frequency analysis) can certainly also break an affine cipher. Also, many techniques that work on simple Caesar shift ciphers can also be adapted for affine ciphers. For example, you could try:

  • Simple frequency analysis: Find the two most common ciphertext symbols, and guess that they correspond to the two most common letters in English (E and T). That should give you a system of linear equations that you can solve for $a$ and $b$. If the results don't make sense, try switching the letters around; if that doesn't help, try the next few most common ciphertext symbols and/or the next most common English letters (A, I and N).

  • Crib dragging: Guess a word of two or more letters that likely appears in the plaintext, and try matching it with different parts of the ciphertext. Common words like "the" are particularly useful here: if the plaintext is supposed to be English, and there's a particular sequence of three symbols that occurs often in the ciphertext, there's a pretty good chance that it decrypts to "the". Conveniently, since "the" has three letters, you get a system of three equations and two unknowns, so you can check it for consistency before even attempting actual decryption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.