Лабораторная работа 1.
OpenMP. Восстановление пароля из хэша MD5.

Информация

Современные средства криптографической защиты информации (СКЗИ) хранят парольно-ключевую информацию в невосстановимом виде (считаем, что СКЗИ не содержит специализированных закладок разработчиков). Это означает, что не существует алгоритмов, кроме полного перебора или метода "грубой силы" (brute force), позволяющих однозначно получить пароль по его слепку или хэшу, хранимому в базе данных СКЗИ.

Существуют ситуации, когда администратору СКЗИ или иным уполномоченным лицам требуется ввостановить пароль по его хэшу. Для этого необходимо:

  1. знать хэш;
  2. знать точный алгоритм преобразования пароля в хэш;
  3. иметь многопроцессорную систему для организации перебора паролей;
  4. иметь параллельную программу для перебора паролей;
Также желательно знать исходную длину пароля.

Механизмы получения хэша могут быть разнообразны и в них достаточно часто применяются дайджест-алгоритмы, например - алгоритм MD5 (RFC 1321). Предполагаем, что хеширование заключается в однократном применении алгоритма MD5 над паролем. Полученный хэш представляет собой последовательность из 32 символов, каждая пара символов (в нижнем регистре) является шестнадцатиричным представлением байта. Например, хэш слова password будет представлять собой строку 5f4dcc3b5aa765d61d8327deb882cf99. Удостовериться в этом можно с помощью команды echo -n "password" | md5sum. Программно получить MD5-хэш можно с помощью библиотеки libcrypto проекта OpenSSL. Для этого следует установить пакет libssl-devel, воспользоваться шаблоном программы, которую скомпилировать командой cc 2.c -lcrypto.

Задание

Разработать многопоточную программу с использованием технологии OpenMP, которая по позволяет по MD5-хэшу восстановить зашифрованный пароль. Считать, что пароль состоит из символов латинского алфавита в нижнем регистре и цифр (всего 36 символов).

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

  1. В первом варианте всевозможные наборы комбинаций символов в пароле разбиваются на непересекающиеся части с возможностью обработки каждой части в отдельной нити отдельным циклом с использованием #pragma omp parallel
  2. Во втором варианте формируется единый цикл обработки, распараллеливаемый с помощью #pargma omp parallel и #pargma omp for.

Для упрощения решения задачи разрешается формировать комбинации символов пароля отдельно для каждой длины пароля, то есть обрабатывать отдельно пароли длиной в один символ, потом - в два символа и т.д. вплоть до нахождения пароля или до достижения максимально возможной длины пароля.

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