The field of Coding Theory has vital applications in the field of computer science, but decoding error-correcting codes by hand is often a tedious task that, while reinforcing the algorithmic process to decoding, isn’t particularly beneficial to a prospective student. Our application was designed to make the lives of aspiring coding theorists easier.
What it does
Our application can decrypt Caesar Shift Ciphers, as well as decode and error correct a few binary coding schemes such as Reed-Muller and Golay Codes.
How we built it
- Python scripts to create the decryption and error correcting algorithms for our alphabetic and binary codes
- Flask to integrate those algorithms with our front end
- Pixilart.com to create the background image and code witch images
Challenges we ran into
- Ensuring that a few typos wouldn’t cause the Caesar Shift Cipher decoder to be unable to decrypt the message
- Validating input for binary strings
- Decreasing runtime of the Caesar Shift Cipher Decrypter
We used a Python script to run the algorithm that corrects errors in the Golay and Extended Golay codes. This algorithm involves computing a syndrome using the Golay code’s parity check matrix, then running through a series of steps (finding the weight of the syndrome, adding the syndrome to each of the rows of part of the generator matrix, etc) to determine the error pattern. The non-extended version of the Golay code is a perfect 3-error correcting code and will never return the message “ask for retransmission”.
Reed-Muller codes are another type of encoding used in deep-space transmission and are defined by two parameters, r and m. Our algorithm, implemented through Python, takes the parameters input by the user and builds the code. Then, it compares the sent word input by the user to each of the codewords and determines if it can be corrected to one of the codewords. If it cannot, the message “ask for retransmission” is returned.
Caesar Shift Ciphers
Another common cypher we decided to encrypt was the Caesar Shift Cipher, which is a pretty simple algorithm where users decode their message by shifting up the alphabet by a certain value (also referred to as “key”). Cryptowizard not only decrypts the user’s message, but it also returns the key the user used to make their encryption. One of the main drawbacks is that for longer sentences, the runtime can be a bit slow; to improve upon this, we utilized a binary search algorithm that searches through a list of English words (provided by the handy nltk library) for a potential match.
Our Caesar Cipher decryption algorithm is resistant to accidental typos. In any given sentence, the algorithm does its best to return the decrypted sentence (including the typo). In the case that a match was not found, our algorithm handles this failure by returning an error message indicating the user likely entered either a polyalphabetic or generic monoalphabetic substitution code.
Accomplishments that we're proud of
- Optimizing the Caesar Shift Cipher Algorithm
- Creating a fun user-interface
- Implementing the recursive nature of Reed-Muller codes.
What we learned
We learned about different types of encryption and encoding techniques for both alphabetic and binary codes.
What's next for CryptoWizard
For binary codes, we would like to add a feature that error-corrects and decodes any linear code given a generator matrix. We would also like to add options for other specific types of codes, like the Golay code, to help the user learn about applications of different types of error-correcting codes. For alphabetic codes, we would like to implement a decryption algorithm for generic monoalphabetic codes that aren’t necessarily Caesar Shift Ciphers using hill climbing and simulated annealing. We would also like to look into decrypting different polyalphabetic schemes, such as the Vigenere code.