Substitution cipher

A **substitution cipher** is a form of cryptography.

In a substitution cipher, a rule is used to change each letter of the message one at a time. The rule is to replace (or "substitute") each letter with another letter from the alphabet.

For instance, this table gives a rule for a substitution cipher:

|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|T|H|A|N|K|Y|O|U|V|E|R|M|U|Z|X|W|S|Q|B|C|D|F|G|I|J|L|

Using that rule, the sentence "Jack and Jill went up the hill" is changed to "Etar tzn Evmm gkzc dw cuk uvmm". The Caesar cipher is an example of a substitution cipher.

Substitution ciphers are not safe enough to use for important messages. Substitution ciphers can be broken by an idea called _frequency analysis_. Some letters are more common than others in English sentences: _E_ is the most common, then _T_, then _A_, and so on. A message that has been changed by a substitution cipher has different common letters, but that gives a hint about the rule. The most common letters in the changed message are likely to be the most common letters in English. Breaking cryptograms (messages hidden with a substitution cipher) is a common puzzle often found in newspapers.

In past centuries, substitution ciphers were sometimes strengthened by combining them in superencryption with transposition ciphers. Improvements in cryptanalysis have caused that method to be abandoned in the early 20th century.

## Example

Suppose the changed message is:

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
 WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
 GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
 IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
 PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
 XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMXXLIYSPH
 KTY
For this example, capital letters are used for unknown letters, and lowercase letters are used to denote letters we know or can guess.

By counting up the letters, we see that the most common is <samp>I</samp>, which we will guess is an <samp>e</samp>. <samp>X</samp> is also quite common, and <samp>XLI</samp> is found many times; we guess that is "<samp>the</samp>", the most common three-letter group in English.

<samp>E</samp> is the second most common letter. We already have a guess for <samp>e</samp> and <samp>t and</samp> so we guess that <samp>E</samp> is <samp>a</samp>. We now have:

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
 WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
 GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
 eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
 PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
 thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMttheYSPH
 KTY

We can now make some more guesses: <samp>heVe</samp> may be <samp>here</samp>; <samp>Rtate</samp> may be <samp>state</samp>, and <samp>atthattMZe</samp> could be <samp>atthattime</samp>. Filling in those guesses, we get:

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
 WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
 GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
 emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
 PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
 thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYittheYSPH
 KTY

That lets us make more guesses, which lead to more guesses until we have guessed everything:

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
 nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
 courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
 emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
 lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
 thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingitthegold
 bug

At this point, we can insert spaces and punctuation:

_Here upon le grand arose with a grave and stately air and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus and
at that time unknown to naturalists of course; a great prize in a scientific
point of view. There were two round black spots near one extremity of the back
and a long one near the other. The scales were exceedingly hard and glossy with
all the appearance of burnished gold. The weight of the insect was very
remarkable and taking all things into consideration I could hardly blame jupiter
for his opinion respecting it._ (The Gold-Bug)

If we had made a wrong guess, we would have found out at some point and could have gone back and made a new guess.