Алгоритм обмена ключа Диффи-Хеллмана

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

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

A mod Q, A₂ mod Q, ..., A_{Q - 1} mod Q

являются различными и состоят из целых от 1 до Q - 1 с некоторыми перестановками. В этом случае для любого целого Y < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что Y = AХ mod Q, где 0 X (Q - 1)

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как indA, Q (Y).

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Общеизвестные элементы
Q	простое число
A	A < Q и A является примитивным корнем Q
Создание пары ключей пользователем I
Выбор случайного числа Хi (закрытый ключ)	Xi < Q
Вычисление числа Yi (открытый ключ)	Yi = AXi mod Q

Создание открытого ключа пользователем J
Выбор случайного числа Хj (закрытый ключ)	Xj < Q
Вычисление случайного числа Yj (открытый ключ)	Yj = AXj mod Q
Создание общего секретного ключа пользователем I
K = (Yj)Xi mod Q

Создание общего секретного ключа пользователем J

K = (Yi)Xj mod Q

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Х_i < Q и вычисляет Y_i = AX_i mod Q. Аналогично пользователь J независимо выбирает случайное целое число Х_j < Q и вычисляет Y_j = AX_j mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как К = (Y_j)X_i mod Q, и пользователь J вычисляет ключ как K = (Y_i)X_j mod Q. В результате оба получат одно и то же значение:

K = (Y_j)X_i mod Q

= (AX_j mod Q)X_i mod Q

= (AX_j )X_i mod Q

по правилам модульной арифметики

= AX_j X_i mod Q

= (AX_j )X_j mod Q

= (AX_i mod Q)X_j mod Q

= (Y_i)X_j mod Q

Таким образом, две стороны обменялись секретным ключом. Так как Х_i и Х_j являются закрытыми, противник может получить только следующие значения: Q, A, Y_i и Y_j. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить

X_j = inda, q (Y_j)

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

Хэш-функции

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

Хэш-код создается функцией Н: h = H (M),

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

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

1) хэш-функция должна применяться к блоку данных любой длины;

2) хэш-функция создает выход фиксированной длины;

3) значение Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М;

4) для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M) = h;

5) для любого х вычислительно невозможно найти y x, что H(y)=H(x);

6) вычислительно невозможно найти произвольную пару (х, y) такую, что H(y)=H(x).

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

Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (S_AB || M). Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить S_AB || M = H-1 (C). Так как атакующий теперь знает и М и S_AB || M, получить S_AB совсем просто.

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

Хэш-функция MD5

Рассмотрим алгоритм получения дайджеста сообщения MD5 (RFC 1321), разработанный Роном Ривестом из MIT.

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

Логика выполнения MD5

Шаг 1: добавление недостающих битов

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина 448 mod 512). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

64-битное представление длины исходного (до добавления) сообщения в битах присоединяется к результату первого шага. Если первоначальная длина больше, чем 264, то используются только последние 64 бита. Таким образом, поле содержит длину исходного сообщения по модулю 264.

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как последовательность 512-битных блоков Y0, Y1, . . ., YL-1, при этом общая длина расширенного сообщения равна L * 512 битам. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам:

Шаг 3: инициализация MD-буфера

Используется 128-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567; В = 89ABCDEF; C = FEDCBA98; D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков.

Основой алгоритма является модуль из четырех циклических обработок (HMD5). Каждый цикл использует свою элементарную логическую функцию, обозначаемую fF, fG, fH и fI соответственно.

Каждый цикл принимает в качестве входа текущий 512-битный блок Yq, обрабатывающийся в данный момент, и 128-битное значение буфера ABCD, которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы T[1 ... 64], построенной на основе функции sin. i-ый элемент T, обозначаемый T[i], имеет значение, равное целой части от 2³² * abs (sin (i)), i задано в радианах. Так как abs (sin (i)) является числом между 0 и 1, каждый элемент Т является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MDq+1 выход четырех циклов складывается по модулю 2³² с MDq. Сложение выполняется независимо для каждого из четырех слов в буфере.

Шаг 5: выход

