Generator für Kombinationen

Dookie · Montag 12. Juli 2004, 14:44

Hallo,

das erste Program vom User AkteXY, hat mich auf die Idee gebracht, einen einfachen Iterator, der alle Möglichen Kombinationen, einer vorgegebenen Anzahl, die mit den Elementen aus einem iterable Objekt (tuple, liste, string ...) besteht, erzeugt.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
    Modul:          Combine
    Version:        1.0
    Copyright:      2004 by Fritz Cizmarov fritz@sol.at
    Created:        11. Jul. 2004
    Last modified:  12. Jul. 2004
    License:        free
    Requirements:   Python2.3
"""

def combine(iterable, n):
    """ Erzeugt alle Kombinationen der Elemente in iterable mit der Länge n """

    iters = [iter(iterable) for i in xrange(n)] # Liste mit Iteratoren
    liste = [it.next() for it in iters]         # Liste mit 1. Kombination
    
    while True:
        yield tuple(liste) # Wichtig weil liste mutable ist !!!
        for i in xrange(n-1,-1,-1): # Stellen weiterschalten
            try:
                liste[i] = iters[i].next()
                break # alles OK, kein Ueberlauf, naechstes Wort bereit
            except StopIteration: # Ueberlauf
                iters[i] = iter(iterable)  # Iterator zuruecksetzen
                liste[i] = iters[i].next() # Stelle zuruecksetzen
                continue # weiter mit naechster Stelle
        else: # alle Stellen hatten einen Ueberlauf
            raise StopIteration # Stop, alle Kombinationen sind durch 


if __name__ == "__main__": # Script direkt gestartet (nicht importiert)
    print u"Dezimal\t\tBinär"
    for bin in combine("01", 4):
        word = "".join(bin) 
        print "% 3i\t\t%s" % (int(word,2), word)

Wichtig ist, daß ein Tuple zurückgegeben wird, wers nicht glaubt kann ja mal das yield tuple(liste) durch yield liste ersetzen und folgendes probieren.

Code: Alles auswählen

>>> from Combine import combine
>>> comb = combine("abcd",4)
>>> a = comb.next()
>>> print "a =", a

>>> b = comb.next()
>>> print "a =", a, "b =", b

>>> c = comb.next()
>>> print "a =", a, "b =", b, "c =" c

Gruß

Dookie

jens · Donnerstag 3. August 2006, 11:15

Ich möchte das Skript nun nutzten

Ich möchte allerdings das es ein klein wenig anders abläuft. Ich möchte ein min-, maxlen angeben können.

Hier die Änderungen:

Code: Alles auswählen

class BruteForcer:
    def __init__(self, words, minlen, maxlen):
        for pos, bin in enumerate(self.combine2(words, minlen, maxlen)):
            bin = "".join(bin)
            print "%-3s - %s" % (pos, bin)

    def combine2(self, iterable, minlen, maxlen):
        for n in xrange(minlen, maxlen+1):
            for bin in self.combine(iterable, n):
                yield bin

        raise StopIteration

    def combine(self, iterable, n):
        """ Erzeugt alle Kombinationen der Elemente in iterable mit der Länge n """

        iters = [iter(iterable) for i in xrange(n)] # Liste mit Iteratoren
        liste = [it.next() for it in iters]         # Liste mit 1. Kombination

        while True:
            yield tuple(liste) # Wichtig weil liste mutable ist !!!
            for i in xrange(n-1,-1,-1): # Stellen weiterschalten
                try:
                    liste[i] = iters[i].next()
                    break # alles OK, kein Ueberlauf, naechstes Wort bereit
                except StopIteration: # Ueberlauf
                    iters[i] = iter(iterable)  # Iterator zuruecksetzen
                    liste[i] = iters[i].next() # Stelle zuruecksetzen
                    continue # weiter mit naechster Stelle
            else: # alle Stellen hatten einen Ueberlauf
                raise StopIteration # Stop, alle Kombinationen sind durch


BruteForcer(
    words = ["a","b","c"],
    minlen = 2,
    maxlen = 3
)

Das kommt dabei raus:

Code: Alles auswählen

0   - aa
1   - ab
2   - ac
3   - ba
4   - bb
5   - bc
6   - ca
7   - cb
8   - cc
9   - aaa
10  - aab
11  - aac
12  - aba
13  - abb
14  - abc
15  - aca
16  - acb
17  - acc
18  - baa
19  - bab
20  - bac
21  - bba
22  - bbb
23  - bbc
24  - bca
25  - bcb
26  - bcc
27  - caa
28  - cab
29  - cac
30  - cba
31  - cbb
32  - cbc
33  - cca
34  - ccb
35  - ccc

jens · Donnerstag 3. August 2006, 13:11

So, ich hab mein Passwort wieder

das fertige Skript:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

"""
TrueCrypt - brute force

Nützlich wenn man ein zusammengesetztes Password benutzt, man die Einzelteile
noch kennt, aber nicht mehr weiß wie die Reihenfolge ist ;)

