MOD calculation / reversing

[raduga_fb]

Hi all.

I am going to prepare a keygen. I need your help.

c = MOD (a * MOD (a*a, b) , b)

(for example, c=48765, b=67890 -> a=12345, can be more valid "a")

"c" and "b" are known. I need to calculate the "a".

"a" and "b" are in 256 digits as Hex, "c" is almost same. They are not Prime.

Thanks,

[raduga_fb]

:-) I have done a progress

c = MOD (a^3, b)

[te$ter]

There is no unique "a" for this condition.
For example for current "b" and "c", "a" may be 3585, 12345, 31965, 42195, 47295...

[raduga_fb]

"a" can be 3 numbers (max.) I am still searching for information on net. In my case;
1 = MOD (b, 3)
4 = MOD (b, 9)

"b" is not prime.

[wilson bibe]

Maybe this function can help you:

#include <stdio.h>
#include <conio.h>

int main(void)
{
int a,b,res

printf ("\nenter a number:");
scanf ("%d", &a);

a = a * a;
a= int a;

printf ("\nenter a number:");
scanf ("%d", &b);

b = b;

res = a / b;

a = a * res;

a = int a;

res = a / b;

printf("\nResult of division of %d / %d = %d. \n",a,b,res));

getch();
return(0);
}

[raduga_fb]

I said that "b" is not a prime. I used the "bdcalc" to test it by function "isprime()". But, I have a doubt now :-(

if "b" is a prime and b = 4 MOD 9 (in my case), the root can be calculated ->
root = powermod (a,(2*b + 1)/9, b)
But, it is quite difficult to calculate it for 128 bytes length numbers (a, b). Any suggestion ?

[bilbo]

Hi raduga_fb,
I think you must provide us more details...

If a can be as big as 256 hex digits, as you said in your first post, using a big integers library and an exhaustive loop, the values which solve your equation

c = MOD (a^3, b)

are many and many, as te$ter pointed out: I calculated 603000 possible solutions for a in the range 0 - 0x10f1e8fab, using for c and b the values you gave!

If numbers are to be manipulated with regular C functions (as wilson bibe suggested), where the max value for a can just be 0x7FFFFFFF, then

c = MOD (a * MOD (a*a, b) , b)

is different from

c = MOD (a^3, b)

for a > 1290 (cube root of 0x7FFFFFFF)!

In any case, the MOD operator is not reversable, in the sense that many inputs can give the same output:

a = b % c

is equivalent to the expression

a + nc = b

with n which can assume all integer values...

Best regards
bilbo

[wilson bibe]

@bilbo
The formula proposed by raduga_fb is wrong C it's not equal C = MOD (a^3, b) to C = MOD (a * MOD (a*a, b) , b), basic math, we are talking about the "rest" in a division, so, multiplie the operands is wrong.
All the best to you

[raduga_fb]

Example ->

b=10093 as a prime, c=5072 ->

root = powmod (c, (2*b + 1)/9, b) = powmod (5072, 2243, 10093) = 777

5072 = 777^3 MOD 10093

as you see, MOD is reversible in some cases...


a = 777
b= 10093

c = 777 * (777 * 777 Mod 10093) Mod 10093 = 777^3 MOD 10093

[bilbo]

@raduga_fb
this sounds interesting... furthermore, in that case the solution is unique!
I need more investigations

@wilson bibe
sorry to contradict you but these are the facts, under a programmer approach:

in "C" (max bits used in calculations 7FFFFFFF):

#include <stdio.h>

void
main(void)
{
	int a, mod=67890, c=48765;

	for (a=0; a<1295; a++)
		if ((a*a*a) % mod != (a*(a*a % mod)) % mod) printf("KO for a=%d\n", a);
}

output is:
KO for a=1291
KO for a=1292
KO for a=1293
KO for a=1294

This means no difference with a < 1291

using GMP big-integers library:

void
main(void)
{
	mpz_t base, mod;
	mpz_t res1, res2, res3, res4;

	mpz_init(base);
	mpz_init(mod);

	mpz_init(res1);
	mpz_init(res2);
	mpz_init(res3);
	mpz_init(res4);

	mpz_set_ui(mod, 67890);

	for ( ; mpz_cmp_ui(base, 0xFFFFF)<=0; mpz_add_ui(base, base, 1)) {
    	mpz_powm_ui(res1, base, 3, mod);  // (a*a*a) % mod
    	mpz_powm_ui(res2, base, 2, mod);  // (a*a) % mod
    	mpz_mul(res3, base, res2);  // a * ((a*a) % mod)
    	mpz_mod(res4, res3, mod);  // (a * ((a*a) MOD mod)) % mod
    	if (mpz_cmp(res4, res1))
        	gmp_printf("KO for a=%Zd\n", base);
    	}
}

Nothing is printed. This means that there is no difference at all between
(a*a*a) % mod and (a * ((a*a) % mod)) % mod (at least for base up to 0x100000)

Best regards
bilbo

[bilbo]

hi raduga_fb,

your assertion

c = powmod(base, 3, mod), where: mod=10093 prime, c=5072

can be reverted as:

base = powmod(c, (2*mod + 1)/9, mod) = powmod(5072, 2243, 10093) = 777

holds only for few values of base!

The output of this program:

#include "gmp.h"

void
main(void)
{
	int ok=0, ko=0;
	int primemod = 10093;
	mpz_t base, mod, res1, res2;

	mpz_init(base);
	mpz_init(mod);
	mpz_init(res1);
	mpz_init(res2);

	mpz_set_ui(mod, primemod);

#if 0
	mpz_set_ui(base, 777);
#else
	for ( ; mpz_cmp_ui(base, 0xFFFFF)<=0; mpz_add_ui(base, base, 1))
#endif
	{
	mpz_powm_ui(res1, base, 3, mod);  // (a*a*a) % mod
	//gmp_printf("%Zd\n", res1);

	mpz_powm_ui(res2, res1, (2*primemod + 1)/9, mod);
	//gmp_printf("%Zd\n", res2);
	if (mpz_cmp(base, res2) == 0) ok++; else ko++;
	}

	gmp_printf("ok %d, ko %d\n", ok, ko);
}

is in fact
ok 3365, ko 1045211
for base in the range 0 - 0xFFFFF

So we need more constraints...

bilbo

[raduga_fb]

Thank you Bilbo for reply & effort. Please look following code.

For our situation, "m", "a" and "b" are known. "b" is equal to (2*m+1)/9

I do not have the "gmp library" at the moment. I'll try to install it today :-)

Just I am wondering about that, the numbers a, b, m have 128 bytes length. Can GMP handle it (result r should be in 128 bytes length also) ? In case YES, I think I found the solution.

Did you read something about "Tonelli-Shanks algorithm" ? The solution is modified version of it :-) Look at the bottom where I took the trick from..



