Find the decrypt function...

Question

Hi all.! I am to encrypt a series of numbers using this formula:

E(x)=(w * x + v )% 256

This only works if w is relatively prime to 256, i.e. the only number which divides both w and 256 is 1.

w is equal to: a % 256.
v is equal to: c % 256).
(a and c are known numbers)

So in the above equation w = a and v = c, or w = a%256 and v = c%256 ?
Also, what will be the decryption formula for the above function ?

Thanks in advance...

Vulpes · Answer

I've just picked some random values for 'a' and 'c' together with a random series of numbers and the following works fine: /* Suppose a = 263 and c = 542 So w = 7 and v = 30 */ using System; class Program { static void Main() { int[] xa = {47 96 167 234 200 10}; int[] ea = new int[xa.Length]; Console.Write(Plain : ); foreach(int x in xa) { Console.Write({03}  x); } Console.Write(
Encrypted : ); for(int x = 0; x { ea[x] = Encrypt(xa[x]); Console.Write({03}  ea[x]); } Console.Write(
Decrypted : ); for(int e = 0; e { Console.Write({03}  Decrypt(ea[e])); } Console.ReadKey(); } static int Encrypt(int x) { int w = 7; int v = 30; return (w * x + v) % 256; } static int Decrypt(int e) { int x; for(x = 0; x { int temp = Encrypt(x); if (e == temp) break; } return x; } } The output is: Plain : 47 96 167 234 200 10 Encrypted : 103 190 175 132 150 100 Decrypted : 47 96 167 234 200 10 A couple of points on this: 1. A number 'a' will give the same encrypted value as another number 'b' if: a % 256 = b % 256 For example if the first number had been 256 + 47 = 303 rather than 47 the encrypted value would still have been 103. Consequently I've assumed that all numbers in the series will lie between 0 and 255 inclusive. 2. It might be possible to come up with a decryption formula by studying the modulo arithmetic relationships in this link: http://en.wikipedia.org/wiki/Modulo_operation However rather than attempt that I've simply iterated through each possible value until I found one which gave the correct encrypted value.

Georgios Karvelas · Answer

OK finally busted it..!!.So it was quite simple afterall... only had to chose one or the other value...thanks a lot...

Vulpes · Answer

It might be simpler that that if {a % 256 b % 256} is intended to mean a choice of two values for 'w'. However if it's meant to be an interval from which you have to choose a value then I think you'll need to do what you just described.

Georgios Karvelas · Answer

Thanks alot for your answer..very enlightning...Now i got it. So the exact phrase of the problem is: Consider the cipher in which the number x is encrypted to E(x) = (w * x + v ) % 256 This only works if w is relatively prime to 256 i.e. the only number which divides both w and 256 is 1. One of {a % 256 b % 256} is equal to w. v is equal to (c % 256) I already know the numbers a b  c. (c >b>a) Does this mean i have to look for all the numbers between a and b that are co prime with 256 (gcd=1) and... randomly choose one of them to put in the decryption function ?