[Russian][Math][Python] Ломаем пароль при помощи комбинаторики и mixed radix

Нужно перебирать все возможные пароли, а каждый символ это A-Za-z0-9, т.е., все латинские символы (строчные и заглавные) и цифры. Обыкновенно, сейчас у всех многоядерные процессоры или даже кластеры, и задача подбора пароля легко параллелизируется. Может быть, даже при помощи OpenMP. Но только как красиво разрезать пространство поиска (search space) на 4 или 8 ядер процессора?

Первое что придет в голову, это разрезать их учитывая первый символ пароля. Например, разделим алфавит a-zA-Z (26*2=52 символа) на 4/8/16/32 ядер:

#!/usr/bin/env python3

import math

az=list(map(chr, range(ord('a'), ord('z')+1)))
AZ=list(map(chr, range(ord('A'), ord('Z')+1)))
az_AZ=az+AZ
_09=list(map(chr, range(ord('0'), ord('9')+1)))
az_AZ_09=az+AZ+_09
specials=['!','@','#','$','%','^','&','*','(',')','_','+'] # 12
az_AZ_09_specials=az+AZ+_09+specials

# https://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks
def chunks(lst, n):
    """Yield successive n-sized chunks from lst."""
    """and convert to string..."""
    for i in range(0, len(lst), n):
        yield "".join(lst[i:i + n])

alphabet=az_AZ
#alphabet=az_AZ_09
#alphabet=az_AZ_09_specials
alphabet_size=len(alphabet)

print (list(chunks(alphabet, math.ceil(alphabet_size/4))))
print (list(chunks(alphabet, math.ceil(alphabet_size/8))))
print (list(chunks(alphabet, math.ceil(alphabet_size/16))))
print (list(chunks(alphabet, math.ceil(alphabet_size/32))))

['abcdefghijklm', 'nopqrstuvwxyz', 'ABCDEFGHIJKLM', 'NOPQRSTUVWXYZ']
['abcdefg', 'hijklmn', 'opqrstu', 'vwxyzAB', 'CDEFGHI', 'JKLMNOP', 'QRSTUVW', 'XYZ']
['abcd', 'efgh', 'ijkl', 'mnop', 'qrst', 'uvwx', 'yzAB', 'CDEF', 'GHIJ', 'KLMN', 'OPQR', 'STUV', 'WXYZ']
['ab', 'cd', 'ef', 'gh', 'ij', 'kl', 'mn', 'op', 'qr', 'st', 'uv', 'wx', 'yz', 'AB', 'CD', 'EF', 'GH', 'IJ', 'KL', 'MN', 'OP', 'QR', 'ST',
'UV', 'WX', 'YZ']

Пароли начинающиеся с символов 'abcdefghijklm' перебираем на первом ядре, начинающиеся с 'nopqrstuvwxyz' - на втором, итд. На 4 ядра пароли порезать получается ровно, но на 8 - не очень. Видите, пароли начинающиеся с 'XYZ' будут перебираться на последнем, 8-м ядре. А значит он будет нагружен меньше всех (относительно остальных ядер). Это не самая большая трагедия в жизни, но всё-таки отдельных перфекционистов подобные ситуации слегка подбешивают. Можно ли как-то поделить все пароли на ядра процессора, чтобы не было таких проблем?

Хочется представлять всякий пароль в виде просто числа. И вот эти числа делить ровно на 4/8/16/32/итд. Как закодировать пароль в виде числа?

В начале попытаемся изобрести велосипед. Если каждый символ пароля имеет алфавит a-zA-Z0-9, это 26*2+10=62 символа. Можно сказать прямо, что каждый символ пароля можно закодировать используя 6 бит ($2^6=64$). Останется два незадействованных значения, ну да и ладно. Обратите внимание - каждый символ пароля мы можем закодировать используя 6 бит. Если в пароле 10 символов, то весь пароль мы можем закодировать используя $6*10=60$ бит. Затем мы делим $2^{60}$ на 4/8/16/32 и на каждом ядре начинаем перебор с этого числа. От числа отрезаем по 6 бит и так конвертируем число в 10-символьный пароль. Даже не важно, откуда отрезаем - с конца или с начала.

Теперь представим, что первые три символа пароля это a-z, вторые три символа пароля - цифры. (Пароли начниаются с aaa000, заканчиваются на zzz999.) Число в пределах 0..25 можно закодировать используя 5 бит, хотя это не экономно. Число в пределах 0..9 можно закодировать используя 4 бита. Чтобы такой пароль представить в виде числа, получается так: 5 бит | 5 бит | 5 бит | 4 бита | 4 бита | 4 бита. При конвертировании числа в пароль, три раза отрезаем по 4 бита, потом три раза отрезаем по 5 бит. Итого 27 бит.

Всё это никак не экономично, но иллюстрирует правило умножения (rule of product) в комбинаторике. Нетрудно догадаться, что в последнем случае, количество всех паролей будет равно 26*26*26*10*10*10=17576000.

Так вот, вместо отрезания бит, мы можем просто делить число на 10. (А отрезание бит это просто деление на числа вида $2^n$.) Остаток от деления - это последний символ пароля. Потом еще раз делим на 10, повторяем процедуру. Еще раз на 10. Потом 3 раза делим на 26, каждый раз используя остаток как символ пароля.

Сейчас будем использовать такой пароль:

1-й символ: A-Za-z
2-й символ: A-Za-z0-9
3-й символ: A-Za-z0-9
4-й символ: A-Za-z0-9
5-й символ: A-Za-z0-9!@#$%^&*()_+
6-й символ: A-Za-z0-9!@#$%^&*()_+

#!/usr/bin/env python3

import math, functools, itertools, operator

az=list(map(chr, range(ord('a'), ord('z')+1)))
AZ=list(map(chr, range(ord('A'), ord('Z')+1)))
az_AZ=az+AZ
_09=list(map(chr, range(ord('0'), ord('9')+1)))
az_AZ_09=az+AZ+_09
specials=['!','@','#','$','%','^','&','*','(',')','_','+'] # 12
az_AZ_09_specials=az+AZ+_09+specials

password=[az_AZ, az_AZ_09, az_AZ_09, az_AZ_09, az_AZ_09_specials, az_AZ_09_specials]

lengths_of_each_char=list(map(len, password))
total=functools.reduce(operator.mul, lengths_of_each_char)

print ("total passwords=", total)
print ("bits ~", math.log(total, 2))

def password_to_number(pw):
    pw=reversed(pw) # start at last char
    rt=0
    base=1
    for char, p in zip(pw, reversed(password)):
        lenght_of_alphabet=len(p)
        rt=rt + p.index(char)*base
        base=base*lenght_of_alphabet
    return rt

def number_to_password(n):
    pw=[]
    for p in reversed(password):
        lenght_of_alphabet=len(p)
        pw.append(p[n % lenght_of_alphabet])
        n = int(n / lenght_of_alphabet)
    return "".join(reversed(pw))

assert password_to_number ("aaaaaa")==0
assert password_to_number ("Z999++")==total-1

assert number_to_password(0)=="aaaaaa"
assert number_to_password(total-1)=="Z999++"
assert number_to_password(total)=="aaaaaa" # overlap!

#print (number_to_password(password_to_number ("hello!")+10))
#print (number_to_password(password_to_number ("hello!")+100))

for cores in [4,8,16,20]:
    print (f"for {cores} cores")
    total_per_core=int(total/cores)-1
    print (f"passwords per core: {total_per_core}")
    start=0
    for core in range(cores):
        end=start+total_per_core
        start_pw=number_to_password(start)
        end_pw=number_to_password(end)
        print (f"core {core}, start={start}, start_pw={start_pw}, end={end}, start_pw={end_pw}")
        start=start+total_per_core+1

