Máy phát điện Brute Force

Question

Tôi vừa viết một chương trình Python 3 nhỏ để tìm ra mọi sự kết hợp có thể có của một bộ 99 ký tự. Nó hoàn thành công việc, nhưng tôi sẽ rất quan tâm đến những gì bạn nghĩ về nó.

Tôi chỉ mới làm quen với Python vài ngày, vì vậy tôi rất biết ơn vì những lời khuyên dường như rõ ràng.

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)

Answer 1

• Chúng ta có thể chuyển đổi một chuỗi thuần túy thành một danh sách hơn là duy trì một danh sách cho các ký tự.

  Sẽ dễ dàng hơn nhiều để sửa đổi và đọc sau đó là danh sách.

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

• Khi chúng ta có counter0, counter1..., counterngợi ý rằng chúng ta nên sử dụng một danh sách.

  counters = [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  

  Sau đó, chúng tôi có thể sử dụng counters[0]như một giọt thay thế cho counter0.

• Bây giờ chúng tôi có countersdanh sách, chúng tôi có thể đơn giản hóa việc in của bạn từ những điều sau đây.

  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")
  

  Chúng ta có thể sử dụng vòng lặp for để lặp qua các bộ đếm, lập chỉ mục libvà in ký tự. Chúng tôi sẽ sử dụng end=""để có được cùng một định dạng mà bạn có. Vì chúng tôi đã thay đổi từ "\r"sang nên ""chúng tôi cần phải in nó sau đó.

  for counter in counters:
      print(lib[counter], end="")
  print(end="\r")
  

• Sẽ tốt hơn nếu sử dụng len(lib)thay vì viết mã cứng 99trong ifs của bạn. Nếu chúng tôi thay đổi nội dung của libnó, nó sẽ dễ dàng hơn nhiều để chỉnh sửa libthay vì libvà 10 99.

• Thay vì counter0=counter0*0loại bỏ phép nhân và chỉ đặt giá trị thành 0 sẽ hợp lý hơn.

  counter0 = 0
  

• Quy ước trong Python là đặt một khoảng trắng ở hai bên của các toán tử. Điều này có nghĩa là a+bthay vào đó a + b. Điều này giúp bạn dễ dàng nhìn thấy những gì được và không phải là một toán tử và một trong hai bên của một toán tử.

• Nó được quy ước trong Python để sử dụng _như một biến 'vứt bỏ'. Điều này có nghĩa là nó bình thường để sử dụng _thay vì itrong vòng lặp for của bạn.

Cùng nhau điều này được:

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)

Vẫn còn một số thay đổi mà chúng tôi có thể thực hiện đối với mã của bạn để làm việc dễ dàng hơn. Đây là những nâng cao hơn một chút vì vậy đừng lo lắng nếu bạn không nhận được chúng ngay lập tức.

• Chúng tôi có thể thay đổi if elifkhối lớn của bạn thành một forvòng lặp duy nhất .
  Hãy xem những gì chúng tôi có cho đến nay:

  if counters[0] > len(lib):
      counters[0] = 0
      counters[1] += 1
  

  Chúng tôi biết rằng phần này được lặp lại mỗi lần cho mỗi chỉ mục. Vì vậy, chúng ta có thể làm cho điều này chung chung bằng cách thay đổi 0thành indexvà 1thành index + 1.

  if counters[index] >= len(lib):
      counters[index] = 0
      counters[index + 1] += 1
  

  Bây giờ chúng ta chỉ cần lặp lại range(len(counters) - 1)để nhân đôi khối 9 lần.

  for index in range(len(counters) - 1):
      if counters[index] >= len(lib):
          counters[index] = 0
          counters[index + 1] += 1
  

• Chúng tôi có thể sử dụng một số đường Python để làm cho bản in cho vòng lặp của bạn 'sạch' hơn. Trước hết chúng ta có thể loại bỏ tất cả các prints bằng cách xây dựng một danh sách.

  combination = []
  for counter in counters:
      combination.append(lib[counter])
  

  Từ đây, chúng ta có thể nối tất cả các chuỗi lại với nhau "".joinvà chuyển nó vào printgiống như bạn đã làm trước đây. Điều này sẽ tham gia danh sách bởi các chuỗi trống để nó chuyển đổi nó giống như thực hiện thủ công combination[0] + combination[1] + ....

  print("".join(combination), end="\r")
  

  Sau đó, chúng ta có thể sử dụng khả năng hiểu danh sách để xây dựng combinationtrong một dòng. Đây chỉ là cú pháp và giống với vòng lặp for mà chúng ta đã sử dụng trước đây. Nó chỉ khác, rõ ràng hơn, cú pháp.

  combination = [lib[counter] for counter in counters]
  

