How *do* you break this cypher? He is generating a lot of random numbers between 0 and 255, and xor'ing each successive one with the next byte of plain- text. I know that this is a trivial cypher to break, according to PRZ at least, but how do you do it?
In this case, since the modulus is a small power of 2, you can do exhaustive search. There is _one_ sequence of 256 distinct values. Still want to know how long it will take to crack his ciphertext?
#define MULTIPLIER 0x015a4e35L #define INCREMENT 1
long RandomSeed;
int GetRandomNumber(int Range) { RandomSeed = MULTIPLIER * RandomSeed + INCREMENT; return(RandomSeed % Range); }
So how do you crack this cipher without trying all the keys, guys?
Since max_integer / gcd (range, max_integer) > range you can move the modulus operation around without worrying about weird effects from the finite word size. This is because the closed form of the loop is: seed[k] = (seed[0] * mult^k + incr * sum (j = 0 to k-1) of mult^j) % range which is equal to seed[k] = (seed[0] % range) * (mult % range)^k + (incr % range) * sum (j = 0 to k-1) of (mult % range)^j and the modulus operation with a power-of-2 range simply keeps the last n bits. But, this also means there are effectively only "range" possible values for the initial seed. Even if you make the increment and multiplier part of the key, they must (both?) be odd so you only have 22 bits of key. Of course at this point you can simply use the fact that this "one time pad" is actually a Vigenere cipher with 256 columns -- easy to crack if you have some insight into the nature of the plaintext (e.g., English text). For instance, 10-15 small documents (40 lines) encrypted with the same key is enough to crack it even if the multiplier and increment are unknown but constant. Bear Giles