Реферат: Обзор современных средств криптографии
Реферат: Обзор современных средств криптографии
Министерство высшего образования Российской Федерации
Красноярский Государственный Технический Университет
Реферат по дисциплине Основы Информационной Безопасности на тему:
Современные средства криптографии
Выполнил: студент гр. ВТ21-4
Якушенок Сергей Александрович
Проверил:
Отческих Михаил Анатольевич
Красноярск 2003 г.
По словарю Владимира Даля криптография – тайно-писанное, шифрованное
тарабарское письмо, знаками вместо букв.
Информационная безопасность.
В настоящее время используются следующие услуги безопасности:
Аутентификация. Различают аутентификацию партнеров по взаимодействию и
аутентификацию источника данных (сообщений).
Аутентификация партнеров по взаимодействию используется при установлении
соединения или выполняется периодически во время сеанса связи и служит для
предотвращения таких угроз, как маскарад и несанкционированное
воспроизведение данных (сообщений) предыдущего сеанса связи.
Аутентификация источника заключается в подтверждении подлинности источника
отдельных сообщений. Следует отметить, что данный вид аутентификации не
обеспечивает защиты от несанкционированного воспроизведения сообщений
предыдущего сеанса.
Управление доступом. Управление доступом обеспечивает защиту от
несанкционированного использования ресурсов сети.
Конфиденциальность данных. Конфиденциальность обеспечивает защиту от
несанкционированного получения информации. Различают следующие
конфиденциальности:
· конфиденциальность при взаимодействии с установлением соединения (в
этом и следующем случае защищается вся пользовательская информация);
· конфиденциальность при взаимодействии без установления соединения;
· конфиденциальность отдельных полей сообщения (избирательная
конфиденциальность);
· конфиденциальность трафика (противодействие различным методам
раскрытия, основанным на анализе потоков сообщения).
Целостность данных. Данная услуга подразделяется на подвиды в зависимости
от того, какой тип взаимодействия используется – с установлением соединения или
без, защищается ли сообщение целиком или только отдельные поля, обеспечивается
ли восстановление в случае нарушения целостности.
Принадлежность. Данная услуга (доказательство принадлежности в случае
отказа от ранее переданного/принятого сообщения) обеспечивает:
· доказательство принадлежности с подтверждением подлинности источника
сообщений;
· доказательство принадлежности с подтверждением доставки.
Для реализации услуг безопасности могут использоваться следующие механизмы и
их комбинации.
Шифрование. Шифрование подразделяется на симметрическое (один и тот же
секретный ключ для шифрование и дешифрование) и ассиметрическое (различные
ключи для шифрования и дешифрования).
Электронная (цифровая) подпись. Механизм электронной подписи включает в
себя две процедуры:
· выработку (вычисление подписи);
· проверку подписанных сообщений.
Процедура выработки подписи использует информацию, известную только
подписывающему. Процедура проверки подписи является общедоступной, при этом,
однако, она не позволяет раскрывать секретную информацию подписывающего.
Механизмы управления доступом. В ходе принятия решения о предоставлении
запрашиваемого доступа могут использоваться следующие виды и источники
информации:
· базы данных управления доступом. В такой базе, поддерживаемой
централизованно или на оконченных системах, могут храниться списки управления
доступом или структуры аналогичного назначения;
· пароли или иная аутентификация информации;
· различные удостоверения, предъявление которых свидетельствует о
наличии прав доступа;
· метки безопасности, ассоциированные с субъектами и объектами доступа;
· время запрашиваемого доступа;
· маршрут запрашиваемого доступа;
· длительность запрашиваемого доступа.
Механизмы управления доступом могут находиться у любой из взаимодействующих
сторон или в промежуточной точке. В промежуточных точках целесообразно
проверять права доступа к коммуникационным ресурсам. Требования механизма,
расположенного на приемном конце, должны быть известны заранее, до начала
взаимодействия.
Механизмы контроля целостности. Различают два аспекта целостности:
целостность сообщения или отдельных его полей и целостность потока сообщений.
Процедура контроля целостности отдельного сообщения (или поля) включает в
себя два процесса – один на передающей стороне, другой на приемной. На
передающей стороне к сообщению добавляется избыточность (та или иная
разновидность контрольной суммы), которая является функцией сообщения.
Полученное приемной стороной сообщение также используется для вычисления
контрольной суммы. Решение принимается по результатам сравнения принятой и
вычисленной контрольной суммы. Отметим, что данный механизм не защищает от
несанкционированного воспроизведения (например дублирования) сообщений.
Для проверки целостности потока сообщений (то есть для защиты от изъятия,
переупорядочивания, реплицирования и вставки сообщений) используються
порядковые номера, временные метки, криптографические методы (в виде
различных режимов шифрования) или иные аналогичные приемы.
При взаимодействии без установления соединения использование временных меток
может обеспечить частичную защиту от несанкционированного воспроизведения
сообщений.
Механизмы аутентификации. Аутентификация может достигаться за счет
использования паролей, персональных карточек или иных устройстваналогичного
назначения, криптографических методов, устройств измерения и анализа
биометрической информации.
Аутентификация бывает односторонней (например, клиент доказывает свою
подлинность серверу) и двусторонней (взаимной). Пример односторонней
аутентификации – вход пользователя в систему.
Для защиты от несанкционированного доступа воспроизведения аутентификационной
информации могут использоваться временные метки и система единого времени, а
так же различные методы на основе хеш-функций.
Механизм дополнения («набивки») трафика. Механизм «набивки» трафика
эффективны только в сочетании с мерами по обеспечению конфиденциальности; в
противном случае злоумышленник сможет выделить полезные сообщения из общего
потока, содержащего шумовую «набивку».
Механизм нотаризации. Механизм нотаризации служит для заверения
подлинности. Заверение обеспечивается надежной третьей стороной, которая
обладает достаточной информацией, для того, чтобы ее заверениям можно было
доверять. Как правило, нотаризация опирается на механизм электронной цифровой
подписи.
Общие принципы и модели.
Криптография составляет основу сформулированных выше услу безопасности и
является наиболее мощным средством обеспечения конфиденциальности, контроля
целостности и аутентификации.
Рис 1.
Базовая модель (рис 1) предполагает существование противника, имеющего доступ к
открытому каналу связи и перехватывающего путем прослушивания все
сообщения, передаваемые от отправителя к получателю. Прослушивание со стороны
противника называется пассивным перехватом сообщений. Кроме того
противник может активно вмешиваться в процесс передачи информации –
модифицировать передаваемые сообщения и даже изымать сообщения из канала. Такие
действия называются активным перехватом сообщений.
Способы противодействия основаны на применении криптографических методов.
Классическая одноключевая (или симметрическая) криптосистема представлена на
рис. 2.
Рис 2.
Прежде чем передать сообщение в открытый канал, отправитель с целью сокрытия
истинного содержания подвергает исходную информацию специальному
преобразованию. Для получения исходной информации на приемном конце необходимо
выполнить обратное преобразование. Процедура прямого преобразования на
передающем конце называется шифрованием, процедура обратного
преобразования называется дешифрованием. В одноключевой криптосистеме для
выполнения процедур шифрования и дешифрования необходимо знать общий для
отправителя и получателя секретный компонент – секретный ключ.
Противник, наблюдая шифротекст, не может прочитать открытый текст. Для
осуществления своей цели криптоаналитик применяет атаки. Известны
следующие классические атаки (в порядке возрастания эффективности).
Атака на основе известного шифротекста. Криптоаналитик располагает только
шифротекстом, который всегда можно получить из канала и на его основе
раскрывает секретный ключ.
Атака на основе известного открытого текста. Криптоаналитик располагает
нужным количеством пар «открытый текст/шифротекст». На практике число ключей,
как правиол, существенно меньше числа передаваемых сообщений. Это означает, что
один ключ используеться для шифрования серии открытых текстов. Таким образом
раскрытие ключа позволяет прочитать все сообщения, зашифрованные на этом ключе
(например, все сообщения одного сеанса связи).
Атака на основе выборочного открытого текста. Криптоаналитик имеет
возможность навязывать отправителю нужный ему открытый текст и получать его в
зашифрованном виде. Все открытые тексты должны быть выбраны заранее – до
получения соответствующих шифротекстов. В зарубежных источниках такую атаку
часто называют «полуночной», или атакой «короткой передышки» - как шутливое
напоминание о том, что противник может воспользоваться криптографическим
устройством и зашифровать подготовленные заранее открытые тексты в тот момент,
когда криптограф оставит свое рабочее место для короткого отдыха. Особенно
эффективной атака может быть, например, в случае если криптоаналитик завладел
устройством (Smart Card, PCMCIA и т.д.), содержащий секретный ключ. При
разработке большинства криптографических устройств применяеться специальная
технология (TEMPEST), не позволяющая считывать секретную информацию с помощью
внешнего воздействия. Однако криптоаналитик может попытаться раскрыть ключ,
работая с устройством как с «черным ящиком», то есть подавая на него
определенный открытый текст, и анализируя полученный шифротекст.
Адаптивная атака на основе выборочного открытого текста. Частный случай
атаки на основе выборочного открытого текста. Криптоаналитик может не только
выбирать шифруемый текст, но и осуществлять свой последующий выбор на основе
полученный результатов шифрования.
Атака на основе выборочного шифротекста. Это частный случай атаки на
основе выборочного шифротекста. Выбирая очередной шифротекст, криптоаналитик
уже знает все открытые тексты, соответствующие всем ранее выбранным
шифротекстам.
Атака на основе выборочного текста. Криптоаналитик имеет возможность
атаковать криптосистему как со стороны отправителя, так и со стороны получателя
– выбирать открытые тексты и шифротексты, шифровать и дешифровать их. Данная
атака может быть адаптивной с любой стороны.
Практическая криптосистема должна выдерживать все разновидности описанных
выше атак.
Для решения в первую очередь задачи распределения ключей была выдвинута
концепция двухключевой (или асимметрической) криптографии (рис. 3).
Рис 3.
В такой схеме для шифрования и дешифрования применяються различные ключи. Для
шифрования информации, предназначенной конкретному получателю, используют
уникальный открытый ключ получателя-адресата. Соответственно для дешифрования
получатель использует парный секретный ключ. Для передачи открытого ключа от
получателя к отправителю секретный канал не нужен. Вместо секретного канал
используют аутентичный канал, гарантирующий подлинность источника
передаваемой информации (открытого ключа отправителя). Подчеркнем, что
аутентичный канал являеться открытым и доступен криптоаналитику противника.
Однако механизм аутентификации позволяет обнаруживать попытки нарушения
целостности и подлинности передаваемой информации (в этом смысле
аутентификация имеет ряд аналогий с методами помехоустойчивого кодирования, в
частности с кодами, обнаруживающими ошибки). Отсутствие аутентификации
позволило бы противнику заменить открытый ключ получателя на свой собственный
открытый ключ. В этой ситуации противник получает доступ ко всей адресованной
получателю информации.
Другое уникальное свойство двухключевых криптосистем заключается в
возможности доказательства принадлежности в случай отказа
отправителя/получателя от ранее переданного/принятого сообщения и достигается
применением цифровой подписи (рис. 4).
Рис. 4
Цифровая подпись обеспечивает также аутентификацию и контроль целостности
передаваемой информации. Процедура вычисления и проверки подписи отличается
порядком применения ключей.
Предъявив аутентичный открытый ключ отправителя, всегда можно доказать, что
принятое сообщение было зашифровано на парном секретном ключе, то есть
принадлежит отправителю. Получатель знает только открытый ключ, которым
пользуется для проверки подписи, и поэтому не может подписать сообщение от
лица отправителя.
Ассиметричные криптосистемы могут быть атакованы теми же способами, что и
симметричные. Однако следует иметь в виду, что в ассиметричной криптосистеме
криптоаналитик знает открытый ключ по определению и, следовательно, атака на
открытом тексте всегда возможна. Существует специфическая атака на основе
проверки шифротекста, когда криптоаналитик, зная открытый ключ, может заранее
зашифровать достаточное количество открытых текстов (при условии, что их не
очень много) и затем сравнивая полученные шифротексты с перехваченными,
раскрыть передаваемый открытый текст.
Гольдвассер, Микали и Ривест предложили классификацию атак для схем цифровой
подписи. Приведем эти атаки в порядке возрастания эффективности.
Атака на основе известного открытого ключа. Криптоаналитик знает только
открытый ключ для проверки цифровой подписи. Атака всегда возможна.
Атака на основе известного сообщения. Криптоаналитик знает открытый ключ
и может получить некоторое количество подписанных сообщений. Однако на выбор
этих сообщений он повлиять не может.
Атака на основе выборочного сообщения. Криптоаналитик может выбрать
необходимое количество сообщений и получить их подписи. Предполагается, что
выбор сообщений выполняется до того, как открытый ключ будет опубликован.
Направленная атака на основе выборочного сообщения. Атака аналогична
предыдущей с той разницей, что сообщения выбираются, когда открытый ключ уже
известен.
Адаптивная атака на основе выборочного сообщения. Атака аналогична
предыдущей, но криптоаналитик выбирает сообщения последовательно, исходя из
вычисленных подписей для ранее выбранных сообщений.
Симметричные криптосистемы и блочные шифры.
Криптографическое преобразование составляет основу любого блочного шифра.
Прямое криптографическое преобразование (шифрование) переводит блок открытого
текста в блок шифротекста той же длины. Обратное криптографическое
преобразование (дешифрование) переводит блок шифротекста в исходный блок
открытого текста. Необходимое условие выполнения как прямого, так и обратного
криптографического преобразования – наличие секретного ключа. Шифры, в
которых прямое и обратное преобразование выполняются над блоками
фиксированной длины, называются блочными. Для многих блочных шифров
разрядность блока составляет 64 бита. Прямое криптографическое преобразование
обладает следующим свойством: различные блоки открытого текста отображаются в
различные блоки шифротекста. При обратном преобразовании соответствие
сохраняется. Прямое преобразование можно рассматривать как перестановку на
множестве сообщений с фиксированным размером блока. Результат перестановки
носит секретный характер, что обеспечивается секретным компонентом – ключом.
Конструкция Фейстеля.
Конструкция Фейстеля, или сеть Фейстеля представляет собой разновидность
интерированного блочного шифра. При шифровании блок открытого текста
разбивается на две равные части – правую и левую. Очевидно, что длина блока при
этом должна быть четной. На каждом цикле одна из частей подвергается
преобразованию при помощи функции f и вспомогательного ключа ki
, полученного из исходного секретного ключа. Результат операции суммируется по
модулю 2 с другой частью. Затем левая и правая часть меняются местами.
Преобразования на каждом цикле идентичны, но на последнем не выполняется
перестановка. Процедура дешифрования аналогична процедуре шифрования, однако k
i выбираются в обратном порядке. Конструкция Фейстеля хороша тем, что
прямое и обратное криптографические преобразования для такого блочного шифра
имеют идентичную структуру.
Конструкция Фейстеля применяеться в криптоалгоритмах DES, ГОСТ 28147-89,
Lucifer, FEAL, Khufu, Khare, LOKI, COST, CAST, Blowfish, и др. Блочный шифр,
использующий такую конструкцию, является обратимым и гарантирует возможность
восстановления входных данных функции f на каждом цикле. Сама функция
f не обязательно должна быть обратимой. При задании произвольной функции
f не потребуется реализовывать две различные процедуры – одну для
шифрования, а другую для дешифрования. Структура сети Фейстеля автоматически
позаботиться об этом.
Федеральный стандарт США – DES.
Стандарт шифрования данных DES (Data Encrypting Standard), который ANSI
называет Алгоритмом шифрования данных DEA (Data Encrypting Algorithm), а ISO
– DEA-1, за 20 лет стал мировым стандартом . За годы своего существования
он выдержал натиск различных атак и при известных ограничениях все еще
считается криптостойким.
DES представляет собой блочный шифр, шифрующий данный 64-битовыми блоками. С
одного конца алгоритма вводиться 64-битовый блок открытого текста, а с
другого конца выходит 64-битный блок шифротекста.
DES является симметричным алгоритмом: для шифрования и дешифрования
используется одинаковые алгоритм и ключ (за исключением небольших различий в
использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется
64-битным числом, но каждый восьмой бит используеться для проверки четности и
игнорируется.) Ключ, который может быть любым 56-битовым числом, можно
изменить в любой момент времени. Криптостойкость полностью определяется
ключом. Фундаментальным строительным блоком DES является комбинация
подстановок и перестановок. DES состоит из 16 циклов (рис. 5).
Рис. 5
В общем цикл преобразования представлен на рис. 6. Если Li и Ri
– левая и правая половины, полученные в результате i-й итерации, Ki –
48-битный ключ для цикла i, а f – функция, выполняющая все подстановки,
перестановки и XOR с ключом, то один цикл преобразования можно представить как
(Li, Ri) = (Ri-1, Li
-1 (XOR) f(Ri-1, Ki)).
DES является шифром Фейстеля и сконструирован так, чтобы выполнялось полезное
свойство: для шифрования и дешифрования используеться один и тот же алгоритм.
Единственное отличие состоит в том, что ключи должны использоваться а
обратном порядке.
То есть если при шифровании использовались ключи K1, K2,
.,K16, то ключами дешифрования будут K16, K15,
., K1. Алгоритм использует только стандартную арифметику 64-битовых
чисел и логические операции, поэтому легко реализуется на аппаратном уровне.
DES работает с 64-битовыми блоками открытого текста. После первоначальной
перестановки блок разбивается на правую и левую половины длиной по 32 бита.
Затем выполняются 16 преобразований (функция f), в которых данные
объединяются с ключом. После шестнадцатого цикла правая и левая половины
объединяються, и алгоритм завершается заключительной перестановкой (обратной по
отношению к первоначальной). На каждом цикле (рис. 6) биты ключа сдвигаются, и
затем из 56 битов ключа выбираются 48 битов. Правая половина данных
увеличивается до 48 битов с помощью перестановки с расширением, объединяется
посредством XOR с 48 битами смещенного и перестановленного ключа, проходит
через S-блоков, образуя 32 новых бита, и переставляются снова. Эти четыре
операции и выполняются функцией f.
Рис. 6
Затем результат функции f объединяется с левой половиной с помощью
другого XOR. В итоге этих действий появляется новая правая половина, а старая
становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16
циклов DES.
Стандарт России – ГОСТ 28147-89
ГОСТ 28147-89 – это блочный шифр с 256-битным ключом и 32 циклами
преобразования, оперирующий 64-битными блоками. В криптоалгоритме также
используется дополнительный ключ, который рассматривается ниже. Для шифрования
открытый текст сначала разбиваеться на левую и правую половины L и R. На i-м
цикле используеться подключ Ki:
Li=Ri-1,
Ri=Li-1 XOR (f(Ri-1, Ki)).
Один цикл криптографического преобразования показан на рис. 7.
Рис 7.
Функция f реализована следующим образом. Сначала правая половина и i-й
складываются по модулю 232. Результат разбивается на восемь
4-битовых подпоследовательностей, каждая из которых поступает на вход своего
S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в
первый S-блок, вторые 4 бита – во второй S-блок и т.д. Каждый S-юлок
представляет собой перестановку чисел от 0 до 15. Например, S-блок может
выглядеть так: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если на входе
S-блока 0, то на выходе 7. Если на входе 1, то на выходе 10 и т.д. Все восемь
S-блоков различны, они фактически являются дополнительным ключевым материалом.
Выходы всех восьми S-блоков объединяются в 32-битное слово, затем все слово
циклически сдвигается влево на 11 битов. Наконец, результат объединяется с
помощью операции XOR с левой половиной, и получается новая правая половина, а
правая половина становиться новой левой половиной. Для генерации подключей
исходный 256-битный ключ разбивается на восемь 32-битных блоков: k1
,k2,.,k8. На каждом цикле используется свой подключ.
Дешифрование выполняется так же, как и шифрование, но инвертируется порядок
подключей ki. Стандарт не определяет способ генерации S-блоков.
Главные различия меду DES и ГОСТом заключаются в следующем:
· DES использует сложную процедуру для генерации подключей из ключей.
В ГОСТе эта процедура очень проста;
· в DES 56-битный ключ, а в ГОСТе – 256-битный. Если добавить
секретные перестановки S-блоков, то полный объем секретной информации ГОСТа
составляет примерно 610 бит;
· у S-блоков DES 6-битные входы и 4-битные выходы, а у S-блоков ГОСТа
4-битные входы и выходы. В обоих алгоритмах используется по восемь S-блоков,
но размер S-блока ГОСТа равен четверти размера S-блока DES;
· в DES используется нерегулярные перестановки, названные P-блоком, а
в ГОСТе используется 11-битный циклический сдвиг влево;
· в DES 16 циклов, а в ГОСТе – 32.
Силовая атака на гост абсолютно бесперспективна. ГОСТ использует 256 битный
ключ, а если учитывать секретные S-блоки, то длина ключа будет еще больше.
ГОСТ, по-видимому более устойчив к дифференциальному и линейному
криптоанализу, чем DES. Хотя случайные S-блоки при некотором выборе не
гарантируют высокой криптостойкости по сравнению с фиксированными S-блоками
DES, их секретность увеличивает устойчивость ГОСТа к дифференциальному и
линейному криптоанализу. К тому же эффективность этих криптоаналитических
методов зависит от количества циклов преобразования – чем больше циклов, тем
труднее криптоанализ. ГОСТ использует в два раза больше циклов, чем DES, что,
возможно, приводит к несостоятельности дифференциального и линейного
криптоанализа. ГОСТ не использует существующую в DES перестановку с
расширением. Удаление этой перестановки из DES ослабляет его из-за ументшения
лавинного эффекта; разумно предположить, что отсутствие такой операции в
ГОСТе отрицательно сказывается на его криптостойкости. С точки зрения
криптостойкости операция арифметического сложения, используемая в ГОСТе, не
хуже, чем операция XOR в DES. Основным различием представляется использование
в ГОСТе циклического сдвига вместо перестановки. Перестановка DES увеличивает
лавинный эффект. В ГОСТе изменение одного входного бита влияет на один S-блок
одного цикла преобразования, который затем влияет на два S-блока следующего
цикла, затем на три блока следующего цикла и т.д. Потребуется восемь циклов,
прежде чем изменение одного входного бита повлияет на каждый бит результата;
в DES для этого нужно только пять циклов. Однако ГОСТ состоит из 32 циклов, а
DES только из 16. Разработчики ГОСТа пытались достигнуть равновесия между
криптостойкостью и эффективностью. Взяв за основу конструкцию Фейстеля, они
разработали криптоалгоритм, который лучше, чем DES, подходит для программной
реализации. Для повышения криптостойкости введен сверхдлинный ключ и удвоено
число циклов. Однако вопрос, увенчались ли усилия разработчиков созданием
более криптостойкого, чем DES, криптоалгоритма, остается открытым.
Так же существуют другие известные блочные шифры, такие как RC2, RC5, IDEA,
SAFER, FEAL, Skipjack, Blowfish, REDOC, LOKI, Khufu и др. Но такого
распространения как ГОСТ и DES они не получили, из-за этого рассматривать мы
их не будем.
Асимметричные криптосистемы.
Криптосистема RSA.
Криптосистема RSA, предложенная в 1977 году Ривестом, Шамиром и Адлеманом,
предназначена для шифрования и цифровой подписи. В настоящее время RSA
являеться наиболее распространенной криптосистемой – стандартом де-факто для
многих кирптографических приложений. Статус де-факто послужил причиной
включения криптосистемы RSA в принятые ранее криптографические стандарты.
Так, финансовый стандарт США ANSI X9.30 предусматривал использование
федерального стандарта цифровой подписи DSS. Выпущенная позднее версия
стандарта ANSI X9.31 была дополнена криптосистемой RSA. Последний является
так же частью многих официальных стандартов, в частности международных
стандартов ISO 9796 и ITU-T X.509, SWIFT, французского финансового стандарта
ETABAC 5, австралийского стандарта управления ключами AS2805.6.5.3.
Криптосистема RSA широко применяется в составе различных стандартов и
протоколов Internet, включая PEM, S/TIME, PEM-MIME, S-HTTP и SSL.
Возможно ли использование RSA в России? С точки зрения правовых норм это
исключено – RSA не входит ни в один из действующих на территории России
кирптографических стандартов. Отметим, что стандарты двухключевого шифрования
и управления ключами в России также пока не приняты. Таким образом,
разработчик криптографических приложений поставлен перед выбором: построить
схему управления ключами по методу полной матрицы, экспоненциального
ключевого обмена Диффи-Хеллмана или воспользоваться методом цифрового
конверта (шифрование сеансового ключа при помощи двухключевого
криптоалгоритма).
Недостатки существующего не одно десятилетие метода полной матрицы хорошо
известны. Протокол Диффи-Хеллмана предполагает двусторонний обмен открытыми
ключами и наличие сертификатов у отправителя и получателя сообщений. В случае
односторонней аутентификации (сертификат имеется только у одной из сторон)
предпочтение отдается последнему методу. В этой ситуации выбор RSA вполне
оправдан – метод цифрового конверта на базе криптоалгоритма RSA описан в
стандарте PKCS и применяется в протоколе SSL и других стандартах Internet
(PEM, PEM-MIME и т.д.).
RSA многие годы противостоит интенсивному криптоанализу. Криптостойкость RSA
основана на трудоемкости разложении на множители (факторизации) больших
чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200
двоичных разрядов иил даже больше) простых чисел. Предполагаеться, что задача
восстановления открытого текста по шифротексту и открытому ключу эквивалентна
задаче факторизации.
Для генерации парных ключей используеться два больших случайных простых
числа, p и q. В целях максимальной криптостойкости p и q выбираються равной
длины. Затем вычисляется произведение:
n=pq.
Далее случайным образом выбираеться ключ шифрования e, такой, что e и
φ(n)=(p-1)(q-1) являються взаимно простыми числами. Наконец расширенный
алгоритм Евклида используеться для вычисления ключа дешифрования d, такого,
что
ed=1 mod φ(n).
Другими словами,
d=e-1 mod φ(n).
Заметим, что d и n – так же взаимно простые числа. Числа e и n – открытый ключ,
а d – секретный. Два простых числа p и q хранятся в секрете. Для шифрования
сообщения m необходимо выполнить его разбивку на блоки, каждый из которых
меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая
n). То есть если p и q – 100-разрядные простые числа, то n будет содержать
около 200 разрядов. И каждый блок сообщения mi должен иметь такое же
число разрядов. (Если нужно зашифровать фиксированное число блоков, их можно
дополнить несколькими нулями слева, тобы гарантировать, что блоки всегда будут
меньше n.) Зашифрованное сообщение c будет состоять из блоков ci той
же самой длины. Шифрование сводиться к вычислению
ci=mie mod n.
При дешифровании для каждого зашифрованного блока ci вычисляеться
mi=cid mod n.
Последнее справедливо, так как
Cid=(mie)e=mied=mikφ(n)+1=mi*mi kφ(n)=mi*1=mi.
Все вычисления выполняються по модулю n.
Отметим, что сообщение может быть зашифровано с помощью d, а дешифровано с
помощью e, возможен любой выбор.
Рассмотрим короткий пример. Если
p=47 и q=71, то n=pq=3337.
Ключ e не должен иметь общих множителей с
φ(n)=46*70=3220.
Выберем (случайное) e равным 79. В этом случае d=79-1 mod 3220 =
1019. Опубликуем e и n, сохранив в секрете d. Для шифрования сообщения
m=6882326879666683
сначала разобьем его на блоки. Для выбранных параметров ограничимся блоками по
три десятичных разряда. Сообщение разбивается на шесть блоков mi:
m1=688
m2=232
m3=687
m4=966
m5=668
m6=003
Первый блок шифруется как 68879 mod 3337 = 1570 = c1.
Выполняя те же операции для последующих блоков, создадим шифротекст сообщения:
c=15702756209122762423158.
Для дешифрования нужно выполнить возведение в степень, используя ключ
дешифрования 1019:
15701019 mod 3337 = 688 = m1.
Аналогично восстанавливается оставшаяся часть сообщения.
Эффективность реализации
Существует много публикаций, затрагивающих тему аппаратных реализаций RSA.
Быстродействие аппаратной реализации RSA примерно в 1000 раз ниже, чем
быстродействие аппаратной реализации DES. Быстродействие СБИС-реализации RSA
с 512-битовым модулем – 64 Кбит/сек. Существуют также микросхемы RSA, которые
оперируют с 1024-битовыми числами. В настоящее время разрабатываются
микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1
Мбит/сек. Производители так же реализуют RSA в интеллектуальных карточках,
однако производительность этих реализаций невысока. Программная реализация
DES примерно в 100 раз быстрее программной реализации RSA. Эти оценки могут
незначительно могут незначительно меняться в зависимости от используемых
технологий, но RSA никогда не достигнет производительности симметрических
алгоритмов.
Шифрование RSA выполняются намного эффективнее, если правильно выбрать значение
e. Чаще всего используются 3, 17 или 65537 = 216+1 – двоичное
представление этого числа содержит только две единицы, поэтому для возведения в
степень нужно выполнить лишь 17 умножений. Стандарт X.509 рекомендует число
65537, PEM – 3, PKCS#1 – 3 или 65537. Использование в качестве e любого из
указанных значений (при условии, что сообщение дополняются случайными числами)
не влияет на криптостойкость, даже если одно и то же значение e используется
группой пользователей. Операции с секретным ключом можно ускорить при помощи
китайской теоремы об остатках, если сохранить значения p и q, а так же заранее
по секретному и открытому ключам вычислить вспомогательные значения: d mod
(p-1), d mod (q-1) и q-1 mod p.
Криптостойкость RSA
Предполагается, что криптостойкостью RSA зависит от проблемы разложения на
множители больших чисел. Однако никогда не было доказано математически, что
нужно разложить n на множители, чтобы восстановить m по c и e. Не исключено,
что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот
новый способ позволит криптоаналитику получить d, он также может быть
использован для разложения на множители больших чисел. Так же можно атаковать
RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на
множители. Доказано, что при использовании RSA раскрытие даже нескольких
битов информации по шифротексту не легче, чем дешифрования всего сообщения.
Самой очевидной атакой на RSA является разложение n на множители. Любой
противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ
дешифрования d, противник должен разложить n на множители. Криптоаналитик
может перебирать все возможные d, пока не подберет правильное значение. Но
подобная силовая атака даже менее эффективна, чем попытка разложения n на
множители. В 1993 г. Был предложен метод кирптоанализа, основанный на малой
теореме Ферма. К сожалению, этот метод оказался медленнее разложения на
множители. Существует еще одна проблема. Большинство общепринятых тестов
устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p
или q окажется составным? Тогда у модуля n будет три или более делителей.
Соответственно некоторые делители будут меньше рекомендованной величины, что,
в свою очередь, открывает возможности для атаки путем факторизации модуля.
Другая опасность заключается в генерации псевдопростых чисел (чисел
Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся
простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На
практике, последовательно применяя набор различных тестов на простоту, можно
свести вероятность генерации составного числа до необходимого минимума.
Итоги по безопасности
На основании известных атак можно сформулировать следующие ограничения при
использовании RSA:
- знание одной пары показателей шифрования/дешифрования для данного
модуля позволяет злоумышленнику разложить модуль на множители; - знание
одной пары показателей шифрования/дешифрования для данного модуля
позволяет злоумышленнику вычислить другие пары показателей, не расладывая
модуль на множители; - в криптографических протоколах с использованием
RSA общий модуль использоваться не должен. (Это являеться очевидным
следствием предыдущих двух пунктов.); - для предотвращения
раскрытия малого показателя шифрования сообщения должны быть дополнены
(«набиты») случайными значениями; - показатель дешифрования должен быть
большим.
Отметим, что недостаточно использовать криптостойкий алгоритм; безопасной
должна быть вся криптосистема, включая криптографический протокол. Слабое
место любого из трех компонентов сделает небезопасной всю систему.
Криптосистема ЭльГамаля.
Криптосистему, предложенную ЭльГамалем в 1985 г. Можно использовать как для
цифровых подписей, так и для шифрования. Криптостойкость определяется
трудоемкость вычисления дискретного алгоритма в конечном поле. Криптоалгоритм
не запатентован, но попадает под действие патента на метод экспоненциального
ключевого обмена Диффи-Хеллмана.
Для генерации пары ключей сначала выбираются простое число p и два случайных
числа, g и x; оба этих числа должны быть меньше p. Затем вычисляется
y=gx mod p.
Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы
пользователей. Секретным является x.
Вычисление и проверка подписи
Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно
простое с p-1. Затем вычисляется a=gk mod p, и с помощью
расширенного алгоритма Евклида из уравнения
M=(xa+kb) mod (p-1)
находиться b. Подписью является пара чисел: a и b. Случайное значение k
должно храниться в секрете. Для проверки подписи необходимо убедиться, что
yaab mod p = gM mod p.
Каждая новая подпись требует нового значения k, и это значение должно
выбираться случайным образом. Если злоумышленник раскроет k, используемое
Алисой, он сможет раскрыть секретный ключ Алисы x. Если злоумышленник сможет
получить два сообщения, подписанные при помощи одного и того же k, он сможет
раскрыть x, даже не зная k.
Рассмотрим простой пример. Выберем p=11 и g=2. Пусть секретный ключ x=8.
Вычислим
y=gx mod p = 28 mod 11 = 3.
Открытым ключом являются y=3, g=2 и p=11. Чтобы подписать M=5, сначала
выберем случайное число k=9. Убедимся, что gcd(9,10)=1. Далее вычислим
a=gk mod p = 29 mod 11 = 6,
и затем с помощью расширенного алгоритма Евклида найдем b из уравнения
5=(8*6+9*b) mod 10.
Решение: b=3, а подпись представляет собой пару: a=6 и b=3. Для проверки подписи
убедимся, что yaab mod p = gM mod p:
3663 mod 11 = 25 mod 11.
Шифрование/дешифрование
Некоторая модификация позволяет использовать криптосистему для
шифрования/дешифрования сообщений.
Для шифрования сообщения M сначала выбирается случайное число k, взаимно-
простое с p-1. Затем вычисляются:
a=gk mod p,
b=ykM mod p.
Пара (a,b) является шифротекстом. Отметим, что шифротекст в два раза длиннее
открытого текста.
Для дешифрования (a,b) вычисляются
По сути описанное преобразование – это то же самое, что и экспоненциальный
ключевой обмен по Диффи-Хеллману, за исключением того, что обмен по
Диффи-Хеллману, за исключением того, что - это часть ключа, а при шифровании
сообщение умножается на yk.
Хеш-функции
Односторонняя функция H применяется к сообщению произвольной длины M и
возвращает значение h=H(M) фиксированной длины m. Многие функции позволяют
значение фиксированной длины по входным данным произвольной длины, но
однонаправленные (или односторонние) хеш-функции обладают рядом
дополнительных свойств:
- зная M, легко вычислить h;
- при заданном h задача нахождения M,
для которого H(M)=h, должна быть вычислительно-трудоемкой; - при
заданном M задача нахождения другого сообщения M’, для которого
H(M)=H(M’), должна быть вычислительно трудоемкой.
Смысл применения однонаправленных хеш-функций и состоит в обеспечении для M
уникального значения – «отпечатка пальца» сообщения. Если Алиса подписала M
цифровой подписью с использованием хеш-функции H(M), а боб может создать другое
сообщение M' отличное от M, для которого H(M)=H(M'), то Боб сможет утверждать,
что Алиса подписала сообщение M'. В некоторых приложениях необходимо выполнение
дополнительного требования, называемого устойчивостью к коллизиям.
Смысл данного требования заключается в том, что задача нахождения двух
случайных сообщений M и M', для которых H(M)=H(M’), должна быть
вычислительно-трудоемкой (с экспоненциальным объемом перебора).
Следующий протокол, впервые описанный Юваловым, показывает, как Алиса может
воспользоваться коллизиями для обмана Боба.
- Алиса готовит две версии контракта: одну, выгодную для Боба, и
другую, приводящую его к банкротству. - Алиса вносит несколько
незначительных изменений в каждый документ и вычисляет хеш-функции. (Этими
изменениями могут быть действия, подобные следующим: замена одного пробела
комбинацией пробелов, вставка одного - двух пробелов перед возвратом
каретки и так далее. Производя или не производя по одному изменению в
каждой из 32 строк, Алиса может Легко получить 232 различных
документов.) - Алиса сравнивает хеш-значения для каждого изменения в
каждом из двух документов, разыскивая пару, для которой эти значения
совпадают. (Если выходом хеш-функции является 64-битное значение, Алиса,
как правило, сможет найти совпадающую пару выполнив 232
сравнений.) Таким образом, она получает два документа, дающих одинаковое
значение хеш-функции. - Алиса получает подписанную Бобом выгодную
для него версию контракта, используя протокол, в котором он подписывает
только значение хеш-функции. - Спустя некоторое время, Алиса
подменяет контракт, подписанный Бобом, другим, которого он не подписывал.
Теперь она может убедить арбитра в том, что Боб подписал другой контракт.
Отметим, что могут применяться и другие атаки. Например, противник может
посылать системе автоматического контроля (может быть, спутниковой) случайные
сообщения со случайными цифровыми подписями. В конце концов подпись под одним
из этих случайных сообщений окажется правильной. Противник не сможет узнать,
к чему приведет эта команда, но если его единственной целью является
вмешательство в работу спутника, он своего добьется.
Хеш-функции с 64-битным выходным значением не могут противостоять описанной выше
атаке. Хеш-функции, выдающие 128-битовые значения, имеют определенные
преимущества. Для того, чтобы найти коллизию, придется вычислить значение
хеш-функции придется вычислить значение хеш-функции для 264
случайных документов, чего, впрочем, недостаточно, если безопасность должна
обеспечиваться в течении длительного периода времени.
Федеральный стандарт СШФ – SHS (алгоритм SHA)
Национальный Институт Стандартов США при участии АНБ разработал алгоритм
вычисления хеш-функции SHA, используемый в алгоритме цифровой подписи DSA
стандарта DSS.
Для любого входного сообщения длиной меньше 264 битов SHA выдает
160-битовый «дайджест» сообщения. Далее «дайджест» подается на вход DSA,
который вычисляет подпись для сообщения. Подписывание «дайджеста» вместо
сообщения часто повышает эффективность процесса, так как «дайджест» намного
меньше, чем само сообщение. Тот же «дайджест» сообщения должен быть получен
тем, кто проверяет подпись. При использовании SHA задача поиска сообщения,
соответствующего данному «дайджесту», или двух различных сообщений с одинаковым
«дайджестом» является вычислительно-трудоемкой. Любые изменения сообщения,
произошедшие во время передачи, с очень высокой вероятностью приведут к
изменению «дайджеста», и подпись не пройдет проверку.
Стандарт России – ГОСТ Р 34.11-94
Разработанная российскими криптографами хеш-функция описана в стандарте ГОСТ
34.11-94. В ней используется блочный шифр ГОСТа 28147-89, хотя теоретически
может использоваться любой блочный шифр с 64-битным блоком и 256-битным
ключом. Хеш-функция выдает 256-битное значение.
Еще стоит отметить такие известные хеш-функции, как MD2, MD4, MD5 и RIPEMD-160.
В реферате были рассмотрены все основные составляющие современной
криптографии. Это симметрические криптосистемы, асимметрические криптосистемы
и хеш-функции. Так же был коротко затронут механизм цифровой подписи, и
системы использующееся для этого.
Список используемой литературы:
- Чмора А.Л. Современная прикладная криптография. 2-е изд., стер. –
М.: Гелиос АРВ, 2002. – 256с.: ил. - А.Г. Ростовцев, Н.В. Михайлова
Методы криптоанализа классических шифров. - А. Саломаа
Криптография с открытым ключом.
|
