Best Practice Passwort Recovery - Schulbeispiel

[fhs14647]

Werte Java-Profis
Als Aufgabe im Informatikunterricht soll man eine Algorithmus entwickeln, welcher ein bis zu vierstelliges Passwort errät. Dabei kann das Passwort ein-, zwei-,drei- oder vierstellig sein, das weiß man vorher nicht. Auch muss jeder Versuch gesondert probiert werden...
Ich habe folgende Lösung erarbeitet, die auch funkt, die mir aber etwas umständlich erscheint.
Meine Bitten:
a.) welche Optimierungsmöglichkeiten fallen Euch da ein ... ;-)
b.) welche Lösungen gäbe es für Passwörter mit unlimitierter Passwortlänge

public class Main {
//Method for handling result in String compare
public static boolean checking(String s, String p) {
    if (s.equals(p)) {
        //Strings are equal
        System.out.println("PW found, it is: " + s);

        return true;
    } else {
        //Strings are not equal, checked letter is shown
        System.out.println("Letter: " + s);
        return false;
    }
}
public static void main(String[] args) {
    // Initial value for ascii char
    char asc1 = 'a';
    char asc2 = 'a';
    char asc3 = 'a';
    char asc4 = 'a';
    //given password
    String pw = "01av";
    //initial value for s
    String s = null;
    //searching for 0,1,2, ....X,Y, Z
    for (int i = 48; i < 123; i++) {
        asc1 = (char) i;
        //building a String to compare
        s = new StringBuilder().append(asc1).toString();
        //static method checking
        if (checking(s, pw) == true) {
            return;
        }

        for (int j = 48; j < 123; j++) {
            asc2 = (char) j;
            s = new StringBuilder().append(asc1).append(asc2).toString();
            if (checking(s, pw) == true) {
                return;
            }

            for (int k = 48; k < 123; k++) {
                asc3 = (char) k;
                s = new StringBuilder().append(asc1).append(asc2).append(asc3).toString();
                if (checking(s, pw) == true) {
                    return;
                }

                for (int l = 48; l < 123; l++) {
                    asc4 = (char) l;
                    s = new StringBuilder().append(asc1).append(asc2).append(asc3).append(asc4).toString();
                    if (checking(s, pw) == true) {
                        return;
                    }
                }
            }
        }
    }
}

 

[Tarrew]

Deine Lösung ist erstmal relativ naheliegend auch wenn du das vllt nicht unbedingt alles in der main-Funktion schreiben solltest.

Wenn du allerdings Passwörter mit variablen Länge rausfinden willst (also b.) ) könntest du eine Funktion haben die deinen String 'inkrementiert'.
Hab das mal schnell ausprobiert:

    public String incrementString(String original) {
        int i;
        char[] array = original.toCharArray();
 
        if(array[array.length-1]<'z'){
            array[array.length-1]++;
            return new String(array);
        }
        for(i=array.length-1;i>=0;i--){
            if(array[i]!='z'){
                array[i]++;
                for(int j=i+1; j<array.length; j++){
                    array[j]='0';
                }
                return new String(array);
            }
        }
        if(i<0){
            return new String(new char[array.length]).replace("\0", "0")+"0";
        }
        throw new IllegalArgumentException();
    }

(nicht ausführlich getestet, könnte also Fehler enthalten).

Die Funktion könntest du dann dauerhaft laufen lassen und nach jedem Aufruf überprüfen ob der zurückgegebene String mit dem Passwort übereinstimmt. Initialer String sollte die "0" sein. Bei leeren Strings fehlt die Fehlerbehandlung

Hab das mal kurz ausgetestet und ab einer Passwortlänge von 7 dauert es schon so lange, dass man sich in der Zwischenzeit ruhig einen Kaffee trinken kann.


#edit:
Grade auf StackOverflow noch eine wesentlich kürzere Funktion zum 'Inkrementieren' von Strings gefunden:

    public static String next(String s) {
        int length = s.length();
        char c = s.charAt(length - 1);

        if (c == 'z')
            return length > 1 ? next(s.substring(0, length - 1)) + '0' : "00";

        return s.substring(0, length - 1) + ++c;
    }

 

[fhs14647]

Hallo Tarrew
Erstmals vielen Dank für deine prompte Antwort. Ich muss aber zugeben, dass ich deine Antwort nicht verstehe. Wenn ich es richtig interpretiere, geht es bei deiner Lösung um einen besseren Algorithmus bzgl. meiner kreierten String-Methode

s = new StringBuilder().append(asc1).append(asc2).append(asc3).append(asc4).toString();

Dürfte ich dich bitten, deinen Code (bzw. den Code von Stackoverflow) noch etwas zu erläutern (sorry für den Mehraufwand...)?
Ich habe jetzt mal wie von dir vorgeschlagen meine Lösung in eine eigene stat. Methode verpackt. Wie könnte ich jetzt hier deinen Lösungsvorschlag einbauen???
Wie könnte ich etwa die 4 Vorschleifen vereinfachen, das ist ja voll redundanter Code...

public class Main {

    //Method for handling result in String compare

    public static boolean checking(String s, String p) {
        if (s.equals(p)) {
            //Strings are equal
            System.out.println("PW found, it is: " + s);

            return true;
        } else {
            //Strings are not equal, checked letter is shown
            System.out.println("Letter: " + s);
            return false;
        }
    }

    //method to compare password pw and created String

    public static void startRecovery(String pw) {
        // Initial value for ascii char
        char asc1 = 'a';
        char asc2 = 'a';
        char asc3 = 'a';
        char asc4 = 'a';
        //given password
        //String pw = "01av";
        //initial value for s
        String s = null;
        //searching for 0,1,2, ....X,Y, Z
        for (int i = 48; i < 123; i++) {
            asc1 = (char) i;
            //building a String to compare
            s = new StringBuilder().append(asc1).toString();
            //static method checking
            if (checking(s, pw) == true) {
                return;
            }

            for (int j = 48; j < 123; j++) {
                asc2 = (char) j;
                s = new StringBuilder().append(asc1).append(asc2).toString();
                if (checking(s, pw) == true) {
                    return;
                }

                for (int k = 48; k < 123; k++) {
                    asc3 = (char) k;
                    s = new StringBuilder().append(asc1).append(asc2).append(asc3).toString();
                    if (checking(s, pw) == true) {
                        return;
                    }

                    for (int l = 48; l < 123; l++) {
                        asc4 = (char) l;
                        s = new StringBuilder().append(asc1).append(asc2).append(asc3).append(asc4).toString();
                        if (checking(s, pw) == true) {
                            return;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        startRecovery("001z");

    }
}

 

[Tarrew]

Hallo Tarrew
Erstmals vielen Dank für deine prompte Antwort. Ich muss aber zugeben, dass ich deine Antwort nicht verstehe. Wenn ich es richtig interpretiere, geht es bei deiner Lösung um einen besseren Algorithmus bzgl. meiner kreierten String-Methode

s = new StringBuilder().append(asc1).append(asc2).append(asc3).append(asc4).toString();

Für die erste Aufgabe ist dein Algorithmus okay und auch naheliegend. Du könntest eine Instanz vom einem StringBuilder haben und diesen jedes mal resetten mit

StringBuilder.setLength(0)

anstatt dir jedes Mal einen neuen StringBuilder zu erstellen. Wenn du auf for-Schleifen setzt, dann gibt es imo keine Möglichkeit da weniger als 4 zu nutzen. Ist halt ziemlich rechenaufwenig aber so ist Brute-Force nunmal. Also für a) ist deine Lösung völlig in Ordnung. Für b) brauchst du aber einen komplett neuen Ansatz, da die Länge variabel sein soll.

Dürfte ich dich bitten, deinen Code (bzw. den Code von Stackoverflow) noch etwas zu erläutern (sorry für den Mehraufwand...)?
Ich habe jetzt mal wie von dir vorgeschlagen meine Lösung in eine eigene stat. Methode verpackt. Wie könnte ich jetzt hier deinen Lösungsvorschlag einbauen???
Wie könnte ich etwa die 4 Vorschleifen vereinfachen, das ist ja voll redundanter Code...

Also meine Lösung von b) ist unabhängig von deiner Lösung für a). Die brauchst du nicht verbinden oder einbauen oder Ähnliches. Ich versuche mal meinen Code zu erläutern. Der Code zählt einfach einen String hoch. Also er fängt bei "0" an, zählt dann bis "z" hoch und geht dann bei "00" weiter. Bzw die Methode an sich gibt dir nur den nächsten String zurück. Wenn du die Methode aber in einer while-Schleife laufen lässt, wird logischerweise der String mehrfach hochgezählt.

