MOD calculation / reversing
 

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,

:-) I have done a progress

c = MOD (a^3, b)

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

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

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);
}

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 ?

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
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 is different from 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:

is equivalent to the expression with n which can assume all integer values...

Best regards
bilbo

@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

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

@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):
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:
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

hi raduga_fb,

your assertion
holds only for few values of base!

The output of this program:
is in fact
ok 3365, ko 1045211
for base in the range 0 - 0xFFFFF

So we need more constraints...

bilbo

powermod
 

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"

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

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.

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.