蛮力java递归密码破解

Question

我接到了另一项家庭作业，我为此绞尽脑汁了一个星期：我得到了一个 class，它只在给定的长度上创建 a-z 的密码。

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

规则：

如果要使用字符串 class，只允许使用以下内容：charAt、equals、length、substring。
你必须使用递归。
您不能使用 26 个递归调用。
没有支持方法。
没有数组。
没有静态变量。
可以重载。

这是我到目前为止得到的：

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

问题是：

如果第一个字符是 'r' 它不会检查它后面的 a、b 或 c，它会直接到 s、t、u...

还有一些问题，但是一旦这个问题消失了，我想剩下的就更容易解决了..

这里是输出的粘贴： http://pastebin.com/CK9AyKUi

希望有人能帮助我:)

Answer 1

您为本应很简单的事情费尽心思：生成所有长度为 n 且仅包含 a-z 字符的字符串。

关于性能的注意事项：当您想执行大量 append 和删除字符时，请使用 StringBuilder 而不是 String。字符串是不可变的，因此它们会在您的代码中被一次又一次地复制。

现在，关于递归，您只需考虑两件事：您的一般情况是什么？你的停止条件是什么？

这里，停止条件很简单：真实密码和当前试用密码长度相同。如果试验正确，那么return就可以了；否则在递归中上升。第二次停止条件：当前前缀所有可能都试过了没有匹配，则递归上去

一般情况也很简单：给定当前前缀，尝试附加每个可能的字母 a-z 并添加一级递归。

现在，您可能想利用这些线索再试一次（提示：重新开始比尝试修复当前代码更容易）。我的解决方案如下，但您可以提出自己的解决方案：

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

Answer 2

我不会给你解决方案。但是假设字母表是 "abc" 并且你想找到长度为 3 的密码，你必须这样编程：

a -> aa -> aaa 
|     |      | 
|     |    aab 
|     |      | 
|     |    aac 
|     |        
|    ab -> aba 
|     |      | 
|     |    abb 
|     |      | 
|     |    abc 
|     |        
|    ac -> aca 
|            | 
|          acb 
|            | 
|          acc 
|              
b -> ba -> baa 
|     |      | 
|     |    bab 
|     |      | 
|     |    bac 
|     |        
|    bb -> bba 
|     |      | 
|     |    bbb 
|     |      | 
|     |    bbc 
|     |        
|    bc -> bca 
|            | 
|          bcb 
|            | 
|          bcc 
|              
c -> ca -> caa 
      |      | 
      |    cab 
      |      | 
      |    cac 
      |        
     cb -> cba 
      |      | 
      |    cbb 
      |      | 
      |    cbc 
      |        
     cc -> cca 
             | 
           ccb 
             | 
           ccc

您必须检查每个递归步骤的 2 条路径。

->，密码不够长，加'a'试试
|，它递增最后一个字符，只要它不是字母表的最后一个。

这两条路径都有一个停止条件，您必须注意：密码长度和字母长度。

Answer 3

 private static boolean findPassword(Password p, String pswd, int length) {

    if (length == pswd.length()) {
        if (p.isPassword(pswd))
            System.out.println(pswd);
        return p.isPassword(pswd);

    }

    String alpha = "abcdefghijklmnopqrstuvwxyz";
    for (int i = 0; i < alpha.length(); i++) {
        if (findPassword(p, pswd + alpha.charAt(i), length)) 
            return true;
    }
    return p.isPassword(pswd);
}

Answer 4

首先非常感谢！

你的代码给了我一些好主意为您修好了:)

我已经更正了你的代码，它的工作非常完美

这里是：

  public static String findPassword(Password p,int length)
  {
      // string and char to be input into the overloading method
      String pswd= "";
      char char2Check = 'a';

      // Checking if the length of the password is 0 so its null
      if (length == 0)
      {
          return "";
      }
      else{
          // going to the overloading method to find the password
          return findPassword(p,length, pswd, char2Check);
      }
  }

  public static String findPassword(Password p,int length, String pswd, char      char2Check)
  {

    // Checking if the length of the password finder is less then the length of the 
    // password we add more chars until they are the same length to check if they're equal
    if (pswd.length() < length)
    {
        pswd+= char2Check;
        pswd = findPassword(p,length,pswd,char2Check);
        char2Check = pswd.charAt(pswd.length() - 1);
        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')
                {
                    char2Check = pswd.charAt(pswd.length() - 1);
                    pswd = pswd.substring(0, pswd.length() - 1);
                    char2Check++;
                    pswd += char2Check;
                    return findPassword(p, length, pswd, 'a');
                }
            }
        }
    }
    // Checking if the password finder length is the same as the original password
    if (pswd.length() == length)
    {
        System.out.println(pswd);
        // Checking if the two password match, if so we return the password finder.
        if (p.isPassword(pswd))
        {
            return pswd;
        }
        // Checking if the char is not the last char -> z
        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;
}

蛮力java递归密码破解

Brute-Force java recursive password crack

java

recursion

brute-force

backtracking