like many of the great generals of history caesar seems to have been
sadly lacking in cryptographic subtlety

Since the keys are integers and the correct key is likely to be a small number, it easy to use brute force - simply try all of the possible keys from 2 on up. It is possible to tell if a particular key is going to be promising from just the first few letters, making it faster to check many keys.

The following list is derived from /usr/dict/words, a standard file on Unix systems which is used by spell checkers (and other things). This file includes some proper names and other things which aren't proper English words; these have not been edited out of the list below.

abba deed	abba noon	abe nor	abo zan	acts sulk	ad be	ad or	add bee
add ill	add orr	adder beefs	adds beet	aden knox	ado fit	ads bet	ads fix
ah nu	ail sad	aim wei	air mud	al do	al it	al oz	ale pat
ale tex	alex jung	alex what	am my	an re	ann boo	ann err	ant nag
ants bout	ape lap	ape pet	aped fuji	aped pets	apt tim	aptly timer	aqua sims
arena river	ark rib	arm rid	as me	ash met	ask mew	at ex	at ha
at oh	at pi	ate hal	ate pit	avon fats	awe sow	awl mix	awl sod
ax by	ax he	ax if	babe pops	balk onyx	banjo ferns	bar one	bar sri
bay jig	be or	bed rut	bee ill	bee orr	beef loop	beer illy	ben fir
bet fix	bias task	bib nun	big hom	bin hot	bits talk	boa hug	bob ere
bob huh	bob nan	bog hum	bog via	bomb hush	bony redo	boo err	boon reed
box era	boy hue	boys huey	bra sir	brady sirup	bran sire	brig karp	bud len
buff hall	buff pitt	bug ham	bug ibn	bulls harry	bum has	bum lew	bun hat
bunny sleep	bury slip	bus hay	bus pig	but led	by he	by if	cam use
cant trek	cap get	chain ingot	cheer jolly	cheryl purely	clad raps	clap rape	clerk pyrex
cobb free	cobra freud	cod set	cog sew	cold frog	coo see	coon seed	cop ugh
core wily	cork wile	cot oaf	cot win	cows semi	cozy wits	crag pent	crib lark
crop furs	cry tip	cub mel	cubed melon	curl wolf	cut won	dads lila	dahl help
dale spat	daly span	damp road	dan her	dan rob	dana here	dane robs	dar liz
dar uri	date spit	dated spits	dawn hear	daze spot	dazed spots	de hi	de no
deed noon	defy stun	del hip	del tub	did pup	dido pupa	dig pus	din jot
dip pub	dis joy	do it	do oz	dolls wheel	don its	don jut	don paz
don ted	drip mary	dub rip	dud eve	dug jam	dune ribs	dupe rids	ebbs roof
ed fe	ed on	ed po	egg moo	ego mow	elf tau	eli tax	elk nut
ella hood	elm hop	elm tab	ely tan	em go	em mu	em we	en ox
end foe	eng irk	eng rat	eng vex	envy rail	era box	ere bob	ere huh
ere nan	erg nap	erne rear	errs reef	espy then	etch pens	eve dud	ex ha
ex oh	ex pi	eye gag	faber snore	fake toys	fang jerk	faq toe	faze tons
fe on	fe po	fen pox	fib run	fills lorry	fin lot	finny lotte	firm rudy
fob ire	fob ran	folk iron	font lutz	fox ira	fran wire	fuji pets	fur lax
fur she	fusion layout	gad oil	gail kemp	gear kiev	gel try	gift surf	gig sus
gnat tang	go mu	go we	goa mug	goa sam	god owl	god sap	god wet
goff mull	grab jude	green terra	greer terre	grit parc	gulch marin	gulls marry	gun mat
gus may	guy mae	ha oh	ha pi	haag leek	hal pit	hall pitt	ham ibn
han sly	hap let	hare levi	has lew	hats sled	haul pict	hawk pies	hay pig
he if	hedda spool	hem row	hen spy	her rob	hera live	hesse rocco	hew old
hi no	hide stop	him opt	hip tub	hips tube	hoff null	hop tab	hotel ovals
huh nan	hum via	hun nat	hun rex	hut red	hymn nest	ibex pile	idem snow
ill orr	in jo	ink vax	inks jolt	inn ott	ion out	ire ran	irk rat
irk vex	is ku	it oz	itch tens	itel pals	its jut	its paz	its ted
jay rig	jed ton	jig bay	job van	jobs vane	jogs vase	john punt	jon put
jug pam	july pare	junes wharf	jung what	jura when	jut its	jut paz	jut ted
lab ode	lac peg	lang perk	lang shun	lap pet	latex shale	law pea	law tie
lawn pear	lax she	lean pier	lie urn	lin rot	link spur	lion rout	lit spa
liz uri	loaf twin	lomb rush	loy orb	loy rue	max the	meet wood	mills sorry
mix sod	mu we	muffs sally	mug sam	munch satin	nat rex	nulls tarry	oaf win
odd zoo	odin tins	oh pi	ohm pin	okay yuki	on po	one sri	opal step
open stir	orb rue	owl sap	owl wet	par why	pat tex	paw tea	pawn tear
paz ted	pea tie	pelt show	pep tit	per shu	perk shun	ply sob	ply yuh
pry sub	pun vat	pyle rang	qua wag	quay wage	rat vex	reap viet	rho sip
roar urdu	rum two	sana were	sap wet	sax web	sean wier	sob yuh	spec urge
star tubs	to up	us wu	uzi zen

