Introduction to Cryptography Part-3(The Knapsack cryptosystem)

This note has been used to help create the Knapsack Cryptosystem wiki

img1 img1

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:

The RSA Cipher

The Diffie-Hellman Key Exchange system

Introduction:-\textbf{Introduction:-}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.

imf imf

The subset sum problem:-\textbf{The subset sum problem:-}

It can be stated as follows :-

"Given a knapsack of volume VV, and nn elements of various volumes a1,a2,a3,.......,ana_1,a_2,a_3,.......,a_n,can a subset of these elements be found that will completely fill the knapsack??"

Another alternative form of the problem is :

"For positive integers a1,a2,a3,...,ana_1,a_2,a_3,...,a_n and a sum VV,solve the equation V=a1x1+a2x2+......anxnV = a_1x_1+a_2x_2+......a_nx_n where the value of xix_i can be 0 or 1 for all i=1i = 1 to nn."

Clearly there may be no solution,or more than one solution to the problem depending on the choice of the sequence a1,a2,...ana_1,a_2,...a_n and the integer VV.

For example, the equation 3x1+7x2+9x3+1x4+20x5=223x_1 + 7x_2 + 9x_3+1x_4 + 20x_5 = 22 has no solution

and the equation 3x1+7x2+9x3+11x4+20x5=223x_1+7x_2+9x_3+11x_4+20x_5 = 22 has 2 distinct solutions which are x2=x3=x4=1x_2 = x_3 = x_4 = 1 , x1=x5=0x_1 = x_5 = 0 and x2=x5=1x_2 = x_5 =1 and x1=x3=x4=0x_1 = x_3 = x_4 = 0

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 2n2^{n} possibilities of x1,x2,....xnx_1,x_2,....x_n.This is computationally in-feasible for n>100n >100

However if the sequence of integers a1,a2,....,ana_1,a_2,....,a_n have some special properties ,the knapsack problem becomes much easier to solve. we call a sequence of integers to be super-increasing when aia_i is greater than each of it's preceding terms,i.e, ai>a1+a2+...........+ai1a_i > a_1+a_2+...........+a_{i-1} for i=1i = 1 to nn.

A simple example of a super-increasing sequence is 1,2,4,8,..........2n1,2,4,8,..........2^{n} where 2i>2i1=1+2+4+........+2i12^{i} > 2^{i} - 1 = 1+2+4+........+2^{i-1}.

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 V=a1x1+a2x2+....anxnV = a_1x_1 + a_2x_2 + ....a_nx_n where a1,a2,......ana_1,a_2,......a_n is a super-increasing sequence of integers then clearly the equation is solvable if Va1+a2+...........+an V \le a_1+a_2+...........+a_n.Working from left to right we begin by putting xn=1x_n = 1 is VanV \ge a_n and xn=0x_n = 0 if V<anV < a_n.Then we obtain the remaining terms by choosing xi=0x_i = 0 if V(ai+1xi+1+........+anxn)aiV - (a_{i+1}x_{i+1}+........+a_{n}x_{n}) \ge a_i xi=1x_i = 1 if V(ai+1xi+1+........+anxn)<aiV - (a_{i+1}x_{i+1}+........+a_{n}x_{n}) < a_i . With this algorithm in mid the super increasing knapsack problems can be solved quite easily.

For example,

2x1+7x2+12x3+21x4+85x5=302x_1 + 7x_2 + 12x_3 + 21x_4 + 85x_5 = 30

we start with the largest co-efficient in the equation,85>3085 > 30hence x5=0x_5 = 0. The next co-efficient is 2121,21<3021<30.Now the sum of the co-effiecients is 2+5+12=19<302+5+12 = 19 < 30,so this cannot fill in the knapsack,so 2121 must be included . So now tthe original problem may be written as,

2x1+7x2+12x3=92x_1 + 7x_2 + 12x_3 = 9 In this way we can solve for the terms.

img img

Key-Generation for the cipher:-\textbf{Key-Generation for the cipher:-}

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.

img3 img3



Step 1.\textbf{Step 1.}A typical user first chooses a super-increasing sequence a1,a2,...,ana_1,a_2,...,a_n.Then a modulus m>2anm > 2a_n and a multiplier 0<a<m0 < a <m and and gcd(a,m)=1gcd(a,m) = 1 is selected.This ensures that the congruence ax1(modm)ax \equiv 1 \pmod{m} has a unique solution say xc(modm) x \equiv c \pmod{m}.

Step 2.\textbf{Step 2.}Then the sequence of integers b1,b2,...bnb_1,b_2,...b_n defined by biaai(modm)b_i \equiv aa_i \pmod{m} for all i=1i=1 to nn where 0<bi<m0<b_i<m is selected.Carrying out this transformation generally destroys the super increasing property enjoyed by aia_i.

Step 3.\textbf{Step 3.} The user keeps secret the original sequence a1,a2,...ana_1,a_2,...a_n and mm and aa, but publishes b1,b2,...bnb_1,b_2,...b_n 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 00s and 11s by using the binary representation of digits as shown below.

img4 img4

Step 4.\textbf{Step 4.}The string is then split into nn blocks of binary digits.The public encrypting sequence b1,b2,...,bnb_1,b_2,...,b_n is then used to transform the given plaintext, say x1,x2,...,xnx_1,x_2,...,x_n into the sum S=b1x1+b2x2+......bnxnS = b_1x_1 + b_2x_2 +...... b_nx_n The number S is the hidden information that the sender transmits over an insecure communication channel.

Clearly since each xix_i is either 00 or 11,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 cc and mm,the recipient computes, S=cS(modm)S' = cS \pmod{m} where 0<S<m0 < S' < m,

S=cb1+cb2+cb3+....+cbn(modm)S' = cb_1 + cb_2 + cb_3 + .... +cb_n \pmod{m}

S=caa1+caa2+caa3+....+caan(modm)S' = caa_1 + caa_2 + caa_3 + .... +caa_n \pmod{m}

Since ca1(modm)ca \equiv 1 \pmod{m} ,we have,

S=a1x1+....+anxn(modm)S' = a_1x_1 + .... + a_nx_n \pmod{m}.

Because m was chosen such that m>2an>a1+a2+...+anm > 2a_n > a_1 + a_2 +... + a_n, we have a1x1+....+anxn<ma_1x_1 + .... + a_nx_n < m.So in the light of the condition S=a1x1+....+anxnS' = a_1x_1 + .... + a_nx_n must hold.The solution of this super increasing knapsack problem furnishes a solution to a difficult problem and the plain-text block x1,x2,....xnx_1,x_2,....x_n is recovered which is converted back to it's alphabetic representation.

Click this link to see the knapsack cryptosystem at work

Security:-\textbf{Security:-}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 b1,b2,....,bnb_1,b_2,....,b_n is too special.The system can be made difficult by changing the values of aa and mm 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.

inh inh

Note by Eddie The Head
7 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...