Электронно-цифровая подпись и алгоритмы её реализации

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

Курсовая работа

Электронно-цифровая подпись и алгоритмы её реализации

Кафедра Электроника и защита информации

Студент: Кондратьев С.А.

Преподаватель: Стряпкин Л.И.



Содержание

1. ЭЦП: основные принципы

1.1 Предпосылки, историческая справка

1.2 Основные требования к ЭЦП

2. Практическая реализация

2.1 Хэширование: основные требования и алгоритм

2.2 Стандарты безопасности применяющие RSA

2.3 Алгоритм цифровой подписи Эль Гамаля (ЕGSА)

2.4 Стандарт цифровой подписи ГОСТ Р 34.10-2001

3. Криптостойкость RSA

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

3.2 Атака на основе выборочного шифротекста

3.3 Атака на основе общего RSA-модуля

3.4 Атака «шифрование коротких сообщений»

3.5 Атака на протокол

Литература



1. ЭЦП: основные принципы

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

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

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

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

- имя файла открытого ключа подписи;

- информация о лице, сформировавшем подпись;

- дата формирования подписи.

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

1.1 Предпосылки, историческая справка

Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была своеобразной криптографической системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры.

История криптографии условно можно разделить на 4 этапа.

1) наивная криптография.

2) формальная криптография.

3) научная криптография.

4) компьютерная криптография.

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

Большинство из используемых шифров сводились к перестановке или моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицей для греческого алфавита размер составляет 5x5). Каждая буква исходного текста заменяется на букву, стоящую в квадрате снизу от нее.

Этап формальной криптографии (кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном «сложении» букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа «Трактат о шифре» (1466) считается первой научной работой по криптологии.

Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования является труд «Полиграфия» (1508 г.) немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).

Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном. Уитстону принадлежит и важное усовершенствование - шифрование «двойным квадратом». Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.

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

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

Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет «прошитую» в нем подстановку.

Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple2 (Япония). Роторные системы -вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоатаки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.

Главная отличительная черта научной криптографии (30-е - 60-е годы XX века) - появление криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона «Теория связи в секретных системах» (1949), где сформулированы теоретические принципы криптографической защиты информации. Шеннон ввел понятия «рассеивание» и «перемешивание», обосновал возможность создания сколь угодно стойких криптосистем.

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

Компьютерная криптография (с 70-х годов XX века) обязана своим появлением вычислительным средствам с производительностью, достаточной для реализации критосистем, обеспечивающих при большой скорости шифрования на несколько порядков более высокую криптостойкость, чем «ручные» и «механические» шифры.

Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году). Один из его авторов, Хорст Фейстел (сотрудник IBM), описал модель блочных шифров, на основе которой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифрования ГОСТ 28147-89.

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



1.2 Основные требования к ЭЦП

В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием «Новые направления в современной криптографии». В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.

В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В 80-90-х годах были разработаны нефейстеловские шифры (SAFER, RC6 и др.), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES.

Относительно применения rsa

Данная криптосистема предложена Ривестом (R. Rivest), Шамиром (A. Shamir), Адлеманом (L. Adleman) в 1977 г. Предназначена как для цифровой подписи, так и для шифрования. Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании THALES (Racal). Кроме того, криптосистема RSA широко применяется в составе различных стандартов и протоколов Internet, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.



2. Практическая реализация

2.1 Хэширование: основные требования и алгоритм

Хеширование (англ. Collision-Resistant Hash Functions) -- преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины таким образом, чтобы изменение входных данных приводило к непредсказуемому изменению выходных данных. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).

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

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

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

Криптографическая хеш-функция должна обеспечивать:

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

необратимость (невозможность вычислить исходные данные по результату преобразования)

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

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

быстрый алгоритм вычисления

2.2 Стандарты безопасности применяющие RSA

Криптосистема RSA - часть многих стандартов. Стандарт ISO 9796 описывает RSA как совместимый криптографический алгоритм, соответствующий стандарту безопасности ITU-T X.509. Кроме этого криптосистема RSA является частью стандартов SWIFT, ANSI X9.31 rDSA и проекта стандарта X9.44 для американских банков. Австралийский стандарт управления ключами AS2805.6.5.3 также включает систему RSA.

Алгоритм RSA используется в Internet, в частности он входит в такие протоколы как S/MIME, IPSEC (Internet Protocol Security) и TLS (которым предполагается заменить SSL), а также в стандарт PKCS, применяемый в важных приложениях.

Для разработчиков приложений с применением PKCS организация OSI Implementers Workshop (OIW) выпустила соглашение, которое в частности посвящено алгоритму RSA.

