Knapsack Encryption (Merkle-Hellman Knapsack)RSA is just one way of doing public key encryption. Merkle-hellman-knapsack is a good alternative where we can create a public key and a private one. The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight [Theory]: |
Other examples
- On this Wiki page [Here], the private key is {2, 7, 11, 21, 42, 89, 180, 354}, n=792, m=881, with data of "01100001" which gives a public key of {295, 592, 301, 14, 28, 353, 120, 236} and gives a cipher of "1129". Try:. here
- On this page [here] we have a private key of {1,2,4,7,12,20,33,54} and n of 147, with m of 250, and gives a public key of {1,2,4,7,12,20,33,54}. Try:. here
- On this page (Slide 18/19) [here] we have a private key of {3, 5, 15, 25, 54, 110, 225} and n of 10, with m of 439, and data of "hello" (1001000 1100101 1101100 1101111). This gives a public key of {30, 50, 150, 250, 101, 222, 55} and a cipher of {280,236,431,708}. Try:. here
In Case 1 our private key is ({2, 7, 11, 21, 42, 89, 180, 354},588,881) and the public key is ({295, 592, 301, 14, 28, 353, 120, 236}), as we have no need to reveal the n and m value.
In Case 2 our private key is ({1,2,4,7,12,20,33,54},147,250) and the public key is ({1,2,4,7,12,20,33,54})
In Case 3 our private key is ({3, 5, 15, 25, 54, 110, 225},10,439) and the public key is ({30, 50, 150, 250, 101, 222, 55})
Making the Public Key
We first start with our super-increasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus (m) of a value which is greater than the total (m - such as 120). For n we make sure that there are no common factors with any of the numbers. Let's select an n value of 53, so we get:
1×53 mod(120) = 53 2×53 mod(120) = 106 4×53 mod(120) = 92 10×53 mod(120) = 50 20×53 mod(120) = 100 40×53 mod(120) = 80
So the public key is: ({53,106,92,50,100,80},53,120) and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy. Let's try to send a message that is in binary code:
111010 101101 111001
We have six weights so we split into three groups of six weights:
111010 = 53 + 106 + 92 + 100 = 351 101101 = 53+ 92 + 50 + 80 = 275 111001 = 53 + 106 + 92 + 80 = 331
Our cipher text is thus 351 275 331.
The two numbers known by the receiver is thus 120 (m - modulus) and 53 (n multiplier).
We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n−1) = 1 mod m. For this we find the inverse of n:
n-1 = 53-1 mod 120 (53 x _n) mod 120 = 1
So we try values of n-1 in (53 x n-1 mod 120) in order to get a result of 1:
n-1 Result 1 53 2 106 3 39 ... 75 15 76 68 77 1
So the inverse is 77. [Calculate]
The coded message is 351 275 331 and is now easy to calculate the plain text:
351×77 mod(120) = 27 = 111010 (1+2+4+20) 275×77 mod(120) = 55 = 101101 331×77 mod(120) = 47 = 111001
The decoded message is thus:
111010 101101 110001
which is the same as our original message:
111010 101101 111001
Code
A quick overview of the code is:
string get_public=getknap(priv, n,m); string cipher = getcipher(get_public,data); int solv = solve(Convert.ToInt32(n), Convert.ToInt32(m)); string plain = getknap(cipher, Convert.ToString(solv), m); public string getcipher(string publickey, string data) { string data_result = ""; string[] vals = publickey.Split(','); int[] weights = new int[vals.Length]; for (int i=0;i<vals.Length;i++) weights[i]=Convert.ToInt32(vals[i]); int ptr = 0; int bit=0; int total = 0; do { total = 0; for (int i = 0; i < 6; i++) { if (data[ptr] == '1') bit = 1; else bit = 0; total += weights[i] * bit; ptr++; } if (data_result == "") data_result += total.ToString(); else data_result += "," + total.ToString(); } while (ptr < data.Length); return (data_result); } public int solve(int n, int m) { int res = 0; for (int i = 0; i < 5000; i++) { if (((n*i)%m)==1) return (i); } return (res); } public string getknap(string key, string n, string m) { string[] vals = key.Split(','); string k = ""; foreach (string v in vals) { int i = (Convert.ToInt32(v) * Convert.ToInt32(n)) % Convert.ToInt32(m); if (k == "") k +=i.ToString(); else k+=","+i.ToString(); } return (k); }