#1
|
|||
|
|||
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, |
#2
|
|||
|
|||
:-) I have done a progress
c = MOD (a^3, b) |
#3
|
|||
|
|||
There is no unique "a" for this condition.
For example for current "b" and "c", "a" may be 3585, 12345, 31965, 42195, 47295... |
#4
|
|||
|
|||
"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. Last edited by raduga_fb; 02-11-2015 at 17:09. |
#5
|
|||
|
|||
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); } |
#6
|
|||
|
|||
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 ? |
#7
|
|||
|
|||
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 Code:
c = MOD (a^3, b) 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 Code:
c = MOD (a * MOD (a*a, b) , b) Code:
c = MOD (a^3, b) In any case, the MOD operator is not reversable, in the sense that many inputs can give the same output: Code:
a = b % c Code:
a + nc = b Best regards bilbo |
#8
|
|||
|
|||
@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 |
#9
|
|||
|
|||
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 Last edited by raduga_fb; 02-11-2015 at 20:39. |
#10
|
|||
|
|||
@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): Code:
#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); } 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: Code:
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); } } (a*a*a) % mod and (a * ((a*a) % mod)) % mod (at least for base up to 0x100000) Best regards bilbo |
#11
|
|||
|
|||
hi raduga_fb,
your assertion Quote:
The output of this program: Code:
#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); } ok 3365, ko 1045211 for base in the range 0 - 0xFFFFF So we need more constraints... bilbo |
#12
|
|||
|
|||
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" Last edited by raduga_fb; 02-11-2015 at 23:27. |
#13
|
|||
|
|||
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 |
#14
|
|||
|
|||
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. |
#15
|
|||
|
|||
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. |
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Been a while!! what needs reversing lol | MEPHiST0 | General Discussion | 3 | 01-18-2014 00:46 |