Number Theory & Cryptography - Assignement 2 - Question 2: Implement Knapsack Cryptosystem. - Done with Aviral - November 10, 2011

knapsack.gp

/* Question 2: Implement Knapsack Cryptosystem. */

/*
   n - the size of all vectors is fixed at 7.
   a is the superincreasing sequence (assumed public key of receiver)

   example a:
	[1,2,4,8,16,32,64]
   m, a 7-bit number - the message to be encrypted
   c, ciphertext
*/

knapsacksum(x, a) = {
	s = 0;
	n = 7;
	i = 1;
	while( ( i <= n ),
		s = s + a[i]*x[i];
		i++;
	);
	/*print(s);*/
	return(s);
}

invknapsacksum(s, a) = {
	n = 7;
	i = n;
	x = vector(n);
	while( ( i >= 1 ),
		if( ( s >= a[i] ), 
			
				x[i] = 1;
				s = s - a[i];
			,
			
				x[i] = 0;
			
		);
		i--;
	);
	/*print(x);*/
	return(x);
}

ksencrypt(m) = {
	a = [1,2,4,8,16,32,64];
	x = binary(m);
	print(x);
	s = knapsacksum(x, a);
	print(s);
}

ksdecrypt(c) = {
	a = [1,2,4,8,16,32,64];
	x = invknapsacksum(c, a);
	m = 0;
	i = 1;
	while( ( i<=7 ),
		m = m + x[8-i]*2^(i-1);
		i++;
	);
	print(m);
}