Длины значений однонаправленных хэш-функций

 

64-битовые хэш-функции слишком малы, чтобы противостоять вскрытию методом «дней рождений». Более практичны однонаправленные хэш-функции, выдающие 128-битовые хэш-значения. При этом, чтобы найти два документа с одинаковыми хэш-значениями, для вскрытия методом «дней рождений» придется хэшировать 2⁶⁴ слу­чайных документов, что, впрочем, недостаточно, если нужна длительная безопасность. Поэтому ряд стандартов безопасного хэширования (Secure Hash Standard, SHS), использует 160-битовое хэш-значение. Это еще сильнее усложняет вскрытие методом «дней рождений», для которого понадобится 2⁸⁰ хэширований.

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

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

2. Хэш значение конкатенируерся с сообщением.

3. Для конкатенации вычисляется новое хэш-значения.

4. Создается хэш-значение большей длины, состоящее из объединения хэш-значения этапа (1) и хэш-значения этапа (3).

5. Этапы (1)-(4) повторяются нужное количество раз для обеспечения требуемой длины хэш-значения.

Структура и алгоритмы MD-функций

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

h _i, =f(М_i, h _i -1)

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

Рисунок 3.1 - Однонаправленная функция

 

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

MD4

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

Цели, преследуемые при разработке алгоритма:

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

Прямая безопасность. Безопасность MD4 не основывается на каких-либо допущениях, например, предположении о трудности разложения на множители.

Скорость. MD4 подходит для высокоскоростных программных реализаций. Она основана на простом набо­ре битовых манипуляций с 32-битовыми операндами.

Простота и компактность. MD4 проста, насколько это возможно, и не содержит больших структур данных или сложных программных модулей.

Удачная архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропро­цессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения.

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

Пусть есть сообщение длиной b бит, для которого мы ищем MD. b может быть равно 0, оно не обязано быть кратно 8.

Представим его в виде:

Расчет MD происходит за 5 шагов:

Шаг 1: Добавление байтов заполнителей

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

Добавление происходит следующим образом:

- первый добавленный бит – «1», остальные «0». Минимум 1 бит, максимум 512.

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

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

Теперь сообщение имеет длину, кратную 512 битам (16 32 битных слова), его можно представить как слова:

где N- кратно 16

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

Буфер из четырех слов (A,B,C,D), используется для расчета MD. Инициализируется:

word A: 01 23 45 67word B: 89 ab cd efword C: fe dc ba 98word D: 76 54 32 10

Шаг 4: Обработка сообщения блоками по 16 слов

Сначала определим три вспомогательный функции, на вход получают 3 слова, результат – слово.

F(X,Y,Z) = XY v not(X) ZG(X,Y,Z) = XY v XZ v YZH(X,Y,Z) = X xor Y xor Z

Каждый бит F – Если X то Y, иначе Z

Каждый бит G – Преобладающее значение X,Y,Z

Каждый бит H – xor, или контроль четности

Делаем следующее: /* Обрабатываем каждый блок в 16 слов. */ For i = 0 to N/16-1 do /* Копируем блок i в X. */ For j = 0 to 15 do X[j] = M[i*16+j]. end /* цикла j */ /* Сохраняем значения A как AA, B как BB, C как CC, и D как DD. */ AA = A BB = B CC = C DD = D /* Раунд 1. */ /* Пусть [abcd k s] определяют операцию a = (a + F(b,c,d) + X[k]) <<< s. */ /* Сделать следующие 16 операций. */ [ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19] [ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19] [ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19] [ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]

/*Несложно заметить, что ABCD циклически сдвигаются влево, k идет по строкам от 0 до 15, а s циклически замкнуто на {3,7,11,19}.*/

 

/* Раунд 2. */ /* Пусть [abcd k s] определяют операцию a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Сделать следующие 16 операций. */ [ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13] [ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13] [ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13] [ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]

/*Несложно заметить, что ABCD циклически сдвигаются влево, k идет по столбцам от 0 до 15, а s циклически замкнуто на {3,5,9,13}.*/

/* Раунд 3. */ /* Пусть [abcd k s] определяют операцию a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Сделать следующие 16 операций. */ [ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15] [ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15] [ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15] [ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]

/*Несложно заметить, что ABCD циклически сдвигаются влево, а s циклически замкнуто на {3,9,11,15}, k также подвержено закономерности*/

/* Изменяем ABCD – регистры для следующего блока */ A = A + AA B = B + BB C = C + CC D = D + DD end /* цикла по i */Примечание: 5A..99 – 32 битная константа – корень из 2 со старшей цифрой в начале.

6E..A1 – 32 битная константа – корень из 3 со старшей цифрой в начале.

Шаг 5: Вывод

MD – это A,B,C,D – начиная с младшего байта A и заканчивая старшим байтом D.

(128 бит)

После первого появления алгоритма был совершен криптоаналитиками ряд вскрытий отдельных этапов MD4. Хотя все эти вскрытия не были распространены на полный алго­ритм, Ривест усилил свою разработку. В результате появился алгоритм MD5.

MD5

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

Описание MD5

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

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

А = 0x01234567

В = 0x89abcdef

С = 0xfedcba98

D = 0x76543210

 

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

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

Четыре переменных копируются в другие переменные: А в а, В в b, С в с и D в d.

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

 

Рисунок 3.2 - Главный цикл MD5

Рисунок 3.3 - Схема одной операции алгоритма MD5

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

Если Mj обозначает j-ый подблок сообщения (от 0 до 15), a <«s обозначает циклический сдвиг влево на s битов, то используются следующие четыре операции:

FF(a,b,c,d,Mj,s,t_i) означает a = b + ((a + ¥(b,c,d) + М,- + t_t) <«s)

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

HH(a,b,c,d,Mj,s,t_i) означает a = b + ((a + H(b,c,d) + M,- + t_t) <«s)

II{a,b,c,dMj,s,t_i) означает a = b + ((a + I(b,c,d) + Mj + t_t) <«s)

Четыре этапа алгоритма.

Шаг 1: Добавление байтов заполнителей

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

- первый добавленный бит – «1», остальные «0». Минимум 1 бит, максимум 512.

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

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

Теперь сообщение имеет длину, кратную 512 битам (16 32 битных слова), его можно представить как слова:

, где N- кратно 16

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

Буфер из четырех слов (A,B,C,D), используется для расчета MD. Инициализируется:

word A: 01 23 45 67word B: 89 ab cd efword C: fe dc ba 98word D: 76 54 32 10

Шаг 4: Обработка сообщения блоками по 16 слов

Сначала определим четыре вспомогательных функции, на вход получают 3 слова, результат – слово.

F(X,Y,Z) = XY v not(X) Z

G(X,Y,Z) = XZ v Y not(Z)

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

I(X,Y,Z) = Y xor (X v not(Z))

Каждый бит F – Если X то Y, иначе Z

Каждый бит G – Преобладающее значение X,Y,Z

Каждый бит H – xor, или контроль четности

Этот шаг использует специальную таблицу T[1..64], заполненную из значений синуса. T[i]=Целая часть 4294967296 * abs(sin(i)), где i в радианах.

Делаем следующее: Обрабатываем каждый блок в 16 слов. */ For i = 0 to N/16-1 do /* Копируем блок i в X. */ For j = 0 to 15 do X[j] = M[i*16+j]. end /* цикла j */ /* Сохраняем значения A как AA, B как BB, C как CC, и D как DD. */ AA = A BB = B CC = C DD = D /* Раунд 1. */

/* Пусть [abcd k s i] определяют операцию

a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */

/* Делаем следующие 16 операций. */

[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]

[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]

[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]

[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

 

/* Раунд 2. */

/* Пусть [abcd k s i] определяют операцию

a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */

/* Делаем следующие 16 операций. */

[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]

[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]

[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]

[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Раунд 3. */

/* Пусть [abcd k s t] определяют операцию

a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */

/* Делаем следующие 16 операций. */

[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]

[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]

[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]

[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

 

/* Раунд 4. */

/* Пусть [abcd k s t] определяют операцию

a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */

/* Делаем следующие 16 операций. */

[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]

[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]

[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]

[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Изменяем ABCD – регистры для следующего блока */ A = A + AA B = B + BB C = C + CC D = D + DD end /* цикла по i */

Шаг 5: Вывод

MD – это A,B,C,D – начиная с младшего байта A и заканчивая старшим байтом D (128 бит).

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

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

1. Добавился еще один этап.

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

3. Функция G на этапе 2 была изменена, чтобы сделать G менее симметричной.

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

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

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

MD2

MD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Она вместе с MD5 используется для цифровой подписи в протоколах РЕМ. Безопасность MD2 опирается на случайную перестановку байтов. Эта перестановка фиксирована и зависит от цифр числа pi. Идентификаторы So, S1, S2,, S255 являются перестановкой.

Чтобы выполнить хэширование сообщения М необходимо:

1. Дополнить сообщение i байтами, значение i должно быть таким, чтобы длина полученного сообщения была кратна 16 байтам.

2. Добавить к сообщению 16 байтов контрольной суммы.

3. Проинициализировать 48-байтовый блок: Х_о, Х\, Х₂,..., Х_А1. Заполнить первые 16 байтов X нулями, во вторые 16 байтов X скопировать первые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X.

4. Вот как выглядит функция сжатия:
t = 0

For j = 0 to 17

For к = 0 to 47

t = X_k XOR S_t,

X_k=t

t = (t +j) mod 256

5. Скопировать во вторые 16 байтов X вторые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X. Выполнить этап (4). Повторять этапы (3) и (4) по очереди для каждых 16 байтов сообщения.

6. Выходом являются первые 16 байтов X.

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

Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA)

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

SHA выдает 160-битовое хэш-значение, более длинное, чем у MD5

Описание SHA

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

Инициализируются пять 32-битовых переменных (в MD5 используется четыре переменных, но рассматри­ваемый алгоритм должен выдавать 160-битовое хэш-значение):

А = 0x67452301

В = 0xefcdab89

С = 0x10325476

D = 0x10325476

E = 0xc3d2elf0

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

Сначала пять переменных копируются в другие переменные: А в а, В в b, С в с, D в d и Е в е.

Главный цикл состоит из четырех этапов по 20 операций в каждом (в MD5 четыре этапа по 16 операций в каждом). Каждая операция представляет собой нелинейную функцию над тремя из а, b, с, d и е, а затем выпол­няет сдвиг и сложение аналогично MD5. В SHA используется следующий набор нелинейных функций:

, для t=0 до 19 , для t=20 до 39

, для t=40 до 59 , для t=60 до 79 в алгоритме используются следующие четыре константы:

К_t = 0х5а827999, для t=0 до 19

К_t = 0x6ed9ebal, для t=20 до 39

К_t = 0x8flbbcdc, для t=40 до 59

К_t = 0xca62cld6, для t=60 до 79

(Если интересно, как получены эти числа, то:0х5а827999 = 2^1/2/4, 0x6ed9ebal = 3^1/2/4, 0x8flbbcdc = 5^1/2/4, 0xca62cld6 = 10^1/2/4; все умножено на 2³²)

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

W_t = M_t, для t = 0 по 15

, для t=16 по 79

Если t - это номер операции (от 1 до 80), W, представляет собой t-ый подблок расширенного сообщения, а <<< - это циклический сдвиг влево на s битов, то главный цикл выглядит следующим образом:

FOR t = 0 to 79

TEMP = (а <<<5) +f_t(b,c,d) + e+W_t + K_t

e = d

d = c

c = b <<< 30

b = a

a = TEMP

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

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

После всего этого а, b, с, d и е добавляются к А, В, С D и Е, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение А, В, С D и Е.

Безопасность SHA

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

 

Задание к лабораторной работе

1. Изучить алгоритм и разработать программу реализации алгоритма хеш-функции в соответствии с вариантом:

- алгоритм MD2 - <номер по журналу > MOD 4 =0;

- алгоритм MD4 - <номер по журналу > MOD 4 =1;

- алгоритм MD5 - <номер по журналу > MOD 4 =2;

- алгоритм SHA - <номер по журналу > MOD 4 =0;

2. Проанализировать алгоритм с точки зрения его безопасности.

Контрольные вопросы к лабораторной работе:

1. Какова кратность длины исходного сообщения?

2. Какова разрядность вычисленного хеш-значения?

3. Какие логические операции используются в алгоритме?

4. Для чего используется метод МД-усиления?

5. Для чего используются однонаправленные хеш-функции?

Лабораторная работа №4

Тема: Ассиметричные алгоритмы шифрования. Шифрование данных алгоритмом RSA. Понятия электронно-цифровой подписи. ЭЦП RSA.

Цель работы: Изучение принципов шифрования в ассиметричных криптосистемах. Изучение и программная реализация алгоритма RSA, ЭЦП RSA.

Методические указания к выполнению лабораторной работы

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

Для со­вре­мен­ных крип­то­гра­фи­че­ских сис­тем за­щи­ты ин­фор­ма­ции сфор­му­ли­ро­ва­ны сле­дую­щие об­ще­при­ня­тые тре­бо­ва­ния:

­ за­шиф­ро­ван­ное сообщение дол­жно под­да­вать­ся чте­нию толь­ко при на­ли­чии клю­ча;

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

­ чис­ло опе­ра­ций, не­об­хо­ди­мых для рас­шиф­ро­вы­ва­ния ин­фор­ма­ции пу­тем пе­ре­бо­ра все­воз­мож­ных ключей долж­но иметь стро­гую ниж­нюю оцен­ку и вы­хо­дить за пре­де­лы воз­мож­но­стей со­вре­мен­ных ком­пь­ю­те­ров (с учетом возможности использования сетевых вычислений);

­ зна­ние ал­го­рит­ма шиф­ро­ва­ния не долж­но вли­ять на на­деж­ность за­щи­ты;

­ не­зна­чи­тель­ное из­ме­не­ние клю­ча долж­но при­во­дить к су­ще­ст­вен­но­му из­ме­не­нию ви­да за­шиф­ро­ван­но­го сообщения да­же при ис­поль­зо­ва­нии од­но­го и то­го же клю­ча;

­ струк­тур­ные эле­мен­ты ал­го­рит­ма шиф­ро­ва­ния долж­ны быть не­из­мен­ны­ми;

­ до­пол­ни­тель­ные би­ты, вво­ди­мые в сообщение в про­цес­се шиф­ро­ва­ния, должен быть пол­но­стью и на­деж­но скры­ты в шиф­ро­ван­ном тек­сте;

­ дли­на шиф­ро­ван­но­го тек­ста долж­на быть рав­ной дли­не ис­ход­но­го тек­ста;

­ не долж­но быть про­стых и лег­ко ус­та­нав­ли­вае­мых зависимостью ме­ж­ду клю­ча­ми, по­сле­до­ва­тель­но ис­поль­зуе­мы­ми в про­цес­се шиф­ро­ва­ния;

­ лю­бой ключ из мно­же­ст­ва возможных дол­жен обес­пе­чи­вать на­деж­ную за­щи­ту ин­фор­ма­ции;

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

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

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

Суть их со­сто­ит в том, что ка­ж­дым ад­ре­са­том ИС ге­не­ри­ру­ют­ся два клю­ча, свя­зан­ные ме­ж­ду со­бой по оп­ре­де­лен­но­му пра­ви­лу. Один ключ объ­яв­ля­ет­ся от­кры­тым, а дру­гой за­кры­тым. От­кры­тый ключ пуб­ли­ку­ет­ся и дос­ту­пен лю­бо­му, кто же­ла­ет по­слать со­об­ще­ние ад­ре­са­ту. Секретный ключ сохраняется в тайне.

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

Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом ис­поль­зу­ют так называемые не­об­ра­ти­мые или од­но­сто­рон­ние функ­ции, ко­то­рые об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нии x от­но­си­тель­но про­сто вы­чис­лить зна­че­ние f(x), од­на­ко ес­ли y = f(x), то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­ния x.

Мно­же­ст­во клас­сов не­об­ра­ти­мых функ­ций и по­ро­ж­да­ет все раз­но­об­ра­зие сис­тем с от­кры­тым клю­чом. Од­на­ко не вся­кая не­об­ра­ти­мая функ­ция го­дит­ся для ис­поль­зо­ва­ния в ре­аль­ных ИС.

В са­мом оп­ре­де­ле­нии не­об­ра­ти­мо­сти при­сут­ст­ву­ет не­оп­ре­де­лен­ность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства за обозримый интервал времени.

Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рисунке 1. В этой криптосистеме применяют два различных ключа:

К_В – открытый ключ получателя В, используемый отправителем А:

k_В – секретный ключ получателя В.

Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ k_В по незащищенному каналу).

 

Рисунок 4.1 - Обобщенная схема асимметричной криптосистемы с открытым ключом

 

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

1) Подготовительный этап:

- абонент В генерирует пару ключей: секретный ключ k_В и открытый ключ К_В;

- открытый ключ К_В посылает абоненту А и остальным абонентам (или делается доступным, например, на разделяемом ресурсе).

2) Использование – обмен информацией между абонентами А и В:

- абонент А зашифровывает сообщение с помощью открытого ключа К_В абонента В и отправляет шифртекст абоненту В;

- абонент В расшифровывает сообщение с помощью своего секретного ключа k_В, Никто другой (в том числе абонент А) не может расшифровать данное сообщение, так как не имеет секретного ключа абонента В. Защита информации в асимметричной криптосистеме основана на секретности ключа k_В получателя сообщения.

Характерные особенности асимметричных криптосистем: открытый ключ и криптограмма могут быть отправлены по незащищенным каналам, то есть они известны противнику; алгоритмы шифрования и расшифрования являются открытыми.

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

1. Пре­об­ра­зо­ва­ние ис­ход­но­го тек­ста долж­но быть не­об­ра­ти­мым и ис­клю­чать его вос­ста­нов­ле­ние на ос­но­ве от­кры­то­го клю­ча.

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

Ал­го­рит­мы шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое рас­про­стра­не­ние в со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах. Так, ал­го­ритм RSA стал ми­ро­вым стан­дар­том де-фак­то для от­кры­тых сис­тем и ре­ко­мен­до­ван МККТТ.

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

1. Разложение больших чисел на простые множители.

2. Вычисление логарифма в конечном поле.

3. Вычисление корней алгебраических уравнений.

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

1. Как са­мо­стоя­тель­ные сред­ст­ва за­щи­тыпе­ре­да­вае­мых и хра­ни­мых дан­ных.

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

3. Сред­ст­ва ау­тен­ти­фи­ка­ции поль­зо­ва­те­лей (электронно-цифровая подпись).

Рассмотрим асимметричный алгоритм шифрования RSA.

Не­смот­ря на до­воль­но боль­шое чис­ло раз­лич­ных систем с открытым ключом, наиболее популярна - криптосистема RSA, разработанная в 1977 году и по­лу­чив­шая на­зва­ние в честь ее соз­да­те­лей: Рона Ри­ве­ста, Ади Ша­ми­ра и Леонарда Эй­дель­ма­на.

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

Общее описание алгоритма RSA:

1. Отправитель выбирает два очень больших простых числа Р и Q и вычисляет два произведения N=PQ и M=(P-1)(Q-1).

2. Затем он выбирает случайное целое число D, взаимно простое с М, и вычисляет Е, удовлетворяющее условию DE = 1 MOD М.

3. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя Е как закрытый ключ.

4. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S'=(S**D) MOD N.

5. Получатель сообщения расшифровывает его, возводя в степень Е по модулю N, так как S =(S'**E) MOD N = (S**(D*E)) MOD N.

Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число Е.

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, SWAN, STT и PCT.

Рас­смот­рим ма­те­ма­ти­че­ские ре­зуль­та­ты, по­ло­жен­ные в ос­но­ву это­го ал­го­рит­ма.

Теорема 1. (Малая теорема Ферма.)

Если р - простое число, то

x^{p -1} = 1 (mod p) (1)

для любого х, простого относительно р, и

x^p = х (mod p) (2)

для любого х.

Доказательство. Достаточно доказать справедливость уравнений (1) и (2) для х ÎZ ^p. Проведем доказательство методом индукции.

Далее

x^p =(x -1+1) ^p = å C(p,j)(x -1)^j=(x -1) ^p +1 (mod p),

0£j£ p

так как C(p,j)=0(mod p) при 0<j< p. С учетом этого неравенства и предложений метода доказательства по индукции теорема доказана.

Определение. Функцией Эйлера j(n) называется число положительных целых, меньших n и простых относительно n.

n
j(n)

Теорема 2. Если n = pq, (p и q - отличные друг от друга простые числа), то

j(n)=(p -1)(q -1).

Теорема 3. Если n = pq, (p и q - отличные друг от друга простые числа) и х - простое относительно р и q, то

x ^j(n) = 1 (mod n).

Следствие. Если n = pq, (p и q - отличные друг от друга простые числа) и е простое относительно j(n), то отображение

Е_e,n: x ® x ^e (mod n)

является взаимно однозначным на Z _n.

Очевиден и тот факт, что если е - простое относительно j(n), то существует целое d, такое, что

ed = 1 (mod j(n)) (3)

На этих математических фактах и основан популярный алгоритм RSA.

Пусть n = pq, где p и q - различные простые числа. Если e и d удовлетворяют уравнению (8.2.3), то отображения Е_e,n и Е_d,n являются инверсиями на Z_n. Как Е_e,n, так и Е_d,n легко рассчитываются, когда известны e, d, p, q. Если известны e и n, но p и q неизвестны, то Е_e,n представляет собой одностороннюю функцию; нахождение Е_d,n по заданному n равносильно разложению n. Если p и q - достаточно большие простые, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.

Пользователь i выбирает пару различных простых p _i и q _i и рассчитывает пару целых (e_i, d_i), которые являются простыми относительно j(n_i), где n _i= p _i q _i. Справочная таблица содержит публичные ключи {(e_i,n_i)}.

Предположим, что исходный текст

x =(x ₀, x ₁,..., x _n-1), x ÎZ_n, 0 £ i < n,

сначала представлен по основанию n _i:

N = c₀+c_{i n i}+....

Пользователь i зашифровывает текст при передаче его пользователю j, применяя к n отображение Ed_i,n_i:

N ® Ed_i,n_i n = n ’.

Пользователь j производит дешифрование n ’, применяя Ee_i,n_i:

N’ ® Ee_i,n_i n ’= Ee_i,n_i Ed_i,n_i n = n.

Очевидно, для того чтобы найти инверсию Ed_i,n_i по отношению к Ee_i,n_i, требуется знание множителей n = p _i q _i. Время выполнения наилучших из известных алгоритмов разложения при n =10¹⁰⁰ на сегодняшний день выходит за пределы современных технологических возможностей.

Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA.

Пример: Зашифруем сообщение “САВ”. Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).

1. Выберем p =3 и q =11.

2. Определим n =3*11=33.

3. Найдем (p -1)(q -1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d =3.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А®1, В®2, С®3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.