I am building an implementation of the [Merkle-Hellman Knapsack Cryptosystem] for my study.(https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem)

One of the things I would like to do, is to create a new private key. A private key in the Knapsack Cryptosystem consists mostly* of a so-called superincreasing knapsack. This is a sequence of numbers K where K[n] > (K[0] + K[1] + ... + K[n-1].

I am wondering if there are smart methods to construct a new sequence for which this holds true. It is easy to create a superincreasing knapsack (such as 1, 2, 4, 8, 16, ...), but I've found it relatively hard until now to do this properly for a sequence that is not predictable.

Are there any algorithms (that probably incorporate a value from a random number generator in there) that can do this?

*there are also two more numbers to compute for the private key, but that is outside of the scope of this question.


I don't suppose this has to be difficult. You know the sum of elements 0 through n-1, so generating n is as simple as picking some value larger than that. A cryptographically secure random number generator should work just fine when doing this, making your answer:

K[n] = sum(K[0] ... K[n-1]) + random(1, c)

Select some value c such that you don't encounter overflow when generating the list, and use that to generate a list as long as you want.

  • And you do not want to recalculate the sum of all priors each time, remember the sum and just add the latest every time instead. – Martin Maat Sep 16 '16 at 5:25
  • This is a good answer, and I will probably select it as accepted answer unless someone else places a better answer during the next few days. The most important issue I still have with this approach is what value to select for c, because regardless of what (finite) value is selected, you are leaking entropy: the algorithm will then never be able to create a Knapsack having a jump > c between consecutive elements. Of course, in practice, the Knapsack cryptography has other problems that make it insecure, but it still is an interesting problem. – Qqwy Sep 24 '16 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.