Brute forcer to keygen

[Scooby D0o]

Hi all

i recently tried to keygen a program but found that i could only make a
brute forcer for it

If "serial" Mod (("serial" Mod 131) + 16127) = 29 Then "serial is good"

was the main part, but when i tried to make a keygen....
i had no such luck, so if anyone could help me out that would be cool =)

Scooby D0o

[Blind Angel]

Hiho

x mod ((x mod 131) + 16127) = 29 means
x mod [16127..16257] = 29

(cause x mod 131 is an integer [0..130])

and x mod (16127 + i) = 29 with 0 <= i < 131 can be written as:

x = n * (16127+i) + 29 [with 0 <= i < 131]

Due to the nice bounds and n being an integer you can easily write a fast 'brute-force' like that:

unsigned long x;

int i, n;



for (n=0; n < 100; n++) {

*for (i=0; i < 131; i++) {

* x = n * (16127 + i) + 29;

* if (x % 131 == i) { * * * * * // check if i == x mod 131 :)

* *printf("Valid x: %ldn", x);

* }

*}

}



Of course 'n' can be adjusted to match other criteria (and get real large ;) but it should be enough as demonstration :)

[kw]

That is a very nice and clean algo you deduced there, me like :)
bruting that should take very very little time.. So it should be perfectly usable as a keygen.. Of course to generate random serials, you can just randomize starting point 'n' and stop at the next matching value. Should be pretty fast and pretty..

-kw

[Haldir]

Let's do it properly now ;)
x mod ((x mod 131) + 16127) = 29
We choose a random value between 0 and 130 (not 117, because then 131 and 16127+117 are not relatively prime)
then we use the Chinese Remainder Theorem
to solve two equations:
x%131 = y and x%16127+y = 29
The CRT can be used to find a value which is valid
for two independent modular equations (with some limitations).
Actually the real background behind that equation above is a Galois Field, but i won't discuss that here (maybe you wondered why the values are prime ?)
Using the CRT is the easy way ;)

Some proper values are:
y=111
x=487169
y=42
x=646789
y=20
x=306822


Just some notice for numbers below 16127+130, the only valid solution is 29 ;)

[Haldir]

Since several people asked me how some source code would look like for it, here is a routine which outputs the 130 possible values (using NTL):



for(int i = 0; i < 131;i++)

{

// we don't want 117

if(i != 117) {

ZZ p1,p2,x,rand;

// definitions of some values

p2 = 16127;

x = 29;

p1 = 131;

rand = i;

cout << rand << "n";

// our chinese remainder routine (integrated in NTL)

CRT(rand,p1,x,p2+rand);

// the part below is just necessary since NTL

// uses a slightly different CRT (results might be negative)

// so we convert it back to positive

ZZ_p::init(p1);

ZZ_p output;

output = to_ZZ_p(rand);

// output...

cout<< output << "n";

}

}

[Scooby D0o]

thanx for the help with my question ppl
tho i didn't realize at the time i forgot to mention the serial
must be greater that 1000000

[Blind Angel]

Nice answer pointing to CRT.

I haven't read much about the CRT yet (besides a quick read-over about it from applied cryptography 2 min ago). My only orientation was a paper I wrote for school about RSA and thus the rules of modular arithmetics ... but you know school - never try to give them more than needed .. :)

here is a routine which outputs the 130 possible values
maybe I misunderstood but ... why 130 possible values?

I modified my code slightly going from n = 63 to 132095. 63 because 16127 * 63 > 100000 and didn't want to use another check to determine x > 100000 for n = 62. 132096 * (16127+130) > 2^31 and although declared as unsigned long int my the results are negative .. so ... screw em *g*

Please note that I am not using any bignum library / math implementations and am limited to 32bit variables ... cause normally I write these test-codes using good old turbo c 2.01 :D

unsigned long x, n, cnt;

int i;



cnt=0;



for (n=63; n < 132096; n++) {

*for (i=0; i < 131; i++) {

* x = n * (16127 + i) + 29;

* if (x % 131 == i) { * * * * * // check if i == x mod 131 :)

* *printf("Valid x: %ld, using n=%ld and y = %dn", x, n, i);

* *cnt++

* }

*}

}

printf ("Found %ld possibilities...n", cnt);

This will output a list of numbers and count 131025 possibilities...

[Haldir]

There are 130 unique values, the others are just modular congruent to them (like 5%3 == 2 and 8%3 == 2 too)