Help solving math problem

Moderator: BarsMonster

Post Reply [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Help solving math problem

Post by bias_resistor » Fri Apr 10, 2009 1:37 pm

hey, i was trying to write my own password cracker.
first problem i can't figure out is this:

If the alphabet is "0123456789" and the start password is "9999"
How many passwords have been tested up to this point?

i wrote some code which seems to work fine.

Code: Select all

#include <stdio.h>
#include <string.h>

int
main(int argc, char *argv[])
{
	char password[]="9999";
	char alphabet[]="0123456789";
	int pass_array[32];
	
	unsigned long long iterations = 0;
	unsigned long long power	= 1;

	size_t passLen  = strlen(password);
	size_t alphaLen = strlen(alphabet);

	for(size_t i = 0;i < passLen && i < sizeof(pass_array);i++)
	{
	  pass_array[i] = strchr(alphabet, password[i]) - alphabet + 1;
	  iterations = iterations + power * pass_array[i];
	  power = power * alphaLen;
	}

	printf("\nTotal iterations:%I64d",iterations);
	return(0);
}
The result of "9999" is 11110

but if the value is 11110, how can i get the string "9999" ???

i already tried this:

Code: Select all

	for(int i = 0; i < passLen;i++)
	{
	  digit = (iterations % alphaLen);
	  iterations /= alphaLen;			// discards any fractional part
	  password[i] = alphabet[ digit ];
	}
but this gives string of "0111" instead of what i wanted "9999"

what am i doing wrong? please give any help/hint?

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Fri Apr 10, 2009 3:12 pm

ok, i wrote something else which works for some strings but not for others

Code: Select all

	power = 10000;	// 10 ^ passLen (alphaLen raised to power of passLen)

	for(int i = 0; i < passLen;i++)
	{
	  digit = (iterations / power);
	  iterations = iterations - (digit * power);

	  if(digit == 0)
		i--;
	  else 
	  	pass_string[3-i] = alphabet[ digit-1 ];

	  power /= alphaLen;
	}
	printf("\nPassword is %s",pass_string);
this works for any string except when digit 9 is used.

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Fri Apr 10, 2009 8:23 pm

ok, this is what i have now

Code: Select all

	power = 1;

	for(int i = 0;i < passLen;i++)
	    power *= alphaLen;

	for(int i = 0; i < passLen;i++)
	{
	  power /= alphaLen;
	  digit = (iterations / power);

	  if(digit == 0) {
           --i;
        }
	  else {
		if(digit > alphaLen) {
		   iterations + iterations + ((digit % alphaLen) * power);
               digit = digit - (digit % alphaLen);
  		}

	  	iterations = iterations - ( digit * power);
	  	pass_string[(passLen-1)-i] = alphabet[ digit-1 ];
	  }

        printf("\nSubtracted %I64d to get \"%c\"",power*digit,alphabet[ digit-1 ]);
	}
and some examples:

string "9999"
Added 10 for "9"
Added 100 for "9"
Added 1000 for "9"
Added 10000 for "9"

Total iterations:11110

Subtracted 10000 to get "9"
Subtracted 1000 to get "9"
Subtracted 100 to get "9"
Subtracted 10 to get "9"
"1234"
Added 2 for "1"
Added 30 for "2"
Added 400 for "3"
Added 5000 for "4"

Total iterations:5432

Subtracted 5000 to get "4"
Subtracted 400 to get "3"
Subtracted 30 to get "2"
Subtracted 2 to get "1"
the problem is when i want use something like "1919"
Added 2 for "1"
Added 100 for "9"
Added 200 for "1"
Added 10000 for "9"

Total iterations:10302

Subtracted 10000 to get "9"
Subtracted 300 to get "2"
Subtracted 0 to get " "
Subtracted 2 to get "1"
anybody any idea whats wrong?

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Fri Apr 10, 2009 10:06 pm

Code: Select all

//http://msdn.microsoft.com/en-us/library/aa302371.aspx

#include <stdio.h>
#include <string.h>

int
main(int argc, char *argv[])
{
	char *password = argv[1];
	char alphabet[]="0123456789abcdefghijklmnopqrstuvwxyz";
	int pass_array[32];
	char pass_string[32]={0};

	unsigned long long iterations = 0;
	unsigned long long power      = 1;

	size_t passLen  = strlen(password);
	size_t alphaLen = strlen(alphabet);

	for(size_t i = 0;i < passLen && i < sizeof(pass_array);i++)
	{
	  pass_array[i] = strchr(alphabet,  password[i]) - alphabet + 1;
	  iterations = iterations + power * pass_array[i];
	  printf("\nAdded %I64d for \"%c\"",power * pass_array[i],password[i]);
	  power = power * alphaLen;
	}

	printf("\n\nTotal iterations:%I64d\n",iterations);

	unsigned long long digit;

	power = 1;

	for(int i = 0;i < passLen;i++)
	    power *= alphaLen;

	for(int i = 0; i < passLen;i++)
	{
	  power /= alphaLen;
	  digit = (iterations / power);

	  if(digit == 0) {
             printf(" - error");
	     power *= alphaLen;
	     iterations += power;

             i--;
             digit = strchr(alphabet,pass_string[passLen-i-1]) - alphabet + 1;
             digit--;
             pass_string[passLen-i-1] = alphabet[ digit-1 ];
             printf("\nSubtracted %I64d for \"%c\"",power*digit,alphabet[ digit-1 ]);
          }
	  else
          {
            if(digit > alphaLen) {
               iterations + iterations + ((digit % alphaLen) * power);
               digit = digit - (digit % alphaLen);
            }
            
            iterations = iterations - (digit * power);
            pass_string[(passLen-1)-i] = alphabet[ digit-1 ];
            
            printf("\nSubtracted %I64d for \"%c\"",power*digit,alphabet[ digit-1 ]);
	  }
	}
	
	printf("\n\nPassword is \"%s\"",pass_string);
	return(0);
}
"zaza"

Added 36 for "z"
Added 396 for "a"
Added 46656 for "z"
Added 513216 for "a"

Total iterations:560304

Subtracted 559872 for "b" - error
Subtracted 513216 for "a"
Subtracted 46656 for "z"
Subtracted 432 for "b" - error
Subtracted 396 for "a"
Subtracted 36 for "z"

Password is "zaza"
"1919"
Added 2 for "1"
Added 360 for "9"
Added 2592 for "1"
Added 466560 for "9"

Total iterations:469514

Subtracted 466560 for "9"
Subtracted 2592 for "1"
Subtracted 360 for "9"
Subtracted 2 for "1"

Password is "1919"
only question i have now is how can i do this better? :)

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Fri Apr 10, 2009 10:15 pm