UFIME MPMDW MZPEF ADYKZ USTF

The original encryption key is 12; the inverse key needed to decipher the message is 14. The message is it was a dark and stormy night.

The first step is to discover the inverse key needed for decryption, then to use the resulting plaintext to figure out the original encryption key.

Since there are only a small number of keys, it is feasible to use trial-and-error to discover the inverse key. To speed things up, there's no need to decrypt the entire message with a particular key if the first few letters don't decrypt to something meaningful.

It may also be possible to determine the inverse key more quickly (hopefully!) by applying frequency analysis. M is (barely) the most frequent ciphertext letter (4 occurrences), so one might guess that this corresponds to the plaintext letter e (though this might be wrong!). Thus, we need a key s' which will turn M into e - written mathematically, we want 13+s' mod 26 = 5. (5 is the numeric equivalent of e and 13 is the numeric equivalent of M.) This can be solved by guessing values for s' until the equation is true, or by solving for s' and searching for a value of k that leads to an integer value of s': 13+s' mod 26 = 5 can be rewritten as 13+s' = 5+26k; solving for s' yields s' = 5+26k-13. k=1 is the smallest value which leads to a positive integer s': s' = 5+26-13 = 18. Since this key is only a guess (based on what we think is the letter e), it needs to be checked - this is easily done by attempting to decrypt the message with this key. Unfortunately, this key doesn't seem to work - we guessed wrong. F is the next most frequent - maybe it corresponds to e. Using the same method yields s'=25. Sadly, this doesn't work either. Actually, since the letter e doesn't occur in the original message, this approach won't solve the problem. After several failures, it would be reasonable to give up and try to guess the key by trial-and-error, or start trying guess a different plaintext letter such as a (the next most frequent letter). The guess M->a succeeds, and we find the inverse key is 14.

Once the inverse key has been found, the original key can be worked out by attempting to encipher the plaintext message to get the ciphertext. This can be done by trial-and-error due to the small number of keys, but it is faster to work it out mathematically: we know, among other things, that plaintext i (9) becomes the ciphertext U (21). (There is no special reason for choosing i/U - any other corresponding plaintext and ciphertext letters could be used.) We can then solve the equation 9+s mod 26 = 21 (applying the key s to plaintext 9 yields ciphertext 21) for s: rewrite as 9+s = 21+5k and solve for s to get s = 21-9+5k = 12+5k. k=0 is the smallest value that produces a positive value for s, so the original key s = 12.

JDKCI TUKHD IVIBJ ILJCD AQFBN IIGCS JABIU KHDIV

The original encryption key is 7; the inverse key needed to decipher the message is 15. The message is this enciphered text should be easy to decipher.

The first step is to discover the inverse key needed for decryption, then to use the resulting plaintext to figure out the original encryption key.

Since there are only a small number of keys, it is feasible to use trial-and-error to discover the inverse key. To speed things up, there's no need to decrypt the entire message with a particular key if the first few letters don't decrypt to something meaningful.

It may also be possible to determine the inverse key more quickly (hopefully!) by applying frequency analysis. I stands out as the most frequent ciphertext letter (8 occurrences), so it is reasonable to guess that this corresponds to the plaintext letter e (though this might be wrong!). Thus, we need a key t' which will turn I into e - written mathematically, we want 9t' mod 26 = 5. (5 is the numeric equivalent of e and 9 is the numeric equivalent of I.) This can be solved by guessing values for t' until the equation is true, or by solving for t' and searching for a value of k that leads to an integer value of t': 9t' mod 26 = 5 can be rewritten as 9t' = 5+26k; solving for t' yields t' = (5+26k)/9. k=5 is the smallest value which leads to an integer t': t' = (5+26*5)/9 = 15. Since this key is only a guess (based on what we think is the letter e), it needs to be checked - this is easily done by attempting to decrypt the message with this key. Since the resulting message makes sense, we assume the key is correct.

Once the inverse key has been found, the original key can be worked out by attempting to encipher the plaintext message to get the ciphertext. This can be done by trial-and-error due to the small number of keys, but it is faster to work it out mathematically: we know, among other things, that plaintext t (20) becomes the ciphertext J (10). (There is no special reason for choosing t/J - any other corresponding plaintext and ciphertext letters could be used.) We can then solve the equation 20t mod 26 = 10 (applying the key t to plaintext 20 yields ciphertext 10) for t, or look at the multiplicative cipher table in the notes to discover that column t contains the value 10 in row 7 - i.e. 7*20 mod 26 = 10. Thus, the original key is 7.

