Introduction
The search for an effective cryptosystem has always been a prevalent question, given the value of privacy in our world today. Given this issue, many solutions have been created, to varying degrees of success. One of the earliest such asymmetric cryptosystems is the Merkle-Hellman knapsack algorithm, initially created by Ralph Merkle and Martin Hellman in 1978. Although this has in fact been broken only 6 years after its conception, it regardless serves as a crucial component of the history of cryptography.
Key Generation
The public and private keys of the Merkle-Hellman knapsack algorithm are created using three main values: w, q, and r.
setW[] :=
Module[{list = {}},
For[i = 0, i < 8, i++,
AppendTo[list, Total[list] + RandomInteger[99] + 1]];
list
]
setQ[w_] := RandomInteger[{Total[w] + 2, 20000}]
setR[q_] := RandomChoice[Pick[Range[q],
CoprimeQ[q, Range[q]]
]]
- w is set to be a super increasing sequence of length 8: it has one element for each of the 8 bits in the binary encoding of a character. In the algorithm used above to create w, each element is greater than the sum of all the previous elements, with a difference of a random integer between 1 and 99. This allows for the quick creation of w, while also fulfilling the variable's necessary conditions.
- q is set to be a random prime greater than the total of the elements of w. The number 20,000 as the ceiling of q has been chosen to balance between randomness and runtime.
- r is set to be a random number less than q that is also relatively prime to q. It is chosen as a random element of set of numbers that adhere to the non-random conditions of r.
With these values selected, the public and private keys can be produced.
MHMakeKeys[] := Module[{w = setW[], q, r},
{q = setQ[w];
r = setR[q];
listToHex[Mod[r w, q]],
listToHex[{w, q, r}]}
]
- To make the public key, r is multiplied by every element of w. Every element is then simplified modulo q, and the resulting list is the public key. To adhere to cryptography standards, this list is lastly converted to hex.
- The private key, on the other hand, is simply w, q, and r placed into a list. This list is then converted to hex, for the same reason as the public key.
Encryption
To encrypt a message using the Merkle-Hellman knapsack algorithm, only the public key is needed.
MHEncrypt[message_String, public_String] :=
listToHex[Table[Total[cur hexToList[public]],
{cur, toBinary[message]}]]
First, the public key is converted back to a list. For every character within the provided message, the following process is done:
- The character is converted to an 8-bit binary list.
- This list is then multiplied by the public key. Specifically, the first elements of each list are multiplied, the second elements of each list are multiplied, etc. This works because both the public key and binary character list are 8 bits in length.
- The elements of the resulting list are then added together.
This means that each character in the message is ultimately converted into a number, and by extension, the message is converted into a list of numbers. This list of numbers is then converted to hex, yielding the ciphertext.
Decryption
To decrypt a message, on the other hand, the private key is required.
knapsack[private[[1]],
Mod[cipher ModularInverse[private[[3]], private[[2]]], private[[2]]]
MHDecrypt[cipher_String, private_String] :=
StringJoin[Table[FromCharacterCode[FromDigits[decrypt[cur, privateToList[private]], 2]],
{cur, hexToList[cipher]}
]]
The ciphertext is first converted from hex back to a list of numbers, and the following process is applied to and reverses the encryption on each character of the original message.
- The number is multiplied by the modular inverse of r modulo q to yield a number s (Note: s is implicit, rather than explicitly included in the above code).
- The knapsack problem is computed on s and w. This yields a subset of w in which the sum of its elements is s.
- For every element of w, it is checked whether that element is in the previously computed subset. If it is, a 1 is returned, otherwise, a 0 is returned. Since w is of length 8, an 8-bit binary number is ultimately produced.
- This binary number can afterwards be simply converted into a character.
Email / Web Support
In order to simplify the usage of this project for others, I have created a collection of web pages for a friendly user experience.
CloudDeploy[FormPage[{}, Column[MHKeyDisplay[]] &,
PageTheme -> "Red",
AppearanceRules -> <|"SubmitLabel" -> "Generate New Keys",
"Title" -> "Merkel Hellman Key Generation",
"Description" ->
"An implementation of the generation of public and private keys \
in the Merkel Hellman knapsack cryptosystem."|>],
"MHMakeKeys",
Permissions -> "Public"];
This website allows for the creation of both a public and corresponding private key through only a single button press.
CloudDeploy[
FormPage[{"email" -> "String", "message" -> "String",
"public" -> "String"}, SendEncrypted[#email, #message, #public] &,
PageTheme -> "Red",
AppearanceRules -> <|"Title" -> "Merkel Hellman Encryption",
"Description" ->
"An implementation of encryption in the Merkel Hellman knapsack \
cryptosystem."|>],
"MHEncryption",
Permissions -> "Public"];
This website takes an email address, a message, and a public key, and sends an email to the given address with the encrypted version of the message. (See below: SendEncrypted)
CloudDeploy[
FormPage[{"cipher" -> "String", "private" -> "String"},
MHDecrypt[#cipher, #private] &,
PageTheme -> "Red",
AppearanceRules -> <|"Title" -> "Merkel Hellman Decryption",
"Description" ->
"An implementation of decryption in the Merkel Hellman knapsack \
cryptosystem."|>],
"MHDecryption",
Permissions -> "Public"];
This website takes an encrypted message and its corresponding private key as inputs, returning the original message.
CloudDeploy[
FormPage[{"function" -> {"Generate Keys", "Encrypt", "Decrypt"}},
If[#function == "Encrypt",
Hyperlink["Encrypt (click here)",
"https://www.wolframcloud.com/objects/tanaykreddy/MHEncryption"],
If[#function == "Decrypt",
Hyperlink["Decrypt (click here)",
"https://www.wolframcloud.com/objects/tanaykreddy/MHDecryption"]\
, Hyperlink["Generate Keys (click here)",
"https://www.wolframcloud.com/objects/tanaykreddy/MHMakeKeys"]]]\
&,
PageTheme -> "Red",
AppearanceRules -> <|"Title" -> "Merkel Hellman Simulator",
"Description" ->
"An implementation of the Merkel Hellman knapsack cryptosystem."|>],
"MHSimulator",
Permissions -> "Public"]
Lastly, this website links the key generation, encryption, and decryption websites together by providing links for each one of them.
As an application for this cipher, I also created a function which sends an encrypted message to another individual via email.
SendEncrypted[email_String, message_String, public_String] := With[{},
SendMail["To" -> email,
"Subject" -> "Encrypted Message",
"Body" -> {Hyperlink[
"https://www.wolframcloud.com/objects/tanaykreddy/MHDecryption"],
"\n", ToString[MHEncrypt[message, public]]}];
"Message encrypted and sent!"
]
This function sends an email to a specified user which includes not only the encrypted version of a message, but also a link to the website where the ciphertext can be decrypted. As aforementioned, this function is moreover included in the encryption website.
Final Product
And the fruits of my labor are below, embedded into the following website:
Merkle Hellman Simulator
Try it Yourself!
Go to the Decryption Microsite and try decrypting the following cipher:
000025c70000052f00003fc90000269a00003ed900003ae900004c8900002af6000057300000052f00003a7d0000434d00002af60000672300005c7c0000052f000051690000705f000043b90000052f00003a7d0000705f0000052f0000606c000051690000052f0000606c00003ed90000672300003a7d0000705f0000368d00003aa50000052f0000306e00002af60000368d00004c8900004c8900002af60000052f0000216b0000705f0000368d00003ed900003ae90000434d0000672300002af600000e6b
and its corresponding private key:
000000230000002b0000008b000000f6000001ed000003d3000007a500000f3a000027d6000017d3
Attachments:
