Is it possible to make it run any faster?

Question

I've tried everything, added a special Parallel For cycle, but it's not just fast enough. Is there a way to make it run faster? I know it's possible to these computations on GPU too, but I don't have any experiences with that.

For comparison, if it's using its full potential or not pc specs here:

CPU: AMD Ryzen 5 3400G with Radeon Vega Graphics 3.70 GHz

GPU: AMD Radeon rx580 8GB

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Timers;


    namespace MyProgram
    {
        public partial class Form1 : Form
        {
            public Form1()
            {
                InitializeComponent();
            } 
           
            int[] code;
            int time = 0;
            Char[] characters = new Char[] 
            {
                'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i','j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
                '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 
            };
    
            String passTry = "";       
    
            private void button1_Click(object sender, EventArgs e)
            {
                code = null;
                time = 0;
                passTry = "";
                code = new int[int.Parse(LengthBox.Text)];
                OutputBox.AppendText("Trying to break password...");
                OutputBox.AppendText(Environment.NewLine);
              
    
                Parallel.For(0, int.Parse(LengthBox.Text), i =>
                {
                    code[i] = 0;
                });
    
                timer1.Enabled = true;
    
               Task.Run(() =>
    
               {
    
                    while (passTry!=passOrig.Text)
                    {
                            Parallel.For(0, (code.Length-1), o =>
                            {
                                
                                if (code[o] > 34 && o < code.Length)
                                {
                                    code[o] = 0;
                                    code[o+1] += 1; 
                                }
    
                                passTry = "";
    
                                Parallel.For(0, (code.Length), i =>
                                {
                                    if (passTry.Length < code.Length)
                                    {
                                        passTry +=characters[code[i]];
                                    }
                                });
    
                           
                            });
    
                            code[0] = code[0] + 1;
                    }
               });
            }
        
          
    
    
            private void Form1_Load(object sender, EventArgs e)
            {
              
            }
    
            private void timer1_Tick(object sender, EventArgs e)
            {
                timeLbl.Text = (time/10).ToString() + "s";
                time++;
    
                if (passTry.Length == code.Length)
                {
                    OutputBox.AppendText("Trying password " + passTry + "...");
                    OutputBox.AppendText(Environment.NewLine);
    
                    if (passOrig.Text == passTry)
                    {
                        OutputBox.AppendText("Success, Password found " + passTry);
                        OutputBox.AppendText(Environment.NewLine);
                        timer1.Enabled = false;
                    }
                }
            }
        
        }
    }

My code takes a simple brute force algorithm of a combination lock. Starts at 0 0 0 0. Then add one to the first digit and when the digit meets maximum resets it and adds one to the next digit and again and when the next digit reaches the maximum add one to the next one again and again until the result of converted characters joined to string doesn't match string passOrig.Text.

Combination lock+ conversion
    
    0 0 0 0 = A A A A
    1 0 0 0 = B A A A
    2 0 0 0 = C A A A 
    3 0 0 0 = D A A A
    0 1 0 0 = A B A A
    1 1 0 0 = B B A A
    2 1 0 0 = C B A A
    3 1 0 0 = D B A A
    0 2 0 0 = A C A A


//code to string conversion

Parallel.For(0, (code.Length), i =>
                            {
                                if (passTry.Length < code.Length)
                                {
                                    passTry +=characters[code[i]];
                                }
                            });

Edit: This is only the first part after deploying the original password won't be known. The only known value will be is it a password or not(true or false) thx for all answers there are 2 interesting answers, but I think I currently don't have brain capacity to understand them.

Answer 1

OK, so let's assume when it's live you'll have a method like this:

public bool IsItTheCombination(string combo) =>
  return combo=="FEDC"; //returns true if the input is FEDC

You're saying you want to start at AAAA then try AAAB, AAAC, AAAD and so on. After AAAJ -> AABA, because J is the 9th letter if A is the 0th letter. And eventually, after 7654 (FEDC) guesses you'll hit the right combo. You don't know what FEDC actually is.. you'll just call it over and over with different strings and get a true or false

So really this is just like counting, 0000, 0001, 0002, .., 0009, 0010. Except we're using letter characters A instead of number characters 0.

---

Let's have a loop that goes from 0 to 9999 - that's all the combinations

for(int x = 0; x <= 9999; x++){

}

