Two attempted implementations of the McEliece Cryptosystem using Reed–Solomon and (7,4) Hamming error correcting codes.
Our implementation of the McEliece Cryptosystem using Reed–Solomon codes lacks operational error generation and decoding functionality. When we first began building, we were naive to assume that the cryptosystem would be functional without any error generation and correction. We figured error generation and correction were unnecessary since we were conducting our experiments in a local environment. After many hours of debugging, this oversight eventually led to the realization that error generation and correction were necessary elements to unraveling the message we inputted. Looking at the math to generate and correct errors, we could not even begin to understand what was happening. Due to the timeline of this project, we saw it unreasonable to learn this math, and we entered a mid-life crisis of sorts.
Unsure of where to go next, we stumbled upon the reedsolo python library (https://pypi.org/project/reedsolo/) and dreamed it could do all the high-level math we could not comprehend. We ran with this assumption for about a day, and again, after many hours of debugging, realized it was inadequate for the McEliece Cryptosystem.
With our spirits at their lowest, we stepped back and examined what we were trying to accomplish from a 30,000-foot view. Doing this allowed us to see that while most literature related to the McEliece Cryptosystem as a quantum-proof encryption protocol talks of high-level error-correcting codes such as Reed-Solomon codes, there are more straightforward ones. The first error-correcting code on a record, Hamming codes, is straightforward and something our undergraduate-level brains could comprehend. It only took hours to get a rickety implementation of the McEliece Cryptosystem using (7,4) Hamming codes. This provided us with enough to begin experimentation:
When implementing the Hamming (7,4) version of the cryptosystem, a significant limitation would be the inability to change the input size of the message. Given that the generator matrix is 7x4, a message can only be 4 bits. However, we then thought of parsing a more extended message into 4-bit chunks, so we created a method for doing just that. We hypothesized that encrypting and decrypting these longer messages would have a time complexity of O(n), n being the total length of the message. This is because the same 4-bit method is called on every chunk. To show this to be accurate, we designed an experiment. Given the complex nature of matrix operations (multiplication, inverse, transpose, permute), we decided to use the number of matrix operations as a metric for overall runtime. We added counter a matrix_ops counter to the code and counter the operations. We then implemented the method with a series of simple loops that would encrypt and then decrypt messages of size 4 bits up to 4n bits. N is the number of trials in the experiment. We plotted size vs. matrix operations using Matplotlib, and this confirmed our hypothesis. We used n=1000, which would create the largest message of 4000 bits.
One of the drawbacks of using Hamming 7,4 as our generator matric is it fairly quickly identifies G from G^ given the small size. This would make "cracking" the code much more accessible; it would be straightforward for someone to decode a cipher. However, they would need to find out the permutation and nonsingular vectors. The file, theoretically brute force analysis.pdf, looks into the complexity of trying to brute force possibilities for P and S private keys.