Generator Brute Force

Oct 05 2020

Saya baru saja menulis program Python 3 kecil untuk mengeluarkan setiap kemungkinan kombinasi dari satu set 99 karakter. Itu menyelesaikan pekerjaan, tapi saya akan sangat tertarik dengan apa yang Anda pikirkan.

Saya hanya beberapa hari di Python, jadi saya akan berterima kasih untuk saran yang tampaknya jelas.


import sys

# List of 99 characters and a blank string:

lib=["","0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","°","!","\"","§","$","%","&","/","(",")","=","ß","´","`","+","#","-",".",",",">","<","@","€","|","^","~","–","{","[","]","}","Ä","Ö","Ü","ä","ö","ü"]


# 10 counters for up to 10-digit-combinations:

counter0=-1
counter1=0
counter2=0
counter3=0
counter4=0
counter5=0
counter6=0
counter7=0
counter8=0
counter9=0

# Repetitive if-statements adding to the counters:

for i in range(sys.maxsize**99999):
    counter0+=1
    
    if counter0>99:
        counter0=counter0*0
        counter1+=1
        
    elif counter1>99:
        counter1=counter1*0
        counter2+=1
        
    elif counter2>99:
        counter2=counter2*0
        counter3+=1
        
    elif counter3>99:
        counter3=counter3*0
        counter4+=1
        
    elif counter4>99:
        counter4=counter4*0
        counter5+=1
        
    elif counter5>99:
        counter5=counter5*0
        counter6+=1
        
    elif counter6>99:
        counter6=counter6*0
        counter7+=1
        
    elif counter7>99:
        counter7=counter7*0
        counter8+=1
        
    elif counter8>99:
        counter8=counter8*0
        counter9+=1
        
    elif counter9>99:
        print("DONE.")
        
# Printing the translation from counters to character - and deleting the former output so it stays in one line:
        
    else:
        print(lib[counter0]+lib[counter1]+lib[counter2]+lib[counter3]+lib[counter4]+lib[counter5]+lib[counter6]+lib[counter7]+lib[counter8]+lib[counter9], end="\r")
        sys.stdout.write("\b"*10+" "*10+"\b"*10)

Jawaban

21 Peilonrayz Oct 05 2020 at 05:24

Kita dapat mengonversi string biasa menjadi daftar daripada mempertahankan daftar karakter.

Jauh lebih mudah untuk memodifikasi dan membaca daftar berikut.
```
lib = [''] + list('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü')
```
Ketika kita memiliki counter0,, counter1..., counternitu adalah petunjuk bahwa kita harus menggunakan daftar.
```
counters = [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```
Kami kemudian dapat menggunakan counters[0]sebagai pengganti counter0.
Sekarang setelah kami memiliki countersdaftar, kami dapat menyederhanakan pencetakan Anda dari berikut ini.
```
print(lib[counters[0]] + lib[counters[1]] + lib[counters[2]] + lib[counters[3]] + > lib[counters[4]] + lib[counters[5]] + lib[counters[6]] + lib[counters[7]] + lib[counters[8]] + lib[counters[9]], end="\r")
```
Kita dapat menggunakan for loop untuk melakukan loop melalui counter, mengindeks libdan mencetak karakter. Kami akan menggunakan end=""untuk mendapatkan format yang sama dengan yang Anda miliki. Karena kita telah berubah dari "\r"menjadi ""kita perlu mencetaknya sesudahnya.
```
for counter in counters:
    print(lib[counter], end="")
print(end="\r")
```
Akan lebih baik untuk menggunakan len(lib)daripada hard coding 99dalam ifs Anda. Jika kita mengubah konten libitu jauh lebih mudah untuk mengedit saja libdaripada libdan 10 99.
Daripada counter0=counter0*0akan lebih masuk akal untuk menghapus perkalian dan hanya mengatur nilainya menjadi 0.
```
counter0 = 0
```
Ini konvensi di Python untuk meletakkan spasi di kedua sisi operator. Ini berarti a+bseharusnya a + b. Ini karena memudahkan untuk melihat apa yang merupakan operator dan sisi mana pun dari operator.
Itu konvensi di Python untuk digunakan _sebagai variabel 'buang'. Ini berarti itu normal untuk digunakan _daripada idi loop for Anda.

