Generate predefined length string from an alphabet in JAVA-CodePudding

I trying to create for a school project a brute force method in JAVA that will generate random keys and it will try to decrypt a String. My approach is to have a String as an alphabet and to define the length so in pseudo-code

final String alphabet = "ABCDEFGHIKLMNOPQRSTUVWXYZ";

List<String> getPossibleKeys(String alphabet, Integer keyLength){
...
}

void decrypt(Integer keyLength, String encryptedText){

List<String> keysArray = getPossibleKeys(alphabet, keyLength);

  for(String key: keysArray){
  out.print(doDecryption(encryptedText,key));
}

}

My problem is that I do not how how to approach the getPossibleKeys method.

For example lets say the key is "MARIA"so it is of length 5. I want to be able to call getPossibleKeys(alphabet, keyLength) and have an output of

MFTER

PWYTS

GFTGB

...

MARIA

...

FENDF

YJVGN

CVBCV

In other words ALL the possible combinations with EXACT length 5 comming from the alphabet provided.

The examples I have found use all the letters of the alphabet so I could use them and keep only the length I want but I guess there is a better way than that.

CodePudding user response：

You really should not want to generate all the keys in one go, as that would create a huge table, which may not even fit into memory. It's amazing how fast you could run out of memory that way.

A better and more appropriate way is to map an integer to each password. Once you have done that you can simply loop over all integers up to the maximum size, and then call a the mapping function.

For passwords (keys are commonly binary), each password consists of letters of the alphabet at each location. So you can create an index of zero to 26^5 for a 5 letter password (assuming your alphabet also contains a J ;) ).

So how do you get to create the passwords? Well, that's easier than you might think. Note that computers are binary, and that we calculate in decimals. So the computer is already able to convert from base 2 to base 10. Similarly you can also convert to base 26. This is called "base conversion" and happens what you call e.g. Long.toString(long i, int radix).

The way to perform base conversion is to simply divide a value by the size of the alphabet, and to use the remainder as index into the alphabet, repeating the process for each character. Of course, in Java the divide and remainder are separate operations (in BigInteger there is a single function because that's more efficient, but for such small numbers that's not a problem).

public static String createPassword(int size, String alphabet, long value) {
    int n = alphabet.length();        
    StringBuilder password = new StringBuilder(size);
    long changingValue = value; 
    for (int i = 0; i < size; i  ) {
        int charIndex = (int) (changingValue % n); 
        char charInAlphabet = alphabet.charAt(charIndex);
        password.append(charInAlphabet);
        changingValue /= n;
    }
    return password.toString();
}

I'll leave it to you to calculate the maximum size given above calculation. If you perform the log_2 over the maximum size then you have the security level in bits that the password provides (somewhat over 23 bits, which should be easy to brute force).

CodePudding user response：

The resulting list should be generated using recursive approach where each string item is formed from a prefix until the length is achieved:

static List<String> getPossibleKeys(alphabet, keyLength) {
    return getPossibleKeys(alphabet, new ArrayList<>, "", keyLength);
}

private static List<String> getPossibleKeys(
    String alphabet, List<String> acc, String prefix, int keyLength
) {
    if (keyLength == 0) {
        acc.add(prefix); // key is ready, add to the result
    } else {
        for (char c : alphabet.toCharArray()) {
            getPossibleKeys(alphabet, acc, prefix   c, keyLength - 1);
        }
    }
    return acc;
}

Test (for a shorter alphabet and length):

System.out.println(getPossibleKeys("ABC", 2));
System.out.println(buildK("AB", 3));

Output:

[AA, AB, AC, BA, BB, BC, CA, CB, CC]
[AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB]