Scribd
Upload
38 views

Knapsack Algorithm Ralph Merkle and Martin Hellman Developed The First Algorithm For

The knapsack algorithm was the first public key encryption algorithm developed by Ralph Merkle and Martin Hellman. It is based on the knapsack problem of determining if items with different weights can be placed in a bag to reach a certain total weight. In the algorithm, a block of plaintext is used to select items from a knapsack based on their positions, and the ciphertext is the resulting sum. Encryption involves breaking the binary data into blocks the length of the knapsack, then adding the numbers in the knapsack corresponding to 1s in each block.

Uploaded by

MuzaffarPalsania
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
38 views

Knapsack Algorithm Ralph Merkle and Martin Hellman Developed The First Algorithm For

The knapsack algorithm was the first public key encryption algorithm developed by Ralph Merkle and Martin Hellman. It is based on the knapsack problem of determining if items with different weights can be placed in a bag to reach a certain total weight. In the algorithm, a block of plaintext is used to select items from a knapsack based on their positions, and the ciphertext is the resulting sum. Encryption involves breaking the binary data into blocks the length of the knapsack, then adding the numbers in the knapsack corresponding to 1s in each block.

Uploaded by

MuzaffarPalsania
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Knapsack Algorithm

Ralph Merkle and Martin Hellman developed the first algorithm for
public key encryption, called as the Knapsack algorithm. It is based on
the Knapsack problem. This is actually a simple problem. Given a pile of
items, each with different weights, is it possible to put some of them in a
bag (i.e. knapsack) in such a way that the knapsack has a certain weight?
That is, if M1, M2, ..., Mn are the given values and S is the sum, find out bi
so that: S = b1M1 + b2M2 + ... + bnMn, each bi can be 0 or 1. A 1
indicates that the item is in the knapsack and a O indicates that it is not.
A block of plain text equal in length to the number of items in the pile
would select the items in the knapsack. The cipher text is the resulting
sum. For example, if the knapsack is 1, 7, 8, 12, 14, 20, then the plain text
and the resulting cipher text is as shown in Fig.
Knapsack steps:
First we have to choose a super-increasing knapsack (to use as the
private key) with which to encrypt our data.
I want to encrypt [0110 11111 0000 10110] in to cipher text for
that we break the binary data in to blocks that are the length of our
knapsack.
Our knapsack is {1 7 8 12 14 20} , the length is 6.
Blocks are [011011 111000 010110]
If we look at the first block (011011), there are 1s in the second,
third, fifth and sixth positions. This means that we take the second,
third, fifth and sixth positions numbers in our public key, and add
them together.

You might also like