Merkle Hellman Algorithm

Question

hey ! I need any help or idea about merkle hellman application and where I can use it in another way ( not in cryptosystem ) sorry for that but im a new student  and dont know how to make a paper so please .... please I need any help just for once and then I'll do it myself. regards

Vulpes · Answer

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(
The encoded string is :
); int count = 0; for(int i= 0; 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(
The 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 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 { string bin = ConvertToBinary(plainText[i]); int sum = 0; for(int j = 0; 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 { char[] bin = new char[8]; for(int j = 0; j int temp = encoded[i] * mir % q; while(temp > 0) { int index = 7; for(int j = 1; 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 return v; } }