actually, it still doesn't work :(

User avatar
LordMike
Posts: 184
Joined: Tue Feb 10, 2009 8:34 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by LordMike » Sat Apr 11, 2009 11:57 am

You have 10 characters. 4 Digits.

So, 4 places of 10:
10 * 10 * 10 * 10:
10000. <-- Total Keyspace.
This is assuming you start with 4 digits. Totally, it will be:

10^4 + 10^3 + 10^2 + 10^1 = 10000 + 1000 + 100 + 10 = 11110.

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Tue Apr 14, 2009 1:30 pm

i thought there was a simple formula towards generating the password from value..but the only way i can see this being done without causing errors
is to convert the initial password to an array, then increment each index until nothing left..unless i'm mistaken? i see no other way atm.

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by BarsMonster » Tue Apr 14, 2009 2:42 pm

bias_resistor wrote:i thought there was a simple formula towards generating the password from value..but the only way i can see this being done without causing errors
is to convert the initial password to an array, then increment each index until nothing left..unless i'm mistaken? i see no other way atm.
It is possible to convert number to password, but it is SLOOWWWWW (because of divisions and %). Also, additional problems when there are more than 2^64 password to generate ;-)
Incrementing things in array is much faster.

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Wed Apr 15, 2009 8:22 pm

It is possible to convert number to password, but it is SLOOWWWWW (because of divisions and %). Also, additional problems when there are more than 2^64 password to generate
Incrementing things in array is much faster.
well to tell the truth, i would just like to know now how its done slow way :)
i was told to look up the inverse function of pow() but haven't had chance yet..

although i see the problem with code i've written is that, for alphabet like "0123456789", "9" would equal 10 for 10^1
but "0" can also equal 10 for 10^2 so i think this inversion of pow() is what i need, although i'm still searching..

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Wed Apr 15, 2009 9:49 pm

lord mike -

if i had "1234" and the alphabet was "0123456789"

to calculate the amount of passwords tested:

1 * 2 = 2
10 * 3 = 30
100 * 4 = 400
1000 * 5 = 5000

total = 5432

i tried to reverse this using:

5432 / 1000 = 5
432 / 100 = 4
32 / 10 = 3
2 / 1 = 2

but if i use "9090"

1 * 10 = 10
10 * 1 = 10 <-- problem in reverse
100 * 10 = 1000
1000 * 1 = 1000

