MikeR MikeR - 5 months ago 29
Java Question

Brute-Force java recursive password crack

I've been given another home assignment that I'm cracking my head about for a week now:
I've been given a class that creates a password of a-z only at a given length.

public class Password {
private String _password = "";

// Constructor that generates a password
public Password(int length) {
Random generator = new Random();
for (int i = 0; i < length; ++i) {
this._password = this._password + (char) (generator.nextInt(26) + 97);
}
}

//Method that compares a given string to the password
public boolean isPassword(String st) {
return st.equals(this._password);
}
}


Rules:


  • If you want to use String class, only the following are allowed: charAt,equals,length,substring.

  • You must use recursion.

  • You cannot use 26 recursive calls.

  • No support methods.

  • No arrays.

  • No static variables.

  • Overloading is ok.



here's what I got until now:

public static String findPassword(Password p, int length) {
String pswd= "";
char char2Check = 'a';

if (length == 0) {
return "";
}
else {
return findPassword(p,length, pswd, char2Check);
}
}

public static String findPassword(Password p,int length, String pswd, char char2Check) {
if (pswd.length() < length) {
pswd+= char2Check;
pswd = findPassword(p,length,pswd,char2Check);
if (pswd.length() < length) {
if (pswd.length() == 0) {
if (char2Check == 'z') {
return pswd;
}
if (char2Check < 'z') {
char2Check++;
pswd += char2Check;
return findPassword(p, length, pswd, char2Check);
}
}
else {
if (char2Check == 'z') {
return pswd.substring(0, pswd.length() - 1);
}
if (char2Check < 'z') {
pswd = pswd.substring(0, pswd.length() - 1);
char2Check++;
pswd += char2Check;
return findPassword(p, length, pswd, char2Check);
}
}
}
}
if (pswd.length() == length) {
System.out.println(pswd);
if (p.isPassword(pswd)) {
return pswd;
}
if (char2Check < 'z') {
pswd = pswd.substring(0, pswd.length() - 1);
char2Check++;
pswd+= char2Check;
return findPassword(p,length,pswd,char2Check);
}
if (char2Check == 'z'){
return pswd.substring(0, pswd.length() - 1);
}
}
return pswd;
}


the problem is:

If the first char is i.e 'r' it will not check a, b or c after it, it'll go stright to s, t, u...

there are a few more problems, but once this problem is gone I think the rest will be easier to solve..

here a paste of the output:
http://pastebin.com/CK9AyKUi

hopefully someone can help me out :)

Answer

You went to great length for something supposed to be simple: generating all strings of length n containing only a-z characters.

A note about the performances: use StringBuilder instead of String when you want to do lots of append and deletion of chars. String are immutable, so they are copied again and again in your code.

Now, about recursion, you have only two things to think of: what is your general case ? What is your stop condition ?

Here, the stop condition is simple: the real password and current trial have the same length. If the trial is correct, then return it ; else go up in the recursion. Second stop condition: all possibilities have been tried for the current prefix and there is no match, then go up in the recursion.

General case is also simple: given the current prefix, try to append every possible letter a-z and add one level of recursion.

Now, you may want to give it another shot with those leads (hint: fresh start is easier than trying to fix your current code). My solution follows, but you can come up with your own:

public static String findPassword(Password p, int length) {
    return findPassword(p,length, new StringBuilder());
}

public static String findPassword(Password password, int length, StringBuilder str) {
    // Stop condition, password and trial have same length
    if (length == str.length()) {
        if (password.isPassword(str.toString())) {
            return str.toString();
        } else {
            return "";
        }
    }

    String s;

    for (char c = 'a'; c <= 'z'; c++) {
        // Add a new character to the given prefix
        str.append(c);
        // Try to find a password for the new prefix
        s = findPassword(password, length, str);
        if (!s.equals("")) {
            return s;
        }
        // Didn't work out, remove the character
        str.deleteCharAt(str.length()-1);
    }
    // All chars have been tried without success, go up one level
    return "";
}
Comments