· 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