Genetic Algorithms and Mathematical Programming to Crack the Spanish Strip Cipher

Abstract

This article describes the application of modern algorithms to crack the official encryption method of the Spanish Civil War: the Strip Cipher. It shows the differences in efficiency and effectiveness between a genetic algorithm and mathematical programming, the optimisation methods known collectively as mathematical optimisation. Unlike the genetic algorithm, the programming approach has been seen to lead to high computational costs or to non-legible plain texts, which make it impractical. To improve the search for the genetic operators used, a dictionary is applied to identify possible words in each partially decrypted text and, thus, unblock the process. Results and conclusions have been obtained by analysing the outcome of the algorithms when attacking real ciphertexts found in the General Archive of the Spanish Civil War in Spain. Both the mathematical programming and the genetic algorithm approaches have merit, but the latter has considerable practical advantages.

Keywords:

• genetic algorithms
• mathematical programming
• poly-alphabetic substitution cipher
• Spanish Civil War
• Strip Cipher

Acknowledgements

The authors would like to thank the staff of the General Archive of the Spanish Civil War (Salamanca) and of the Military General Archive (Madrid) for the assistance provided in the location, consultation, and reproduction of the document collections used in this work.

Notes

SA = simulated annealing; TS = tabu search; AC = ant colony; HC = hill climbing.

I = number of individuals, G = number of generations, CP = crossover probability, MP = mutation probability, and ET = execution time in minutes (runtime on a laptop HP Compaq 6730 s with Intel Core 2 Duo 1.80 GHz Windows Vista Home Premium). Column L measures the results' legibility, where N = plaintext obtained is absolutely incomprehensible; I = some vowels and consonants are found correctly, but not all the text is comprehensible. A = language is comprehensible in general although some fragments or words require context to be understood; and P = text is perfectly or almost perfectly decrypted.

L = legibility; ET = execution time.

Additional information

Notes on contributors

Fco. Alberto Campos

Fco. Alberto Campos obtained a degree in Maths in 1999 (special subject: operations research) from the Universidad Complutense de Madrid, and his Ph.D. in Industrial Engineering from the Universidad Pontificia Comillas, Madrid, in 2006. Currently, he is a Research Fellow at the Instituto de Investigación Tecnológica (Technological Research Institute) and associate professor of the Industrial Organization Department, Universidad Pontificia Comillas. His areas of interest include the application of possibilistic Nash games, simulation and risk analysis techniques to the operating and planning problems of electric energy systems, cryptography, and cryptanalysis.

Alberto Gascón

Alberto Gascón graduated as an Industrial Engineer (Electronics) from the Universidad Pontificia Comillas in 2010. He is currently working as a Research Assistant at the Institute for Research in Technology. His areas of interest include forecasting and data analysis.

Jesús María Latorre

Jesús María Latorre received the degree of Electronic Engineer from Universidad Pontificia Comillas in 2001 and the Ph.D. degree in November 2007. He is currently a Researcher at the Institute for Research in Technology. His main interest areas include operations research and mathematical modeling, stochastic programming, parallel and distributed computing, algorithms, and numerical methods.

J. Ramón Soler

J. Ramón Soler gained his degree in sciences at the University of Barcelona. He received his Ph.D. in Engineering from the Universidad Nacional de Educación a Distancia. He is now a teacher in the University School of Tourism in Ibiza (Spain). His interest in cryptology began years ago and since then he has been a dedicated collector of studies on the subject. His main interest is in the field of Spanish cryptology and especially Spanish cryptology of the 20th century.