Ticker

6/recent/ticker-posts

Knapsack Encryption Algorithm

Knapsack Encryption Algorithm - Knapsack is an asymmetric-key cryptosystem that requires two keys for communication: a public key and a private key.

The knapsack a cryptosystem is a public-key cryptosystem based on a special case of the classic problem in combinatorics known as the knapsack problem.

It was developed by Ralph Merkle and Martin Hellman in 1978 and is one of the earliest public-key cryptosystems.

In a knapsack public key is used only for encryption and the private key is used only for decryption.



Super Increasing knapsack problem.

The super-increasing knapsack is a sequence in which every next term is greater than the sum of all preceding terms.

Example 1 –

{1, 2, 4, 10, 20, 40} is a super increasing as

1<2, 1+2<4, 1+2+4<10, 1+2+4+10<20 and 1+2+4+10+20<40.

Example 2 -

if you have a knapsack that weighs 23 that has been made from the weights of the superincreasing series {1, 2, 4, 9, 20, 38} then it does not contain the weight 38 (as 38 > 23)

  • but it does contain the weight 20; leaving 3;
  • which does not contain the weight 9 still leaving 3;
  • which does not contain the weight 4 still leaving 3;
  • which contains the weight 2, leaving 1; which contains the weight 1.
  • The binary code is therefore 110010.

Example –

  1. Let's our plain text is 100100111100101110.

1. Encryption :

As our knapsacks contain six values, so we will split our plain text into a group of six:

100100  111100  101110

Multiply each value of the public key with the corresponding values of each group and take their sum.

100100  {31, 62, 14, 90, 70, 30}

1x31+0x62+0x14+1x90+0x70+0x30 = 121

 

111100  {31, 62, 14, 90, 70, 30}

1x31+1x62+1x14+1x90+0x70+0x30 = 197

 

101110  {31, 62, 14, 90, 70, 30}

1x31+0x62+1x14+1x90+1x70+0x30 = 205

So, our cipher text is 121 197 205.

2. Decryption:

The receiver receives the ciphertext which has to be decrypted. The receiver also knows the values of m and n.
So, first we need to find the n^-1, which is multiplicative inverse of n mod m i.e.,

n x n^-1 mod(m) = 1

31 x alt="n^-1" class="ql-img-inline-formula quicklatex-auto-format" title="Rendered by QuickLaTeX.com" v:shapes="_x0000_i1027"> mod(110) = 1

n^-1 = 71

Now, we have to multiply 71 with each block of ciphertext take modulo m.

121 x 71 mod(110) = 11

Post a Comment

0 Comments