int main()
{
mpz_t a, b, m, r;

mpz_init_set_str(a, "5072", 0);
mpz_init_set_str(b, "2243", 0);
mpz_init_set_str(m, "10093", 0);

mpz_init(r);
mpz_powm(r, a, b, m);

gmp_printf("%Zd\n", r); /* r = 777 */

mpz_clear(a);
mpz_clear(b);
mpz_clear(m);
mpz_clear(r);

return 0;






#include <gmp.h>

int main()
{
mpz_t a, b, m, r;

mpz_init_set_str(a, "2988348162058574136915891421498819466320"
"163312926952423791023078876139", 0);
mpz_init_set_str(b, "2351399303373464486466122544523690094744"
"975233415544072992656881240319", 0);
mpz_init(m);
mpz_ui_pow_ui(m, 10, 40);

mpz_init(r);
mpz_powm(r, a, b, m);

gmp_printf("%Zd\n", r); /* ...16808958343740453059 */

mpz_clear(a);
mpz_clear(b);
mpz_clear(m);
mpz_clear(r);

return 0;
}





#assumes p prime returns cube root of a mod p
def cuberoot(a, p):
if p == 2:
return a
if p == 3:
return a
if (p%3) == 2:
return pow(a,(2*p - 1)/3, p)
if (p%9) == 4:
root = pow(a,(2*p + 1)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
if (p%9) == 7:
root = pow(a,(p + 2)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
else:
print "Not implemented yet. See the second paper"

[bilbo]

I'll have a look to the algorithm you said.

GMP can handle every size and can be used with gcc (MINGW on Windows). If you want to use Visual Studio, grab MPIR, which is perfectly compatible with GMP.

Best regards
bilbo

[raduga_fb]

Example ->

b=104683 as a prime, c=84697 ->

root = powmod (c, (2*b + 1)/9, b) = powmod (84697, 23263, 104683) = 11484

84697 = 11484^3 MOD 104683

It is OK. But, root can be 4444 also. It is not problem for me, root can be more than one :-) I can say that the formula is working properly for prime number.

I used the library GMP and the program REXX. They gave me same result for big numbers. Unfortunately, I could not find the solution. I guess, real "b" which has 128 bytes length is not prime but composite. Now, I'll try to factorize the "b" or searching for other approach.

[raduga_fb]

OK. This is RSA 1024 and I am not going to calculate the factors of b :-)
I will patch the public exponent (it is 3 in our case) to 1, that is all. And "c" and "a" became same number. I do not have to patch even "b" public key.
Thanks for everything, regards.