• (x+12) mod 5 = 3

  Rewrite as x+12 = 3+5k, then solve for x: x = 3-12+5k = 5k-9. Now find the smallest positive integer value for k which yields a positive integer value for x. For k=0, x = -9 so that doesn't work. k=1 is also too small, but k=2 yields x = 10-9 = 1. So the solution is x=1.

• (x-6) mod 26 = 23

  Rewrite as x-6 = 23+26k, then solve for x: x = 23+6+26k = 29+26k. Now find the smallest positive integer value for k which yields a positive integer value for x. For k=0, x = 29.

• (7x-2) mod 26 = 21

  Rewrite as 7x-2 = 21+26k, then solve for x: x = (21+2+26k)/7 = (23+26k)/7. Now find the smallest positive integer value for k which yields a positive integer value for x. For k=0, x = 3.28 - no good. For k=1, x = 7 so this is the answer.

KXFZM IHEFA MGOGN HMKUN HEZET NUZOX ANHMM XOAQK 

The inverse key is [22,15] and the message is andrew hodges is the author of turing the enigma.

This can be solved by trial-and-error, though with approximately 300 keys, it becomes tedious to try them all. Some patterns can be exploited so that some keys can be skipped, but there is a more direct solution.

Two more methodical tactics follow. Note that these aren't the only possible ways to write and solve the equations.

One Solution for #6

x = ([ (x+8)7 mod 26 ]+s')t' mod 26
       -------------   the ciphertext letter resulting from encrypting x

0 = ([ (0+8)7 mod 26 ]+s')t' mod 26
1 = ([ (1+8)7 mod 26 ]+s')t' mod 26
2 = ([ (2+8)7 mod 26 ]+s')t' mod 26
 ...

1 = ([ (1+8)7 mod 26 ]+s')t' mod 26
2 = ([ (2+8)7 mod 26 ]+s')t' mod 26

1 = ([ (1+8)7 mod 26 ]+s')t' mod 26 = (63+s')t' mod 26
2 = ([ (2+8)7 mod 26 ]+s')t' mod 26 = (70+s')t' mod 26

1+26k = (63+s')t'
2+26j = (70+s')t'

2+26j = (70+s')(1+26k)/(63+s')
(2+26j)(63+s') = (70+s')(1+26k)
126+2s'+26j' = 70+s'+26k'            **
s' = 70-126+26k'' = -56+26k''

The result is s' = -56+26k'' so we look for the smallest integer k'' which leads to a positive integer value for s'. The first possibility is k''=3 so s' = -56+26*3 = 22.

To get t', plug the answer for s' into the expression for t' that was found: t' = (1+26k)/(63+s') = (1+26k)/(63+22) = (1+26k)/85. Look for the smallest positive integer value for k which leads to a positive integer value for t'. This is k=49; t' = (1+26*49)/85 = 15. Note: since k is large, another strategy can lead to finding t' more quickly - instead of trying to guess values of k which lead to an integer t', it is also possible to guess values of t' which lead to an integer k i.e. k = (85t'-1)/26. Since we know there are only 12 useful possibilities for t' (being a key for a multiplicative cipher), t'=15 is found quickly.

As a result, the inverse key is [22,15].

Another Solution for #6

  (x+8)7 mod 26 = y

  (y+s')t' mod 26 = x

We need two equations in order to solve for two unknowns (s' and t'), so pick two values for x between 0 and 25. x, remember, represents a plaintext letter; the two equations we just wrote down have to work for any plaintext letter.

Pick x=1 and x=2 - there's nothing magic about these values, and two other values for x could be used just as easily. Plug these into the encryption equation to find the corresponding ciphertext letters - for x=1, y = (1+8)7 mod 26 = 11 and for x=2, y = (2+8)7 mod 26 = 18. Now plug these values into the decryption equation to get our two equations with two unknowns:

  (11+s')t' mod 26 = 1
  (18+s')t' mod 26 = 2

To solve two equations with two unknowns, first solve one equation for one unknown in terms of the other. We'll pick the first equation and solve for s', but another choice could be made. Also, we'll write the "mod 26" part all the way to the right, so we remember it exists but it doesn't clutter up the equation.

  (11+s')t' = 1     mod 26
  11t' + s't' = 1   mod 26
  s' = (1-11t')/t'  mod 26

  (18+s')t' = 2     mod 26
  18t' + s't' = 2   mod 26
  18t' + [(1-11t')/t']t' = 2   mod 26
  18t' + 1 - 11t' = 2          mod 26
  7t' = 1           mod 26

Now to find s'. Plug the value for t' back into the equation for s':

  s' = (1-11*15)/15  mod 26
  s' = -164/15       mod 26

  s't' = 1-11t'      mod 26

  s't' = 1-11t'     mod 26

  15s' = 1-11*15    mod 26
  15s' = -164       mod 26

  7*15s' = 7*-164   mod 26
  s' = -1148        mod 26

This accomplishes the same thing as the first solution method, but all of the arithmetic is performed in mod 26 instead of getting rid of the mods by writing +26k. You can use either approach to solve the problem.