После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения.

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

Логика выполнения отдельного шага

A ← B + CLSs (A + f (B, C, D) + X [k] + T [i]),

где A, B, C, D - четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово.

f - одна из элементарных функций fF, fG, fH, fI.

CLSs - циклический сдвиг влево на s битов 32-битного аргумента.

X [k] - M [q * 16 + k] - k-ое 32-битное слово в q-ом 512 блоке сообщения.

T [i] - i-ое 32-битное слово в матрице Т.

+ - сложение по модулю 232.

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

fF = (B & C) (not B & D)

fG = (B & D) V (C & not D)

fH = B C D

fI = C (B & not D)

Массив из 32-битных слов X [0..15] содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

Можно суммировать алгоритм MD5 следующим образом:

MD0 = IV

MDq+1 = MDq + fI[Yq, fH[Yq, fG[Yq, fF[Yq, MDq]]]]

MD = MDL-1,

где IV - начальное значение буфера ABCD, определенное на шаге 3,

Yq - q-ый 512-битный блок сообщения.

L - число блоков в сообщении (включая поля дополнения и длины).

MD - окончательное значение дайджеста сообщения.

Хэш-функция SHA-1

Безопасный хэш-алгоритм (Secure Hash Algorithm) был разработан национальным институтом стандартов и технологии (NIST) и опубликован в качестве федерального информационного стандарта (FIPS PUB 180) в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4.

Алгоритм получает на входе сообщение максимальной длины 264 бит и создает в качестве выхода дайджест сообщения длиной 160 бит.

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

Шаг 1: добавление недостающих битов

Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512 (длина 448 mod 512). Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления.

Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y₀, Y₁, ..., Y_L-1, так что общая длина расширенного сообщения есть L * 512 бит. Таким образом, результат кратен шестнадцати 32-битным словам.

Шаг 3: инициализация SHA-1 буфера

Используется 160-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как пять 32-битных регистров A, B, C, D и E. Эти регистры инициализируются следующими шестнадцатеричными числами:

A=67452301; B=EFCDAB89; C=98BADCFE; D=10325476; E=C3D2E1F0

Шаг 4: обработка сообщения в 512-битных (16-словных) блоках

Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.

Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Y_q и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера.

В каждом цикле используется дополнительная константа Кt, которая принимает только четыре различных значения:

0 t 19 K_t = 5A827999 (целая часть числа [230 × 21/2])

20 t 39 Kt = 6ED9EBA1 (целая часть числа [230 × 31/2])

40 t 59 Kt = 8F1BBCDC (целая часть числа [230 × 51/2])

60 t 79 Kt = CA62C1D6 (целая часть числа [230 × 101/2])

Для получения SHA_q+1 выход 80-го цикла складывается со значением SHA_q. Сложение по модулю 232 выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHA_q.

Шаг 5: выход

После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битного блока. Каждый цикл можно представить в виде:

A, B, C, D, E (CLS₅ (A) + f_t (B, C, D) + E + W_t + K_t), A, CLS₃₀ (B), C, D

Где

A, B, C, D, E - пять слов из буфера.

t - номер цикла, 0 t 79.

ft - элементарная логическая функция.

CLSs - циклический левый сдвиг 32-битного аргумента на s битов.

Wt - 32-битное слово, полученное из текущего входного 512-битного блока.

Kt - дополнительная константа.

+ - сложение по модулю 232.

Логика выполнения отдельного цикла

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

Номер цикла	ft (B, C, D)
(0 t 19)	(B C) ( B D)
(20 t 39)	B C D
(40 t 59)	(B C) (B D) (C D)
(60 t 79)	B C D

На самом деле используются только три различные функции. Для 0 t 19 функция является условной: if B then C else D. Для 20 t 39 и 60 t 79 функция создает бит четности. Для 40 t 59 функция является истинной, если два или три аргумента истинны.

32-битные слова W_t получаются из очередного 512-битного блока сообщения следующим образом.

Получение входных значений каждого цикла из очередного блока

Первые 16 значений W_t берутся непосредственно из 16 слов текущего блока. Оставшиеся значения определяются следующим образом:

