[srtrzzuy] Simple ciphers

Simple ciphers are entertaining to implement on a computer. Here we show a Haskell implementation.

We will eventually need a 32 character alphabet (exact power of 2), so we use the following alphabet, inspired by Norwegian: 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 å é ê ó ø ü

As plaintext, we take the first amendment:

Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.

Here is a Caeser cipher with shift 2:

> run (caesar 2)

Eqpitguu ujcnn ocmg pq ncy tgurgevkpi cp guvcdnkujogpv qh tgnkikqp, qt rtqjkdkvkpi vjg htgg gzgtekug vjgtgqh; qt cdtkfikpi vjg htggfqo qh urggej, qt qh vjg rtguu; qt vjg tkijv qh vjg rgqrng rgcegcdnå vq cuugodng, cpf vq rgvkvkqp vjg Iqxgtpogpv hqt c tgftguu qh itkgxcpegu.

Of course, in a real cipher, one would not preserve word spacing, punctuation, or capitalization. That would give too much information!

Here is a substitution cipher:

> run sub32

Ypjcóbhh hatoo rtåb jp otn óbhdbyumjc tj bhutgomharbju pw óbomcmpj, pó dópamgmumjc uab wóbb bvbóymhb uabóbpw; pó tgómécmjc uab wóbbépr pw hdbbya, pó pw uab dóbhh; pó uab ómcau pw uab dbpdob dbtybtgoq up thhbrgob, tjé up dbumumpj uab Cpfbójrbju wpó t óbéóbhh pw cómbftjybh.

The substitution is 19 6 24 27 1 22 2 0 12 11 26 14 17 9 15 3 4 29 7 20 30 5 13 21 16 25 18 23 31 28 10 8