Множество других разрабатываемых в настоящее время стандартов включают в себя либо сам алгоритм RSA или его поддержку либо рекомендуют криптосистему RSA для обеспечения секретности и/или установления подлинности (аутентификации). Например, включают в себя систему RSA рекомендации IEEE P1363 и WAP WTLS.

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

Описание криптосистемы RSA

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

Для генерации парных ключей берутся два больших случайных простых числа p и q. В целях максимальной криптостойкости p и q выбираются равной длины. Затем вычисляется их произведение n=pq (n называется модулем). Далее случайным образом выбирается число e (ключ шифрования), удовлетворяющее условию: 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом ?(n)=(p-1)*(q-1).

Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что ed=1 mod ?(n). Число d такое, что (ed - 1) делится на (p - 1)(q-1).

Открытый ключ: (public)	n- произведение двух простых чисел p иq (должны храниться в секрете); e - число, взаимно простое с ?(n)
Секретный ключ: (private)	d = e-1mod ?(n)
Шифрование:	c = me mod n
Дешифрование:	m = cd mod n

Числа d и n - также взаимно простые числа.

Числа e и n - открытый ключ, а d - секретный.

Два простых числа p и q хранятся в секрете.

Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q - 100 разрядные простые числа, то n будет содержать около 20 разрядов и каждый блок сообщения m_i должен иметь такое же число разрядов. Если же нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков c_i той же самой длины. Шифрование сводиться к вычислению

c_i =m_i^e mod n.

При дешифровании для каждого зашифрованного блока c_i вычисляется

m_i = c_i^d mod n

Последнее справедливо, так как

c_i^d = (m_i^e)^d = m_i^ed = m_i^k?(n)+1 = m_i?1 = m_i

Все вычисления выполняются по mod n. Сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.

2.3 Алгоритм цифровой подписи Эль Гамаля (ЕGSА)

Название ЕGSА происходит от слов ЕІ GаmаІ Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля). Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,- задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10³⁰⁸ или ~2¹⁰²⁴) и G (~10¹⁵⁴ или ~2⁵¹²), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 < Х ? (Р-1), и вычисляет

Y =G^X mod Р.

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

Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h() в целое число m:

m = h(М), 1<m<(Р-1),

и генерирует случайное целое число К, 1 < К < (Р -1), такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а:

а = G^K mod Р



и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения

m = Х * а + К * b (mod (Р-1)).

Пара чисел (а,b) образует цифровую подпись S:

S = (а, b),

проставляемую под документом М.

Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К).держится в секрете.

После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись

S = (а, b)

сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число

m = h(М),

т.е. хэширует принятое сообщение М.

Затем получатель вычисляет значение

А = Y^a a^b (mod Р)

и признает сообщение М подлинным, если, и только если

А = G^m (mod Р).

Иначе говоря, получатель проверяет справедливость соотношения