• Chúng ta có thể sử dụng một while Truevòng lặp hoặc itertools.countthay vì range(sys.maxsize**99999)lặp vô hạn.

  while True:
      counters[0] += 1
  

  import itertools
  
  for _ in range(itertools.count()):
      counters[0] += 1
  

• Chúng tôi có thể chỉ sử dụng printhơn là sys.stdout.write.

  Để làm cho nó không có dòng mới chúng tôi có thể vượt qua end="". Tuy nhiên, điều này không làm dòng chảy trôi đi ngay lập tức, và vì vậy chúng ta cần phải vượt qua 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)

Answer 2

Có thể hữu ích khi biết rằng python có một số tùy chọn tích hợp để thực hiện các phép tổ hợp. Đặc biệt, tôi thấy mô-đun itertools rất tiện dụng cho những loại hoạt động này. Nó có thể hơi nâng cao khi vẫn bắt đầu với Python, nhưng theo thời gian, bạn sẽ nhận được nhiều điều hữu ích này.

Đối với trường hợp bruto buộc mật khẩu, productphương pháp này có vẻ lý tưởng.

Ví dụ: nếu bạn muốn tất cả các kết hợp có thể có với 5 chữ số, bạn có thể chạy:

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

Vì vậy, nếu bạn muốn mở rộng điều này thành tất cả số chữ số lên đến 10, bạn có thể sử dụng:

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

---

Lưu ý khi sử dụng máy phát điện

Một ưu điểm của phương pháp này là các phương thức từ itertoolskhông lưu trữ tất cả các kết hợp mà thay vào đó chúng tạo ra chúng khi đang di chuyển. Do đó, việc sử dụng bộ nhớ của chúng không tăng theo số lần kết hợp.

Điều này khá quan trọng trong một kịch bản như của bạn, nơi số lượng các kết hợp có thể có tăng trưởng giai thừa. Bài viết này giới thiệu tốt, với một số trường hợp sử dụng bổ sung.

Một phần hay khác của điều này là, khá dễ dàng để mã này tiếp tục thử tất cả các kết hợp tăng độ dài cho đến khi tìm thấy thứ gì đó.

Điều này cũng sử dụng count()phương pháp từ itertools, là một trình tạo bắt đầu từ một số và tiếp tục tăng lên mãi mãi.

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

Answer 3

Để có khả năng sử dụng tốt hơn (sẽ rất hữu ích trong giây lát), hãy thay đổi mã của bạn thành một trình tạo. Đó chỉ là một hàm mang lại từng giá trị một khi được yêu cầu (hay đúng hơn, về mặt kỹ thuật, đối tượng trình tạo mà nó trả về thực hiện). Vì vậy, thay đổi duy nhất là thay vì in, bạn mang lại :

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]

Bây giờ chúng ta có thể ví dụ lặp lại kết quả của nó và in chúng:

for comb in combinations():
    print(comb)

Đầu ra:

0
1
2
3
4
5
6
7
8
9
A
B
...

Hoặc chúng ta có thể lấy một số để tạo danh sách:

from itertools import islice

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

Đầu ra:

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

Hãy xem nó chuyển từ một sang hai ký tự:

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

Hoặc từ hai đến ba:

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

Chờ gì? Tại sao được 'üü'theo sau '10'? Điều đó không nên đến sớm hơn rất nhiều ? Chúng tôi đã sản xuất hai lần?

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

Vâng, chúng tôi đã làm. Giáo sư. Vì vậy, có một số lỗi trong mã của bạn. Khó nhận thấy hơn trong phiên bản của bạn, btw, với tất cả các kết hợp vừa được in và ngay lập tức bị ghi đè :-)

Dù sao, tôi không thực sự muốn tìm hiểu sâu hơn về điều đó nhưng chỉ ra một giải pháp thay thế đơn giản. Hãy bắt đầu lại từ đầu. Trong khi chúng ta đang ở đó, hãy gọi nó wordsvà biến bảng chữ cái thành một tham số. Bắt đầu đơn giản, chỉ mang lại các từ có độ dài 0 và 1:

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

Bản giới thiệu:

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

Bây giờ làm thế nào để tạo ra các từ dài hơn? Hãy xem những gì chúng tôi muốn:

''         '' + ''
'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'
 ...           ...