Bersama-sama ini mendapat:

import sys

lib = [''] + list('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü')
counters = [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

for _ in range(sys.maxsize**99999):
    counters[0] += 1
    if counters[0] >= len(lib):
        counters[0] = 0
        counters[1] += 1
    elif counters[1] >= len(lib):
        counters[1] = 0
        counters[2] += 1
    elif counters[2] >= len(lib):
        counters[2] = 0
        counters[3] += 1
    elif counters[3] >= len(lib):
        counters[3] = 0
        counters[4] += 1
    elif counters[4] >= len(lib):
        counters[4] = 0
        counters[5] += 1
    elif counters[5] >= len(lib):
        counters[5] = 0
        counters[6] += 1
    elif counters[6] >= len(lib):
        counters[6] = 0
        counters[7] += 1
    elif counters[7] >= len(lib):
        counters[7] = 0
        counters[8] += 1
    elif counters[8] >= len(lib):
        counters[8] = 0
        counters[9] += 1
    elif counters[9] >= len(lib):
        print("DONE.")
    else:
        for counter in counters:
            print(lib[counter], end="")
        print(end="\r")
        sys.stdout.write("\b"*10 + " "*10 + "\b"*10)

Masih ada beberapa perubahan yang dapat kami lakukan pada kode Anda agar lebih mudah dikerjakan. Ini sedikit lebih canggih jadi jangan khawatir jika Anda tidak mendapatkannya langsung.

Kami dapat mengubah if elifblok besar Anda menjadi satu forlingkaran.
Mari kita lihat apa yang kita miliki sejauh ini:
```
if counters[0] > len(lib):
    counters[0] = 0
    counters[1] += 1
```
Kita tahu bahwa bagian ini diulangi setiap kali untuk setiap indeks. Jadi kita bisa membuat ini umum dengan mengubah 0ke indexdan 1ke index + 1.
```
if counters[index] >= len(lib):
    counters[index] = 0
    counters[index + 1] += 1
```
Sekarang kita hanya perlu mengulang range(len(counters) - 1)untuk menduplikasi blok sebanyak 9 kali.
```
for index in range(len(counters) - 1):
    if counters[index] >= len(lib):
        counters[index] = 0
        counters[index + 1] += 1
```
Kita dapat menggunakan gula Python untuk membuat cetakan Anda untuk loop 'lebih bersih'. Pertama kita bisa menghapus semua printdengan membuat daftar.
```
combination = []
for counter in counters:
    combination.append(lib[counter])
```
Dari sini kita dapat menggabungkan semua string bersama "".joindan menyebarkannya printseperti yang Anda lakukan sebelumnya. Ini akan bergabung dengan daftar dengan string kosong sehingga mengubahnya seperti dilakukan secara manual combination[0] + combination[1] + ....
```
print("".join(combination), end="\r")
```
Kami kemudian dapat menggunakan pemahaman daftar untuk membangun combinationdalam satu baris. Ini hanyalah gula sintaks dan sama dengan loop for yang kita gunakan sebelumnya. Ini hanya berbeda, lebih bersih, sintaks.
```
combination = [lib[counter] for counter in counters]
```
Kita dapat menggunakan satu while Trueperulangan atau itertools.countdaripada range(sys.maxsize**99999)untuk melakukan perulangan tanpa batas.
```
while True:
    counters[0] += 1
```
```
import itertools

for _ in range(itertools.count()):
    counters[0] += 1
```
Kami mungkin hanya bisa menggunakan printdaripada sys.stdout.write.

Untuk membuatnya agar tidak ada jalur baru yang bisa kita lewati end="". Namun ini tidak langsung menyiram arus, jadi kita harus lewat flush=True.

lib = [''] + list('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü')
counters = [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

while True:
    counters[0] += 1
    for index in range(len(counters) - 1):
        if counters[index] >= len(lib):
            counters[index] = 0
            counters[index + 1] += 1
    
    if counters[9] >= len(lib):
        print("DONE.")
    else:
        print("".join([lib[counter] for counter in counters]), end="\r")
        print("\b"*10 + " "*10 + "\b"*10, end="", flush=True)

10 IvoMerchiers Oct 05 2020 at 16:25

Mungkin berguna untuk mengetahui bahwa python memiliki beberapa opsi bawaan untuk melakukan kombinatorik. Secara khusus, saya menemukan modul itertools sangat berguna untuk operasi semacam ini. Ini mungkin sedikit lebih maju ketika masih memulai dengan Python, tetapi pada waktunya Anda akan mengambil banyak hal berguna ini.

Untuk kasus bruto yang memaksa kata sandi, productmetode ini tampaknya ideal.

Misalnya, jika Anda menginginkan semua kemungkinan kombinasi dengan 5 digit, Anda dapat menjalankan:

from itertools import product

lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü'
for combination in product(lib, repeat=5):
  attempt="".join(combination) # This turns combination (a list of characters) into a string.
  # Use your password attempt here

Jadi jika Anda ingin memperluas ini ke semua jumlah digit hingga 10, Anda dapat menggunakan:

for length in range(10):
  for combination in product(lib, repeat=length):
    attempt="".join(combination)
    # Use your password attempt here

Catatan tentang penggunaan generator

Satu keuntungan dari metode ini adalah bahwa metode dari itertoolstidak menyimpan semua kombinasi, tetapi mereka membuatnya saat dalam perjalanan. Akibatnya, penggunaan memori mereka tidak meningkat seiring dengan banyaknya kombinasi.

Ini cukup penting dalam skenario seperti Anda, di mana jumlah kemungkinan kombinasi memiliki pertumbuhan faktorial. Artikel ini memberikan pengantar yang baik, dengan beberapa kasus penggunaan tambahan.

Bagian bagus lainnya dari ini adalah, cukup mudah untuk membiarkan kode ini terus mencoba semua kombinasi yang bertambah panjang sampai sesuatu ditemukan.

Ini juga menggunakan count()metode dari itertools, yaitu generator yang dimulai dari angka dan terus meningkat selamanya.

from itertools import product, count
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü'

for length in count(0):
  for combination in product(lib, repeat=length):
    attempt="".join(combination)
    # Use your password attempt here
    if password_found:
      print(attempt)
      break

6 StefanPochmann Oct 06 2020 at 00:00

Untuk kegunaan yang lebih baik (akan sangat berguna sebentar lagi), mari ubah kode Anda menjadi generator. Itu hanya fungsi yang menghasilkan nilai satu per satu saat diminta (atau lebih tepatnya, secara teknis, objek generator yang dikembalikan). Jadi satu-satunya perubahan adalah alih-alih mencetak, Anda menghasilkan :

def combinations():

    # List of 99 characters and a blank string:

    ...

        else:
            yield lib[counter0]+lib[counter1]+lib[counter2]+lib[counter3]+lib[counter4]+lib[counter5]+lib[counter6]+lib[counter7]+lib[counter8]+lib[counter9]

Sekarang kita dapat misalnya mengulang hasilnya dan mencetaknya:

for comb in combinations():
    print(comb)

Keluaran:

Atau kita dapat mengambil beberapa untuk membuat daftar:

from itertools import islice

print(list(islice(combinations(), 13)))

Keluaran:

['', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B']

Mari kita lihat beralih dari satu menjadi dua karakter:

>>> list(islice(combinations(), 98, 102))
['ö', 'ü', '00', '10']

Atau dari dua menjadi tiga:

>>> list(islice(combinations(), 99*100-1, 99*100+3))
['öü', 'üü', '10', '20']

Tunggu apa? Mengapa 'üü'diikuti oleh '10'? Bukankah seharusnya itu datang lebih awal ? Apakah kami memproduksinya dua kali?

>>> list(islice(combinations(), 99*100+3)).count('10')
2

Ya kami lakukan. Ups. Jadi ada beberapa bug di kode Anda. Jauh lebih sulit untuk diperhatikan dalam versi Anda, btw, dengan semua kombinasi baru saja dicetak dan segera ditimpa :-)

Bagaimanapun, saya tidak benar-benar ingin menggali lebih dalam tetapi menunjukkan alternatif sederhana. Mari kita mulai dari awal. Sementara kita melakukannya, mari kita menyebutnya wordsdan membuat alfabet sebagai parameter. Mulailah dengan sederhana, hanya menghasilkan kata-kata dengan panjang 0 dan 1:

def words(alphabet):
    yield ''
    for letter in alphabet:
        yield letter

Demo:

>>> list(words('abc'))
['', 'a', 'b', 'c']

Sekarang bagaimana menghasilkan kata-kata yang lebih panjang? Mari kita lihat apa yang kita inginkan:

''         '' + ''
'a'        '' + 'a'
'b'        '' + 'b'
'c'        '' + 'c'
'aa'       'a' + 'a'
'ab'       'a' + 'b'
'ac'       'a' + 'c'
'ba'       'b' + 'a'
'bb'       'b' + 'b'
'bc'       'b' + 'c'
'ca'       'c' + 'a'
'cb'       'c' + 'b'
'cc'       'c' + 'c'
'aaa'      'aa' + 'a'
'aab'      'aa' + 'b'
'aac'      'aa' + 'c'
'aba'      'ab' + 'a'
'abb'      'ab' + 'b'
 ...           ...

Di sebelah kiri adalah kata-kata yang kita inginkan, dan di sebelah kanan saya membaginya menjadi awalan dan huruf terakhir (jika ada). Jika kita melihat huruf terakhir, kita dapat melihat bahwa itu terus berputar melalui alfabet. Semua huruf untuk setiap awalan. Mari kita anggap kita memiliki prefixfungsi yang memberi kita awalan. Kemudian kita bisa menulis solusi kita seperti ini:

def words(alphabet):
    yield ''
    for prefix in prefixes(alphabet):
        for letter in alphabet:
            yield prefix + letter

Tapi tunggu. Awalan pertama '', kemudian 'a', 'b', 'c', 'aa', 'ab', dll Jadi awalan hanya berjalan melalui urutan yang sama kata-kata yang kita inginkan secara keseluruhan. Jadi ... wordsfungsi kita bisa menggunakan dirinya sendiri untuk menghasilkan prefiks:

def words(alphabet):
    yield ''
    for prefix in words(alphabet):
        for letter in alphabet:
            yield prefix + letter

Itu dia. Itulah solusinya.

Demo:

>>> list(islice(words('abc'), 20))
['', 'a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca',
 'cb', 'cc', 'aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca']

Terakhir, mari kita coba dengan alfabet Anda lagi dan lihat peralihan dari dua menjadi tiga huruf:

>>> alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß´`+#-.,><@€|^~–{[]}ÄÖÜäöü'
>>> list(islice(words(alphabet), 99*100-1, 99*100+3))
['üö', 'üü', '000', '001']

Jadi ... kami akhirnya mengimplementasikan semuanya dengan fungsi generator yang hanya memiliki empat baris sederhana, dan bekerja dengan alfabet sembarang, dan sebagai generator, mudah digunakan dalam banyak hal.

Ini mungkin juga jauh lebih cepat daripada milik Anda, meskipun karena bug Anda, itu tidak mudah untuk melakukan benchmark dengan benar. Versi Peilonrayz juga memiliki bug saat ini, tetapi kita dapat membandingkan dengan solusi Ivo_Merchiers dan beberapa variasi.