Список использованных источников

2.

2. Анализ сложности алгоритма

Обозначим за K – мощность множества Alpfabet длина алфавита, L – максимальная длина искомого пароля, N – число возможных комбинаций.

Программа хранит алфавит Alphabet, хеш искомой строки и хеш текущей строки, а также временную строку для перебора комбинаций.

 

· K = |Alphabet|

·  - общее число возможных комбинаций.

 

2.1 Сложность по памяти

    Для данного алгоритма нам необходимо хранить алфавит размером K, индексный массив размером numcell, и временную строку размером L. Тогда сложность по памяти составит:

O(max(K) + L + |K|),

где max(K) — наибольший ASCII-код символа в алфавите.

2.2 Временная сложность

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

3. Выполнение работы

3.1 Задачи

В данной работе поставленной задачей было написание кода, с использованием стандарта MPI, реализующего алгоритм “Brute Force” хеш-функции MD5 максимально эффективно, а также, с хорошей масштабируемостью итоговой программы.

 

3.2 Работа программы

    Несколько основных аспектов:

1. На вход поступает “пароль” который будет преобразован в хеш-функцию для поиска коллизий по принципу Brute Force.

2. При расчетах каждый процесс обрабатывает строки с номерами rank + commsize * i, пока не будет найдено совпадения хешей.

 

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

    Каждый процесс, в соответствии со своим номером, определяет начальную комбинацию позиций символов перебираемого слова в алфавите и затем проверяет, чтобы начальная комбинация была корректной (для случая, когда commsize >= alphabetSize). Далее, на основе массива позиций символов в алфавите (numcell) каждый процесс формирует слово из символов, соответствующих позициям. После этого вычисляется хэш данного слова и сравнивается хэшем кодового слова. При совпадении, результат (найденная комбинация и ее хэш, а также время работы программы) выводится на экран, и процесс, в котором найдена коллизия завершает работу всей программы вызвав MPI_Abort. В противном случае перебор идет дальше. При достижении комбинации, которая является последней для текущей длины («zzz…zz»), длина инкрементируется и перебор начинается сначала, но для большей длины.

 

 

4. Практические измерения

4.1 Характеристики системы

        Вычислительные эксперименты выполнялись на высокопроизводительном кластере Jet со следующими характеристиками:

· Количество всех узлов: 18;

· Количество задействованных узлов: 8;

· Соединение между узлами: Gigabit Ethernet (1 ГиБ/с).

4.2 Результаты экспериментов

Коэффициент S_p(n) ускорения параллельной программы считается по формуле:

где T(n) – время выполнения последовательной программы при заданном размере n входных данных и T_p(n) – время выполнения параллельной программы на p процессорах при заданном размере n входных данных.

Эксперимент проводился на алфавите “abcdefghijklmnopqrstuvwxyz” с хеш-функцией слова ”zzzzz” и “zzzzzzz”

 

Таблица 4.2 – Результаты эксперимента

Количество процессов

Ускорение алгоритма со словом “zzzzz”, с

Ускорение алгоритма со словом

“zzzzzzz”, с

3,82303

2,94721

6,98412

7,40937

13,84628

15,40015

31,28631

29,65391

38,65012

39,54017

63,39564

62,76183

 

 

Рисунок 4.2.1 – График зависимости ускорения от числа процессов.

    На рисунке 4.2.1 показано, что с увеличением числа процессов увеличивается коэффициент ускорения примерно в P раз и, соответственно, скорость перебора коллизий.

5. ЗАКЛЮЧЕНИЕ

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

 

1. Message Passing Interface Forum. MPI: A Message-Passing Interface Standard Version 3.1 // University of Tennessee, Knoxville, Tennessee, 2015. - 868 p.

2. Bruce Schneier. Schneier on Security [Электронный ресурс]: // Bruce Schneier. - (February 18, 2005). "Schneier on Security: Cryptanalysis of MD5". 7 декабря 2017. - Электронно текстовые данные. - Режим доступа: https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html, свободный.

