Find the decrypt function...

Georgios Karvelas

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...

4 Replies

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

Vulpes12y ago
Accepted 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("{0,3} ", x);
}

Console.Write("\nEncrypted : ");
for(int x = 0; x < xa.Length; x++)
{
ea[x] = Encrypt(xa[x]);
Console.Write("{0,3} ", ea[x]);
}

Console.Write("\nDecrypted : ");

for(int e = 0; e < ea.Length; e++)
{
Console.Write("{0,3} ", 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 < 256; 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.

0
Georgios Karvelas12y ago
OK, finally busted it..!!.So, it was quite simple afterall... only had to chose one or the other value...thanks a lot...
0
Vulpes12y ago
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.
0
Georgios Karvelas12y ago
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 ?
0