Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник
Коллекция курьезных вопросов из форумов
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »
Страницы: 1 2 3

Распределенный брутфорс


Inovet ©   (09.09.20 00:40[40]

> [39] cryptologic ©   (08.09.20 22:55)

Я не в курсе.
Не пробовал.


monolife ©   (09.09.20 04:07[41]

> cryptologic ©   (06.09.20 22:24) [37]
> ... Так, что имейте ввиду, что бывших не бывает..

типа, "Знакомство с Факерами" ))


cryptologic ©   (21.09.20 19:35[42]

И так подошел ближе к теоретическому аспекту задачи

Ключ размером в 16 byte = 340282366920938463463374607431768211456 (39) комбинаций
Ясное дело, что такое количество комбинаций одному процессору не под силу и эту задачу можно разбивать на шары.
Разделение на шары позволит брутфорс проходить не линейно т.е. если все шары записать в список или в БД то их можно выполнять в случайном порядке ( random() )

И вот я определил размеры шар определенных размеров и разделил весь диапазон на эти шары и получал сколько потребуется шар  
размер шары 2 byte = 65536 (5) количество шар = 5192296858534827628530496329220096 (34) ни одна БД не вмещает столько записей
размер шары 4 byte = 4294967296 (10) количество шар = 79228162514264337593543950336 (29) ни одна БД не вмещает столько записей
размер шары 6 byte = 281474976710656 (15) количество шар = 1208925819614629174706176 (25) ни одна БД не вмещает столько записей
размер шары 8 byte = 18446744073709551616 (20) количество шар = 18446744073709551616 (20) ни одна БД не вмещает столько записей
размер шары 10 byte = 1208925819614629174706176 (25) количество шар = 281474976710656 (15) ни одна БД не вмещает столько записей
размер шары 11 byte = 309485009821345068724781056 (27) количество шар = 1099511627776 (13)
размер шары 12 byte = 79228162514264337593543950336 (29) количество шар = 4294967296 (10)
размер шары 13 byte = 20282409603651670423947251286016 (32) количество шар = 16777216 (8)
размер шары 14 byte = 5192296858534827628530496329220096 (34) количество шар = 65536 (5)

И тут вылазят 2 неприятные проблемы,
1. что если шара мала или достаточная для решения хотя бы на одном процессоре, то их общее количество такое огромное, что не влезут не в одну БД т.е. не хватит количество записей БД,
2. Если шары сделать более большими, что бы их общее количество уже можно было бы записать в БД, то тогда шары получаются "великими" и ее решение на одном процессоре можно никогда не дождаться.

Отсюда следует, что такой огромный ключ не возможно брутить рандомно, хотя такой метод наверное более эффективен чем линейное прохождение

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

Как то так. Если у кого есть особое мнение, то можете пивать сюда.


Inovet ©   (22.09.20 00:50[43]

Смысл в рандомности? Чёт мне кажется разницы никакаой в сравнении с линейностью. Ну и да, достаточно хранить диапазоны уже рассмотренных ключей, они будут рваться, но постепенно объединятся.


cryptologic ©   (24.09.20 09:19[44]


> Inovet ©   (22.09.20 00:50) [43]
> Смысл в рандомности?


А смысл в том, что ключ более вероятнее найдешь, чем при линейном прохождении.
Например, х- это решение ключа и решение ключа лежит в середине 000000Х0000000 диапазона или вообще ближе к концу  диапазона 0Х000000000000, и например, чтобы хотя бы до середины диапазона добраться, потребуются месяцы, а рандомный способ позволяет сделать тоже количество, т.е. можно потратить те же месяцы, но есть вероятность случайно найти решение, по случайному обстоятельству может выпасть та самая шара в которой находится решение.


Inovet ©   (24.09.20 09:26[45]

> [44] cryptologic ©   (24.09.20 09:19)

Ты протьиворечишь сам себе. Говоришь случайное, но в то же время предопределённое. Нет никакой разницы в каком порядке перебирать варианты, если в ключе нет некоторой закономерности, а её не должно быть иначе это плохой алгоритм генерации последовательностей и 128 (или сколько их там) бит реально имеют меньшую мощность.


cryptologic ©   (24.09.20 09:39[46]


> cryptologic ©   (21.09.20 19:35) [42]



> размер шары 2 byte = 65536 (5) количество шар = 5192296858534827628530496329220096
> (34) ни одна БД не вмещает столько записей


Посмотрел технические характеристики MS SQL сервера и оказалось что вмещает согласно на спецификации https://docs.microsoft.com/ru-ru/sql/sql-server/maximum-capacity-specifications-for-sql-server?view=sql-server-ver15 индексный ключ может быть до 900 байт

а это значение будет равно 900= 7200 bit  соответственно 2^7200 =
26059662129249685387376387004434371037157945606729517772442936762276378682786 74702501095879893118314353040942929989072872515085709507783258196584722803109563 42974007014525969591280499428602593250384675135136622307675917177004209127097482 47315464182057123680676384940331361299678856240930663284688250797033074034112606 46167499909654506111999652710351941177890031254934159811711186073879463518677901 11092081991887656787508578732742450859462458623087315404584549719525189734544764 49762164758633118302227738557845547767994339626696802634936326170734660886023469 63063011080542418876414202573469203038914326771485750333341789171809712145596298 93967858016332659950055473026300538062448415564363986847143599465279454445526844 65375721531656839826762041187734447628600810346701525329659841489857842707411353 19451522659654938468003782602658017316001711940483124398582743330277819783481234 83783159280209215091265680529639399286727347900939244864271688676881438906174918 89751419842709404977830817750378677443038246349160531531154672529523163491541824 40772508936189726720262293805208127083752328031643922005962504483913638198555278 23229764943916281370088902902976017756910096247837537282425684157558246670321156 87017139030150837487530941611840926077926163891233272703210170140139190595211852 74135631128908807708348360734018287183256174751752651511110634420613027356394663 94412440724675200061118404396645974589881244747851476279860784955301315469747722 72757864576548099637241899138016900371681147638570434004824448707028598503486731 41117984261702546890272213728411275237574597028239885280026509761902977495688491 12115986750943909174229460025883992139109268116522806117556732354540823583604216 12001338273030001605128962913994003040962033674878311533572356065480428882191636 22309110484379531414985006800012844337550176971639494651038308917004259511739125 18073056641999904114637806054034820860434009916707997873282230817974274014317183 31724324364346576012662166181134222831740687276898817211801905622426553571343908 65477094217825615634802372115784516981509730402764788361006853333135509972021491 63021375578335451299882869725565822102266384773894543671680219286679745566107933 83842021376 (2168)   = записей  в БД


cryptologic ©   (24.09.20 10:03[47]


> Inovet ©   (24.09.20 09:26) [45]
> > [44] cryptologic ©   (24.09.20 09:19)
>
> Ты протьиворечишь сам себе. Говоришь случайное, но в то
> же время предопределённое. Нет никакой разницы в каком порядке
> перебирать варианты, если в ключе нет некоторой закономерности,
>  а её не должно быть иначе это плохой алгоритм генерации
> последовательностей и 128 (или сколько их там) бит реально
> имеют меньшую мощность.


Ни фига не понял из того, что ты сказал, а можно более поподробнее?


Inovet ©   (24.09.20 10:09[48]

> [47] cryptologic ©   (24.09.20 10:03)

Подробнее - нет разницы последовательно или случайно, если нет багов в алгоритме генерации ключа.


cryptologic ©   (24.09.20 10:11[49]


> Inovet ©   (24.09.20 09:26) [45]


Давай проведем теоретический эксперимент.  Я создам алгоритм поиска числа от 0 до 100
искомое число разместим случайно в этом диапазоне, и будем перебирать рандомно все числа, пока не найдем нужное число, после каждой попытке будем вычеркивать вариант неудачного числа, можем даже удалять из массива, что бы массив чисел сокращался.
И посмотрим каким алгоритмом будет найдено быстрее линейным или рандомным?
Кстати эксперимент внесет ясность на все недоразумения.


Inovet ©   (24.09.20 10:16[50]

> [49] cryptologic ©   (24.09.20 10:11)

Да по определению случайного и будет одинаково. Какой ещё эксперимент нужен. Попадание с вероятностью 1/100, потом 1/99 и т.д. до 1/1.


cryptologic ©   (24.09.20 10:20[51]


> cryptologic ©   (24.09.20 10:11) [49]

Конечно же линейный поиск будет успешным, если число находится в начале, но а если в конце?
Вообще я думаю, что лучший вариант поиска числа это гибридный поиск, например, чередовать все нечетные значения счетчика операций выполняют линейный поиск, а все четные выполняют рандомной поиск.

А потом, можно сравнить каждый алгоритм по отдельности, и определить который будет быстрее


cryptologic ©   (24.09.20 10:22[52]


> Inovet ©   (24.09.20 10:16) [50]
> > [49] cryptologic ©   (24.09.20 10:11)
>
> Да по определению случайного и будет одинаково. Какой ещё
> эксперимент нужен. Попадание с вероятностью 1/100, потом
> 1/99 и т.д. до 1/1.


Тут идея в чем, чтобы за меньшее количество интераций найти нужное число.


Inovet ©   (24.09.20 10:29[53]

Не понимаешь если, возьми да проверь. Программа за 5 минут пишется. Генератор псевдослучайных чисел, конечто псевдо, но я думаю годится. Но можешь поимать аппаратные случайные числа, если хочешь, на новых процессорах есть, на чипсетах тоже есть.


Inovet ©   (24.09.20 10:47[54]

И получится у тебя, что в среднем надо будет перебрать половину значений, и неважно последовательно или рандомно.


cryptologic ©   (24.09.20 13:21[55]


> Inovet ©   (24.09.20 10:47) [54]


Но все же я все равно пересчитал

procedure TFrmMain.sButton2Click(Sender: TObject);
var i,J: SmallInt;
   c: SmallInt;
   x: SmallInt;  // искомое число
   cnt, cnt_find: SmallInt;

   st: TStrings;
begin

 st := TStringList.Create;

 cnt_find := 0;

 for i := 1 to 100 do
 begin
   st.Clear;
   for j:= 1 to 100 do st.Add(IntToStr(j)); // заполняю список числами

   Randomize;
    x  := RandomRange(50, 100 +1); // случайное число которое нужно найти
   cnt := 0;

   while st.Count > 0 do
   begin
    Application.ProcessMessages;
    Inc(cnt);

    {
    if (cnt mod 2) = 0 then
    begin
     // четное знасение счетчика
     Randomize;
     c := RandomRange(0, st.Count);
    end
    else
    begin
      // нечетное значение счетчика
     c := 0;
    end;
    }

    Randomize;
    c := RandomRange(0, st.Count);

    // mm.Lines.Add('счетчик = ' + IntToStr(cnt) + ' случайное число = ' + IntToStr(c));

    if st.Strings[c] = IntToStr(x) then
      Break
    else
     st.Delete(c);

   end;

   if cnt < x then Inc(cnt_find); //
   mm.Lines.Add(IntToStr(i) + ' Количество попыток = ' + IntToStr(cnt) + ' искомое число = ' + IntToStr(x));

  end;

 mm.Lines.Add('Когда рандомный метод нашел количество = ' + IntToStr(cnt_find) + ' против 100');

end;


Рандомный метод в все-таки работает в большинстве случаев только в тех случаях, где искомое число лежит от 50% диапазона и выше
Вот табличка результатов:

1 Количество попыток = 80 искомое число = 84
2 Количество попыток = 100 искомое число = 95
3 Количество попыток = 38 искомое число = 86
4 Количество попыток = 9 искомое число = 84
5 Количество попыток = 98 искомое число = 80
6 Количество попыток = 38 искомое число = 63
7 Количество попыток = 29 искомое число = 61
8 Количество попыток = 33 искомое число = 86
9 Количество попыток = 12 искомое число = 57
10 Количество попыток = 63 искомое число = 72
11 Количество попыток = 64 искомое число = 78
12 Количество попыток = 66 искомое число = 91
13 Количество попыток = 50 искомое число = 98
14 Количество попыток = 73 искомое число = 76
15 Количество попыток = 18 искомое число = 75
16 Количество попыток = 60 искомое число = 88
17 Количество попыток = 46 искомое число = 58
18 Количество попыток = 53 искомое число = 92
19 Количество попыток = 73 искомое число = 79
20 Количество попыток = 97 искомое число = 55
21 Количество попыток = 70 искомое число = 77
22 Количество попыток = 28 искомое число = 63
23 Количество попыток = 35 искомое число = 74
24 Количество попыток = 30 искомое число = 78
25 Количество попыток = 72 искомое число = 89
26 Количество попыток = 99 искомое число = 61
27 Количество попыток = 85 искомое число = 96
28 Количество попыток = 24 искомое число = 51
29 Количество попыток = 38 искомое число = 69
30 Количество попыток = 48 искомое число = 87
31 Количество попыток = 33 искомое число = 93
32 Количество попыток = 33 искомое число = 89
33 Количество попыток = 60 искомое число = 55
34 Количество попыток = 91 искомое число = 57
35 Количество попыток = 94 искомое число = 61
36 Количество попыток = 98 искомое число = 79
37 Количество попыток = 80 искомое число = 94
38 Количество попыток = 64 искомое число = 56
39 Количество попыток = 58 искомое число = 83
40 Количество попыток = 25 искомое число = 59
41 Количество попыток = 61 искомое число = 57
42 Количество попыток = 94 искомое число = 58
43 Количество попыток = 72 искомое число = 93
44 Количество попыток = 74 искомое число = 58
45 Количество попыток = 52 искомое число = 69
46 Количество попыток = 22 искомое число = 94
47 Количество попыток = 99 искомое число = 98
48 Количество попыток = 76 искомое число = 80
49 Количество попыток = 16 искомое число = 71
50 Количество попыток = 41 искомое число = 64
51 Количество попыток = 9 искомое число = 63
52 Количество попыток = 53 искомое число = 68
53 Количество попыток = 87 искомое число = 78
54 Количество попыток = 32 искомое число = 68
55 Количество попыток = 24 искомое число = 50
56 Количество попыток = 75 искомое число = 100
57 Количество попыток = 83 искомое число = 87
58 Количество попыток = 27 искомое число = 60
59 Количество попыток = 83 искомое число = 76
60 Количество попыток = 73 искомое число = 64
61 Количество попыток = 60 искомое число = 87
62 Количество попыток = 10 искомое число = 64
63 Количество попыток = 91 искомое число = 71
64 Количество попыток = 69 искомое число = 50
65 Количество попыток = 62 искомое число = 67
66 Количество попыток = 88 искомое число = 91
67 Количество попыток = 2 искомое число = 52
68 Количество попыток = 75 искомое число = 84
69 Количество попыток = 53 искомое число = 69
70 Количество попыток = 18 искомое число = 89
71 Количество попыток = 92 искомое число = 69
72 Количество попыток = 89 искомое число = 53
73 Количество попыток = 3 искомое число = 86
74 Количество попыток = 19 искомое число = 75
75 Количество попыток = 13 искомое число = 92
76 Количество попыток = 5 искомое число = 67
77 Количество попыток = 69 искомое число = 89
78 Количество попыток = 73 искомое число = 52
79 Количество попыток = 17 искомое число = 50
80 Количество попыток = 80 искомое число = 95
81 Количество попыток = 97 искомое число = 52
82 Количество попыток = 23 искомое число = 85
83 Количество попыток = 44 искомое число = 96
84 Количество попыток = 23 искомое число = 94
85 Количество попыток = 15 искомое число = 51
86 Количество попыток = 32 искомое число = 80
87 Количество попыток = 77 искомое число = 66
88 Количество попыток = 61 искомое число = 82
89 Количество попыток = 80 искомое число = 53
90 Количество попыток = 97 искомое число = 71
91 Количество попыток = 56 искомое число = 88
92 Количество попыток = 46 искомое число = 84
93 Количество попыток = 27 искомое число = 65
94 Количество попыток = 15 искомое число = 70
95 Количество попыток = 82 искомое число = 74
96 Количество попыток = 6 искомое число = 60
97 Количество попыток = 49 искомое число = 91
98 Количество попыток = 97 искомое число = 73
99 Количество попыток = 54 искомое число = 52
100 Количество попыток = 32 искомое число = 54
Когда рандомный метод нашел количество = 72 против 100


cryptologic ©   (24.09.20 13:27[56]

тестировал 100 раз и каждый раз искомое число генерировалось x  := RandomRange(50, 100 +1);

получилось рандомный метод нашел = 72  из 100
и так раз несколько пробовал тесты и получается почти вседа положительный результат около 70%


cryptologic ©   (24.09.20 13:37[57]

Inovet ©  -  в общем то ты прав рандомный метод себя не оправдывает так как само искомое число это и есть рандом, не никакой гарантии, что оно будет лежать в "удобном" диапазоне.


cryptologic ©   (24.09.20 13:43[58]

Лучший вариант потратить время на оптимизацию самого алгоритма хэша ключа т.е. написать его на ассемблере


Страницы: 1 2 3 версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо