Системы шифрования с открытыми ключами

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ НАЛОГОВЫЙ ИНСТИТУТ»

Кафедра: Экономико – правовая

Дисциплина: «Защита информации»

РЕФЕРАТ

на тему:

Системы шифрования с открытыми ключами

Выполнила

Понкратьева Рита Энверовна

заочная, 2 курс, № группы ВВМс-2

Специальность «Менеджмент организации»

Руководитель

заведующий кафедрой общих математических

и естественнонаучных дисциплин

доктор исторических наук, доцент

Бардыго Н.С

Москва 2011

Содержание

Введение                                                                                                                                                                        3

1 Описание метода шифрования с открытым ключом                                                   5

1.1 Криптография с открытым ключом                                                                                                  5

1.2 Структура программы                                                                                                                       12

2 Эллиптические функции – реализация метода открытых ключей   15

2.1 Типы криптографических услуг                                                                                                          15

2.2 Электронные платы и код с исправлением ошибок                                                  20

Заключение                                                                                                                                                    22

Список использованных источников                                                                                            23

3

Введение

На протяжении многих веков человечество использовало криптографические методы для защиты информации при ее передаче и хранении. Приблизительно к концу XIX в. эти методы стали объектом математического изучения. Отрасль математики, изучающая защиту информации, традиционно называется криптологией (cryptology) и подразделяется на криптографию (cryptography), занимающуюся разработкой новых методов и обоснованием их корректности, и криптоанализ (cryptanalysis), задача которого - интенсивное изучение существующих методов, часто с целью реального раскрытия секретов другой стороны. Криптография и криптоанализ находятся в тесном взаимодействии друг с другом и с практическими нуждами и развиваются параллельно закрытыми правительственными организациями многих государств и международным научным сообществом.

В настоящее время существуют тысячи криптографических систем, реализованных как программно, так и аппаратно. Среди них можно выделить системы, сам криптографический принцип работы которых держится в секрете, как, например, микросхема Clipper, предлагаемая правительством США в качестве криптографического стандарта для телекоммуникаций, и системы, алгоритм которых открыт, а секретной является только определенная, как правило небольшая, порция информации, называемая (секретным) ключом [(secret) key] - к ним относится большинство систем, реализуемых программно и предназначенных для широкого использования. В дальнейшем мы будем рассматривать только системы второго типа.

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

4

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

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

5

1.Описание метода шифрования с открытым ключом

1.1 Криптография с открытым ключом

В 1976 г. У.Диффи и М.Хеллманом (DH76) был предложен новый тип криптографической системы - система с открытым ключом (public key cryptosystem). В схеме с открытым ключом имеется два ключа, открытый (public) и секретный (private, secret), выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений.

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

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

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

6

цифровую подпись, но не поддерживают шифрование.

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

Из-за особенностей алгоритмов, лежащих в основе систем с открытым ключом, их быстродействие при обработке единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа - полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция (дайджест) (one-way hash function, digest), представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или

7

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

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

Система RSA

В 1978 г. Р.Ривест, А.Шамир и Л.Адлеман (RSA78) создали первую криптосистему с открытым ключом для шифрования и цифровой подписи, получившую название RSA (по первым буквам фамилий авторов). Система описывается в терминах элементарной теории чисел. Ее надежность обуславливается практической неразрешимостью задачи разложения большого натурального числа на простые множители. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита - безусловно надежным. Длина подписи в системе RSA совпадает с длиной ключа.

8

Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, а также задачи разложения на множители к классу NP-полных задач, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов.