Now we just need to turn 0000 into AAAA. Good thing then that chars and numbers in C# are interchangeable

How do we break an integer into its thousands, hundreds, tens and units? Could make it a string, and pull it apart.. We could also do it with math.. Let's do math.

• 1234 divide by 1 modulo 10 is 4.
• 1234 divide by 10 modulo 10 is 3.
• 1234 divide by 100 modulo 10 is 2.
• 1234 divide by 1000 modulo 10 is 1.

We don't need to divide by 1, or modulo after doing the divide by 1000 (non ops)

for(int x = 0; x <= 9999; x++){

  int thousands = x/1000;
  int hundreds = (x/100)%10;
  int tens = (x/10)%10;
  int units = x%10;

}

So when x = 1234, we now have 4 variables that represent each of the 4 numbers. To turn them into a character, all you have to do is add whatever character you want, and cast it to a char:

charc c = (char)('A' + 0);

A+0 is A. A+1 is B. A+2 is C..

for(int x = 0; x <= 9999; x++){

  char thousands = (char)('A' + x/1000);
  char hundreds = (char)('A' + (x/100)%10);
  char tens = (char)('A' + (x/10)%10);
  char units = (char)('A' + x%10);

}

You now hove 4 chars. Turning chars into strings is easy, and it's even easier if those chars are in an array because we can use the new string(char[]) constructor

Array mode:

char[] guess = new char[4];
for(int x = 0; x <= 9999; x++){

  guess[0] = (char)('A' + x/1000);
  guess[1] = (char)('A' + (x/100)%10);
  guess[2] = (char)('A' + (x/10)%10);
  guess[3] = (char)('A' + x%10);

}

Then just see if the guess is right:

char[] guess = new char[4];
for(int x = 0; x <= 9999; x++){

  guess[0] = (char)('A' + x/1000);
  guess[1] = (char)('A' + (x/100)%10);
  guess[2] = (char)('A' + (x/10)%10);
  guess[3] = (char)('A' + x%10);

  var guessStr = new string(guess);
  if(IsItTheCombination(guessStr)){
    Console.WriteLine("The combo is " + guessStr);
  }
}

This can, of course, be altered for any length of guessing. It's also easier to work backwards, because you just divide by 10 each time to cut another digit off:

  guess[3] = (char)('A' + x%10);
  x=x/10;
  guess[2] = (char)('A' + x%10);
  x=x/10;
  guess[1] = (char)('A' + x%10);
  x=x/10;
  guess[0] = (char)('A' + x%10);

You can see that all the operations become the same: mod 10, assign, divide 10 over and over. This means an inner loop can handle our logic:

char[] guess = new char[20];
for(int x = (int)Math.Pow(10, guess.Length-1) - 1; x >= 0; x--){

  int num = x;                                   //take a copy of x because we'll modify it with division and we don't want to lose our place in the brute forcing

  
  guess[guess.Length - 1] = (char)('A' + x%10);  //do the right most digit as a special case (no division)
  for(int c = guess.Length - 2; c >= 0; c--){
    num = num/10;                                //cut a digit off
    guess[c] = (char)('A' + num%10);             //what is the rightmost digit?
  }

  var guessStr = new string(guess);
  if(IsItTheCombination(guessStr)){
    Console.WriteLine("The combo is " + guessStr);
  }
}

Answer 2

I tried not to overthink it and wrote this single-threaded version and on my laptop it seems to be hundreds of time faster then what is shown in the question.

I tested with "zzzz" because it's the worst case for my implementation.

My version is taking ~0.1s.

Your version is taking >10s.

static void Naive(string password)
{
    var sw = Stopwatch.StartNew();
    var characters = new string(new Char[]
    {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i','j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 
    });
    int characterLength = characters.Length;
    
    // Let's make the password an array of numbers
    byte[] passwordAsNumbers = password.Select(c =>(byte)characters.IndexOf(c)).ToArray();

    var attempt = new byte[password.Length];

    Find(0);
    var found = new string(attempt.Select(i => characters[i]).ToArray());
    var elapsed = sw.Elapsed;

    bool Find(int index)
    {
        if (index >= attempt.Length) return false;

        for (byte i = 0; i < characterLength; i++)
        {
            attempt[index] = i;
            if (attempt.SequenceEqual(passwordAsNumbers)) return true;
            if (Find(index + 1)) return true;
        }
        return false;
    }
}