Московский Государственный Университет им. М. В. Ломоносова
Механико-математический факультет
Реферат
по теории интеллектуальных систем на тему:
«Метод получения цифровой подписи. Система RSA»
Выполнила:
студентка 431 группы
Арюткина Наталия
Москва 2012
Цифровая подпись
Ассиметричные алгоритмы шифрования
Развитие основных типов криптографических протоколов (ключевой обмен, электронно-цифровая подпись (ЭЦП), аутентификация и др) было бы невозможно без создания открытых ключей и построенных на их основе ассиметричных протоколов шифрования.
Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании – другой. Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования – это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение – прочесть его можно только с помощью второго ключа – ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать – зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах "открытым ключом", а вот ключ дешифрования получателю сообщений необходимо держать в секрете – он называется "закрытым ключом".
Таким образом, мы избавляемся от необходимости решать сложную задачу обмена секретными ключами.
Напрашивается вопрос: "Почему, зная открытый ключ, нельзя вычислить закрытый ключ?" – это третье необходимое условие асимметричной криптографии – алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, было невозможно вычислить закрытый ключ.
В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: "открытый" Ej и "закрытый" Dj, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E9 и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент №9, получив послание, производит над ним преобразование с помощью известного только ему ключа D9 и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E7, а для дешифрования – ключ D7).
Как мы видим, во-первых, в асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, при нарушении конфиденциальности k-ой рабочей станции злоумышленник узнает только ключ Dk: это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяет вывадавать себя за него при отправке писем.
Стандарт ассимметричного шифрования RSA
Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-1978 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. В 1993 году метод RSA был обнародован и принят в качестве стандарта (PKCS #1: RSA Encryption standart). RSA можно применять как для шифрования/расшифрования, так и для генерации/проверки электронно-цифровой подписи.
Генерация ключей
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:
Выбираются два простых (!) числа p и q
Вычисляется их произведение n(=p*q)
Выбирается произвольное число e (e Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах. Два числа (e,n) – публикуются как открытый ключ. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n). Шифрование/расшифрование Как же производится собственно шифрование с помощью этих чисел: Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)^e)mod n. Блоки ci и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi. А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y): (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Теперь умножим обе ее части на x: (x(-y)(p-1)(q-1)+1)mod n = 1*x = x. А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m: ((ci)d)mod n = ((mi)e*d)mod n = mi. На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла. Кpиптосистемы на основе эллиптических уpавнений Эллиптические кpивые - математический объект, котоpый может быть опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x,y), удовлетвоpяющее следующему уpавнению: y^2 = x^3 + ax + b, а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA. В pеальных кpиптосистемах на базе эллиптических уpавнений используется уpавнение y^2 = x^3 + ax + b mod p, где p - пpостое. Пpоблема дискpетного логаpифма на эллиптической кpивой состоит в следующем: дана точка G на эллиптической кpивой поpядка r (количество точек на кpивой) и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G. Электронно-цифровая подпись Общие положения При ведении деловой переписки, при заключении контрактов подпись ответственного лица является непременным аттрибутом документа, преследующим несколько целей: Выполнение данных требований основывается на следующих свойствах подписи: Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи. Существует несколько методов посторения ЭЦП, а именно: Кроме перечисленных, существуют и другие методы построения схем ЭЦП: групповая подпись, неоспариваемая подпись, доверенная подпись и др. Появление этих разновидностей обусловлено разнообразием задач, решаемых с помощью электронных технологий передачи и обработки электронных документов. Генерация ЭЦП При генерации ЭЦП используются параметры трех групп: Общие параметры необходимы для функционирования системы в целом. Секретный ключ используется для формирования ЭЦП, а открытый – для проверки ЭЦП. Общими параметрами системы являются простые целые числа p, q, g, удовлетворяющие следующим условиям: p: 2^511 q: простой делитель числа (p-1), который удовлетворяет условию 2^159 g: так называемый генератор, удовлетворяющий равенству g = h^((p-1)/q)mod p >1. Парараметры p, q, g публикуются для всех участников обмена ЭД с ЭЦП. Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете. Открытый ключ вычисляется: y = g^x mod p. Также при описании данной схемы будут использоваться следующие обозначения и дополнительные параметры: m – входное сообщение пользователя для схемы с ЭЦП; k - случайное число, удовлетворяющее условию 0 Процесс генерации ЭЦП состоит из нескольких этапов: 1. Вычисляется хэш-код сообщения m h=H(m) 2. Из диапазона [1,q] случайным образом выбирается значение k и вычисляется r= (g^k mod p) mod q 3. Вычисляется S= (k^-1(h+xr)) mod q, где k^-1 удовлетворяет условию (k^-1*k) mod q =1 Значения r, s являются ЭЦП сообщения m и передаются вместе с ним по каналам связи. Проверка ЭЦП Пусть принято сообщение m1 и его подпись s1,r1. Проверка ЭЦП происходит следующим образом: проверяется выполнений условий 0 Вычисляются значения: w= s1^-1 mod q u1 = (H(m1)w) mod q u2 = ((r1/w) mod q v = (( g^u1y^u2) mod p ) mod q проверяется равенство v = r1 Если последнее равенство выполняется, то подпись принимается. В данном стандарте специфицируется также процедура генерации основных параметров системы и проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s. Атаки на ЭЦП Стойкость большинства схем ЭЦП зависит от стойкости ассиметричных алгоритмов шифрования и хэш-функций. Существует следующая классификация атак на схемы ЭЦП: Каждая атака преследует определенную цель, которые можно разделить на несколько классов: На практике применение ЭЦП позволяет выявить или предотвратить следующие действия нарушителя: Так же существуют нарушения, от которых невозможно оградить систему обмена сообщениями – это повтор передачи сообщения и фальсификация времени отправления сообщения. Противодействие данным нарушениям может основываться на использовании временных вставок и строгом учете входящих сообщений. Некоторые средства работы с ЭЦП В настоящее время существует большое кодичество комплексов для работы с электронной подписью, или использующие ее. Приведем некоторые из них: PGP Наиболее известный - это пакет PGP (Pretty Good Privacy) – (www.pgpi ), без сомнений являетющийся на сегодня самым распространенным программным продуктом, позволяющим использовать современные надежные криптографические алгоритмы для защиты информации в персональных компьютерах. К основным преимуществам данного пакета, выделяющим его среди других аналогичных продуктов следует отнести следующие: 1. Открытость. Исходный код всех версий программ PGP доступен в открытом виде. Любой эксперт может убедиться в том, что в программе эффективно реализованы криптоалгоритмы. Так как сам способ реализации известных алгоритмов был доступен специалистам, то открытость повлекла за собой и другое преимущество - эффективность программного кода. 2. Стойкость. Для реализации основных функций использованы лучшие (по крайней мере на начало 90-х) из известных алгоритмов, при этом допуская использование достаточно большой длины ключа для надежной защиты данных Бесплатность. Готовые базовые продукты PGP (равно как и исходные тексты программ) доступны в Интернете в частности на официальном сайте PGP Inc. ( www.pgpi ). 4. Поддержка как централизованной (через серверы ключей) так и децентрализованной (через «сеть доверия») модели распределения открытых ключей. 5.Удобство программного интерфейса. PGP изначально создавалась как продукт для широкого круга пользователей, поэтому освоение основных приемов работы отнимает всего несколько часов Текущая версия – 7.0.3 для платформ Windows 9x/NT/2000, MacOS. GNU Privacy Guard (GnuPG) GnuPG (www.gnupg ) - полная и свободно распространяемая замена для пакета PGP. Этот пакет не использует патентованый алгоритм IDEA, и поэтому может быть использован без каких-нибудь ограничений. GnuPG соответсвует стандарту RFC2440 (OpenPGP). Текущая версия – 1.0.4, платформы – Unices, Windows 9x/NT Криптон Пакет программ КРИПТОН®Подпись (ancud/crypto/crpodpis.htm )предназначен для использования электронной цифровой подписи (ЭЦП) электронных документов. Программы пакета КРИПТОН®Подпись функционируют на компьютере, удовлетворяющем следующим требованиям: наличие операционной системы Windows-95/98 или Windows NT 4.0; наличие УКЗД серии КРИПТОН с соответствующим драйвером для Windows-95/98/NT или его программного драйвера-эмулятора для Windows - Crypton Emulator версии 1.3 или выше. наличие Crypton API для Windows версии 2.2 или выше (входит в поставку УКЗД серии КРИПТОН и содержит также драйвер поставляемого УКЗД); наличие манипулятора "мышь". В стандартной поставке для хранения файлов открытых ключей используются дискеты. Помимо дискет, пакет КРИПТОН®Подпись дает возможность использования всех типов ключевых носителей (смарт-карт, электронных таблеток Touch Memory и др.), поддерживаемых текущей версией интерфейса SCApi, входящего в поставку Crypton API v2.2 и выше. ВербаО ( ntc.spb/def/verbao.htm ) Система криптографической защиты информации "Верба - О" Система криптографической защиты информации (СКЗИ) "Верба - О" разработана Московским отделением Пензенского научно - исследовательского электротехнического института (МО ПНИЭИ), полномочным представителем которого в регионе является наш филиал. СКЗИ "Верба-О" представляет собой программный комплекс, предназначенный для защиты информации при ее хранении на дисках и (или) передаче по каналам связи. СКЗИ "Верба - О" решает следующие задачи: шифрование/расшифрование информации на уровне файлов; генерацию электронной цифровой подписи (ЭЦП); проверку ЭЦП; обнаружение искажений, вносимых злоумышленниками или вирусами в защищаемую информацию. СКЗИ "Верба - О" может поставляться в следующих вариантах: в виде автономного рабочего места; в виде модулей, встраиваемых в ПО заказчика. СКЗИ "Верба - О" в различных модификациях функционирует под управлением операционных систем MS DOS v5.0 и выше, Windows95, Windows NT, UNIX (HP UX) на персональных ЭВМ, совместимых с IBM PC/ AT. Требуемый объем оперативной памяти не более 155 Кбайт. Кроме того, необходим накопитель на гибком магнитном диске (НГМД). Алгоритм шифрования выполнен в соответствии с требованиями ГОСТ 28147-89 "СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ. ЗАЩИТА КРИПТОГРАФИЧЕСКАЯ". Цифровая подпись выполнена в соответствии с требованиями ГОСТ Р34.10-94 "ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. ПРОЦЕДУРЫ ВЫРАБОТКИ И ПРОВЕРКИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА БАЗЕ АССИМЕТРИЧНОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА." Функция хэширования выполнена в соответствии с требованиями ГОСТ Р 34.11-94 "ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. ФУНКЦИЯ ХЭШИРОВАНИЯ". Ключи шифрования симметричные. Ключи для подписи асимметричные. При обработке информации на ПЭВМ СКЗИ "Верба - О" обеспечивает следующие показатели: Операции PC/AT 486/33, ISA PC/AT 486/100 VESA Шифрование 200 Кб/с 520 Кб/с Вычисление хэш-функции 120 Кб/с 330 Кб/с Формирование ЭЦП 0.3с 0.04 с Проверка ЭЦП 0.7 с 0.2 с СКЗИ "Верба - О" имеет сертификат ФАПСИ № 124-0264 от 10.04.99г.
Список литературы
1. Петров А.А «Компьютерная безопасность. Криптографические методы защиты» ДМК Москва, 2000 г.
2. «Методы и средства защиты информации» (курс лекций)
3. Криптография (http://citforum.ru/internet/securities/crypto.shtml)
4. Баричев С.Г., Гончаров В.В., Серов Р.Е. «Основы современной криптографии»
5. Также для подготовки данной работы были использованы материалы с сайтов:
http://www.ed.vseved.ru/
http://www.wikipedia.org/
(zip - application/zip)
Статистика файлового архива
