· 1983 paper – “Simulated annealing” in Science by Kirkpatrick, Gelatt, Vecchi http://doi.org/10.1126/science.220.4598.671

· 1986 “random restart hillclimbing” Glover https://doi.org/10.1016/0305-0548(86)90048-1

· 1988-1990 Kryptos codes

· 1993 Forsyth and Safavi-Naini “Automated cryptanalysis of substitution ciphers” (SA) http://doi.org/10.1080/0161-119391868033

·
1994 Giddy and Safavi-Naini
“Automated cryptanalysis of transposition ciphers” (SA) http://doi.org/10.1093/comjnl/37.5.429

· 1995 “shotgun hillclimbing” by Gillogly – The Cryptogram Nov/Dec 1995 issue

· 1998 Andrew J Clark QUT thesis “Optimisation heuristics for cryptology” https://eprints.qut.edu.au/15777/ - chapter 3 concerns attacks on classical ciphers with simulated annealing, genetic algorithms and tabu search

· 2007 Michael J Cowan – MJ2007, SO2007 on Simulated annealing.

also some example code at http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-bifid-cipher/#c-code-for-breaking-bifid

*Trifid
can also be solved by SA, which again*

*finds
the solution much more quickly than*

*hillclimbing**.
There are 6 possible mixed*

*alphabets
for any particular Trifid key, depending*

*on
assignment of numbers in the*

*tableau.
I've illustrated this below using just*

*the
first 3 columns:*

*POW POW POW POW
POW POW*

*111 111
222 111 222 333*

*111 111
222 111 222 333*

*123 132
213 321 231 312*

*These
six different assignments produce six*

*variations
in mixed alphabet, all of which*

*give
the same encipherment or decipherment,*

*shown
below. It can be seen that*

*3-letter
groups move position in the mixed*

*alphabet,
and also the letters within a group*

*change
in order. In the simulated annealing*

*program
it pays to include swaps that move*

*these groups around.*

*POWERANDMIGHTBCFJKLQSUVXYZ#*

*PWONMDEARLSQY#ZUXVIHGFKJTCB*

*BTCGIHJFKREAOPWDNMVUXQLSZY#*

*#ZYXVUSQLKJFCBTHGIMDNAREWOP*

*#YZSLQXUVMNDWPOAERKFJHIGCTB*

*BCTJKFGHIVXUZ#YQSLRAEDMNOWP*

· 2008 Michael J Cowan publishes articles on “Solving Trifid” with simulated annealing in The Cryptogram (May/June 2008, Computer Corner, page 12)

· 2008 Cowan – “Breaking short playfair ciphers with the simulated annealing algorithm” (Cryptologia). Mentions SA works well on bifid, and better than hill climbing. http://doi.org/10.1080/01611190701743658

· 2012 McLaughlin thesis – section 3.5 - http://etheses.whiterose.ac.uk/3674/1/unified_doc_redux_3.pdf -

Particularly section 3.5.2 on SA parameter choices

· 2013 Sanborn big tech day talk mentions “matrix codes” as method used for K1-K3

· 2017 Thomas, commenter on Klaus blog - http://scienceblogs.de/klausis-krypto-kolumne/2016/07/24/kryptos-skulptur-fuehrt-ein-90-jahre-altes-verschluesselungsverfahren-zur-loesung/ - suggests Trifid based on references to Rows and Layer. Also, the word fragment “id” in “id by rows” may indicate a multifid cipher. Bifid is less likely because the ciphertext has 26 characters, and digrafid seems like an ACA invention c1960. This leaves trifid.

· 2017 Lasry thesis published online, discussing much of the above. “A methodology for the cryptanalysis of classical ciphers with search metaheuristics” http://doi.org/10.19211/KUP9783737604598

11 characters of known plaintext may reduce the search space from 27! (1.1*10^28) by a factor of 3^33 – to as low as (2.0*10^12) – not yet accounting for symmetry. For a given position (e.g. first character in mapping) we only need to test 6 possibilities, so this reduces the space by another 26/6 factor. Thus for a particular period it’s even possible to do a brute force search.

Likely periods – see http://kryptools.com/Sheets/sheets.htm

ACA guidelines are 5-15 http://www.cryptogram.org/downloads/aca.info/ciphers/Trifid.pdf and 120-150 letters

14 x 24

42 x 8

31 x 14

98 characters – 7 x 14; factors of 98

7 – based on the length of “KRYPTOS”

14

24

31 – also aligning it with the 3 bottom rows

18, 21, 49 – based on K3 = 21x18, and 49 a factor of 98

Also consider if BERLIN crib location is supposed to be aligned with a period

Then it’s position 64, solving 64=x.period+1 gives period = 3, 7, 9, 21, 63

__More obscure ideas__

31 is 24+7 (HR+DAY from DYAHR)

3 or 33 if you make it 99 (Q?OBKR)

Lots of extra factors if you make it 100 (add in YAR, hopefully at the beginning or end, not sprinkled through it somewhere) or 96 (leave out a letter somewhere) … 2, 4, 5, 10, 20, 25, 50.

A “TRIFID BY ROWS” – i.e. write the plaintext in by rows, and extract it by columns

Be careful with the scoring function – should # be scored like an X, like a question mark, a full stop, an E, or a space? Also, with the known plaintext, we can allow for scoring which gives texts which are just close to the crib, without matching it exactly; in case the encryption has a mistake in it.

`Based on Michael Cowan’s old site cryptoden – we can use “tries” to change the scoring function so that it’s based completely on words – which is mentioned in his description of the “Churn algorithm” https://web.archive.org/web/20141129010802/http://www.cryptoden.com:80/index.php/algorithms/churn-algorithm/20-churn-algorithm`