Merkle Hellman Algorithm

I couldn't find any C# implementation of the Merkle-Hellman algorithm on the internet so I've written my own using this Wikipedia article as a guide:

http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem

and this implementation of the Modular Inverse Function:

http://www.dzone.com/snippets/modular-inverse-function

I've no idea what use this algorithm is outside cryptography so I assume you have something in mind:

using System;

class Merkle_Hellman

{

static void Main()

{

int[] w = {2, 7, 11, 21, 42, 89, 180, 354}; // super-increasing

int q = 881;

int r = 588;

int[] beta = GetPublicKey(w, q, r);

Console.Write("Enter string to be encoded : ");

string plainText = Console.ReadLine();

int[] encoded = Encrypt(plainText, beta);

Console.WriteLine("\nThe encoded string is :\n");

int count = 0;

for(int i= 0; i < encoded.Length; i++)

{

Console.Write("{0, 5}", encoded[i]);

count++;

if (count == 16)

{

count = 0;

Console.WriteLine();

}

if (count > 0) Console.WriteLine();

string decoded = Decrypt(encoded, w, q, r);

Console.WriteLine("\nThe decrypted string is : {0}", decoded);

Console.ReadKey();

}

static int[] GetPublicKey(int[] w, int q, int r)

{

int[] beta = new int[w.Length];

for(int i = 0; i < w.Length; i++) beta[i] = w[i] * r % q;

return beta;

}

static int[] Encrypt(string plainText, int[] beta)

{

if (String.IsNullOrEmpty(plainText)) return null;

int[] encoded = new int[plainText.Length];

for(int i = 0; i < encoded.Length; i++)

{

string bin = ConvertToBinary(plainText[i]);

int sum = 0;

for(int j = 0; j < 8; j++) sum += (bin[j] - 48) * beta[j];

encoded[i] = sum;

}

return encoded;

}

static string Decrypt(int[] encoded, int[] w, int q, int r)

{

if (encoded == null || encoded.Length == 0) return null;

char[] chars = new char[encoded.Length];

int mir = ModInverse(r, q);

if (mir == 0)

{

Console.WriteLine("Modular inverse does not exist. Decryption aborted");

return null;

}

for(int i = 0; i < encoded.Length; i++)

{

char[] bin = new char[8];

for(int j = 0; j < 8; j++) bin[j] = '0';

int temp = encoded[i] * mir % q;

while(temp > 0)

{

int index = 7;

for(int j = 1; j < w.Length; j++)

{

if(w[j] > temp)

{

index = j - 1;

break;

}

bin[index] = '1';

temp -= w[index];

}

chars[i] = ConvertFromBinary(new string(bin));

}

return new string(chars);

}

static string ConvertToBinary(char c)

{

return Convert.ToString((int)c, 2).PadLeft(8, '0');

}

static char ConvertFromBinary(string bin)

{

return (char)Convert.ToInt32(bin, 2);

}

static int ModInverse(int r, int q)

{

int i = q, v = 0, d = 1;

while (r > 0)

{

int t = i/r, x = r;

r = i % x;

i = x;

x = d;

d = v - t * x;

v = x;

}

v %= q;

if (v < 0) v = (v+q) % q;

return v;

}

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Vulpes13y ago
I couldn't find any C# implementation of the Merkle-Hellman algorithm on the internet so I've written my own using this Wikipedia article as a guide:

http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem

and this implementation of the Modular Inverse Function:

http://www.dzone.com/snippets/modular-inverse-function

I've no idea what use this algorithm is outside cryptography so I assume you have something in mind:

using System;

class Merkle_Hellman
{
static void Main()
{
int[] w = {2, 7, 11, 21, 42, 89, 180, 354}; // super-increasing
int q = 881;
int r = 588;
int[] beta = GetPublicKey(w, q, r);

Console.Write("Enter string to be encoded : ");
string plainText = Console.ReadLine();
int[] encoded = Encrypt(plainText, beta);
Console.WriteLine("\nThe encoded string is :\n");
int count = 0;

for(int i= 0; i < encoded.Length; i++)
{
Console.Write("{0, 5}", encoded[i]);
count++;
if (count == 16)
{
count = 0;
Console.WriteLine();
}
}

if (count > 0) Console.WriteLine();

string decoded = Decrypt(encoded, w, q, r);
Console.WriteLine("\nThe decrypted string is : {0}", decoded);
Console.ReadKey();
}

static int[] GetPublicKey(int[] w, int q, int r)
{
int[] beta = new int[w.Length];
for(int i = 0; i < w.Length; i++) beta[i] = w[i] * r % q;
return beta;
}

static int[] Encrypt(string plainText, int[] beta)
{
if (String.IsNullOrEmpty(plainText)) return null;
int[] encoded = new int[plainText.Length];

for(int i = 0; i < encoded.Length; i++)
{
string bin = ConvertToBinary(plainText[i]);
int sum = 0;
for(int j = 0; j < 8; j++) sum += (bin[j] - 48) * beta[j];
encoded[i] = sum;
}

return encoded;
}

static string Decrypt(int[] encoded, int[] w, int q, int r)
{
if (encoded == null || encoded.Length == 0) return null;
char[] chars = new char[encoded.Length];
int mir = ModInverse(r, q);
if (mir == 0)
{
Console.WriteLine("Modular inverse does not exist. Decryption aborted");
return null;
}

for(int i = 0; i < encoded.Length; i++)
{
char[] bin = new char[8];
for(int j = 0; j < 8; j++) bin[j] = '0';
int temp = encoded[i] * mir % q;

while(temp > 0)
{
int index = 7;

for(int j = 1; j < w.Length; j++)
{
if(w[j] > temp)
{
index = j - 1;
break;
}
}

bin[index] = '1';
temp -= w[index];
}

chars[i] = ConvertFromBinary(new string(bin));
}

return new string(chars);
}

static string ConvertToBinary(char c)
{
return Convert.ToString((int)c, 2).PadLeft(8, '0');
}

static char ConvertFromBinary(string bin)
{
return (char)Convert.ToInt32(bin, 2);
}

static int ModInverse(int r, int q)
{
int i = q, v = 0, d = 1;

while (r > 0)
{
int t = i/r, x = r;
r = i % x;
i = x;
x = d;
d = v - t * x;
v = x;
}

v %= q;
if (v < 0) v = (v+q) % q;
return v;
}
}