Cryptography: Markle-Hellman knapsack cryptosystem Algorithm

Markle-Hellman knapsack cryptosystem Algorithm

Description :-

MerkleHellmanis an asymmetric key crypto-system based on the subset sum problem. The problem is as follows:

Given a set of numbers A and a number b, find a subset of A which sums to b.

In general, this problem is known to be NP-complete. However, if the set of numbers are super-increasing (i.e. each element of the set is greater than the sum of all the numbers before it) the problem is "easy" and solvable in polynomial time with a simple greedy algorithm.

Key-generation :-

In MerkleHellman,the keys are two knapsacks(set of numbers). The public key is a 'hard' knapsack A, and the private key is an 'easy'(super-increasing), knapsack B, combined with two additional numbers, a multiplier and a modulus.

The multiplier and modulus can be used to convert the super-increasing knapsack into the hard-knapsack. These same numbers are used to transform the sum of the subset of the hard knapsack into the sum of the subset of the easy knapsack, which is a problem that is solvable in polynomial time.

Encryption :-

To encrypt a message, a subset of the hard knapsack A is chosen by comparing it with a set of bits (the-plaintext) equal in length to the key.
Elements corresponding to 1 are taken and those corresponding to 0 are ignored while constructing the subset A_m. The elements of this subset are added together and the resulting sum is the ciphertext.

Decryption :-

Decryption is possible because the multiplier and modulus used to transform the easy knapsack into the public key can also be used to transform the ciphertext into the sum of the corresponding elements of the superincreasing knapsack.
Then, using a simple greedy algorithm, the easy knapsack can be solved using O(n) arithmetic operations, which decrypts the message.

MATHEMATICAL MODEL

KEY GENERATION

To encrypt n-bit messages, choose a superincreasing sequence of n nonzero natural numbers.
w = (w₁, w₂, ..., w_n)
Pick a random integer q, such that
$q>\sum_{i = 1}^n w_i$ ,
and a random integer r co-prime to q.

q is chosen this way to ensure the uniqueness of the cipher-text. (If it is any smaller, more than one plaintext may encrypt to the same ciphertext.)
Since q is larger than the sum of every subset of w, no sums are congruent mod q and therefore none of the private key's sums will be equal.
r must be coprime to q or else it will not have an inverse mod q. The existence of the inverse of r is necessary so that decryption is possible.

Now calculate the sequence
β = (β₁, β₂, ..., β_n)
where
β_i = rw_i mod q.

The public key is β, while the private key is (w, q, r).

ENCRYPTION

To encrypt an n-bit message [ α = (α₁, α₂, ..., α_n) ] where each

\alpha_i

is either 0 or 1, calculate

c = \sum_{i = 1}^n \alpha_i \beta_i.

c is the cipher-Text.

DECRYPTION

In order to decrypt a ciphertext c a receiver has to find the message bits α_i such that they satisfy

c = \sum_{i = 1}^n \alpha_i \beta_i.

If the β_i were random values , the receiver would have to solve an instance of the subset sum problem(NP-hard).

However, the values β_i were chosen such that decryption is easy if the private key (w, q, r) is known.

Find an integer s that is the modular inverse of r modulo q.
sr = kq + 1
Since gcd(r,q)=1,s and k can be found out by using the Extended Euclidean algorithm.
Next the receiver of the ciphertext c computes
$c'\equiv cs \pmod{q}.$
Hence
$c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}.$
Because (rs mod q = 1) and (β_i = rw_i) mod q follows

$\beta_i s\equiv w_i r s\equiv w_i\pmod{q}.$
Hence
$c' \equiv \sum_{i = 1}^n \alpha_i w_i\pmod{q}.$
The sum of all values w_i is smaller than q and hence $\sum_{i = 1}^n \alpha_i w_i$ is also in the interval [0,q-1]. Thus the receiver has to solve the subset sum problem
$c' = \sum_{i = 1}^n \alpha_i w_i.$
This problem is easy because w is a super-increasing sequence.
Take the largest element in w, say w_k. If w_k > c' , then α_k = 0, if w_k≤c' , then α_k = 1. Then, subtract w_k×α_k from c' , and repeat these steps until you have figured out α.

EXAMPLE

a superincreasing sequence w is created

w = {2, 7, 11, 21, 42, 89, 180, 354}

From this, calculate the sum.

\sum w = 706

Now choose a number q that is greater than the sum.

q = 881

Now choose a number r that is in the range $[1, q)$ and is coprime to q.

r = 588

The private key consists of q, w and r.

To calculate a public key generate the sequence β by multiplying each element in w by r mod q

β = {295, 592, 301, 14, 28, 353, 120, 236}

because

(2 * 588) mod 881 = 295  
(7 * 588) mod 881 = 592  
(11 * 588) mod 881 = 301 
(21 * 588) mod 881 = 14  
(42 * 588) mod 881 = 28  
(89 * 588) mod 881 = 353 
(180 * 588) mod 881 = 120
(354 * 588) mod 881 = 236

The sequence β makes up the public key.

Say Alice wishes to encrypt "a".

a=01100001

She multiplies each respective bit by the corresponding number in β

a = 01100001
0 * 295     
+ 1 * 592   
+ 1 * 301   
+ 0 * 14    
+ 0 * 28    
+ 0 * 353   
+ 0 * 120   
+ 1 * 236   
  = 1129

She sends this to the recipient.

To decrypt, Bob multiplies 1129 by r ⁻¹ mod q

1129 * 442 mod 881 = 372

Now Bob decomposes 372 by selecting the largest element in w which is less than or equal to 372.
Then selecting the next largest element less than or equal to the difference, until the difference is 0:

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0

The elements we selected from our private key correspond to the 1 bits in the message

01100001

This "a" is the final decrypted message.

Cryptography

Monday, March 23, 2015

Markle-Hellman knapsack cryptosystem Algorithm

MATHEMATICAL MODEL

KEY GENERATION

ENCRYPTION

DECRYPTION

EXAMPLE

No comments:

Post a Comment