Распределенный перебор паролей Захаров Александр aka ZaCo -- В продолжение статьи <Циклический инкремент паролей> хотелось бы затронуть тему распределения диапазонов паролей из заданного множества символов. Во время развития распределения мощностей между различными машинами задача является наиболее актуальной, например, описанный ниже метод уже был применен в системе распределенного перебора BruteNet. Применяемый язык C++. Назовем заданное множество символов, на котором ведется перебор, charset. На уровне программы это будет обычный массив байт (будем считать для ясности, что любой символ можно представить в одном байте), таким образом, если перебор ведется на множестве 'abc', то: Code: charset[]='abc'; На момент описания внутреннего представления каждой строки мы можем абстрагироваться от ее непосредственного представления, храня каждую строку как набор позиций, начиная с единицы, текущего символа в массиве charset. Такое представление действительно является удобным: строка 'bab', хранимая в виде '\x02\x01\x02' дает возможность перейти к следующей допустимой строке 'bac' простой инкрементацией последнего байта. Примем очевидным факт того, что начиная со строки 'a' и переходя подобным образом к следующей строке мы обойдем последовательно все участвующее в переборе строки. Такое поведение наталкивает на мысль о <численно-подобном> поведении строк. Действительно, прибавление единицы почти в точности выполняется по правилам сложения столбиком, однако при переходе за предел длины charset мы ставим текущий символ не в ноль, а в единицу, делая перенос на разряд влево. Таким образом, следующая строка после 'bac' будет 'bba'. Если бы мы научились выполнять арифметические операции на такими <числами> нам бы, очевидно, не составило бы и труда выполнить изначальную задачу деления диапазона. Но это и не представляется проблемой, ведь тема длинной целочисленной арифметики в пределах нашей задачи не является трудоемкой. Итак, установив связь между строками и числами нам остается только понять как их хранить в виде непосредственно чисел; параллельно возникает и обратная задача - преобразование числа в строку. Длинная арифметика и деление диапазона Заметим, что отображение каждой строки на множество целых чисел больше нуля является взаимно-однозначным, более того будем считать значением строки abc...def длинной n число равное: f+e*power+d*power^2+...+c*power^(n-3)+b*power^(n-2)+a*power^(n-1) Причем очевидно, что каждый символ строки принимает значение из диапазона [1..power], где power - количество символов в charset. Будем считать power степенью системы исчисления нашей арифметики. Для того чтобы строка была корректной для привычных операций столбиком, необходимо, ее изменить так, чтобы соответствующее ей число не поменяло значения и каждый символ находился в промежутке от [0..power-1]. Для этого достаточно пройтись по строке в цикле с младшего разряда к большему и, если, текущее значение больше либо равно power вычесть power и прибавить единицу к следующему разряду. Затроним момент реализации. Для простоты будем считать, что количество символов лежит в константе PASS_SIZE: Code: BYTE power; BYTE word[PASS_SIZE]; Массив word будет хранить в себе число с которым мы и будем проводить все арифметические операции. В итоге функция преобразующая строку в необходимый нам вид будет выглядить так: Code: ariphmetic ariphmetic::operator=(char * rhs) { memset(word,0,PASS_SIZE); memcpy(&word[PASS_SIZE-strlen(rhs)],rhs,strlen(rhs)); for(i=PASS_SIZE-1;word[i]>0;i--) if(word[i]>=power) { word[i]-=power; word[i-1]++; } } где rhs - наша строка. Обратная операция - вывод числа из нашей арифметики в строку: Code: int ariphmetic::ToWord(char * result) { int i,v; char buff[PASS_SIZE]; memcpy(buff,word,PASS_SIZE); for(j=0;( (j<PASS_SIZE) && (buff[j]==0));j++); if(j==PASS_SIZE) return 0; v=0; for(i=PASS_SIZE-1;i>j;i--) { int c=buff[i]+v; buff[i]=c; if(c<=0) { buff[i]+=power; v=-1; } else { v=0; } } buff[i]+=v; if(buff[i]==0) { j++; } memcpy(result,&buff[j],(PASS_SIZE-j)); } Сначала мы определяем с какой позиции в массиве начинается слово и заносим это значение в переменную j. Далее проделываем в цикле операцию обратную той, что использовалось в предыдущей функции: если текущая элемент меньше или равен нулю, прибавляем к нему power и вычитаем единицу из следующего разряда. Предположим нам нужно узнать какая строка будет, к примеру, через 5 000 000 инкрементаций. Благодаря настоящим выкладкам это можно сделать естественнее и быстрее чем циклом и сложением с единицей на каждом итерационном шаге. Ответ на задачу о представлении целого числа в нашей арифметике поможет в дальнейшем в разделении диапазона перебора на равное количество частей. Здесь все очень просто: Code: void ariphmetic::Dec2Word(unsigned int rhs) { memset(&word[0],0,PASS_SIZE); int i=PASS_SIZE-1; do { if(i==0) break; word[i--]=rhs%power; rhs=rhs/power; } while(rhs>0); } Нет смысла приводить в данном контексте алгоритм деления или умножения двух чисел, потому как это скорее тема длинной арифметики, я приведу лишь пример сложения двух таких чисел: Code: void ariphmetic::Add(const ariphmetic & rhs) { int i; int sum,v=0; for(i=PASS_SIZE-1;i>0;i--) { sum=word[i]+rhs.word[i]+v; if(sum<power) { word[i]=sum; v=0; } else { word[i]=sum-power; v=1; } } } } После реализации всех необходимых арифметических операций, код распределения диапазона на N частей будет выглядить так: Code: void ReDistribute(const ariphmetic & first, const ariphmetic & last) { int i; ariphmetic temp; temp=(last-first)/(N); for(i=0;i<N-1;i++) { cl[i]->first=temp*i+first; cl[i]->last=cl[i]->first+temp-1; } cl[i]->first=temp*i+first; cl[i]->last=last; }; где, cl - массив частей, last, first - соответственно нижняя и верхнии границы диапазона. Перед вызовом необходимо указать границы: Code: first='\x01'; last='\x03\x03\x03'; Заключение Хотелось бы отметить действительную привлекательность предложенного метода, который, при должной реализации, является не сколько быстрым и удобным, сколько универсальным. Затронутая и применяемая тема длинной арифметики описана мной в заметке <Длинная и быстрая арифметика>. Полноценную же библиотеку для языка C++, входящую в состав проекта BruteNet, можно скачать с моего сайта. Все мысли, идеи и пожелания можете отправить на zaco@yandex.ru или http://zaco.itdefence.ru.
На мой взгляд вся задача распределения диапазонов паролей из заданного множества символов сводится к: 1. Приведение строки в вид b-ричной позиционной системы счисления. 2. Перевод в любую удобную систему для вычислений (операции -,+,/) например десятичная, шестнадцатиричная. 3. Собственно проведение операций деления полного диапазона на подмножества. 4. Обратное преобразование в строку в момент подбора (запись в виде b-ричной позиционной системы - это и есть пароль) Вот например имеем пасс из трёх символов 'aZ/' в charsete[]=mixalpha-numeric-all-space, тогда основание b-ричной системы равно 95 (число возможных символов чарсета) Тогда: a(95)=0(10) b(95) = 1(10) c(95) = 2(10) ------------------- --пропущено-- ------------------- _(95) = 94(10) "_" - обозначил пробел, так как он последний в чарсете. (для удобства отображения можно пробел поставить в начало чарсета и сделать, чтоб он, а не 'a' соответствовал '0' в десятичной системе, но оставим пока как есть). Наш пароль: aZ/(95)=0*95^2+31*95^1+93*95^0=3038(10) Итак, например у нас диапазон [aaa-___], чарсет mixalpha-numeric-all-space т.е. фактически 95-ричная позиционная система исчисления. charset[]=mixalpha-numeric-all-space = [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/ ] Переводим его в десятичную систему: aaa(95)=0(10) ___(95)=94*95^2+94*95^1+94*95^0=94*9025+8930+94=848350+8930+94=857374 - самое наибольшее число в дясятичной системе, соответствующее пассу из 3-х пробелов. Проверим, что нам говорит Winrtgen-> он говорит, что всего возможно 866495 ключей (паролей). Кто из нас ошибся? Похоже, что я, так как отсутствие какого либо символа в пароле это тоже результат имеющий значение, т. е. множестово одно и двух символьных паролей тоже учитывается в Winrtgen, тогда и мы исправим ошибку: ___(95)=95*95^2+95*95^1+95*95^0=866495 и получим результат, который сообщает Winrtgen. И так мы получили: полное множество [пусто-___] -> [0-866495] и [aaa-'три пробела'] -> [0-857374] - теперь можно дробить на поддиапазоны, например разбить на два второй диапазон: 857374/2=428687 Затем остаётся перевести обратно в 95-ричную систему и можно использовать для подбора паролей. ЗЫ Написал почти тоже самое ,что и Zaco, только щас заметил, заисключением того, что как я понял, все арифметические операции Zaco предлагает проводить в b-ричной системе счисления, вообщем смысл ясен...
>>все арифметические операции Zaco предлагает проводить в b-ричной системе счисления, вообщем смысл ясен... в 10-ой системе проводить операции крайне бессмысленно и что более важно расточительно в плане памяти и скорости.
прально. нех из системы в систему переводить... сам когдато на олимпиаде решал похожую проблемку. я двоичным делением к-ричной системы делал. приближение хорошее выходит, главное быстро.