Способы взлома криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака: найти закрытый ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым (public) ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудноразрешимой задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления частного (private) ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M (mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть

9

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

Существуют и другие типы атак, позволяющие, однако, вскрыть только одно сообщение и не позволяющие нападающему вскрыть прочие сообщения, зашифрованные тем же ключом. Самое простое нападение на единственное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, например, "Нападение на рассвете", затем шифрует предполагаемый текст открытым (public) ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака единственного сообщения применяется в том случае если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M. Такую атаку можно предотвратить вводя в сообщение перед каждым шифрованием несколько случайных бит. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.

Разумеется, существуют и атаки нацеленные не на криптосистему

10

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

Проект DSS

В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота.

Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля (E85) в варианте Шнорра (S89). Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.

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

11

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

Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи.

Вместе с проектом DSS опубликован проект стандарта SHS (Secure Hash Standard), описывающий однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.

Российский стандарт цифровой подписи

В 1993 г. в России были изданы два государственных стандарта “Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма” и “Функция хэширования”, под общим заголовком “Информационная технология. Криптографическая защита информации”.

Стандарт “Процедуры выработки и проверки электронной цифровой подписи...” во многом схож со своим американским аналогом DSS. Для формирования и проверки цифровой подписи в нем используется тот же алгоритм Эль-Гамаля и Шнорра, что и в DSS, с незначительными модификациями. Имеется две альтернативных длины ключа, 512 и 1024 бит; длина подписи составляет 512 бит.

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

12

обоснованием алгоритма, в случае российского стандарта несколько

смягчается тем, что элемент ключа q выбирается более длинным, чем в DSA. Критика связанная с отсутствием спецификации на способ получения псевдослучайных чисел, остается в силе.

Как и DSS, российский стандарт определяет только алгоритм цифровой подписи, но не шифрования. Быстродействие обоих алгоритмов приблизительно совпадает.

Стандарт “Функция хэширования” предназначен для использования вместе со стандартом “Процедуры выработки и проверки цифровой подписи” и представляет собой оригинальный алгоритм, основанный на методе шифрования с симметричным ключом ГОСТ 28147. Стандарт не содержит криптографического обоснования выбранного алгоритма и не корректирует ГОСТ 28147 в части заполнения узлов замены.

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

Программная криптографическая система ТерКрипт

Санкт-петербургским МГП “ТЕРКОМ” разработана криптографическая система ТерКрипт, представляющая собой комплекс программ на языке C стандарта ANSI. Система реализует в полном объеме алгоритмы DES, ГОСТ 28147, RSA, DSS/SHS и российских криптографических стандартов. Алгоритмы реализованы на основе общих процедур теории чисел, использующих современные теоретико-числовые методы для достижения максимальной эффективности. Имеется специальная версия системы, оптимизированная для работы на персональных компьютерах IBM AT 286, 386, 486.

1.2 Структура программы

Данная программа написана на языке Object Pascal в соответствии с принципами структурного программирования и представляет собой набор

13

процедур и функций, выполняющих определенные действия основной

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

Рассматриваемая программа предусматривает работу в диалоге с пользователем. Для этого разработана система меню и использована библиотека Borland Delphi.

Основная программа представляет собой три этапа: подготовка к работе, сама работа и её завершение.

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

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

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

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

14

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

- процедура вычисления n и m; в этой же процедуре находится d – взаимообратное число с m и вычисляется e;

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

- функция возведения в степень (результат не должен превышать значение 9*1018);

- процедура зашифрования;

- процедура расшифрования.

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

15

2. Эллиптические функции – реализация метода открытых ключей

2.1Типы криптографических услуг

Сегодня безопасные решения используют некоторую комбинацию из пяти

различных криптографических услуг. Эти услуги:

- Проверка пользователя – введением пути в оперативную транзакцию, пользователь подтверждает, что это именно он.

- Идентификация Начала координат Данных - обеспечение источника сообщения.

- Целостность Данных - обеспечение сохранения данных неправомочными сторонами.

- Не отказ -  получатель транзакции способен демонстрировать нейтральному

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

Существуют два главных типа криптографии симметрично - ключевые и шифрование с открытым ключом, которые основаны на комплексных математических алгоритмах и управляются ключами.

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

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

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

16

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

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

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

Криптосистемы с ключом общего пользования решают ключевые проблемы

управления, связанные с симметрично - ключевым кодированием; однако,

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

Цифровые представления

Цифровые представления – это электронный эквивалент традиционных

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

17

Системы с открытым ключом

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

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

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

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

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

18

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