Seite 1 von 1
Generator für Kombinationen
Verfasst: Montag 12. Juli 2004, 14:44
von Dookie
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
Verfasst: Donnerstag 3. August 2006, 11:15
von jens
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
Verfasst: Donnerstag 3. August 2006, 13:11
von jens
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
Verfasst: Dienstag 3. Juli 2007, 23:35
von jan!
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
...
Verfasst: Mittwoch 4. Juli 2007, 08:11
von BlackJack
Was Du suchst nennt sich Permutation. Da sollte es im Netz genügend Beispiele geben.
Verfasst: Mittwoch 4. Juli 2007, 14:24
von jan!
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
Verfasst: Mittwoch 4. Juli 2007, 15:02
von BlackJack
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
Verfasst: Mittwoch 4. Juli 2007, 16:59
von jan!
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
Verfasst: Dienstag 24. März 2009, 14:28
von jens