3. Вычислительный кластер D (Jet) [Электронный ресурс]: // ЦПВТ ФГОБУ ВПО «СибГУТИ» 7 декабря 2017. - Электронно текстовые данные. - Режим доступа: http://cpct.sibsutis.ru/index.php/Main/Jet.

4. Кормен Т. Алгоритмы: вводный курс. - Москва: Вильямс, 2014. - 208 с.

 

ПРИЛОЖЕНИЕ

Исходный код

main.c

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <mpi.h>

#include "md5.h"

 

#define BUFFERSIZE 256

 

char alphabet[] = "abcdefghijklmnopqrstuvwxyz";

int alphabetSize = sizeof(alphabet) - 1;

char* keyword = NULL;

char* keywordhash = NULL;

int root = 0;

 

void iteration_brute(int rank, int commsize);

void hash(char *input, char **output);

 

int main(int argc, char** argv)

{

int rankm, commsizem;

 

  MPI_Init(&argc, &argv);

  MPI_Comm_rank(MPI_COMM_WORLD, &rankm);

  MPI_Comm_size(MPI_COMM_WORLD, &commsizem);

 

  keyword = (char *)malloc(BUFFERSIZE * sizeof(char));

  if (argc > 1) {

    strcpy(keyword, argv[1]);

      }

else {

    strcpy(keyword, "keyword");

      }

  hash(keyword,&keywordhash);

  iteration_brute(rankm, commsizem);

 

  free(keyword);

  free(keywordhash);

 

  MPI_Finalize();

  return 0;

}

 

void iteration_brute(int rank, int commsize)

{

  if (!strcmp(keyword, "")) return;

 int lenght = 1;

  long i = 0, j = 0, k = 0;

 

  char* wordhash = NULL;

  char* word = (char*)malloc(lenght + 1 * sizeof(char));

  word[lenght] = 0;

 int* numcell = (int*)malloc(lenght * sizeof(int));

 

  if (rank == root) {

   printf("Keyword: %s\nKeywordHash: %s\n\n", keyword,                           keywordhash);

}

 

  double time = MPI_Wtime();

 

  while (1) {

 

    for (i = 0; i < lenght; i++) {

       numcell[i] = 0;

    }

    numcell[0] = rank;

    for (i = 0; ; i++) {

      if (numcell[lenght - 1] >= alphabetSize)break;

          for (j = 0; j < lenght - 1; j++) {

               if (numcell[j] >= alphabetSize)

                   {

         numcell[j + 1] += numcell[j] / alphabetSize;

                   numcell[j] = numcell[j] % alphabetSize;

            }

          }

      for (j = 0, k = lenght - 1; j < lenght, k >= 0; j++, k--){

           word[k] = alphabet[numcell[j]];

      }

      hash(word, &wordhash);

      if (!strcmp(word, keyword))

      {

           printf("Word: %s\nWordHash: %s\nTime: %lf\n", word, wordhash, MPI_Wtime() - time);

           MPI_Abort(MPI_COMM_WORLD,0);

      }

      free(wordhash);

      numcell[0]+=commsize;   

    }

    lenght++;

    word = (char*)realloc(word, lenght + 1 *   sizeof(char));

    word[lenght] = 0;

    numcell = (int*)realloc(numcell, lenght * sizeof(int));

}

  time = MPI_Wtime() - time;

  free(word);

 free(numcell);

  return;

}

 

void hash(char *input, char **output)

{

  md5_state_t HASH;

  md5_byte_t digest[16];

  char *hex_output = NULL;

  hex_output = malloc((16 * 2 + 1) * sizeof(char));

 int di;

 

  md5_init(&HASH);

  md5_append(&HASH, (const md5_byte_t *) input,         strlen(input));

  md5_finish(&HASH, digest);

 

  for (di = 0; di < 16; ++di) {

    sprintf(hex_output + di * 2, "%02x", digest[di]);

  }

  *output = hex_output;

}