Here is a 32-column columnar transposition cipher, using the same permutation as above (I'm being lazy):

> run perm

Llsseefs btgrs tsnr hl ovc pfoehconii rl rriheotinetde yn cabrpbel, ee egeelmerilr ero rptn atxdtnrn rcotosh; sf eemrkoeoo deg sigstmr tn isoeio, rt cg ssl httsf; ai epp tgnha he oea gnoanm neehadwgt ee irefrmft, spo eo enaoeifh poe Oecpiegibe avt r ofaeeah rf rbasiehheo.

Here is a Bacon cipher:

> putStrLn(unwords(bacon_sep(get_lower(first_amd))))

aaaba abbba abbab aabba baaab aabaa baaba baaba baaba aabbb aaaaa ababb ababb abbaa aaaaa ababa aabaa abbab abbba ababb aaaaa babba baaab aabaa baaba abbbb aabaa aaaba baabb abaaa abbab aabba aaaaa abbab aabaa baaba baabb aaaaa aaaab ababb abaaa baaba aabbb abbaa aabaa abbab baabb abbba aabab baaab aabaa ababb abaaa aabba abaaa abbba abbab abbba baaab abbbb baaab abbba aabbb abaaa aaaab abaaa baabb abaaa abbab aabba baabb aabbb aabaa aabab baaab aabaa aabaa aabaa babbb aabaa baaab aaaba abaaa baaba aabaa baabb aabbb aabaa baaab aabaa abbba aabab abbba baaab aaaaa aaaab baaab abaaa aaabb aabba abaaa abbab aabba baabb aabbb aabaa aabab baaab aabaa aabaa aaabb abbba abbaa abbba aabab baaba abbbb aabaa aabaa aaaba aabbb abbba baaab abbba aabab baabb aabbb aabaa abbbb baaab aabaa baaba baaba abbba baaab baabb aabbb aabaa baaab abaaa aabba aabbb baabb abbba aabab baabb aabbb aabaa abbbb aabaa abbba abbbb ababb aabaa abbbb aabaa aaaaa aaaba aabaa aaaaa aaaab ababb bbaaa baabb abbba aaaaa baaba baaba aabaa abbaa aaaab ababb aabaa aaaaa abbab aaabb baabb abbba abbbb aabaa baabb abaaa baabb abaaa abbba abbab baabb aabbb aabaa aabba abbba babab aabaa baaab abbab abbaa aabaa abbab baabb aabab abbba baaab aaaaa baaab aabaa aaabb baaab aabaa baaba baaba abbba aabab aabba baaab abaaa aabaa babab aaaaa abbab aaaba aabaa baaba

Things begin to get interesting when we combine the Bacon cipher with columnar transposition. This is called fractionation.

> run (un_bacon . perm . bacon)

Abaaavey óøépz hézw fn nhê bjveüzebbc jn irlbzlsbtåqøa ob yygiaafó, yt haegqyksuoc iye êcué ciåshyêa fårbmro; ts åyóezeuno bpd cwoubqu iy kzcwqa, is cå qyi kkgkq; üe jxh btkyo êø yam sfodya zpiiaêeóh cn amstmgej, iiø qc mgcøvkts iaw Abskvcqrzs qyc d zdlcdbf ên münybedcwa.

Cipher block chaining causes later ciphertext to depend on previous ciphertext. When used alone, it is an extremely weak autokey cipher.

> run cbc

Cqóduykê ovval xxbf sa llb swixéóqyfl ly êobbcnvhoåølø mr cgrzühvc, qb qbpwøühåcpv ipt yjnr vmqbdlób uéüquch; vg ghyadjrøe xøc hyêadró lq crvzéc, qb pu hos bswiå; iz mtx iqwóq ød wób qucrêa pttvzzåfó qø øqcgstøc, cps ft cgzbuêkx krv Éjøctamqóq vdu u fjmóbtf ty øpxéqqóüdv.

We apply a substitution cipher over cipher block chaining. This cannot be broken the same way normal substitution ciphers are broken (by counting letter frequencies).

> run (sub32 . cbc)

Yeêéøqåü pffto vvgw ht oog hnmvxêeqwo oq üpggyjfapskok ró ycóziafy, eg egdnkiasydf mdu qljó fregéoêg øxieøya; fc caqtélókb vky aqütéóê oe yófzxy, eg dø aph ghnms; mz ruv menêe ké nêg eøyóüt duufzzswê ek keychuky, ydh wu yczgøüåv åóf Xlkyutreêe féø ø wlrêguw uq kdvxeeêiéf.

Let's combine substitution, Bacon cipher, and columnar transposition. This begins to resemble one round of a modern substitution-permutation cipher.

> run (un_bacon . perm . bacon . sub32)

Bvjdêavó üvvvå óyas my óêm qyrgeéómpm fu üszwtkrcrêuåg jw üéfkddlj, øb jlchqiuijws yaó eåêé åqåådmam kuóêekm; bs yanbhgstå pai zvójerm qy ydåoiq, åi ké éar wsêxu; tm oil fngrc rg uyê kzszye ktmmqvqpl qj useüåioo, gzm gy vøéovxlê rqn Yjsåvåaqaø ijd j écijdoj vv awotegdgqf.

Bvjdêavó üvvvå óyas my óêm qyrgeéómpm fu üszwtkrcrêuåg jw üéfkddlj, øb jlchqiuijws yaó eåêé åqåådmam kuóêekm; bs yanbhgstå pai zvójerm qy ydåoiq, åi ké éar wsêxu; tm oil fngrc rg uyê kzszye ktmmqvqpl qj uqeüåioo, gzm gy vøéovxlê rqn Yjsåvåaqaø ijd j écijdoj vv awotegdgqf.

The above two outputs are an experiment of what results if we change the final character of the plain text. Ideally, a change in plaintext should result in a large change in ciphertext, so that an adversary cannot tell that plaintexts are similar if ciphertexts are similar (the basis for a chosen ciphertext or chosen plaintext attack). Unfortunately, this is not the case; the ciphertexts ended up largely the same.

Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievanceb.

> let { x :: (String -> String); x = (cbc . un_bacon . perm . bacon . sub32); }

If we add cipher block chaining, things become better

> run x

Bwücøøtq pezoi fóóp ét qmy iarxéwtüoå üt seótgqbduqeøe nd cócmpsóg, ef ozécsåowüvh üüê aåwr lévpsøøk uifbfpé; êo ggtuébtga ppx qfclpam êu mpjxüp, jr éw rrc ykgór; eq øgr wdjåê nt hüé føqjbf pcoåküpøj zc wimlfnéj, piu ås hfaodåfb scp Hqcêrllééz bkn w rtéehvø ti iømüdjmsch.

Bwücøøtq pezoi fóóp ét qmy iarxéwtüoå üt seótgqbduqeøe nd cócmpsóg, ef ozécsåowüvh üüê aåwr lévpsøøk uifbfpé; êo ggtuébtga ppx qfclpam êu mpjxüp, jr éw rrc ykgór; eq øgr wdjåê nt hüé føqjbf pcoåküpøj zc wgkjdlzh, ngs yq fdømbydü qan Foaåpjjzzx üil u przcftê rg gêkóbhkqaf.

Then, if we repeat 3 rounds, then the ciphertexts become completely different. This is an example of Claude Shannon's confusion and diffusion.

> run (x . x . x)

Xkhóndsh ålnqs xêrg xv slv fbwtéøsmku ql biiåjubqlvnêq fw zmxhbqms, øj xkbøóyêwhxk lzc xjfm låfjéólq spygepx; lf øddgümkvó ral sójxóvq zq dnülgi, dt ém ozv uohyp; ty ahw zvheê ph hwy xóvjsy lbaüéånér pb sømbszêê, due üa kqexecüu tme Ünåfgtéóåb éét a øhtsøvz êw erxüalåruü.

Üugdêmhé zelyk üegg ér wwu oyevuåncnt ah åügóntxudgoyó hc pêfédjfx, lo opliüépøjno øjl móåb fågsklfå éxodqøz; zg cåfétqiim rêp emüvivq rf üvrvøc, êh mn nfü sótzv; kw éch awhfø oê aéø lyêgtd xpaåuüeqi én bólafgåd, ånd åj déüysópb êma Yødégøcclq xuu å rpguêål hø qóqqucmjzé.

Just for fun, let's run a million rounds, taking 4 hours 43 minutes on my laptop computer. A million rounds (a 32 element permutation is equivalent to a 117-bit key) should be pretty strong, unless there is some underlying group structure of the rounds. In a real cipher, one would use a key schedule to generate different round keys for each round. Perhaps I should have done this with a lagged Fibonacci generator. Threading the key schedule through all the rounds would be a monad exercise.

> run (n_iterate 1000000 x)

Etsubpåj ibprm sloê yn jvu édccetåóvl sz ytpdfxêjuøbêé nc bsêbxoêt, bw lgüaexcfglc rzé kpåt tcmøóykh zdkvlas; or mzrbcfpih åug évcdåxu af iaydêe, ün yê msn iêwdl; bo shø msfir pø nwk fióuix tuqbdzvdh im qgbuuyxé, eiê co uåsbdsdg djé Øxyatxejap zwó m êsåxjüo ql yusmeafüaó.

Finally, we can recover the plaintext by deciphering:

> let { y :: (String -> String); y = (un_sub32 . un_bacon . un_perm . bacon . un_cbc) }

> run (y . y . y . x . x . x)

Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.