Полный двоичный перебор и его ускорение путем отсечения заведомо неподходящих вариантов

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию Российской федерации

Вологодский государственный университет

Кафедра АВТ

КУРСОВАЯ РАБОТА

по дисциплине «Построение и анализ алгоритмов»

по теме «Полный двоичный перебор и его ускорение путем отсечения заведомо неподходящих вариантов»

Выполнил студент группы ЭПО-11

Богданов Д.И.

Принял: Андрианов И.А.

Вологда

2018



1. Описание заданной структуры данных или алгоритма

1.1 Историческая справка

Полный двоичный перебор, как метод решения задач, появился одним из первых, так как требовал лишь в качестве ресурса лишь время. За всю историю было немало инцидентов связанных с этим алгоритмом. В числе которых: алгоритм программное обеспечение интерфейс

Атака «Энигмы»

Изобретённая в 1918 году шифровальная машина, названная «Энигма», широко использовалось немецким военно-морским флотом начиная с 1929 года. В течение дальнейших нескольких лет система модифицировалась, а с 1930 года активно использовалась немецкой армией и правительством в процессе Второй мировой войны[.

Первые перехваты сообщений, зашифрованных с кодом Энигмы, относятся к 1926 году. Однако прочитать сообщения долгое время не могли. На протяжении всей Второй мировой шло противостояние между польскими и германскими криптографами. Поляки, получая очередной результат по взлому немецкой криптосистемы, сталкивались с новыми трудностями, которые привносили германские инженеры, постоянно модернизирующие систему «Энигма». Летом 1939 года, когда неизбежность вторжения в Польшу стала очевидна, бюро передало результаты своей работы английской и французской разведкам.

Дальнейшая работа по взлому была организована в Блетчли-парке. Основным инструментом криптоаналитиков стала дешифровальная машина «Бомба». Её прототип был создан польскими математиками накануне Второй мировой войны для министерства обороны Польши. На основе этой разработки и при непосредственной поддержке её создателей в Англии был сконструирован более «продвинутый» агрегат.

Теоретическую часть работы выполнил Алан Матисон Тьюринг. Его работы по криптографическому анализу алгоритма, реализованного в шифровальной машине «Энигма», основывался на более раннем криптоанализе предыдущих версий этой машины, которые были выполнены в 1938 году польским криптоаналитиком МарианомРеевским. Принцип работы разработанного Тьюрингом дешифратора состоял в переборе возможных вариантов ключа шифра и попыток расшифровки текста, если была известна структура дешифруемого сообщения или часть открытого текста.

С современной точки зрения шифр «Энигмы» был не очень надёжным, но только сочетание этого фактора с наличием множества перехваченных сообщений, кодовых книг, донесений разведки, результатов усилий военных и даже террористических атак позволило «вскрыть» шифр.

После войны Черчилль, из соображений безопасности, приказал разрушить эти машины.

Уязвимость протокола WPS

В 2007 году группа компаний, входящих в организацию Wi-FiAlliance, начали продажу беспроводного оборудования для домашних сетей с поддержкой нового стандарта Wi-FiProtectedSetup. Среди производителей беспроводных маршрутизаторов, поддерживающих данную технологию, были такие крупные компании, как Cisco/Linksys, Netgear, Belkin и D-Link. Стандарт WPS был призван существенно упростить процесс настройки беспроводной сети и её использования для людей, не обладающих широкими знаниями в области сетевой безопасности. Однако, к концу 2011 года были опубликованы сведения о серьезных уязвимостях в WPS, которые позволяли злоумышленнику подобрать PIN-код беспроводной сети всего за несколько часов, обладая вычислительными ресурсами обыкновенного персонального компьютера.

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

Массовый взлом домашних сетей посредством WASP

В 2010 году на конференции DEFCON18 был представлен беспилотный летательный аппарат WASP, предназначенный для массового сбора статистики по домашним Wi-Fi сетям. БПЛА оснащён компактным бортовым компьютером под управлением BackTrackLinux, Одной из его функций называлась возможность автоматического взлома паролей беспроводных сетей посредством bruteforce.

1.2 Описание работы алгоритма

К алгоритмам полного перебора обращаются тогда, когда нет других способов решить определенную задачу. Например, никому в голову не придет решать квадратное уравнение перебором всех возможных значений, даже если известно, что решением являются целые числа. Полный перебор - это решение “в лоб”, построенное на подстановке и проверке всех возможных вариантов из области допустимых значений. На словах в решении задачи полного перебора нет ничего сложного, но на деле алгоритмы, которые действительно ищут и находят решения подобным способом за “приемлемое время” довольно таки непростые. К наиболее популярным задачам, решение которых методом полного перебора рассматривают в школах и ВУЗах (в рамках дисциплин, связанных с комбинаторикой и программированием) можно отнести заполнение прямоугольной области фигурками из тетриса, поиск выхода из лабиринта, задачу о рюкзаке, поиск связанных областей и т.п. Многие задачи на графах также можно решать с помощью полного перебора, хотя для их решения придуманы специальные методики - оптимальные с точки зрения количества операций алгоритмы, которые осуществляют поиск решений на порядки быстрее, чем обычный полный перебор. К таким задачам относят поиск кратчайшего маршрута между вершинами (алгоритм Дейкстры) или поиск максимального пропускного потока в графе. Если обобщить все вышесказанное, то для решения некоторой задачи методом полного перебора нужно разработать алгоритм перебора всех возможных кандидатов на решение и реализовать процедуру проверки корректности решения для каждого из них.Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлено за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими.В частности, по отношению к нашей задаче относится следующий специализированный алгоритм перебора:

Для представления подмножеств создадим массив a из N элементов, где a[i]=1, если i-й элемент входит в текущее подмножество, и 0 - если нет. Заметим, что массив a можно рассматривать как запись некоторого N-разрядного двоичного числа, где элемент a[i] содержит значение его i-го разряда. При этом каждому подмножеству из N элементов однозначно соответствует некоторое N-разрядное двоичное число. Получив последовательно в массиве a записи всех N-разрядных двоичных чисел, мы тем самым переберём все подмножества.

Будем получать числа в порядке возрастания. Для того, чтобы перейти от предыдущего числа к следующему, необходимо прибавить к нему единицу. В случае двоичной записи это делается следующим образом. Движемся от младших разрядов к старшим, пока все они равняются единице, и присваиваем им значение 0. Дойдя до первого нуля, присваиваем ему значение 1. Например, при прибавлении 1 к числу 010010111 получится число 010011000.

1.3 Класс входных данных, для которых применим алгоритм или структура

В данный класс входят, как правило, численные входные данные.

1.4 Анализ временной сложности алгоритма

В самом плохом варианте сложность алгоритма равна2^n.

1.5 Примеры практических задач, где может использоваться данный алгоритм

В криптографии на полном переборе основывается криптографическая атака методом «грубой силы». Её особенностью является возможность применения против любого практически используемого шифра. Однако такая возможность существует лишь теоретически, зачастую требуя нереалистичные временные и ресурсные затраты. Наиболее оправдано использование атаки методом «грубой силы» в тех случаях, когда не удается найти слабых мест в системе шифрования, подвергаемой атаке (либо в рассматриваемой системе шифрования слабых мест не существует). При обнаружении таких недостатков разрабатываются методики криптоанализа, основанные на их особенностях, что способствует упрощению взлома.

Устойчивость к brute-force атаке определяет используемый в криптосистеме ключ шифрования. Так, с увеличением длины ключа сложность взлома этим методом возрастает экспоненциально. В простейшем случае шифр длиной в N битов взламывается, в наихудшем случае, за время, пропорциональное 2^N. Среднее время взлома в этом случае в два раза меньше и составляет 2^N-1. Существуют способы повышения устойчивости шифра к «bruteforce», например, запутывание (обфускация) шифруемых данных, что делает нетривиальным отличие зашифрованных данных от незашифрованных.



2. Разработка визуализатора

Непосредственная задача:

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

2.1 Выбор средств разработки

В качестве средства разработки был выбран IDELazarus.

2.2 Определение отображаемых элементов, проектирование интерфейса

Программа внешне состоит из окнаTForm с расположенными в нем несколькими объектами TEdit, TMemo, TButton, Tlabel.

Форма программы



2.3 Программная реализация, листинг

Код программы состоит из нескольких процедур, четыре из которых привязаны к четырем объектам типа Button.Для начала рассмотрим функцию, выполняемую при формировании непосредственно самого окна.

Листингprocedure TForm1.FormCreate(Sender: TObject)

var

i:integer;

begin

for i:=1 to 10 do begin

b[i]:=0;

end;

Edit11.Color:=clLime;

Edit12.Color:=clAqua;

При создании окна происходит заполнение бинарного массива нулями.

Далее рассмотрим процедуру,связанную с объектом типа Button, имеющую название в окне «Сформировать».

Листингprocedure TForm1.Button1Click(Sender: TObject)

var

i:integer;

begin

randomize;

for i:=1 to 10 do begin

b[i]:=0;

end;

if b[1]=0 then Edit1.Color:=clWhite;

if b[2]=0 then Edit2.Color:=clWhite;

if b[3]=0 then Edit3.Color:=clWhite;

if b[4]=0 then Edit4.Color:=clWhite;

if b[5]=0 then Edit5.Color:=clWhite;

if b[6]=0 then Edit6.Color:=clWhite;

if b[7]=0 then Edit7.Color:=clWhite;

if b[8]=0 then Edit8.Color:=clWhite;

if b[9]=0 then Edit9.Color:=clWhite;

if b[10]=0 then Edit10.Color:=clWhite;

for i:=1 to 10 do begin

a[i]:=random(10)+1;

end;

Edit1.Text:=FloatToStr(a[1]);

Edit2.Text:=FloatToStr(a[2]);

Edit3.Text:=FloatToStr(a[3]);

Edit4.Text:=FloatToStr(a[4]);

Edit5.Text:=FloatToStr(a[5]);

Edit6.Text:=FloatToStr(a[6]);

Edit7.Text:=FloatToStr(a[7]);

Edit8.Text:=FloatToStr(a[8]);

Edit9.Text:=FloatToStr(a[9]);

Edit10.Text:=FloatToStr(a[10]);

Memo1.Text:='Весасформированы';

end;

В данной процедуре выполняется заполнение рабочего массива случайными числами в пределах от 1 до 10 включительно.

Далее рассмотрим процедуру, связанную с объектом типа Button, имеющую название в окне «Ввести».

Листинг procedure TForm1.Button4Click(Sender: TObject)

var i:integer;

begin

for i:=1 to 10 do begin

b[i]:=0;

end;

if b[1]=0 then Edit1.Color:=clWhite;

if b[2]=0 then Edit2.Color:=clWhite;

if b[3]=0 then Edit3.Color:=clWhite;

if b[4]=0 then Edit4.Color:=clWhite;

if b[5]=0 then Edit5.Color:=clWhite;

if b[6]=0 then Edit6.Color:=clWhite;

if b[7]=0 then Edit7.Color:=clWhite;

if b[8]=0 then Edit8.Color:=clWhite;

if b[9]=0 then Edit9.Color:=clWhite;

if b[10]=0 then Edit10.Color:=clWhite;

a[1]:=StrToInt(Edit1.Text);

a[2]:=StrToInt(Edit2.Text);

a[3]:=StrToInt(Edit3.Text);

a[4]:=StrToInt(Edit4.Text);

a[5]:=StrToInt(Edit5.Text);

a[6]:=StrToInt(Edit6.Text);

a[7]:=StrToInt(Edit7.Text);

a[8]:=StrToInt(Edit8.Text);

a[9]:=StrToInt(Edit9.Text);

a[10]:=StrToInt(Edit10.Text);

Memo1.Text:='Весавведены';

end;

В данной процедуре пользователь вносит собственные данные в рабочий массив.

Далее подвергнем рассмотрению процедуру, связанную с объектом типа Button, имеющую название в окне «Авто».

Листинг procedure TForm1.Button2Click(Sender: TObject)

var

n, m, i, k0, k1, res: longint;

s:array[1..10]of byte;

begin

z:=StrToInt(Edit13.Text);

z:=z;

Memo1.Text:='Идет поиск ответа';

res := 100;

n:=10;

begin

repeat

for i := 1 to n do

begin

if b[i] = 0 then k0 := k0 + a[i]

else k1 := k1 + a[i];

end;

m := abs(k0 - k1);

if res > m then begin

res := m;

s:=b;

end;

k0 := 0;

k1 := 0;

until not NextSubset(b, n-z-1);

end;

Edit16.Text:=FloatToStr(res);

for i := 1 to n do

begin

if s[i] = 0 then k0 := k0 + a[i]

else k1 := k1 + a[i];

end;

Memo1.Text:='Найден конечный результат';

Edit15.Text:=FloatToStr(k0);

Edit14.Text:=FloatToStr(k1);

if s[1]=0 then Edit1.Color:=clLime

else Edit1.Color:=clAqua;

if s[2]=0 then Edit2.Color:=clLime

else Edit2.Color:=clAqua;

if s[3]=0 then Edit3.Color:=clLime

else Edit3.Color:=clAqua;

if s[4]=0 then Edit4.Color:=clLime

else Edit4.Color:=clAqua;

if s[5]=0 then Edit5.Color:=clLime

else Edit5.Color:=clAqua;

if s[6]=0 then Edit6.Color:=clLime

else Edit6.Color:=clAqua;

if s[7]=0 then Edit7.Color:=clLime

else Edit7.Color:=clAqua;

if s[8]=0 then Edit8.Color:=clLime

else Edit8.Color:=clAqua;

if s[9]=0 then Edit9.Color:=clLime

else Edit9.Color:=clAqua;

if s[10]=0 then Edit10.Color:=clLime

else Edit10.Color:=clAqua;

end;

Данная процедура выполняет поиск и вывод результата в автоматическом режиме.

Далее рассмотрим процедуру, связанную с объектом типа Button, имеющую название в окне «Шаг».

Листинг procedure TForm1.Button3Click(Sender: TObject)

var

n, m, i, k0, k1, res: longint;

s:array[1..10]of byte;

begin

z:=StrToInt(Edit13.Text);

z:=z+1;

Memo1.Text:='Идет поиск ответа';

k0 := 0;

k1 := 0;

res := 100;

n:=10;

for i := 1 to n do

begin

if b[i] = 0 then k0 := k0 + a[i]

else k1 := k1 + a[i];

end;

m := abs(k0 - k1);

if res > m then begin

res := m;

s:=b;

end;

begin

Edit16.Text:=FloatToStr(res);

Edit15.Text:=FloatToStr(k0);

Edit14.Text:=FloatToStr(k1);

if b[1]=0 then Edit1.Color:=clLime

else Edit1.Color:=clAqua;

if b[2]=0 then Edit2.Color:=clLime

else Edit2.Color:=clAqua;

if b[3]=0 then Edit3.Color:=clLime

else Edit3.Color:=clAqua;

if b[4]=0 then Edit4.Color:=clLime

else Edit4.Color:=clAqua;

if b[5]=0 then Edit5.Color:=clLime

else Edit5.Color:=clAqua;

if b[6]=0 then Edit6.Color:=clLime

else Edit6.Color:=clAqua;

if b[7]=0 then Edit7.Color:=clLime

else Edit7.Color:=clAqua;

if b[8]=0 then Edit8.Color:=clLime

else Edit8.Color:=clAqua;

if b[9]=0 then Edit9.Color:=clLime

else Edit9.Color:=clAqua;

if b[10]=0 then Edit10.Color:=clLime

else Edit10.Color:=clAqua;

end;

if res=0 then begin Memo1.Text:='Найденконечныйрезультат';

exit;

end;

k0 := 0;

k1 := 0;

NextSubset(b, n-z);

if NextSubset(b, n-z) then begin

Edit16.Text:=FloatToStr(res);

for i := 1 to n do

begin

if s[i] = 0 then k0 := k0 + a[i]

else k1 := k1 + a[i];

end;

Memo1.Text:='Найден конечный результат';

Edit15.Text:=FloatToStr(k0);

Edit14.Text:=FloatToStr(k1);

if s[1]=0 then Edit1.Color:=clLime

else Edit1.Color:=clAqua;

if s[2]=0 then Edit2.Color:=clLime

else Edit2.Color:=clAqua;

if s[3]=0 then Edit3.Color:=clLime

else Edit3.Color:=clAqua;

if s[4]=0 then Edit4.Color:=clLime

else Edit4.Color:=clAqua;

if s[5]=0 then Edit5.Color:=clLime

else Edit5.Color:=clAqua;

if s[6]=0 then Edit6.Color:=clLime

else Edit6.Color:=clAqua;

if s[7]=0 then Edit7.Color:=clLime

else Edit7.Color:=clAqua;

if s[8]=0 then Edit8.Color:=clLime

else Edit8.Color:=clAqua;

if s[9]=0 then Edit9.Color:=clLime

else Edit9.Color:=clAqua;

if s[10]=0 then Edit10.Color:=clLime

else Edit10.Color:=clAqua;

end;

end;

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

Далее рассмотрим функцию, которая изменяет бинарный массив, при каждом выполнении прибавляя единицу.

Листинг function NextSubset(var a: array of byte; n: integer): boolean

begin

while a[n] = 1 do

begin

a[n] := 0;

dec(n);

end;

if n < 1 then

NextSubset := false

else

begin

NextSubset := true;

a[n] := 1;

end;

end;

2.4 Методика и результаты тестирования ПО

Программа готовая к работе

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

Программа со сформированными значениями

Далее пользователь выбирает каким способом произвести поиск результата, в автоматическом или пошаговом режиме. Предположим, пользователь выбрал пошаговый и отсечением 2 камней.

Процесс пошагового выполнения с отсечением

В результате пошагового выполнения результат с нулевой разницей не был найден и был выведен результат с минимальной разницей.



Конечный результат



Заключение

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



Список использованной литературы:

1.Интернет-ресурс Wikipedia - https://ru.wikipedia.org/wiki/Полный_перебор#Атака_«Энигмы»;

2.Интернет-ресурс LMatrix - http://lmatrix.ru/news/theory/polnyjj-perebor_172.html;

3.А.В. Ахо, Д.Э.Хопкрофт, Д.Д.Ульман - Структуры данных и алгоритмы.

Размещено на Allbest.ru