Kann auch statt TrueCrypt jedes andere Kommandozeilen Programm benutzten.


WICHTIG:
    Der Pfad und die Parameter zum TrueCrypt Kommandozeilen Programm müßen
    angepasst werden!!!


used the combine method by Fritz Cizmarov alias Dookie
"""

__author__      = "Jens Diemer (http://www.jensdiemer.de)"
__url__         = "http://www.python-forum.de/topic-1812.html"
__license__     = "GNU General Public License (GPL)"


import sys, subprocess, time


class BruteForcer:
    def __init__(self, words, minlen, maxlen, command):
        # Anzahl der Kombinationen ermitteln
        count = self.count(words, minlen, maxlen)

        start_time = time_threshold = int(time.time())
        for pos, bin in enumerate(self.combine2(words, minlen, maxlen)):
            bin = "".join(bin)

            current_time = int(time.time())
            if current_time > time_threshold:
                elapsed = float(current_time-start_time)    # Vergangene Zeit
                estimated = elapsed / pos+1 * count         # Geschäzte Zeit

                if estimated>60:
                    time_info = "%.1f/%.1fmin" % (elapsed/60, estimated/60)
                else:
                    time_info = "%.0f/%.1fsec" % (elapsed, estimated)

                sys.stdout.write("\r")
                sys.stdout.write(
                    "tested %i password from %i - %s          " % (
                        pos+1, count, time_info
                    )
                )
                time_threshold = current_time

            returncode = self.cmd(command % bin)
            if returncode == 0:
                print
                print "Richtige Password gefunden!!!"
                print ">>>%s<<<" % bin
                sys.exit()


    def count(self, iterable, minlen, maxlen):
        """ Liefert die Anzahl der Kombinationen zurück """
        count = 0
        l = len(iterable)
        for n in xrange(minlen, maxlen+1):
            count += l ** n

        return count


    def combine2(self, iterable, minlen, maxlen):
        """
        Erzeugt alle Kombinationen der Elemente in iterable
        mit der Länge von >minlen< bin >maxlen<
        """
        for n in xrange(minlen, maxlen+1):
            for bin in self.combine(iterable, n):
                yield bin

        raise StopIteration


    def combine(self, iterable, n):
        """
        Erzeugt alle Kombinationen der Elemente in iterable mit der Länge n
        """
        iters = [iter(iterable) for i in xrange(n)] # Liste mit Iteratoren
        liste = [it.next() for it in iters]         # Liste mit 1. Kombination

        while True:
            yield tuple(liste) # Wichtig weil liste mutable ist !!!
            for i in xrange(n-1,-1,-1): # Stellen weiterschalten
                try:
                    liste[i] = iters[i].next()
                    break # alles OK, kein Ueberlauf, naechstes Wort bereit
                except StopIteration: # Ueberlauf
                    iters[i] = iter(iterable)  # Iterator zuruecksetzen
                    liste[i] = iters[i].next() # Stelle zuruecksetzen
                    continue # weiter mit naechster Stelle
            else: # alle Stellen hatten einen Ueberlauf
                raise StopIteration # Stop, alle Kombinationen sind durch


    def cmd(self, command):
        """
        Führt den Befehl in der shell aus und liefert den Rückgabecode zurück
        """
        # stderr auch lesen:
        process = subprocess.Popen(
            command, shell=True,
            #~ stdout=subprocess.PIPE, stderr=subprocess.PIPE
        )
        # warten, bis der gestartete Prozess zu Ende ist
        process.wait()

        # die Standardausgabe des Prozesses ausgeben
        #~ print process.stdout.read()
        # die Fehlerausgabe (sofern vorhanden) anzeigen
        #~ print process.stderr.read()

        # den Rückgabewert des Prozesses ausgeben
        # ist 0 wenn das Programm problemlos durchgelaufen ist
        return process.returncode



BruteForcer(
    words = [
        "syllable","part","lot","component","fragment","brick"
    ],
    minlen = 2,
    maxlen = 3,
    command = (
        "E:\\TrueCrypt\\TrueCrypt.exe /auto /beep /quit /silent"
        " /password %s"
        " /keyfile D:\\keyfile.dat"
        " /volume D:\\volumenfile.tc"
    )
)

Vielleicht kann es jemand gebrauchen

Zumindest hab ich auf der Suche nach einem Brute Force Tool für TrueCrypt einige Postings in Foren gefunden, die auch sowas suchen

EDIT: Das Skript ist nun in meinem SVN:
http://pylucid.net:8080/pylucid/browser ... ueCrypt.py
bzw.
http://svn.pylucid.net/pylucid/CodeSnip ... ueCrypt.py

jan! · Dienstag 3. Juli 2007, 23:35

Hab seit ein paar Tagen leider ebenfalls das Problem, dass mir ein Passwort entfallen ist, ich mich aber an darin vorkommende Wörter erinnern kann. Allerdings fallen mir neben einigen Wörtern bei denen ich mir sicher bin auch einige ein, bei denen ich mir unsicher bin. So kommt leider eine Anzahl an Wörtern zustande, die mit der Kombinationsart des Skripts nicht mehr zu bewälltigen ist, da das Skript alle Kombinationen testet.

Ich weiß aber sicher, dass jedes Wort genau EINMAL im Passwort vorkommt. Leider habe ich keinerlei Python-Kenntnisse und nur sehr begrenzte Kenntnisse in anderen Sprachen. Falls es einfach zu integrieren ist, würde ich mich sehr freuen, wenn mir jemand helfen könnte das Skript so anzupassen, dass jedes Wort in den Kombinationen nur einmal vorkommt.

Also:

Aus a,b,c:

a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba

und eben nicht alle möglichen Kombinationen wie

aa
ab
ac
...
aaa
aab
aac
...

BlackJack · Mittwoch 4. Juli 2007, 08:11

Was Du suchst nennt sich Permutation. Da sollte es im Netz genügend Beispiele geben.

jan! · Mittwoch 4. Juli 2007, 14:24

Danke für den Tipp. Ich habe auch einiges im Internet gefunden, leider nichts, was mein Problem wirklich löst.

Es werden immer nur alle Permutationen der vorgegebenen Werte ausgegeben, diese enthalten immer alle Werte.

Ich suche etwas das aus einer Liste mit möglichen Werte alle möglichen Kombinationen ausspuckt, bei denen jeder Wert nur einmal vorkommt.

Also bei den Werten a,b,c sollen folgende Kombinationen generiert werden:

a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba

und nicht nur:

abc
acb
bac
bca
cab
cba

BlackJack · Mittwoch 4. Juli 2007, 15:02

Wenn Du nicht auf der Reihenfolge bestehst, lässt sich eine rekursive Lösung die immer nur die "volle" Länge liefert, relativ leicht anpassen. Man muss ja nur alle Zwischenergebnisse ebenfalls zurückgeben. Das dürfte dann so aussehen:

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

jan! · Mittwoch 4. Juli 2007, 16:59

Danke für deine Hilfe, ich hab jetzt hier zwei Permutations-Codes. Leider hab ich keine Ahnung von Python. Wie kann ich denn die Zwischenergebnisse ausgeben lassen? Und wie bekomm ich die Ausgabenwerte so hin, dass sie in einer Variable stecken und nicht mehr im Array(?)?

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf8 -*-
#
# 9.7.2006

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]

for p in all_perms(['a','b','c']):
	print p

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf8 -*-
#
# 9.7.2006

"""
Permuationen erzeugen
"""

import sys

# Initial-Permutation;
# init_perm verweist im Laufe des Algorithmus auf die jeweils aktuell
# generierte Permutation
init_perm = [1, 3, 7, 9]

# Liste aller Permutationen
perm_list = []

def perm(anz_elems):
  """Erzeugen aller Permutationen der letzten anz_elems Elemente von init_perm"""

  # den Start-Index berechnen, ab dem die Elemente von init_perm noch zu
  # permutieren sind
  start = len(init_perm) - anz_elems

  if anz_elems < 2:
    # init_perm enthaelt eine gueltige Permuation, da keine weiteren Elemente zu
    # permutieren sind
    #
    # Duplikat von init_perm durch Slicing erstellen (init_perm[:]) und an
    # perm_list anhaengen
    #
    # ohne diese Duplizierung des Objekts wuerde eine Referenz auf die globale
    # Variable init_perm in die Liste perm_list eingefuegt, so dass sie immer
    # nur identische Objekte enthielte; durch jede Aenderung an init_perm wuerde
    # dann die Liste perm_list veraendert
    perm_list.append(init_perm[:])
  else:
    # wir haben anz_elems Elemente zu permutieren; wir permutieren jeweils
    # rekursiv anz_elems-1 Elemente und holen danach jedes dieser anz_elems-1
    # Elemente an den linken Rand der zu permutierenden anz_elems Elemente; wir
    # benoetigen daher anz_elems Durchlaeufe, um am Ende wieder den
    # Ausgangszustand hergestellt zu haben
    for i in range(1, anz_elems + 1):
      perm(anz_elems - 1)
      if i < anz_elems:
        # kein letzter Durchlauf --> hole das nächste Element an den linken
        # Rand
        init_perm[start], init_perm[start+i] = init_perm[start+i], init_perm[start]
      else:
        # letzter Durchlauf --> Ausgangszustand herstellen
        init_perm.append(init_perm.pop(start))

# Permuationen generieren
perm(len(init_perm))

# und ausgeben
for perm in perm_list:
  print perm

jens · Dienstag 24. März 2009, 14:28

...alten Thread ausbuddel...

Hab gerade das gebastelt: http://paste.pocoo.org/show/109336/

Ansehen sollte man sich aber auch:
http://docs.python.org/library/itertool ... rmutations (neu in 2.6)
http://aspn.activestate.com/ASPN/search ... Subsection