This note offers a comprehensive explanation of one of the world's earliest public key cryptosystems. This note is self-contained and has no prerequisite except elementary knowledge in Number Theory.To view the previous two posts of my cryptography series click the links below:
A public-key cryptosystem based on a special case of the classic problem in combinatorics known as the knapsack problem was developed by Ralph Merklee and Martin Hellman in 1978.It is one of the earliest public key cryptosystems.Thsi special case of the knapsack problem is also known as the subset sum problem To explain this algorithm first we need to understand what the subset sum problem is.Here is a picture of the two developers.
It can be stated as follows :-
"Given a knapsack of volume , and elements of various volumes ,can a subset of these elements be found that will completely fill the knapsack??"
Another alternative form of the problem is :
"For positive integers and a sum ,solve the equation where the value of can be 0 or 1 for all to ."
Clearly there may be no solution,or more than one solution to the problem depending on the choice of the sequence and the integer .
For example, the equation has no solution
and the equation has 2 distinct solutions which are , and and
The solution to any randomly chosen knapsack problem is NP-hard.All the methods that are used are almost as time consuming as conducting an exhaustive search,that is testing all the possibilities of .This is computationally in-feasible for
However if the sequence of integers have some special properties ,the knapsack problem becomes much easier to solve. we call a sequence of integers to be super-increasing when is greater than each of it's preceding terms,i.e, for to .
A simple example of a super-increasing sequence is where .
If a particular knapsack problem is based on a super-increasing sequence it has an unique solution is it is solvable at all.
If we want to solve the problem where is a super-increasing sequence of integers then clearly the equation is solvable if .Working from left to right we begin by putting is and if .Then we obtain the remaining terms by choosing if if . With this algorithm in mid the super increasing knapsack problems can be solved quite easily.
we start with the largest co-efficient in the equation,hence . The next co-efficient is ,.Now the sum of the co-effiecients is ,so this cannot fill in the knapsack,so must be included . So now tthe original problem may be written as,
In this way we can solve for the terms.
Tn the Merklee-Hellman cipher,the keys are two knapsacks.The public key is the hard knapsack and the private key is the super-increasing knapsack.Two numbers,one called a multiplier and the other called a modulus are used to convert the super-increasing knapsack into the hard knapsack.These same number are used to convert the sum of the subsets of the hard knapsack into the sum of the subsets of the easy knapsack which is a problem solvable in polynomial time.
A typical user first chooses a super-increasing sequence .Then a modulus and a multiplier and and is selected.This ensures that the congruence has a unique solution say .
Then the sequence of integers defined by for all to where is selected.Carrying out this transformation generally destroys the super increasing property enjoyed by .
The user keeps secret the original sequence and and , but publishes in a public directory.Anyone who wishes to send a message employs this publicly available sequence as the encryption key.
The sender begins by converting the plaintext message into a string of s and s by using the binary representation of digits as shown below.
The string is then split into blocks of binary digits.The public encrypting sequence is then used to transform the given plaintext, say into the sum The number S is the hidden information that the sender transmits over an insecure communication channel.
Clearly since each is either or ,the problem of obtaining the plaintext block from S is equivalent to solving a difficult knapsack problem.But the private key can be used to convert this hard knapsack into an easy one.
Knowing the values of and ,the recipient computes, where ,
Since ,we have,
Because m was chosen such that , we have .So in the light of the condition must hold.The solution of this super increasing knapsack problem furnishes a solution to a difficult problem and the plain-text block is recovered which is converted back to it's alphabetic representation.
This cipher aroused a great deal of interest at the beginning because it was based on a probably hard problem but in 1982 Adi Shamir provided a fast algorithm for solving knapsack problems.The main weakness of this system is that the sequence is too special.The system can be made difficult by changing the values of and at regular intervals(iterating) but even that variant was cracked in the year 1985!! Since this cipher has been broken , it makes the RSA Cipher the dominant public key cryptography algorithm.