    public String incrementString(String original) {
        int i;
        char[] array = original.toCharArray();
        if(array[array.length-1]<'z'){
            array[array.length-1]++;
            return new String(array);
        }

Als erstes zerlege ich den String in ein char-Array um leichter Zeichen auszutauschen etc.
Danach überprüfe, ob das letzte Zeichen kleiner als 'z' ist. Wenn ja, dann zähle einfach den letzten Buchstaben hoch. Aus "00ab" wird also "00ac". Der String wird dann returned.

        for(i=array.length-1;i>=0;i--){
            if(array[i]!='z'){
                array[i]++;
                for(int j=i+1; j<array.length; j++){
                    array[j]='0';
                }
                return new String(array);
            }
        }

Wenn nein, (das letzte Zeichen ist also 'z'), dann laufe im char-Array so lange von hinten nach vorne, bis du das erste Zeichen findest das nicht 'z' ist. Wenn eins gefunden wurde, dann inkrementiere das Zeichen und setze alle Zeichen dahinter auf 0.
Aus azz wird also: b00

        if(i<0){
            return new String(new char[array.length]).replace("\0", "0")+"0";
        }
        throw new IllegalArgumentException();
    }

Wenn i kleiner als 0 ist (also wenn die for-Schleife komplett durchgelaufen ist und nicht returned hat) dann weißt du, dass alle Buchstaben 'z' sind. Wenn das der Fall ist, dann erstelle einen String aus einem neuen char-Array mit der alten Länge und ersetze alle '\0' (Defaultwert) durch '0' und hänge zusätzlich eine '0' an.
Aus: zzz wird also: 0000

Wenn nichts davon zutrifft wird eine Exception geworfen, was aber mit korrekter Eingabe etc. nie der Fall sein sollte.

Der Code von StackOverflow macht im Prinzip genau das gleiche, nur dass er das sehr geschickt rekursiv aufruft.


Wenn du das jetzt für beliebige Passwörter nutzen willst, kannst du deinen Code aus a) erstmal außen vorlassen. Zum Beispiel könnte das so gehen:

    public static void main(String[] args) {
        new Main().startRecovery("01z8f");
    }

    public void startRecovery(String pw){
        String s = "0";
        while(!s.equals(pw)){
            s=incrementString(s);
        }
        System.out.println("Found password: " + s);
    }

    public String incrementString(String original) {
        int i;
        char[] array = original.toCharArray();

        if (array[array.length - 1] < 'z') {
        array[array.length - 1]++;
            return new String(array);
        }
        for (i = array.length - 1; i >= 0; i--) {
            if (array[i] != 'z') {
                array[i]++;
                for (int j = i + 1; j < array.length; j++) {
                    array[j] = '0';
                }
                return new String(array);
            }
        }
        if (i < 0) {
            return new String(new char[array.length]).replace("\0", "0") + "0";
        }
        throw new IllegalArgumentException();
    }
}

Wenn man die Passwörter mal mit dem Algorithmus von Stackoverflow sucht (der wie ich finde echt genial ist) sieht man allerdings, dass dieser im Mittel (bei ein paar kurzen Tests) auch deutlich langsamer ist.

 

[fhs14647]

Hallo Tarrew
Ich finde auch deine Lösung genial!
Danke fürs ausführliche Kommentieren!!