Disclaimer: This project is mostly done with a few experimental things thrown in and some flashy things added for presentation purposes, both of which can be safely ignored, extended or removed.
This project implements the Merkle-Hellman Knapsack Cryptosystem (MHKC) and basis reduction techniques to break it.
It provides a GUI client interface to communicate with other connected clients through a multicast server. It also provides a console interface for breaking the MHKC encrypted ciphers when the public key is known.
Important:
- Make sure the public key (if changed) is known to the console breaking interface.
- If you want to change the private key, make sure it is superincreasing and then add it to MHKC_Encryption.java. Then make sure you uncomment the lines to generate an encryption rule and a new public key. Finally, add this public key, modulo, sum and multiplier to MHKC_Encryption.java.
- If you want to change just the public key, then uncomment the lines to generate an encryption rule and a new public key. Then add this public key, modulo, sum and multiplier to MHKC_Encryption.java.
To run this project:
- First launch the server then as many clients as you want (change the host address if necessary).
- Next, observe the encrypted ciphertexts being displayed on the server console interface.
- If so desired, run the BreakMHKCConsole and paste in any of these ciphertexts from the server.
- The ciphertext should (but not always) be broken and the detailed output can then be examined.
Algorithms Implemented (and why):
- MHKC Encryption / Decryption to implement the cryptosystem.
- Gram-Schmidt Orthonormalization (GSO) to make all vectors mutually orthogonal and all of unit length.
- Lenstra-Lenstra-Lovász (LLL) Algorithm for lattice basis reduction, this calls GSO.
- Weight Reduction (WR) Algorithm for further reducing the weight of the basis.
- Kreher-Radziszowski (KR) Algorithm which is a superior method of reduction compared to using either LLL or WR alone.
API:
- Open the doc/ folder.
- Then open the index.html file using your browser of choice.
- This should show the JavaDoc API documentation generated from the doc comments in the source code.
- Of note is that this is probably out of date and should be rerun as necessary.
References:
- Chapter 8 of "Combinatorial Algorithms: Generation, Enumeration, and Search" by Donald L. Kreher and Douglas R. Stinson
If you have any questions or difficulties please make an issue report at https://github.com/wazy/mhkc/issues and I will get back to you as soon as possible.