Image for post
Image for post

Pack Your Knapsack For Some Secret Messages — Difficult to Pack/Easy to Unpack

RSA is just one way of doing public key encryption. 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. In general the problem is:

  • Given a set of numbers A and a number b.
  • Find a subset of A which sums to b (or gets nearest to it).

So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).

So our code would become 11011 (represented by ‘1’, ‘4’, no ‘6’, ‘8’ and ‘15’).

Then if our plain text is 11011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15 which gives us 28.

A plain text of 00001 will give us a cipher text of 15.

With public key cryptography we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).

Creating a public and a private key

We can now create a superincreasing sequence with our weights where the current value is greater than the sum of the preceding ones, such as {1, 2, 4, 9, 20, 38}. Superincreasing sequences make it easy to solve the knapsack problem, where we take the total weight, and compare it with the largest weight, if it is greater than the weight, it is in it, otherwise it is not.

For example with weights of {1,2,4,9,20,38} with a value of 54, we get:

Check 54 for 38? Yes (smaller than 54). [1] We now have a balance of 16.
Check 16 for 20? No. [0].
Check 16 for 9? Yes. [1]. We now have a balance of 5.
Check 5 for 4? Yes. [1]. We now have a balance of 1.
Check 1 for 2? No. [0].
Check 1 for 1? Yes [1].

Our result is 101101.

If we have a non-superincreasing knapsack such as {1,3,4,6,10,12,41}, and have to make 54, it is much more difficult. So a non-superincreasing knapsack can be the public key, and the superincreasing one is the private key.

Making the Public Key

We first start with our superincreasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number , and take a modulus () of a value which is greater than the total ( — such as 120). For 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} 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 ( — modulus) and 53 ( 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):

_n = 53^(-1) mod 120
(53 x _n) mod 120 = 1

So we try values of _n in (53 x _n mod 120) in order to get a result of 1:

So the inverse is 77 [Calculator].

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

The decoding was so easy, the only thing we had was to find the inverse which is not to difficult.

Try this example here.

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 example here.

Conclusion

Knapsack encryption provides a good approach to creating public and private keys, where there private key is easy to use, while the public key is difficult to compute. The method was outlined by Ralph Merkle in his search for a trap door function [1], but the glory of the sustainable trap door went to RSA, and soon cracks began to show when Adi Shamir [2] published methods to crack it.

References

[1] Merkle, Ralph; Hellman, Martin (1978). “Hiding information and signatures in trapdoor knapsacks”. 24 (5): 525–530. doi:10.1109/TIT.1978.1055927.

[2] Shamir, Adi (1984). “A polynomial-time algorithm for breaking the basic Merkle — Hellman cryptosystem”. 30 (5): 699–704. doi:10.1109/SFCS.1982.5.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store