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

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

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

Хэш-функции также используются в некоторых структурах данных: хэш-таблицах, фильтрах Блума и декартовых деревьях.

Существует множество алгоритмов хэширования с различными характеристиками, (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хэш-функции определяется спецификой решаемой задачи. Простейшими примерами хэш-функций могут служить контрольная сумма или CRC.

Глава 1. Описание алгоритма MD5

1.1 История MD5

MD5 — один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института. Разработан в 1991 году, как более надёжный вариант предыдущего алгоритма MD4. 1] Позже Гансом Доббертином были найдены недостатки алгоритма MD4.

В 1993 году Берт ден Боер (Bert den Boer) и Антон Босселарис (Antoon Bosselaers) показали, что в алгоритме возможны псевдоколлизии, когда разным инициализирующим векторам соответствуют одинаковые дайджесты для входного сообщения.

В 1996 году Ганс Доббертин (Hans Dobbertin) объявил о коллизии в алгоритме и уже в то время было предложено использовать другие алгоритмы хэширования, такие какWhirlpool, SHA-1 или RIPEMD-160.

Из-за небольшого размера хэша в 128 бит, можно рассматривать birthday атаки. В марте 2004 года был запущен проект MD5CRK с целью обнаружения уязвимостей алгоритма, используя birthday атаки. Проект MD5CRK закончился 17 августа 2004 года, когда Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) обнаружили уязвимости в алгоритме.

1 марта 2005 года Arjen Lenstra, Xiaoyun Wang и Benne de Weger продемонстрировали построение двух X.509 документов с различными открытыми ключами и одинаковым хэшем MD5.

18 марта 2006 года исследователь Властимил Клима (Vlastimil Klima) опубликовал алгоритм, который может найти коллизии за одну минуту на обычном компьютере, метод получил название «туннелирование».

хэширование delphi calc интерфейс

1.2 Однонаправленные хэш-функции

Однонаправленная функция H (M) применяется к сообщению произвольной длины M и возвращает значение фиксированной длины h.

h = H (M)

где h имеет длину m

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

Зная М, легко вычислить h.

Зная Н, трудно определить М, для которого H (M) =h.

Зная М, трудно определить другое сообщение M', для которого

H (M) = Н (М')

Нелегко построить функцию, вход которой имеет произвольный размер, а тем более сделать ее однонаправленной. В реальном мире однонаправленные хэш-функции строятся на идее функция сжатия. Такая однонаправленная функция выдает хэш-значение длины n при заданных входных данных большей длины m. Входами функции сжатия являются блок сообщения и выход предыдущего блока текста. Выход представляет собой хэш-значение всех блоков до этого момента. То есть, хэш-значение блока Мi равно

hi=f (Mi, hi-1)

Это хэш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия. Хэш-значением всего сообщения является хэш-значение последнего блока.

Хэшируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения. Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение. Иногда такой метод называется MD-усилением.

1.3 Описание алгоритма

Существует множество алгоритмов хэширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.).

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

MD5 — это улучшенная версия MD4. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение. Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алгоритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Инициализируются четыре переменных:

А = Ox01234567

В = Ox89abcdef

С = Oxfedcba98

D = Ox76543210

Они называются переменными сцепления.

Теперь перейдем к основному циклу алгоритма. Этот цикл продолжается, пока не исчерпаются 512-битовые блоки сообщения. Четыре переменных копируются в другие переменные: A в a, B в b, C в c и D в d.

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тремя из а, b, с и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных а, Ь, с и d. Наконец результат заменяет одну из переменных а, b, с и d. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа — другая функция).

Рис. 0. Главный цикл MD5

Рис. 2. Одна операция MD5

F (X, Y, Z) = (X Y) ((X) Z)

G (X, Y, Z) = (X Z) (Y (Z))

H (X, Y, Z) = X Y Z

I (X, Y, Z) = Y (X (Z))

(- это XOR, — AND, — OR, а — NOT.)

Эти функции спроектированы так, чтобы, если соответствующие биты X, Y и Z независимы и не смещены, каждый бит результата также был бы независимым и несмещенным. Функция F — это побитовое условие: если X, то Y, иначе Z. Функция H — побитовая операция четности.

Если Mj обозначает j-ый подблок сообщения (от 0 до 15), а <<