Y^a a^b (mod Р) = G^m (mod Р).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(а, b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.

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

2.4 Стандарт цифровой подписи ГОСТ Р 34.10-2001

Российский стандарт цифровой подписи ГОСТ Р 34.10-2001 был принят в 2001 году. Этот стандарт разработан взамен первого стандарта цифровой подписи ГОСТ Р 34.10-94. Необходимость разработки стандарта ГОСТ Р 34.10-2001 вызвана потребностью в повышении стойкости электронной цифровой подписи к несанкционированным изменениям. Стойкость ЭЦП основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости используемой хэш-функции по ГОСТ Р 34.11.Принципиальное отличие нового стандарта от предыдущего ГОСТ Р 34.10-94 состоит в том, что все вычисления при генерации и проверке ЭЦП в новом алгоритме производятся в группе точек эллиптической кривой, определенной над конечнымполем Fp.Принадлежность точки (пары чисел х и у) к данной группе определяется следующим соотношением:

=

где модуль системы р является простым числом, большим 3, а а и b - константы, удовлетворяющие следующим соотношениям:

a,b? и 4не сравнимо с нулем по модулю р.

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

Обозначения

В данном стандарте использованы следующие обозначения:

- множество всех двоичных векторов длиной 256 бит;

V? - множество всех двоичных векторов произвольной конечной длины;

Z - множество всех целых чисел;

р - простое число, р > 3;

- конечное простое поле, представляемое как множество из р целых чисел {0, 1, ..., p ?1};

b p (mod ) - минимальное неотрицательное число, сравнимое с b по модулю р;

М - сообщение пользователя, M V? ?;

- конкатенация (объединение) двух двоичных векторов;

а, b - коэффициенты эллиптической кривой;

m - порядок группы точек эллиптической кривой;

q - порядок подгруппы группы точек эллиптической кривой;

О - нулевая точка эллиптической кривой;

Р - точка эллиптической кривой порядка q;

d - целое число - ключ подписи;

Q - точка эллиптической кривой - ключ проверки;

w - цифровая подпись под сообщением М.

Общие положения

Механизм цифровой подписи реализуется посредством двух основных процессов:

? формирования цифровой подписи;

? проверки цифровой подписи. В процессе формирования цифровой подписи в качестве исходных данных используются сообщение М, ключ подписи d и параметры схемы ЭЦП, а в результате формируется цифровая подпись w. Ключ подписи d является элементом секретных данных, специфичным для субъекта и используемым только данным субъектом в процессе формирования цифровой подписи.

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

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

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

Криптографическая стойкость данной схемы цифровой подписи основывается на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой, а также на стойкости используемой хэш-функции. Алгоритм вычисления хэш-функции установлен в ГОСТ Р 34.11.

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

Основные процессы

В данном разделе определены процессы формирования и проверки электронной цифровой подписи под сообщением пользователя.

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

Кроме того, каждому пользователю необходимо иметь ключ подписи d и ключ проверки подписи Q(,), которые также должны удовлетворять приведенным выше требованиям.

Формирование цифровой подписи. Для получения цифровой подписи под сообщением M ?V µ необходимо выполнить следующие действия (шаги).

Шаг 1 - вычислить хэш-код сообщения M:

h = h(M ).

Шаг 2 - вычислить целое число б, двоичным представлением которого является вектор h , и определить значение

e ? б(mod q).

Если е = 0, то определить е = 1.

Шаг 3 - сгенерировать случайное (псевдослучайное) целое число k, удовлетворяющее неравенству

0 < k < q.

Шаг 4 - вычислить точку эллиптической кривой С = kР и определить

r(mod q)

где хi - х-координата точки С. Если г = 0, то вернуться к шагу 3.

Шаг 5 - вычислить значение

s=(rd+ke)mod( q) .

Если s = 0, то вернуться к шагу 3.

Шаг 6 - вычислить двоичные векторы r и s , соответствующие r и s, и определить цифровую подпись w = (r||s) как конкатенацию двух двоичных векторов.

Исходными данными этого процесса являются ключ подписи d и подписываемое сообщение M, а выходным результатом - цифровая подпись w.

Проверка цифровой подписи.

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

Шаг 1 - по полученной подписи w вычислить целые числа r и s. Если выполнены неравенства 0 <r <q, 0 < s <q, то перейти к следующему шагу. В противном случае подпись неверна.

Шаг 2 - вычислить хэш-код полученного сообщения M:

= h(M ).

Шаг 3 - вычислить целое число а, двоичным представлением которого является вектор h , и определить

e ? б(mod q).

Если е = 0, то определить е = 1.

Шаг 4 - вычислить значение

v?

Шаг 5 - вычислить значения

sv*mod (q) ,

? -rv*mod (q) .

Шаг 6 - вычислить точку эллиптической кривой C = P + Q и определить

R ? mod (q )

где хс - х-координата точки С.

Шаг 7 - если выполнено равенство R = r, то подпись принимается, в противном случае подпись неверна.

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

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



3. Криптостойкость RSA

Предполагается, что криптостойкость RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно nразложить на множители. Чтобы восстановить m по с и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d , он также может быть использован для разложения на множители больших чисел. Также можно атаковать RSA, угадав значение (p-1)(q-1).Однако этот метод не проще разложения n на множители. При использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрование всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. был предложен метод криптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

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

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

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

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку c = me(mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки - единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

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

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

3.2 Атака на основе выборочного шифротекста

Некоторые атаки используют уязвимость криптографического протокола. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности системы. Рассмотрим несколько сценариев.

Сценарий 1.

Злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью открытого RSA-ключа Алисы. Он хочет прочитать сообщение. Для раскрытия m = сd он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым ключом Алисы е, вычисляет

x = re mod n,

y = xc mod n,

t = r-1 mod n.

Если х = re mod n , то r= xdmod n

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

u = yd mod n



Теперь злоумышленник раскрывает m, вычисляя

tu mod n =r-1yd mod n = r-1 xdcd mod n =cd mod n = m

Сценарий 2.

Если Алиса хочет заверить документ, она посылает его нотариусу. Нотариус подписывает его цифровой подписью и отправляет обратно. (Хеш-функции не используются, нотариус шифрует все сообщение на своем секретном ключе.) Злоумышленник хочет, чтобы нотариус подписал такое сообщение, которое в обычном случае тот никогда не подпишет. Это может быть фальшивая временная метка, либо автором этого сообщения может являться другое лицо. Какой бы ни была причина, нотариус никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение т'. Сначала злоумышленник выбирает произвольное значение х и вычисляет у = xе mod п. Параметр e он может получить без труда -- это открытый ключ нотариуса, и должен быть опубликован для проверки подписи последнего. Теперь злоумышленник вычисляет m = ym mod n и посылает mнотариусу на подпись. Нотариус возвращает md mod n. Далее злоумышленник вычисляет (md mod n)x-1 mod n, которое равно m? d mod n и является подписью m'. На самом деле у злоумышленника есть множество различных способов решения подобной задачи. Описанная атака основана на сохранении мультипликативной структуры арифметической операции возведения в степень:

(хт)d mod п =xdmd тоd п.

Сценарий 3.

Злоумышленник хочет, чтобы Алиса подписала некое сообщение m3. Для этого он создает два сообщения, m1 и m2, такие, что m3 = m1m2 mod n. Если злоумышленник заставит Алису подписать m1 и m2, то сможет вычислить подпись для m3:

m3d = (m1d mod n)(m2d mod n).

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

3.3 Атака на основе общего RSA-модуля

При реализации RSA можно попробовать раздать всем абонентам криптосети одинаковый модуль n, но каждому -- свои значения показателей степени e и d. При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (при фиксированном модуле) и эти два показателя -- взаимно-простые числа (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Пусть заданы: m -- открытый текст, e1 и e2 -- два ключа шифрования, n -- общий модуль. Шифротекстами сообщения являются:

c1 = me1 mod n,

c2 = me2 mod n,

Криптоаналитик знает n, e1, e2, c1 и c2. Так как e1 и e2 -- взаимно-простые числа, то, воспользовавшись расширенным алгоритмом Евклида, можно найти такие числа r и s, что

re1 + se2 = 1.

Полагая r отрицательным (или r, или s должно быть отрицательным), можно снова воспользоваться расширенным алгоритмом Евклида для вычисления c1-1. Тогда

(c1-1)-rc2s = m mod n.

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

3.4 Атака «шифрование коротких сообщений»

Известно, что криптосистема RSA обладает низкой криптостойкостью при зашифрованном на малом e коротком сообщении. Действительно, при c = me < n открытый текст mможет быть восстановлен по шифротексту c при помощи процедуры извлечения корня. Фактически подобная атака возможна и тогда, когда в процессе возведения в степень выполнялось некоторое количество приведений по модулю. При c > n трудоемкость такой атаки ниже трудоемкости исчерпывающего перебора для m. Однако меры противодействия также очевидны, -- либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в искусственном наращивании коротких открытых текстов («набивки»). При этом необходимо следить за тем, чтобы удлиненный открытый текст при числовом отображении не превращался в набор множителей некоторого известного числа P, например P = 2l, что происходит при дополнении открытого текста последовательностью нулей справа (со стороны младших разрядов).

Раскрытие малого показателя…

шифрования

Хэстед (J. Hasted) продемонстрировал уязвимость RSA при условии, если криптоаналитик может получить множество шифротекстов фиксированного сообщения m, зашифрованного при помощи криптосистемы RSA с различными секретными параметрами p и q, но при использовании фиксированного открытого ключа e. При соблюдении сформулированных условий можно раскрыть сообщение m. Известен частный случай, когда при заданных l раз-личных результатах шифрования me mod n1,…,me mod nl можно раскрыть m при помощи Китайской теоремы об остатках. В общем случае, при заданных t результатах шифрования

(a1m +b1)e mod n1,…,(atm + bt)e mod nt,

где ai и bi, заданы и t > е(е+1)/2, можно раскрыть сообщение т, воспользовавшись известным математическим методом. Еще раз отметим, что данная атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом (фиксированное сообщение т является частным случаем) дешифрования.

Другая атака позволяет раскрывать d, когда d не превышает четверти размера n, а e < n . При случайном выборе e и d, это маловероятно и никогда не произойдет, если значение e мало. Значение d, должно быть большим.

3.5 Атака на протокол

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

(meB mod nB)dA mod nA

Однако Боб может доказать, что Алиса послала ему m', а не m. Так как Бобу известно разложение на множители nB (это его собственный модуль), он может вычислить дискретные логарифмы по основанию nB. Следовательно, ему остается найти x, для которого

m?x = m mod nB

Если он может опубликовать xeB в качестве своего нового открытого показателя степени и сохранить свой прежний модуль nB, он сможет утверждать, что Алиса послала ему сообщение m', зашифрованное на xeB. Применение хэш-функции не позволяет решить проблему. Однако ее можно решить путем использования фиксированного показателя шифрования для каждого пользователя криптосети.



Литература

1. Чмора А.Л.: Современная прикладная криптография. 2-е изд., стер. - М.: Гелиос АРВ., 2002.

2. www.cryptography.ru

3. www.ciphersbyritter.com

5. Ященко В.В. (ред.) - Введение в криптографию (изд. 3-е)

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

...