Backpack problem . The “simple knapsack problem”, also called the “supergrowing knapsack problem”, is a type of NP-complete problem to which a series of conditions are applied that make it possible to pose it as the sum of subsets and has important applications in the world of cryptography .
Summary
[ hide ]
- 1 Definition
- 2 Resolution
- 3 Applications
- 1 Symmetric key
- 2 Asymmetric key
- 4 Source
Definition
Dices:
- A set of m positive integers S = {S 1, S 2 , …, S m }, ordered from least to greatest, where the sequence of the elements meet the condition that the i-th element is greater than the sum of the previous elements (it is a super-growing sequence ). Mathematically
- A value T that is the result of some of the possible sums of those elements,
Find S ‘= {S a , S b , …, S j }, where S’ is the subset of S whose sum is equal to the value T.
Resolution
The solution to this type of backpack is very easy because the S sequence is a super-growing sequence:
The elements of the backpack are traversed from largest to smallest, checking if said value is less than T. If it is greater, that value will not be in the sum and therefore in the corresponding position of the solution vector x i there will be a 0. Otherwise it will have a 1 and the resolution will continue with the remaining elements of the backpack for the problem TS j
For this type of problem, if there is a solution, it will be unique.
Applications
Symmetric key
A simple backpack problem can be used as a secret key to a symmetric encryption algorithm . For this, what you have to do is represent the information you want to encrypt in binary and each bit is passed through the backpack by the sequence of numbers in the set S. If a bit is 1, then the corresponding element is included in the sum. . If it is 0 then it is not included.
For example, let S = {2, 4, 10, 19, 40}. So m = 5. Suppose I want to encrypt the message M = GOODBYE. Passing the message to ASCII / ANSI (A = 01000001, D = 01000100, I = 01001001, O = 01001111, S = 01010011) we have the message (group of 5 in 5 since m = 5)
M = 01000 00101 00010 00100 10010 10011 11010 10011
Doing the sums of each quintet I get
C = (4), (10 + 40), (19), (10), (2 + 19), (2 + 19 + 40), (2 + 4 + 19), (2 + 19 + 40) = 4, 50, 19, 10, 21, 61, 25, 61
What will be the encrypted message .
To decipher the receiver, which knows S, receives the message C and operates in the opposite way solving the problem of the simple backpack for each of the values of C.
- To obtain a sum of 4, the solution is 01000
- 50 -> 00101
- 19 -> 00010
- 10 -> 00100
- 21 -> 10010
- 61 -> 10011
- 25 -> 11010
- 61 -> 10011
If I join all the bits and group them into groups of 8 bits (ANSI / ASCII) I get the original message.
This way of encrypting is not secure since it is evident that having enough pairs, of original message and associated encrypted message, it will be very easy to obtain the S key with which it is being encrypted. However, this form of encryption is very fast and can be exploited in encryption applications with an asymmetric key .
Asymmetric key
The basic idea to use a simple backpack in an asymmetric cryptography system is to achieve a secret transformation that transforms the simple backpack into a general backpack whose resolution has a high computational cost. We will call this backpack a cheating backpack . The public key will be the cheating backpack and with it the sender will encrypt the message in the same way as before . The private key will be formed by the parameters that allow to convert the encrypted message with the cheating backpack into an encrypted message with the simple backpack. Once this is achieved, the receiver can easily decipher the message using the simple backpack.
In summary, the scheme is based on encrypting with a one-way function based on a NP-complete problem ( the backpack problem ) that they have a trap door that takes advantage of the receiver to decrypt the message. If this trap door is not available, the decryption process, being an NP-complete problem , theoretically would have a very high computational cost.
This idea is based, for example, on the Merkle-Hellman cryptosystem . This algorithm for doing the transformation finds:
- A value u such that are the elements of the simple backpack.
- An integer value w such that in the group of the integers of modulus u
The cheating backpack is found using the expression . It must be verified that the cheat backpack thus obtained is not an easy backpack to solve (it is not always the case).
To decrypt the cryptogram , the C sums obtained by encrypting must be applied for each one. Then each transformed sum value has to be deciphered in the usual way with the original simple backpack, which is trivial.
