Knap-Sack Encryption

Knap-Sack Encryption

This is an old encryption method. Nowadays even desktop computers can break the key. A simple implementation of this encryption method can be found here. This program takes a string and encrypts it with knap-sack.

The Algorithm

C Source Code

File Name: Knapsack.cpp

/*
  This program encrypts a text array using Knap-Sack algorithm
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#include<time.h>
#include< Knapsack.h>

unsigned long calc_fim(unsigned int m)
{
  unsigned long fim, t, i, j, s;
  unsigned int carpan[100]={0};

  t = Asal[0];
  i = 1;
  j = 0;
  while ((m > t) && (i< Asal_Adet))
    if ((m % t) == 0)
     {
       carpan[j] = t;
       j++;
       m = m / t;
     }
    else // bir sonraki asal sayy test edilecek
     {
       t = Asal[i];
       i++;
     }
  carpan[j] = t;
  j++;
  i = 1;
  t = carpan[0];
  fim = t - 1;
  s = 1;
  m = t;
  while (i < j)
   {
     if (carpan[i] == t)
      {
            s++;
            m = m * t;
      }
     else
      {
            m = m / t;
            fim = fim * m;
            t = carpan[i];
            fim = fim * (t-1);
            s = 1;
            m = t;
      }
     i++;
   }
  if (s > 1)
   {
     m = m / t;
     fim = fim * m;
   }
  fim--;
  return fim;
}

unsigned long findmod(unsigned long a, unsigned long b, unsigned long c)
{
  unsigned long i, s, x, t;
  x = a % c;
  s = 1;
  while (b != 0)
   {
     i = b & 1; // 0 for even, 1 for odd
     b = b >> 1;
     t = (x * i) % c;
     if ( t != 0)
       s = (s * t) % c;
     x = (x * x) % c;
   }
  return s;
}

unsigned long TPower(int a, int b)
{
  unsigned long i, r=1;
  if (b > 0) // Mesela 2^0 = 1  'dir
     for(i=0;i<b;i++)
       r = r * a;
  return r;
}

int encode( unsigned int A[],
                 char Text[],
                 char AN,
                 unsigned int t,
                 unsigned int m,
                 unsigned long sifre[],
                 unsigned int *L )
{
  long i, j, n;
  unsigned int B[10], s;
  char T1, T2;
  for(i=0;i<10;i++)
   {
     B[i] = (t * A[i]) % m;
   }
  *L = 0;
  i = 0;
  while(i<AN)
   {
     n = 0;
     T2 = Text[i];
     T1 = Text[i+1];
     s = 9; // last element is 9
     for(j=0;j<5;j++)
      {
       if( (T2 & 1) > 0 ) // odd number
             n = n + B[s];
       s--;
       T2 >>=1; // division by 2
      }
     for(j=0;j<5;j++)
      {
       if( (T1 & 1)> 0 ) // odd number
             n = n + B[s];
       s--;
       T1 >>=1; // division by 2
      }
     sifre[*L] = n;
     *L = *L + 1;
     i +=2;
   }
  return 0;
}

int decode( unsigned int A[],
                   char Text_Geri[],
                   unsigned int t,
                   unsigned int m,
                   unsigned int L,
                   unsigned long sifre[] )
{
  unsigned long i, j, p, x, u, m_1;
  unsigned int k, s;
  int z;
  m_1 = calc_fim(m);
  u = findmod(t, m_1, m);

  j = 0;
  for(i=0;i<L;i++)
   {
     p = sifre[i];

     s = (p * u) % m;
     x = 0;
     k = 0;
     for(z=9;z>=5;z--)
      {
            if(s >= A[z])
             {
               x = x + TPower(2, k);
               s = s - A[z];
             }
            k++;
      }
     Text_Geri[j] = x;
     k = 0;
     x = 0;
     for(z=4;z>=0;z--)
      {
            if(s >= A[z])
             {
               x = x + TPower(2, k);
               s = s - A[z];
             }
            k++;
      }
     Text_Geri[j+1] = x;
     j += 2;
   }

  return 0;
}

void main(void)
{
  char Text[50]={0}, Text_Geri[50]={0}, AN;
  unsigned long sifre[50]={0};
  unsigned int i, L, t, m, A[10]={1,3,5,11,21,44,87,175,349,701};
  clrscr();
  printf("Input Text: ");scanf("%s", Text);
  printf("t :");scanf("%d", &t);
  printf("m :");scanf("%d", &m);
  AN = strlen(Text);
  for(i=0;i<AN;i++) Text[i] = toupper(Text[i]);
  for(i=0;i<AN;i++) Text[i] = Text[i] - 64;
  encode(A, Text, AN, t, m, sifre, &L);
  decode(A, Text_Geri, t, m, L, sifre);
// visualization
  for(i=0;i<AN;i++) Text_Geri[i] = Text_Geri[i] + 64;
  printf("Encoded output : ");
  for(i=0;i<L;i++)
    printf("%ld ",sifre[i]);
  Text_Geri[AN+1] = NULL;
  printf("\nDecoded text : %s", Text_Geri);

  getch();
}

File Name: KNAPSACK.H

#define Asal_Adet 168

Asal[168] = {  2, 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
                   67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,
                   139,149,151,157,163,167,173,179,181,191,193,197,199,
                   211,223,227,229,233,239,241,251,257,263,269,271,277,
                   281,283,293,307,311,313,317,331,337,347,349,353,359,
                   367,373,379,383,389,397,401,409,419,421,431,433,439,
                   443,449,457,461,463,467,479,487,491,499,503,509,521,
                   523,541,547,557,563,569,571,577,587,593,599,601,607,
                   613,617,619,631,641,643,647,653,659,661,673,677,683,
                   691,701,709,719,727,733,739,743,751,757,761,769,773,
                   787,797,809,811,821,823,827,829,839,853,857,859,863,
                   877,881,883,887,907,911,919,929,937,941,947,953,967,
                   971,977,983,991,997};

Sample Executions

Input Text : BIZ_DE_BURADAN_GECTIK

t :43

m :1590

Encoded output: 1729 3323 2283 4721 3506 1738 2340 5839 4064 2499 2781

Decoded text : BIZ_DE_BURADAN_GECTIK

Input Text : BUNDAN_DAHA_IYISI_OLAMAZ

t :43

m :1590

Encoded output : 1858 2638 2340 4463 1652 3286 3159 3503 3847 4290 2770 2168

Decoded text : BUNDAN_DAHA_IYISI_OLAMAZ