total is 2020

now is problem..

2020 / 1000 = 2
20 / 100 = 0
20 / 10 = 2
0 / 1 = 0
....

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by BarsMonster » Wed Apr 15, 2009 10:01 pm

bias_resistor wrote:lord mike -

if i had "1234" and the alphabet was "0123456789"
Well, it more like

1*1000+2*100+3*10+4 = 1234 :-)
Or 4*1000+3*100+2*10+1 if you are incrementing password from the other side.

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by BarsMonster » Wed Apr 15, 2009 10:03 pm

So, slow way, for a-z :

Code: Select all

int len = 7;//password length
for(int i=0;i<1000000000)
{
  int tmp = i;
  for(int j=0;j<len;j++)
  {
    cout << 'a'+tmp%26;
    tmp/=26;
  }
  cout << endl;
}
That's it

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Wed Apr 15, 2009 10:33 pm

thanks bars!

i changed your code to the following:

assuming we use alphabet length of 10, and start value of "9999" which
would translate to 11,110

Code: Select all

#include <iostream>

using namespace std;

int
main(int argc, char *argv)
{
  int len = 4;   //password length

  for(int i = 11110;i <= 11110;i++)
  {
   int tmp = i;

   for(int j = 0;j < len;j++)
   {
    cout << tmp % 10;
    tmp /= 10;
   }

   cout << endl;
  }
  return(0);
}
the output of this was "0111" which is same when using the following code

Code: Select all

   for(int i = 0; i < passLen;i++)
   {
     digit = (iterations % alphaLen);
     iterations /= alphaLen;         // discards any fractional part
     password[i] = alphabet[ digit ];
   }
when i would like for 11,110 to translate to "9999"

i am guessing there is some multiple root finding algorithm??

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Wed Apr 15, 2009 10:35 pm

i'm looking through wikipedia entries :)

http://en.wikipedia.org/wiki/Category:R ... algorithms

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by BarsMonster » Thu Apr 16, 2009 12:20 am

I.e. you want to count all password of shorter lengths, not for specific fixed password length?
Forget about it, and count every new password length starting from 0 :-) Too much extra work & slow down with minimal benefits for bruteforcer (as far as I see it)

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Thu Apr 16, 2009 12:38 am

I.e. you want to count all password of shorter lengths, not for specific fixed password length?
yes :) i know it would be more difficult, but just like to know how its done anyway.

surely there must be some method or formula for calculating this..

will keep reading to see if such algorithm exist and post here results (if any)

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: Help solving math problem

Post by Sc00bz » Mon Apr 20, 2009 2:59 pm

Code: Select all

#include <stdio.h>

#ifdef _WIN23
	#define uint64 unsigned __int64
#else
	#define uint64 unsigned long long
#endif

void num2pw(uint64 number, char *buffer, const char *charSet, int charSetLen, bool incRight = true, int minLength = 1)
{
	uint64 pow = 1;
	int len, pos;

	if (charSetLen <= 0 || minLength < 0)
	{
		buffer[0] = '\0';
		return ;
	}
	for (len = 0; len < minLength; len++)
	{
		pow *= charSetLen;
	}
	while (number >= pow)
	{
		number -= pow;
		pow *= charSetLen;
		len++;
	}
	if (incRight)
	{
		for (int pos = len - 1; pos >= 0; pos--)
		{
			buffer[pos] = charSet[number % charSetLen];
			number /= charSetLen;
		}
	}
	else
	{
		for (pos = 0; pos < len; pos++)
		{
			buffer[pos] = charSet[number % charSetLen];
			number /= charSetLen;
		}
	}
	buffer[len] = '\0';
}

int main()
{
	char buffer[65];

	num2pw(12345, buffer, "0123456789", 10);
	printf("%s\n", buffer);
	return 0;
}

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Help solving math problem

Post by bias_resistor » Tue Apr 21, 2009 1:45 am

damn...it was this easy? :oops:

i see now how it works and it was staring right at me whole time..

Code: Select all

   for(size_t i = 0;i < passLen && i < sizeof(pass_array);i++)
   {
     pass_array[i] = strchr(alphabet, password[i]) - alphabet + 1;
     iterations = iterations + power * pass_array[i];               //           <-- power is added
     power = power * alphaLen;
   }

Code: Select all

   for(len = 1;number >= power;len++) {
     number -= power;                                                     // <-- subtract power
     power *= charSetLen;
   }
what can i say..thank you sc00bz!! :D
i owe you.

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest