Современные криптографические системы

Размещено на http://www.allbest.ru/

Лекция 8

Современные криптографические системы

1. Шифрование данных, как средство защиты информации

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

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

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

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

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

1.1 Симметрические криптографические системы

В ряде работ [SIMM79, OENN82] представлены алгоритмы для симметрических систем, и среди них наиболее известным на сегодняшний день является Американский стандарт шифрования данных DES (Data Encryption Standard), который принят в качестве федерального стандарта США [FIPS77]. Существенным дополнением к нему являются японский ускоренный алгоритм шифрования данных FEAL (Fast Enciphering Algorithm) и алгоритм B-Crypt Британской службы телекоммуникаций, реализованный в виде, модуля для шифрования потока сообщений [VARA86].

Стандарт шифрования данных DES

Основу криптографического алгоритма, используемого при проектировании большинства устройств шифрования, составляет стандарт шифрования данных DES. Соответствующий алгоритм принят в качестве стандарта США. Он также поддержан Американским национальным институтом стандартов ANSI (American National Standards Institute) и рекомендован для применения Американской ассоциацией банков ABA.

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

Дешифрирование должно выполняться с использованием того же ключа, который использовался для шифрования, но с измененным способом адресации битов ключа и так, чтобы процедура дешифрования была обратная процедуре шифрования. Блок, который должен быть зашифрован, подвергается тщательной перестановке IP (Initial Permutation), сложным преобразованиям, зависящим от ключа защиты, и перестановке, которая является обратной по отношению к начальной IP. Преобразования, зависящие от значения ключа, могут быть описаны в виде функции f, называемой функцией шифрования и функцией KS, называемой таблицей ключей

(Key Schedule).

Обозначим через input входную 64-битовую строку, которую следует зашифровать (исходный текст), и output - соответствующую 64-битовую выходную строку (шифрованный текст), L и R - 32-битовые строки и LR - их конкатенацию (объединение) в 64-битовую строку. Пусть KS - функция, которая в зависимости от целого числа п из диапазона 1-16 и 64-битового входного блока KEY формирует 48-битовый блок К. Последний является результатом перестановки битов с блока KEY, поэтому

Алгоритм шифрования может быть представлен в виде схемы CRYPTO 1.

шифрование данных асимметрическая криптосистема

Некоторые характеристики DES-алгоритма

Эффект "обвала"

Если небольшое изменение ключа или исходного текста вызывает соответственно малое изменение в шифрованном тексте, это позволяет существенно сократить размер текста или ключа, который необходимо раскрыть. Следовательно, один из основных принципов хорошего криптографического алгоритма состоит в том, чтобы малое изменение исходного текста или ключа приводило к значительному изменению шифрованного текста. DES-алгоритм обладает этим свойством, названным1 эффектом "обвала" [KONH81]. В работе [MEYE78] показано, что после пяти циклов на каждый бит шифрованного текста окажут влияние все биты исходного текста и ключа. Это свойство посимвольной зависимости можно использовать для выявления ошибки или подтверждения подлинности.

Свойство операции дополнения

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

где Ек - операция шифрования с ключом К;

X - исходный текст;

Е, К, X - операции дополнения (побитовой инверсии).

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

Анализ DES-алгоритма показывает, что развернутое преобразование исходного текста представляет собой сложный процесс с вектором ключей К, на каждом цикле. Обозначим этот процесс функцией f. Тогда

где E(R.) - развернутая форма преобразования исходного текста на 1-м цикле; 0 - операция ИСКЛЮЧАЮЩЕЕ ЩЕЙ. , Функция / не изменяется, если использовать дополнения R, и Кж, т.е.

Поскольку

(дополнение исходного текста X означает дополнение L0 и R0. Дополнение ключа К означает дополнение ключей K1 ,...,К16, что приводит к дополнению L1 и R1 По индукции это свойство распространяется на и, следовательно, на шифрованный текст С. Благодаря свойству дополнительности DES-алгоритма криптоаналитик, имея Y1 = Ек(X) и Y2 =Ek (X) для произвольного исходного текста X, может сократить число исследуемых ключей в 2 раза от 256 до 255. Криптоаналитик зашифровывает текст X всеми ключами К, которые начинаются с бита 0. Результирующий текст С сравнивается с У1 и Y2. Если С <> Y1 то используемый ключ не равен К, а если С <> Y2, ключ не равен ключу, начинающемуся с 1. Следовательно, такая симметрия сокращает объем исследований вдвое.

Недостатки DES-алгоритма

К недостаткам DES-алгоритма относятся:

малый размер ключа,

отсутствие публикаций по алгоритмам проектирования,

малое число циклов,

относительно простои алгоритм назначения ключей.

сложность перестановок IP и IP.

1.2 Асимметрические (открытые) криптосистемы

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

В этих системах фазы шифрования и дешифрования отделены, и защита сообщения обеспечивается без засекречивания ключа шифрования, поскольку он не используется при дешифровании. Поэтому ключ публикуется вместе с алгоритмами шифрования и дешифрования, и это не приносит вреда защите системы. Принцип функционирования системы с открытыми ключами шифрования заключается в следующем: пользователь i шифрует сообщение М, используя открытый ключ шифрования пользователя j, и посылает шифрованное сообщение пользователю j по незащищенному каналу передачи данных. Только пользователь j может выполнить дешифрование, чтобы восстановить М, поскольку только он знает секретный ключ дешифрования. Алгоритмы шифрования Е(Encryption) и дешифрования D (Decryption) в таких системах характеризуются следующими свойствами [RIVE78]:

Свойство 1. Дешифрование шифрованного сообщения восстанавливает исходное сообщение М, т. е.

Свойство 2. Алгоритмы шифрования Е и дешифрования D являются простыми в реализации.

Свойство 3. При раскрытии алгоритма шифрования Е алгоритм дешифрования D не раскрывается, т. е. только получатель или отправитель могут дешифровать сообщение, зашифрованное алгоритмом Е, т. е. выполнить алгоритм дешифрования D.

Свойство 4. Если сообщение М сначала дешифровано, а затем зашифровано, то справедливо условие

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

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

Как функция у =f(x), она вычисляется просто.

Имеет обратную функцию.

Обратную функцию крайне сложно вычислить.

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

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

Криптографическая система RSA (Rivest-Shamir-Adleman)

Обходной путь в асимметрической схеме системы RSA основан на замене процедуры нахождения больших простых чисел процедурой их разложения на множители.

Принцип, системы RSA, можно описать следующим образом. Получатель выбирает два больших простых числа p и qтак, чтобы произведение n=pq находилось за пределами вычислительных возможностей. Исходное сообщение М может иметь произвольную длину в диапазоне 1 < М < п. Шифрованный текст С, соответствующий сообщению М, может быть получен из перестановки

Исходный текст М восстанавливается из шифрованного С обратным преобразованием

Алгоритм шифрования RSA-методом следующий:

Шаг 0: Задать входную последовательность

input

Шаг 1: Пусть - двоичное представление числа e

Шаг 2: Установить С=1

Шаг 3: Повторять шаги 3а и 3б для i=k…1,0

3а: Присвоить С значение остатка от деления С2 на n

3б: Если ei=1, то присвоить С значение остатка от деления С input на n

Шаг 4: Останов. С- шифрованный текст входа input.

Порядок дешифрирования следующий:

Получатель выбирает e и d так, чтобы выполнялись условия:

а) НОД (е, Ф(n))=1;

б) ed = 1 (mod Ф(n)) где

Ф(n) - функция Эйлера (p-1)(q-1)

НОД(a,b) - наибольший общий делитель двух чисел;

Работа схемы шифрования-дешифрования основана на теореме Эйлера, которая устанавливает, что для любого целого М, взаимно простого с n, справедливо

Используя условие б) получим для некоторого целого K

Для всех M, не делящихся на p, выполняется сравнение

Поскольку Ф(n) кратно (p-1), справедливо

Когда , то предыдущее уравнение выполняется тривиально. По аналогии, для q справедливо

По теореме остатков для всех М справедливо

В этой системе числа е и п являются несекретными и определяют ключ шифрования. Числа d, p, и q сохраняются секретными и определяют ключ дешифрования. Если п легкоразложимо на множители р и q, то криптоаналитик найдет F(n), а затем d и раскроет систему шифрования.

Выбор показателей степени при кодировании

Выбрав простые числа р и q, а следовательно, и п, необходимо приступить к выбору показателей степени eиd. Для этого d выбирается из условия, чтобы оно было взаимно |простым с Ф(n). Это достигается вычислением остатка d(mod n) и НОД(d, Ф(и)) с помощью алгоритма Евклида. Алгоритм позволяет не только проверить, являются ли числа d и Ф(п) взаимно простыми, но также подсчитать мультипликативно - обратный к d показатель степени е. Известно, что сложность вычисления функции HОД имеет временную оценку O(log2n) [KNUT81]. На выбор показателей е к d необходимо наложить условие, чтобы эти величины превышали log2n. Если е < log2n, то малые сообщения окажутся незашифрованными.

Если будет выполняться условие , то шифр раскрывается простым перебором. Если d < log2n, то система может быть раскрыта только случайно.

Существует еще одно условие при выборе е. Как уже упоминалось, чтобы осуществить перестановки в сообщении в соответствии с функцией xе, е должно быть взаимно простым с функцией Эйлера Ф(n), или,

более точно, взаимно простым с НОК - наименьшим общим кратным следующих чисел:

Среди этих перестановок есть и такие, которые сохраняют сообщение, и они удовлетворяют условию конгруэнтности

где е - нечетное число, большее 3, и n=рд. Известно, что любое решение уравнения удовлетворяет и первому уравнению. Далее отметим, что второе уравнение имеет 9 решений в диапазоне чисел 1 < х < п-1 (n=pq).

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

Криптографический анализ RSA-системы

Вероятно, главной целью криптографического раскрытия является определение секретного показателя степени d. Известны три способа, которыми мог бы воспользоваться криптоаналитик для раскрытия величины d по открытой информации j паре (е, n).

Факторизация п

Разложение величины п на простые множители позволяем вычислить функцию Ф(n) и, следовательно, скрытое значения d, используя уравнение .

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

Вычисление Ф(п) без факторизации

Другой возможный способ криптоанализа связан с непосредственным вычислением функции Эйлера Ф(n) без факторизации п. В работе [RIVE78] показано, что прямое вычисление Ф(п) нисколько не проще факторизации п, поскольку Ф(п) позволяет после этого легко факторизовать п. Это можно видеть из следующего примера. Пусть

Зная Ф(n), можно определить х и, следовательно, у; зная х и у, простые р и q можно определить из следующих соотношений

Прямая оценка d без факторизации п или вычисления Ф(n)

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

где k - произвольное целое число.

Факторизацию п можно выполнить, используя любое значение, кратное F(n). Дешифровщик, с другой стороны, может попытаться найти некоторую величину d', которая была бы эквивалентна скрытой величине d, использованной при разработке шифра. Если существует много таких d', то можно попытаться использовать прямой перебор, чтобы раскрыть шифр. Но все d' различаются множителем, равным НОК(р-1, q-1), и если этот множитель вычислен, то п можно факторизовать. Таким образом, нахождение d' столь же сложно, сколь и факторизация п.

Размещено на Allbest.ru