W_t = W_t-16 W_t-14 W_t-8 W_t-3

В первых 16 циклах вход состоит из 32-битного слова данного блока. Для оставшихся 64 циклов вход состоит из XOR нескольких слов из блока сообщения.

Алгоритм SHA-1 можно суммировать следующим образом:

SHA₀ = IV

SHA_q+1 = Σ₃₂ (SHA_q , ABCDE_q )

SHA = SHA_L-1,

где IV - начальное значение буфера ABCDE.

ABCDEq - результат обработки q-того блока сообщения.

L - число блоков в сообщении, включая поля добавления и длины.

Σ32 - сумма по модулю 232, выполняемая отдельно для каждого слова буфера.

SHA - значение дайджеста сообщения.

Сравнение SHA-1 и MD5

Можно суммировать ключевые различия между алгоритмами.

	MD5	SHA−1
Длина дайджеста	128 бит	160 бит
Размер блока обработки	512 бит	512 бит
Число итераций	64 (4 цикла по 16 итераций)
Число элементарных функций
Число дополнительных констант

Сравним оба алгоритма в соответствии с теми целями, которые были определены для каждого алгоритма:

Безопасность: наиболее очевидное и наиболее важное различие состоит в том, что дайджест SHA-1 на 32 бита длиннее, чем дайджест MD5. Если предположить, что оба алгоритма не содержат каких-либо структурированных данных, которые уязвимы для криптоаналитических атак, то SHA-1 является более стойким алгоритмом. Используя лобовую атаку, труднее создать произвольное сообщение, имеющее данный дайджест, если требуется порядка 2¹⁶⁰ операций, как в случае алгоритма SHA-1, чем порядка 2¹²⁸ операций, как в случае алгоритма MD5. Используя лобовую атаку, труднее создать два сообщения, имеющие одинаковый дайджест, если требуется порядка 2⁸⁰ как в случае алгоритма SHA-1, чем порядка 2⁶⁴ операций как в случае алгоритма MD5.

Скорость: так как оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру. SHA-1 содержит больше шагов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25% медленнее, чем MD5 на той же аппаратуре.

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

Хэш-функции SHA-2

В 2001 году NIST принял в качестве стандарта три хэш-функции с существенно большей длиной хэш-кода. Часто эти хэш-функции называют SHA-2 или SHA-256, SHA-384 и SHA-512 (соответственно, в названии указывается длина создаваемого ими хэш-кода). Эти алгоритмы отличаются не только длиной создаваемого хэш-кода, но и длиной обрабатываемого блока, длиной слова и используемыми внутренними функциями. Сравним характеристики этих хэш-функций.

Алгоритм	Длина сообщения (в битах)	Длина блока (в битах)	Длина слова (в битах)	Длина дайджеста сообщения (в битах)	Безопасность (в битах)
SHA-1	<264
SHA-256	<264
SHA-384	<2128
SHA-512	<2128

В данных алгоритмах размер блока сообщения равен m бит. Для SHA-256 m = 512, для SHA-384 и SHA-512 m = 1024. Каждый алгоритм оперирует с w-битными словами. Для SHA-256 w = 32, для SHA-384 и SHA-512 w = 64. В алгоритмах используются обычные булевские операции над словами, а также сложение по модулю 2w, правый сдвиг на n бит SHR_n (x) , где х - w-битное слово, и циклические (ротационные) правый и левый сдвиги на n бит ROTR_n (x) и ROTL_n (x), где х - w-битное слово.

SHA-256 использует шесть логических функций, при этом каждая из них выполняется с 32-битными словами, обозначенными как x, y и z. Результатом каждой функции тоже является 32-битное слово.

Хэш-функция ГОСТ 3411

Алгоритм ГОСТ 3411 является отечественным стандартом для хэш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1,2 или MD5, в основе которых лежит алгоритм MD4.

Длина хэш-кода, создаваемого алгоритмом ГОСТ 3411, равна 256 битам. Алгоритм разбивает сообщение на блоки, длина которых также равна 256 битам. Кроме того, параметром алгоритма является стартовый вектор хэширования Н - произвольное фиксированное значение длиной также 256 бит.

