Trying to decrypt a PHP PseudoCrypt class

Question

I am trying to create a way to reverse the PseudoCrypt script listed at: http://blog.kevburnsjr.com/php-unique-hash. In this code it has the following equation:

$dec = ($num * $prime)-floor($num * $prime/$ceil)*$ceil;

I have been able to get every variable except for the $num. For instance take the following numbers:

$dec = 566201239;
$prime = 566201239;
$ceil = 916132832;

The equation would then look like this:

566201239 = ($num * 566201239)-floor($num * 566201239/916132832)*916132832;

The answer should be 1. However I have not determined the way make the equation = $num. I am wanting to use the hash it creates in a URL, then decrypt the hash to perform queries in my database.

Edit: If there is a better way to create a hash that will be unique with very little room for duplication I would be open to that instead.

Edit: Somehow I put the wrong value in for $dec. Edit: Blog posting updated with functioning code.

Answer 1

Thanks to some help from commenter Padraig Kennedy, the library has been upgraded to support reversibility
http://blog.kevburnsjr.com/php-unique-hash

Answer 2

Observe that

thing - floor(thing/ceil)*ceil

is the same as (thing%ceil) where % is the modulo operator (remainder after division). In your case,

$dec = ($num * $prime) % $ceil

Note that this is always between 0 and $ceil-1, so the value $dec you have, which is equal to $ceil, cannot be obtained. On the other hand, for a given $dec between 0 and $ceil-1, you can efficiently find a solution $num between 0 and $ceil-1.

(An observation is that if $num is a solution than $num+i*$ceil for any i is a solution as well.)

Here is how you proceed for $dec=42.

We will use the fact that $ceil = 2^5 * 31^5. The equation thus gives

42 = ($num * 566201239) % (2^5 * 31^5)

First let us find ($num%2), in other words, whether $num is odd or even. We take both sides of the equation modulo 2:

0 = 42 % 2 = (($num * 566201239) % (2^5*31^5)) % 2.

Since 2 divides $ceil, the right-hand side is ($num * 566201239)%2. If this has to be 0, $num has to be even (since $prime is not). We thus have ($num = 2*$a) for some $a and

2*21 = 42 = (2 * $a * 566201239) % (2^5 * 31^5),

after division by 2 we get

21 = ($a * 566201239) % (2^4 * 31^5).

Note that the part after the % sign got divided by 2 as well. We continue by taking this modulo 2. We get that $a is odd, i.e., $a = 2*$b+1 for some $b.

21 = ((2*$b+1) * 566201239) % (2^4 * 31^5),

349931614 ≡ 21-566201239 ≡ (2*$b * 566201239) % (2^4 * 31^5),

(I started to use the congruence notation ≡; by x ≡ y % z I mean x%z = y%z).

174965807 ≡ ($b * 566201239) % (2^3 * 31^5)

We continue...

174965807 ≡ ((2*$c+1) * 566201239) % (2^3 * 31^5)

174965807 - 566201239 ≡ (2*$c * 566201239) % (2^3 * 31^5)

66830984 ≡ 2*$c * 566201239) % (2^3 * 31^5)

33415492 ≡ ($c * 566201239) % (2^2 * 31^5)

33415492 ≡ (2*$d * 566201239) % (2^2 * 31^5)

16707746 ≡ ($d * 566201239) % (2 * 31^5)

16707746 ≡ (2*$e * 566201239) % (2 * 31^5)

8353873 ≡ ($e * 566201239) % (31^5).

To summarize the substitutions, recall that

$num = 2*$a = 2*(2*$b+1) = 4*$b+2 = 4*(2*$c+1)+2 = 8*$c+6 = 8*2*$d+6 = 8*2*2*$e+6 = 32*$e + 6

By the way, we can reduce the $prime in the equation modulo 31^5 as well (we could keep reducing it by the current modul in each step, but who cares?):

8353873 ≡ ($e * 22247370) % (31^5).

We can see that the multiplier is not a prime, but in fact it does not matter.

Now we look at the last equation modulo 31.

8353873 ≡ ($e * 22247370) % (31^5).

24 ≡ 8353873 ≡ ($e * 22247370) % (31^5) ≡ ($e*22247370) ≡ ($e*3) % 31

In a lookup table of multiples of 3 modulo 31 we find that $e≡8 % 31, or that $e=31*$f+8:

8353873 ≡ ((31*$f+8) * 22247370) % (31^5).

8353873 - 8*22247370 ≡ (31*$f*22247370) % (31^5).

2149819 ≡ 8353873 - 8*22247370 ≡ (31*$f*22247370) % (31^5).

69349 = 2149819/31 ≡ ($f*22247370) % (31^4)

and we go on...

2 ≡ 69349 % 31 ≡ ($f*22247370) % (31^4) ≡ ($f*3) % 31

$f ≡ 11 % 31

$f = 31*$g + 11

69349 ≡ ((31*$g+11)*22247370) % (31^4)

81344 ≡ 69349 - 11*22247370 ≡ (31*$g*22247370) % (31^4)

2624 ≡ ($g*22247370) % (31^3)

Let us reduce the multiplier again...

2624 ≡ ($g*23284) % (31^3)

20 ≡ 2624 ≡ ($g*23284) % (31^3) = ($g*3) % 31

$g = 31*$h+17

2624 ≡ ((31*$h+17)*23284) % (31^3)

23870 ≡ 2624 - 17*23284 ≡ (31*$h*23284) % (31^3)

770 ≡ ($h*23284) % (31^2)

26 ≡ 770 ≡ ($h*23284) % (31^2) = ($h*3) % 31

$h = 31*$i + 19

770 ≡ ((31*$i+19)*23284) % (31^2)

434 ≡ 770 - 19*23284 ≡ (31*$i*23284) % (31^2)

14 = ($i*3) % 31

$i = 15

and by backward substitution we get $h=31*15+19 = 484, $g=31*$h+17 = 15021, $f=31*$g+11 = 465662, $e=31*$f+8 = 14435530, $num=32*e+6 = 461936966.

It remains just to check the result:

.>>> (461936966*566201239)%916132832

42

Wow! :-)

The guy of the blog should have rather used md5.

Answer 3

As this is called a Hash function by its author, I do not think it can be 'decrypted'. When searching long enough, you will find multiple inputs that produce the same Hash, so there is no way to know wich one was used.