1 Теоретические основы криптографии 9. КолСодержание Теоретические основы криптографии 9

• Название: КолСодержание Теоретические основы криптографии 9
• Дата: 01.12.2019
• Размер: 0.52 Mb.
• Имя файла: 1 Теоретические основы криптографии 9.doc
• Тип: Реферат; #97986
• страница: 13 из 16

5. Хэш-функции и хэширование

5.1. Общие сведения

Выше нами были рассмотрены механизмы двухключевой криптографии, которые дают возможность подписывать сообщения ограниченной длины (порядка 10³ бит). Если сообщение имеет большой размер, то при прямолинейном использовании таких механизмов потребуется разбить исходное сообщение на большое число блоков меньшего размера и выработать столько подписей, сколько блоков будет содержаться в сообщении. Это сильно усложняет проблему хранения подписей и самих подписанных сообщений, а также организации баз данных, содержащих большое число подписанных документов. Для упрощения этой проблемы подписывается не сам документ, а некоторый его цифровой образ небольшого размера, полученный по специальным криптографическим процедурам, называемым хэшированием.

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

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

5.2. Типы хэш-функций

Существует три типа построения хэш-функций:

• 
  на основе какой-либо трудновычисляемой математической задачи;
  
• 
  на основе алгоритмов блочного шифрования;
  
• 
  разработанные с нуля.
  

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

5.3. Требования к хэш-функциям.

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

• 
  алгоритм должен обладать высокой скоростью обработки информации;
  
• 
  хэш-функция должна быть стойкой против атаки методом “грубой силы”;
  
• 
  программная реализация хэш-функции должна быть оптимизирована под использование на современной аппаратно-программной базе.
  

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

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

5.4. Стойкость хэш-функций.

С точки зрения криптографической стойкости важным свойством хэш-функций является отсутствие коллизий, то есть невозможность найти такие значения х  у, чтобы h(x) = h(y). В криптографических приложениях важным понятием является криптографически стойкая хэш-функция, для которой не существует эффективного алгоритма нахождения значений х  у,где выполнялось бы условие h(x) = h(y) (функция, стойкая в сильном смысле), или не существует эффективного алгоритма нахождения коллизии при заданном х такого у  х, что h(x) = h(y) (функция, стойкая в слабом смысле). Росс Андерсон показал, что отсутствие коллизий не позволяет судить о практической стойкости хэш-функций. Другими словами, данное требование носит формальный характер. Практически значимым является отсутствие у хэш-функции корреляции. Свободной от корреляции называется хэш-функция, у которой не возможно найти пары таких значений х  у, что вес Хэмминга¹⁰ двоичного вектора h(x) XOR h(y) будет меньше веса Хэмминга применительно к двоичному вектору h(M) для некоторого малого М. Свобода от корреляции с точки зрения криптографической стойкости является гораздо более сильным свойством хэш-функции, чем свобода от коллизий. Данный факт подтверждается тем, что из любой хэш-функции, являющейся свободной от коллизий и одновременно свободной от корреляций, можно построить другую хэш-функцию, которая тоже будет свободной от коллизии, но при этом может не сохранить свойства свободы от корреляции.

5.5. Алгоритмы хэширования

Рассмотрим наиболее известные на сегодняшний день алгоритмы хэширования, а именно MD5 и SHA.

5.5.1. Алгоритм MD5

MD5 – это односторонняя функция, разработанная Роном Ривестом. Ее результатом является 128-битное хэш-значение.

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых блоков. Выходом алгоритма является набор из 4 32-битовых блоков, которые объединяются в единое 128-битное хэш-значение.

Во-первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения дописывается столько нулей, сколько нужно. Затем к результату добавляется 64-битовое представление длины сообщения. Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам, и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Затем инициализируются четыре переменных:

A = 0x01234567

B = 0x89abcdef

C = 0xfedcba98

D = 0x76543210

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

После этого начинается главный цикл алгоритма. Он продолжается, пока не исчерпаются 512-битовые блоки сообщения.

Четыре переменных копируются в другие переменные A → a, B → b, C → c, D → d.

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

5.5.2. Алгоритм безопасного хэширования SHA

Этот стандарт определяет алгоритм безопасного хэширования (Secure Hash Algorithm), необходимый для обеспечения безопасности алгоритма цифровой подписи DSA (Digital Signature Algorithm). Для любого входного значения длиной меньше 2⁶⁴ бит SHA выдает 160-битовый результат, называемый кратким содержанием сообщения, которое далее становится входом DSA, который вычисляет подпись для всего сообщения.

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

Алгоритм SHA состоит из следующих шагов:

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

Инициализируются пять 32-битовых переменных:

A = 0x67452301

B = 0xefcdab89

C = 0x98badcfe

D = 0x10325476

E = 0xc3d2e1f0

Затем начинается главный цикл алгоритма. Он обрабатывает сообщение 512-битовыми блоками и продолжается, пока не исчерпаются все блоки сообщения.

Сначала пять переменных копируются в другие переменные: A → a, B → b, C → c, D → d, E → e.

Главный цикл состоит из четырех этапов по 20 операций в каждом. Каждая операция представляет собой нелинейную функцию над тремя из a, b, c, d, e, затем выполняется сдвиг и сложение аналогично MD5.

В SHA используются следующие функции:

, для t = 0…19

, для t = 20…39
, для t = 40…59

, для t = 60…79

а также следующие константы:

K_t = 0x5a827999, для t = 0…19

K_t = 0x6ed9eba1, для t = 20…39

K_t = 0x8f1bbcdc, для t = 40…59

K_t = 0xca62c1d6, для t = 60…79

Блок сообщения превращается из шестнадцати 32-битовых слов (M₀ по M₁₅) в восемьдесят 32-битовых слов (W₀ по W₇₉) с помощью следующего алгоритма:

, для t = 0…15

, для t = 16…79

Если t – это номер операции (от 1 до 80), W_t представляет собой t-ый подблок расширенного сообщения, а <<
For t:=0 to 79 do

Begin

temp:=(a<<<5)+f_t(b,c,d)+e+W_t+K_t;

e:=d;

d:=c;

c:=b<<<30;

b:=a;

a:=temp;

End;

На рис. 8 показана одна операция. Сдвиг переменных выполняет ту же функцию, которую в MD5 выполняет использование в различных местах различных переменных.



Рисунок 6. Одна операция SHA

Дальнейшие вычисления рассматривать не будем ввиду их большого объема.

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