·         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.

http://www.cryptogram.org/resource-area/computer-column-programs/simulated-annealing-example-using-playfair/

http://www.cryptogram.org/resource-area/computer-column-programs/aristo-excel-worksheet-and-playfair-simulated-annealing-program/

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