Алгоритм обработки одного блока сообщения

Сообщение обрабатывается блоками по 256 бит справа налево.

Каждый блок сообщения обрабатывается по следующему алгоритму.

Генерация четырех ключей длиной 256 бит каждый.

Шифрование 64-битных значений промежуточного хэш-кода H на ключах Ki (i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

Перемешивание результата шифрования.

Для генерации ключей используются следующие данные:

промежуточное значение хэш-кода Н длиной 256 бит;

текущий обрабатываемый блок сообщения М длиной 256 бит;

параметры - три значения С2, С3 и С4 длиной 256 бит следующего вида: С2 и С4 состоят из одних нулей, а С3 равно

18 08 116 024 116 08 (08 18)2 18 08 (08 18)4 (18 08)4

где степень обозначает количество повторений 0 или 1.

Используются две формулы, определяющие перестановку и сдвиг.

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

Перестановка Р элементов 256-битной последовательности выполняется по формуле y = (x), где x - порядковый номер 8-битного значения в исходной последовательности; y - порядковый номер 8-битного значения в результирующей последовательности.

(i + 1 + 4(k - 1)) = 8i + k

i = 0 ÷ 3, k = 1 ÷ 8

Сдвиг А определяется по формуле

A (x) = (x1 x2) || x4 || x3 || x2

Где

xi - соответствующие 64 бита 256-битного значения х,

|| обозначает конкатенацию.

Присваиваются следующие начальные значения:

i = 1, U = H, V = M.

W = U V, K₁ = Р (W)

Ключи K2, K3, K4 вычисляются последовательно по следующему алгоритму:

U = A(U) Сi,

V = A(A(V)),

W = U V,

K_i = Р(W)

Далее выполняется шифрование 64-битных элементов текущего значения хэш-кода Н с ключами K₁, K₂, K₃ и K₄. При этом хэш-код Н рассматривается как последовательность 64-битных значений:

H = h4 || h3 || h2 || h1

Выполняется шифрование алгоритмом ГОСТ 28147:

s_i = EK_i [h_i], i = 1, 2, 3, 4

S = s₁ || s₂ || s₃ || s₄

Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений. Сдвиг обозначается Ψ и определяется следующим образом:

η16 || η15 || ... || η1 - исходное значение

η1 η2 η3 η4 η13 η16 || η16 || ... || η2 - результирующее значение

Результирующее значение хэш-кода определяется следующим образом:

Χ(M, H) = ₆₁ (H (M ₁₂(S)))

где

H - предыдущее значение хэш-кода,

М - текущий обрабатываемый блок,

Ψi - i-ая степень преобразования Ψ.

Логика выполнения ГОСТ 3411

Входными параметрами алгоритма являются:

• исходное сообщение М произвольной длины;
• стартовый вектор хэширования Н, длина которого равна 256 битам;
• контрольная сумма Σ, начальное значение которой равно нулю и длина равна 256 битам;
• переменная L, начальное значение которой равно длине сообщения.

Сообщение М делится на блоки длиной 256 бит и обрабатывается справа налево. Очередной блок i обрабатывается следующим образом:

H = Χ(M_i, H)

Σ = Σ ' M_i

L рассматривается как неотрицательное целое число, к этому числу прибавляется 256 и вычисляется остаток от деления получившегося числа на 2²⁵⁶. Результат присваивается L.

Где ' обозначает следующую операцию: Σ и M_i рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2²⁵⁶. Этот остаток и является результатом операции.

Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:

Блок добавляется слева нулями так, чтобы его длина стала равна 256 битам.

Вычисляется Σ = Σ ' M_i.

L рассматривается как неотрицательное целое число, к этому числу прибавляется длина исходного сообщения М и находится остаток от деления результата сложения на 2²⁵⁶.

Вычисляется Н = Χ(М', Н).

Вычисляется Н = Χ(L, Н).

Вычисляется Н = Χ(Σ, Н).

Значением функции хэширования является Н.