FF (a, b, c, d, Mj, s, ti) означает a = b + ((a + F (b, c, d) + Mj + ti) <<

GG (a, b, c, d, Mj, s, ti) означает a = b + ((a + G (b, c, d) + Mj + ti) <<

HH (a, b, c, d, Mj, s, ti) означает a = b + ((a + H (b, c, d) + Mj + ti) <<

II (a, b, c, d, Mj, s, ti) означает a = b + ((a + I (b, c, d) + Mj + ti) <<

Четыре этапа (64 действия выглядят следующим образом):

Этап 1:

FF (a, b, c, d, M0, 7, 0xd76aa478)

FF (d, a, b, c, M1, 12, 0xe8c7b756)

FF (c, d, a, b, M2, 17, 0×24 2070db)

FF (b, c, d, a, M3, 22, 0xc1bdceee)

FF (a, b, c, d, M4, 7, 0xf57c0faf)

FF (d, a, b, c, M5, 12, 0×4787c62a)

FF (c, d, a, b, M6, 17, 0xa8304613)

FF (b, c, d, a, M7, 22, 0xfd469501)

FF (a, b, c, d, M8, 7, 0×69 8098d8)

FF (d, a, b, c, M9, 12, 0x8b44f7af)

FF (c, d, a, b, M10, 17, 0xffff5bb1)

FF (b, c, d, a, M11, 22, 0×895cd7be)

FF (a, b, c, d, M12, 7, 0x6b901122)

FF (d, a, b, c, M13, 12, 0xfd987193)

FF (c, d, a, b, M14, 17, 0xa679438e)

FF (b, c, d, a, M15, 22, 0×49b40821)

Этап 2:

GG (a, b, c, d, M1, 5, 0xf61e2562)

GG (d, a, b, c, M6, 9, 0xc040b340)

GG (c, d, a, b, M11, 14, 0×265e5a51)

GG (b, c, d, a, M0, 20, 0xe9b6c7aa)

GG (a, b, c, d, M5, 5, 0xd62fl05d)

GG (d, a, b, c, M10, 9, 0×2 441 453)

GG (c, d, a, b, M15, 14, 0xd8ale681)

GG (b, c, d, a, M4, 20, 0xe7d3fbc8)

GG (a, b, c, d, M9, 5, 0×2,lelcde6)

GG (d, a, b, c, M14, 9, 0xc33707d6)

GG (c, d, a, b, M3, 14, 0xf4d50d87)

GG (b, c, d, a, M8, 20, 0×455al4ed)

GG (a, b, c, d, M13, 5, 0xa9e3e905)

GG (d, a, b, c, M2, 9, 0xfcefa3f8)

GG (c, d, a, b, M7, 14, 0×676f02d9)

GG (b, c, d, a, M12, 20, 0x8d2a4c8a)

Этап 3:

HH (a, b, c, d, M5, 4, 0xfffa3942)

HH (d, a, b, c, M8, 11, 0×8771f681)

HH (c, d, a, b, M11, 16, 0x6d9d6122)

HH (b, c, d, a, M14, 23, 0xfde5380c)

HH (a, b, c, d, M1, 4, 0xa4beea44)

HH (d, a, b, c, M4, 11, 0x4bdecfa9)

HH (c, d, a, b, M7, 16, 0xf6bb4b60)

HH (b, c, d, a, M10, 23, 0xbebfbc70)

HH (a, b, c, d, M13, 4, 0×289b7ec6)

HH (d, a, b, c, M0, 11, 0xeaa127fa)

HH (c, d, a, b, M3, 16, 0xd4ef3085)

HH (b, c, d, a, M6, 23, 0×04881d05)

HH (a, b, c, d, M9, 4, 0xd9d4d039)

HH (d, a, b, c, M12, 11, 0xe6db99e5)

HH (c, d, a, b, M15, 16, 0x1fa27cf8)

HH (b, c, d, a, M2, 23, 0xc4ac5665)

Этап 4:

II (a, b, c, d, M0, 6, 0xf4292244)

II (d, a, b, c, M7, 10, 0×432aff97)

II (c, d, a, b, M14, 15, 0xab9423a7)

II (b, c, d, a, M5, 21, 0xfc93a039)

II (a, b, c, d, M12, 6, 0×655b59c3)

II (d, a, b, c, M3, 10, 0x8f0ccc92)

II (c, d, a, b, M10, 15, 0xffeff47d)

II (b, c, d, a, M1, 21, 0×85845ddl)

II (a, b, c, d, M8, 6, 0x6fa87e4f)

II (d, a, b, c, M15, 10, 0xfe2ce6e0)

II (c, d, a, b, M6, 15, 0xa3014314)

II (b, c, d, a, M13, 21, 0x4e081lal)

II (a, b, c, d, M4, 6, 0xf7537e82)

II (d, a, b, c, M11, 10, 0xbd3af235)

II (c, d, a, b, M2, 15, 0x2ad7d2bb)

II (b, c, d, a, M9, 21, 0xeb86d391)

Эти константы, ti, выбирались следующим образом:

На i-ом этапе ti является целой частью 232*abs (sin (i)), где i измеряется в радианах.

После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.

1.4 Безопасность MD5

Рон Ривест привел следующие улучшения MD5 в сравнении с MD4:

Добавился четвертый этап.

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

Функция G на этапе 2 с ((XY)(XZ)(YZ)) была изменена на (XZ)(Y (Z)), чтобы сделать G менее симметричной.

Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быстрый лавинный эффект.

Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3, чтобы сделать шаблоны менее похожими.

Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для ускорения лавинного эффекта.

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

Том Берсон (Tom Berson) попытался применить дифференциальный криптоанализ к одному этапу MD5, но его вскрытие не оказалось эффективным ни для одного из четырех этапов. Более успешное вскрытие ден Боера и Босселаерса, использующее функцию сжатия, привело к обнаружению столкновений в MD5 Само по себе это вскрытие невозможно для вскрытия MD5 в практических приложениях, оно не влияет и на использование MD5 в алгоритмах шифрования, подобных Luby-Rackoff.

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

Хотя справедливо, что «кажется, что у функции сжатия есть слабое место, но это практически не влияет на безопасность хэш-функции «

Глава 2. Описание программы, реализующей алгоритм MD5 на Delphi

2.1 Анализ технического задания и постановка задачи проектирования

Согласно заданию необходимо разработать программу вычисляющую хэш-код сообщения. Для решения поставленной задачи был выбран язык программирования Delphi, так как он является языком высокого уровня и позволяет быстро и эффективно создавать приложения. Delphi — это продукт Borland International, высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В основе Delphi лежит язык Object Pascal, который является расширением объектно-ориентированного языка Pascal.

Преимущества Delphi по сравнению с аналогичными программными продуктами.

— быстрота разработки приложения;

— высокая производительность разработанного приложения;

— низкие требования разработанного приложения к ресурсам компьютера;

— наращиваемость за счет встраивания новых компонент и инструментов в среду Delphi;

— возможность разработки новых компонент и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходных кодах);

— удачная проработка иерархии объектов.

Система программирования Delphi рассчитана на программирование различных приложений и предоставляет большое количество компонентов для этого.

Поскольку данная программа является приложением Windows, то для ее реализации будем использовать стандартный подход при написании программ под Windows с использованием графического интерфейса. Так отдельно создается форма с визуальными компонентами, для различных визуальных компонент сопоставляются процедуры — обработчики. Далее, как только происходит событие на каком-то из визуальных компонент (щелчок мыши, нажатие на кнопку или пункт меню), операционная система посылает приложению соответствующее сообщение, и запускается соответствующий обработчик именно для этого события. Тогда решение задачи можно разбить на 2 этапа:

1. Разработка визуального интерфейса пользователя, на основе экранных форм среды Delphi и визуальных компонент.

2. Разработка обработчиков событий от элементов экранных форм, разработка алгоритмов и программных кодов действий.

2.2 Разработка экранных форм программы

В Windows основной элемент пользовательского интерфейса — форма. В Delphi каждый проект имеет, по крайней мере, одно окно — главное окно приложения. Все окна в Delphi основаны на объекте TForm. Формы имеют свои свойства, события и методы, при помощи которых мы можем управлять видом и поведением формы. Форма, это обычный компонент Delphi, но в отличие от других, её нет на панели компонентов. В данном проекте используются 2 формы

— f_main (основная форма)

— f_info (форма «О программе», содержит информацию о программе, версию продукта, ФИО разработчика) Список и назначение основных компонентов, расположенных на главной форме f_main:

— Label. Этот компонент используется для отображения различных надписей на формах. Основное свойство для этого компонентаCaption. Именно оно и отвечает за надпись на компоненте.

— Edit. Представляет собой однострочное текстовое поле, служащее для ввода данных пользователем. Основным свойством компонента, передающим введённую информацию, является свойство Edit1. Text типа String. На главной форме программы расположено два таких компонента e_file (предназначен для ввода полного пути к файлу, для которого необходимо вычислить хэш) и e_text (необходим для ввода текста, для которого так же нужно вычислить хэш).

— RzToolbar. Это панель, которая управляет компоновкой инструментальных быстрых кнопок и других компонентов. Размещаемые на панели компоненты автоматически располагаются рядами и упорядочиваются по размерам. Обычно размещается вверху формы под меню. На ней располагаются кнопки класса TRzToolButton.

Кроме визуальных компонентов на форме на расположены следующие объекты:

— PopupMenu. Контекстное меню, вызываемое в приложении Windows по щелчку правой кнопкой мыши. В данной программе используется для вызова меню при нажатии кнопки Btn_in_buf на панели инструментов r_toolbar.

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

— ImageList — представляет собой набор изображений одинаковых размеров, на которые можно ссылаться по индексам, начинающимся с 0. Этот компонент позволяет организовать эффективное и экономное управление множеством пиктограмм и битовых матриц. Он может включать в себя монохромные битовые матрицы, содержащие маски для отображения прозрачности рисуемых изображений. В данной программе используются стандартные изображения на кнопках панели инструментов r_toolbar

— XPManifest — фактически его предназначение сводится к тому, что при помещении на форму, к проекту подключается модуль XPMan, который, в свою очередь, подключает файл ресурсов WindowsXP.res. Результатом помещения компонента XPManifest на форме приложения будет то, что интерфейс программы при работе в Windows XP будет «понимать» темы оформления Windows XP, и все его компоненты во время выполнения программы будут выглядеть так, как это принято в Windows XP. В данной программе этот компонент необходим всего лишь для более приятного интерфейса.

2.3 Описание основных типов данных, обработчиков событий и функций, используемых в данном курсовом проекте

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

К константам и переменным можно обращаться по именам. Литерал не

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

В данной программе используются константы для подсчета блоков вычислений в цикле для функции MD5Transform. Объявление происходит в начале программы после выражения const. Кроме констант используются типы данных.

Тип определяет множество значений, которые могут принимать элементы программы, и совокупность операций, допустимых над этими значениями. Например, значения -34 и 67 относятся к целочисленному типу и их можно умножать, складывать, делить и выполнять другие арифметические операции, а значения abed и sdfhi23 относятся к строковому типу и их можно сцеплять (складывать), но нельзя делить или вычитать.

Основные типы данных, используемые в программе MD 5 Calc:

— string. Строки обеспечивает тип string, который представляет строку с максимальной длиной около 2×1031 символов. Символы строки кодируются в коде ANSI.

— longword. Целые числа, имеющие положительные значения до 4 294 967 295. Он занимает 32 бита памяти.

— byte. Тип Byte является наименьшей формой целого числа, занимая 8 битов (1 байт) памяти. Он поддерживает только положительные целых числа от 0 до 255.

— integer. Тип Integer — целое число, размер которого не гарантируется. Это — основной целочисленный тип в Delphi, и в настоящее время имеет ту же самую ёмкость как LongInt тип — 1 бит на знак, и 31 бит на значение.

Обработчики событий.

Объекты экранной формы были описаны в разделе «Разработка экранных форм программы». Но у нее еще имеются обработчики событий. Обработчиком события называется поведение объекта на то или иное событие, рассмотрим основные из них, используемые в данном приложении:

— b_openClick. После нажатия на кнопку b_open происходит запуск компонента o_file, который позволяет узнать имя файла, выбранного пользователем.

— o_fileSelectionChange. При смене выбранного файла, его имя и путь записывается в поле ввода e_file, для последующего вычисления хэш-суммы именно этого файла.

— b_md5_fileClick. После нажатия на кнопку b_md5_file происходит проверка на ввод пустого значения в поле ввода e_file, если значение не пустое, то вызывается функция MD5File и полученное хэш-значение выводится в компонент типа TLabel (l_hash_file), иначе происходит вывод сообщения об ошибке с помощью стандартного диалогового окна MessageBox.

— e_textChange. При смене значения в поле ввода e_text происходит вычисление хэша и готовое значение выводится так в компонент типа TLabel (l_hash_text).

Функции.

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

Блок функции представляет собой локальный блок, по структуре аналогичный блоку процедуры. В теле функции должен быть хотя бы один оператор присваивания, в левой части которого стоит имя функции. Именно он и определяет значение, возвращаемое функцией. Вызов функции осуществляется по ее имени с указанием в круглых скобках списка аргументов, которого может и не быть. При этом аргументы должны попарно соответствовать параметрам, указанным в заголовке функции, и иметь те же типы. В отличие от процедуры, имя функции может входить как операнд в выражения.

Основные функции, используемые в данной программе:

— function MD5String (const S: string): TMD5Digest. Вычисляет хэш-сумму для строки.

— function MD5File (const FileName: string): TMD5Digest. Вычисляет хэш-сумму для файла

— function MD5Stream (const Stream: TStream): TMD5Digest. Вычисление хэш-суммы для потока Stream

— function MD5Buffer (const Buffer; Size: Integer): TMD5Digest. Вычисление хэш-суммы для произвольного буфера

— function MD5DigestToStr (const Digest: TMD5Digest): string.

Преобразование хэш-суммы в строку из шестнадцатеричных цифр.

Заключение

Данный курсовой проект был выполнен в полном соответствии поставленному заданию в среде Delphi 7.0. В ходе выполнения курсовой работы была разработана программа для подсчета хэш-суммы файла и текста с графическим интерфейсом.

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

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