total passwords= 67864374656
bits ~ 35.98193538055962
for 4 cores
passwords per core: 16966093663
core 0, start=0, start_pw=aaaaaa, end=16966093663, start_pw=m999++
core 1, start=16966093664, start_pw=naaaaa, end=33932187327, start_pw=z999++
core 2, start=33932187328, start_pw=Aaaaaa, end=50898280991, start_pw=M999++
core 3, start=50898280992, start_pw=Naaaaa, end=67864374655, start_pw=Z999++
for 8 cores
passwords per core: 8483046831
core 0, start=0, start_pw=aaaaaa, end=8483046831, start_pw=gE99++
core 1, start=8483046832, start_pw=gFaaaa, end=16966093663, start_pw=m999++
core 2, start=16966093664, start_pw=naaaaa, end=25449140495, start_pw=tE99++
core 3, start=25449140496, start_pw=tFaaaa, end=33932187327, start_pw=z999++
core 4, start=33932187328, start_pw=Aaaaaa, end=42415234159, start_pw=GE99++
core 5, start=42415234160, start_pw=GFaaaa, end=50898280991, start_pw=M999++
core 6, start=50898280992, start_pw=Naaaaa, end=59381327823, start_pw=TE99++
core 7, start=59381327824, start_pw=TFaaaa, end=67864374655, start_pw=Z999++
for 16 cores
passwords per core: 4241523415
core 0, start=0, start_pw=aaaaaa, end=4241523415, start_pw=dpE9++
core 1, start=4241523416, start_pw=dpFaaa, end=8483046831, start_pw=gE99++
core 2, start=8483046832, start_pw=gFaaaa, end=12724570247, start_pw=jUE9++
core 3, start=12724570248, start_pw=jUFaaa, end=16966093663, start_pw=m999++
core 4, start=16966093664, start_pw=naaaaa, end=21207617079, start_pw=qpE9++
core 5, start=21207617080, start_pw=qpFaaa, end=25449140495, start_pw=tE99++
core 6, start=25449140496, start_pw=tFaaaa, end=29690663911, start_pw=wUE9++
core 7, start=29690663912, start_pw=wUFaaa, end=33932187327, start_pw=z999++
core 8, start=33932187328, start_pw=Aaaaaa, end=38173710743, start_pw=DpE9++
core 9, start=38173710744, start_pw=DpFaaa, end=42415234159, start_pw=GE99++
core 10, start=42415234160, start_pw=GFaaaa, end=46656757575, start_pw=JUE9++
core 11, start=46656757576, start_pw=JUFaaa, end=50898280991, start_pw=M999++
core 12, start=50898280992, start_pw=Naaaaa, end=55139804407, start_pw=QpE9++
core 13, start=55139804408, start_pw=QpFaaa, end=59381327823, start_pw=TE99++
core 14, start=59381327824, start_pw=TFaaaa, end=63622851239, start_pw=WUE9++
core 15, start=63622851240, start_pw=WUFaaa, end=67864374655, start_pw=Z999++
for 20 cores
passwords per core: 3393218731
core 0, start=0, start_pw=aaaaaa, end=3393218731, start_pw=cLmy7n
core 1, start=3393218732, start_pw=cLmy7o, end=6786437463, start_pw=fmyXSB
core 2, start=6786437464, start_pw=fmyXSC, end=10179656195, start_pw=hXLmDP
core 3, start=10179656196, start_pw=hXLmDQ, end=13572874927, start_pw=kyXLo3
core 4, start=13572874928, start_pw=kyXLo4, end=16966093659, start_pw=m999+*
core 5, start=16966093660, start_pw=m999+(, end=20359312391, start_pw=pLmy7j
core 6, start=20359312392, start_pw=pLmy7k, end=23752531123, start_pw=smyXSx
core 7, start=23752531124, start_pw=smyXSy, end=27145749855, start_pw=uXLmDL
core 8, start=27145749856, start_pw=uXLmDM, end=30538968587, start_pw=xyXLoZ
core 9, start=30538968588, start_pw=xyXLo0, end=33932187319, start_pw=z999+$
core 10, start=33932187320, start_pw=z999+%, end=37325406051, start_pw=CLmy7f
core 11, start=37325406052, start_pw=CLmy7g, end=40718624783, start_pw=FmyXSt
core 12, start=40718624784, start_pw=FmyXSu, end=44111843515, start_pw=HXLmDH
core 13, start=44111843516, start_pw=HXLmDI, end=47505062247, start_pw=KyXLoV
core 14, start=47505062248, start_pw=KyXLoW, end=50898280979, start_pw=M999+9
core 15, start=50898280980, start_pw=M999+!, end=54291499711, start_pw=PLmy7b
core 16, start=54291499712, start_pw=PLmy7c, end=57684718443, start_pw=SmyXSp
core 17, start=57684718444, start_pw=SmyXSq, end=61077937175, start_pw=UXLmDD
core 18, start=61077937176, start_pw=UXLmDE, end=64471155907, start_pw=XyXLoR
core 19, start=64471155908, start_pw=XyXLoS, end=67864374639, start_pw=Z999+5

Красота! Хотя в последнем случае, для последнего ядра, последний пароль немного неверен. Это потому что кол-во паролей не всегда делится нацело на кол-во ядер.

То, что мы делаем, еще называется mixed radix. Это позиционные системы записи чисел, где у каждой цифры база может не подчиняться никакой системе (как в десятичной записи). Популярный пример - время в формате 24-часов. Первое число в пределах 0..23, второе и третье - 0..59. А еще могут быть миллисекунды: 0..999. А еще может быть дата - число/месяц/год.

В нашем случае, мы записываем число в виде пароля, кодируя его используя mixed radix. Т.е., пароль на выходе, это тоже число, просто записанное в другой системе счисления. Т.е., мы просто конвертируем числа из одной системы счисления в другую.

Ну а если кому-то захочется применить всё это на практике, не нужно забывать, что операция вычисления остатка от деления - тяжелая. Наверное, на практике, так можно только находить начальный пароль для каждого ядра, а затем, во время самого перебора, просто инкрементировать символы по очереди, так будет быстрее.

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.