Ở bên trái là những từ chúng ta muốn chúng như thế nào, và ở bên phải tôi chia chúng thành tiền tố và chữ cái cuối cùng (nếu có). Nếu chúng ta nhìn vào chữ cái cuối cùng, chúng ta có thể thấy rằng nó tiếp tục quay vòng trong bảng chữ cái. Tất cả các chữ cái cho mỗi tiền tố. Hãy giả sử chúng ta có một prefixhàm cung cấp cho chúng ta các tiền tố. Sau đó, chúng tôi chỉ có thể viết giải pháp của mình như sau:

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

Nhưng đợi đã. Tiền tố đầu tiên là '', sau đó 'a', 'b', 'c', 'aa', 'ab', vv Vì vậy, tiền tố chỉ đi qua cùng một chuỗi các từ mà chúng tôi muốn nói chung. Vì vậy, ... wordshàm của chúng ta có thể sử dụng chính nó để tạo ra các tiền tố:

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

Đó là nó. Đó là toàn bộ giải pháp.

Bản giới thiệu:

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

Cuối cùng, hãy thử lại với bảng chữ cái của bạn và xem nó chuyển từ hai sang ba chữ cái:

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

Vì vậy, ... chúng tôi đã kết thúc việc triển khai toàn bộ với một hàm trình tạo chỉ có bốn dòng đơn giản và nó hoạt động với một bảng chữ cái tùy ý, và là trình tạo, nó dễ sử dụng theo nhiều cách.

Nó có lẽ cũng nhanh hơn rất nhiều so với của bạn, mặc dù do lỗi của bạn, điều đó không dễ dàng để chuẩn đúng. Phiên bản của Peilonrayz hiện tại cũng có một số lỗi, nhưng chúng tôi có thể so sánh với giải pháp của Ivo_Merchiers và một vài biến thể.

Mười triệu từ đầu tiên sử dụng bảng chữ cái dài gồm 99 chữ cái của bạn:

same first 9,999,999: True
same 10,000,000th: True {'9TT8'}

1.41  1.38  1.38  seconds   Stefan_Pochmann
1.66  1.64  1.63  seconds   Stefan_Pochmann_2
2.45  2.45  2.45  seconds   Ivo_Merchiers
2.19  2.20  2.21  seconds   Ivo_Merchiers_2
1.50  1.49  1.50  seconds   Ivo_Merchiers_3
1.20  1.20  1.20  seconds   Ivo_Merchiers_chain

Mười triệu từ đầu tiên sử dụng bảng chữ cái abc:

same first 9,999,999: True
same 10,000,000th: True {'abcaccbbcccacbc'}

2.49  2.43  2.48  seconds   Stefan_Pochmann
4.16  4.17  4.19  seconds   Stefan_Pochmann_2
3.91  3.91  3.93  seconds   Ivo_Merchiers
3.64  3.66  3.64  seconds   Ivo_Merchiers_2
2.74  2.74  2.75  seconds   Ivo_Merchiers_3
2.45  2.46  2.45  seconds   Ivo_Merchiers_chain

Mã điểm chuẩn đầy đủ:

from itertools import product, count, islice, chain
from timeit import repeat
from collections import deque

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

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

def Stefan_Pochmann_2(alphabet):
    yield ''
    for prefix in Stefan_Pochmann_2(alphabet):
        yield from map(prefix.__add__, alphabet)

def Ivo_Merchiers(lib):
    for length in count(0):
        for combination in product(lib, repeat=length):
            yield ''.join(combination)

def Ivo_Merchiers_2(lib):
    join = ''.join
    for length in count(0):
        for combination in product(lib, repeat=length):
            yield join(combination)

def Ivo_Merchiers_3(lib):
    for length in count(0):
        yield from map(''.join, product(lib, repeat=length))

def Ivo_Merchiers_chain(lib):     # from Peilonrayz
    join = ''.join
    return chain.from_iterable(
        map(join, product(lib, repeat=length))
        for length in count(0)
    )

solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain

for alphabet in lib, 'abc':
    print(alphabet)

    n = 10**7
    
    # Correctness
    sets = map(set, zip(*(words(alphabet) for words in solutions)))
    print(f'same first {n-1:,}:', all(len(s) == 1 for s in islice(sets, n - 1)))
    s = next(sets)
    print(f'same {n:,}th:', len(s) == 1, s)
    print()
    
    # Speed
    tss = [[] for _ in solutions]
    for _ in range(3):
        for words, ts in zip(solutions, tss):
            t = min(repeat(lambda: deque(islice(words(alphabet), n), 0), number=1))
            ts.append(t)
    for words, ts in zip(solutions, tss):
        print(*('%.2f' % t for t in ts), 'seconds ', words.__name__, sep='  ')
    print()