poster

Evolutionary algorithm for decryption of monoalphabetic homophonic substitution ciphers encoded as constraint satisfaction problems

Author:

David OranchakAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1717 - 1718

https://doi.org/10.1145/1389095.1389425

Published: 12 July 2008 Publication History

Get Access

Abstract

A homophonic substitution cipher maps each plaintext letter of a message to one or more ciphertext symbols [4]. Monoalphabetic homophonic ciphers do not allow ciphertext symbols to map to more than one plaintext letter. Homophonic ciphers conceal language statistics in the enciphered messages, making statistical-based attacks more difficult. We present a dictionary-based attack using a genetic algorithm that encodes solutions as plaintext word placements subjected to constraints imposed by the cipher symbols. We test the technique using a famous cipher (with a known solution) created by the Zodiac serial killer. We present several successful decryption attempts using dictionary sizes of up to 1,600 words.

References

[1]

J. M. Carrol and S. Martin. The automated cryptanalysis of substitution ciphers. Cryptologia, X(4):193--209, 1986.

Digital Library

Google Scholar

[2]

R. Graysmith. Zodiac. St. Martin's, New York NY, 1986.

Google Scholar

[3]

T. Jakobsen. A fast method for cryptanalysis of substitution ciphers. Cryptologia, 19(3):265--274, 1995.

Crossref

Google Scholar

[4]

J. C. King and D. R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems. Cryptologia, XVII(1):45--54, 1993.

Digital Library

Google Scholar

[5]

M. Lucks. A constraint satisfaction algorithm for the automated decryption of simple substitution ciphers. In CRYPTO, pages 132--144, 1988.

Digital Library

Google Scholar

[6]

R. A. J. Matthews. The use of genetic algorithms in cryptanalysis. 17(2):187.201, Apr. 1993. cryptanalysis; genetic algorithms; cryptographic systems; keyspaces; GENALYST.

Google Scholar

[7]

E. Olson. Robust dictionary attack of short simple substitution ciphers. 2007.

Digital Library

Google Scholar

[8]

R. Spillman, M. Janssen, B. Nelson, and M. Kepner. Use of a genetic algorithm in the cryptanalysis of simple substitution ciphers. 17(1):31--44, Jan. 1993.

Digital Library

Google Scholar

Cited By

View all

Picek SJakobovic DWagner M(2022)Evolutionary computation and machine learning in securityProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534087(1572-1601)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534087
Picek SJakobovic DKrawiec K(2021)Evolutionary computation and machine learning in cryptologyProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461420(1089-1118)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461420
Picek SJakobovic DCoello Coello C(2020)Evolutionary computation and machine learning in cryptologyProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389886(1147-1173)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389886
Show More Cited By

Index Terms

Evolutionary algorithm for decryption of monoalphabetic homophonic substitution ciphers encoded as constraint satisfaction problems
1. Security and privacy
  1. Cryptography
    1. Cryptanalysis and other attacks
2. Social and professional topics
  1. Computing / technology policy
    1. Computer crime

Recommendations

Designing substitution boxes for secure ciphers

In cryptography, a Substitution box (S-box) constitutes a cornerstone component of symmetric key algorithms. In block ciphers, they are typically used to obscure the relationship between the plaintext and the ciphertext. It is well-known that the more ...
Efficient Cryptanalysis of Homophonic Substitution Ciphers

This article focuses on the design and implementation of an efficient algorithm to break homophonic substitution ciphers. The authors employ a nested hill climb approach that generalizes the fastest known attack on simple substitution ciphers. They test ...
Attacking Turkish texts encrypted by homophonic cipher
NEHIPISIC'11: Proceeding of 10th WSEAS international conference on electronics, hardware, wireless and optical communications, and 10th WSEAS international conference on signal processing, robotics and automation, and 3rd WSEAS international conference on nanotechnology, and 2nd WSEAS international conference on Plasma-fusion-nuclear physics

Homophonic cipher is developed as an alternative to substitution cipher to compose more resistant ciphertexts against to the frequency analysis attacks. Nevertheless, Attacking with taking advantage of characteristic vulnerabilities of the language is ...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Picek SJakobovic DWagner M(2022)Evolutionary computation and machine learning in securityProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534087(1572-1601)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534087
Picek SJakobovic DKrawiec K(2021)Evolutionary computation and machine learning in cryptologyProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461420(1089-1118)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461420
Picek SJakobovic DCoello Coello C(2020)Evolutionary computation and machine learning in cryptologyProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389886(1147-1173)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389886
Jain SChhibber NKandi S(2018)Cryptanalysis of Mono-Alphabetic Substitution Ciphers using Genetic Algorithms and Simulated AnnealingIARS International Research Journal10.51611/iars.irj.v8i1.2018.848:1Online publication date: 8-Feb-2018
https://doi.org/10.51611/iars.irj.v8i1.2018.84
Fyrbiak MRokicki SBissantz NTessier RPaar C(2018)Hybrid Obfuscation to Protect Against Disclosure Attacks on Embedded MicroprocessorsIEEE Transactions on Computers10.1109/TC.2017.264952067:3(307-321)Online publication date: 1-Mar-2018
https://doi.org/10.1109/TC.2017.2649520
Reddy SKnight KLi HLin COsborne M(2012)Decoding running key ciphersProceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Short Papers - Volume 210.5555/2390665.2390686(80-84)Online publication date: 8-Jul-2012
https://dl.acm.org/doi/10.5555/2390665.2390686
Ravi SKnight KLin D(2011)Bayesian inference for Zodiac and other homophonic ciphersProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 110.5555/2002472.2002504(239-247)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002472.2002504

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Designing substitution boxes for secure ciphers

Efficient Cryptanalysis of Homophonic Substitution Ciphers

Attacking Turkish texts encrypted by homophonic cipher

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations