Алгоритм электронной цифровой подписи на основе решения системы сравнений
СОДЕРЖАНИЕ:
ВВЕДЕНИЕ 3
ГЛАВЫ 1. ЭЛЕКТРОННАЯ ЦИФРОВАЯ ПОДПИСЬ: ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ 5
1.1. Основные понятия связанные с ЭЦП. Назначение и применение ЭЦП 5
1.2. Обзор алгоритмов ЭЦП 8
ГЛАВА 2. СХЕМЫ ЭЦП С НОВЫМ МЕХАНИЗМОМ ФОРМИРОВАНИЯ ПОДПИСИ 11
2.1. Схема цифровой подписи ElGamal 11
2.2. Схема цифровой подписи RSA 13
2.3. Схема цифровой подписи ECDSA 14
2.4. Схемы с формированием подписи на основе решения системы сравнений 16
ЗАКЛЮЧЕНИЕ 23
СПИСОК ЛИТЕРАТУРЫ 24
ВВЕДЕНИЕ
В последнее время все больше и больше внедряются в нашу повседневную жизнь информационные технологии, пытаясь захватить в ней все: от важнейших государственных проектов до решения обычных бытовых проблем. Вместе с огромной пользой и, казалось бы, неограниченными возможностями новые технологии приносят и новые проблемы. Одной из них является проблема защиты информации от несанкционированного посягательства теми, кто доступа к этой информации иметь не должен. В связи с этим почти одновременно с развитием информационных и компьютерных технологий начали развиваться и технологии защиты информации, развитие которых с некоторой точки зрения гораздо более критично, чем развитие непосредственно информационных технологий. Ведь с совершенствованием систем защиты, совершенствуются и методы взлома, обхода этих защит, что требует постоянного пересмотра и увеличения надежности защиты информации.
Актуальность темы. Электронная цифровая подпись – это эффективное средство защиты информации от модификации, искажений, позволяющее при этом однозначно идентифицировать отправителя сообщения и перенести свойства реальной подписи под документом в область электронного документа. Электронная цифровая подпись является наиболее перспективным и широко используемым в мире способом защиты электронных документов от подделки и обеспечивает высокую достоверность сообщения.
Данная курсовая работа посвящена одной из важнейших задач криптографии – электронной цифровой подписи (digital signature). Электронная цифровая подпись (ЭЦП) необходима для однозначного и никем неоспоримого установления автора какого-либо документа. Фактически, ЭЦП служит аналогом обычной подписи, которая устанавливает подлинность какого-либо документа или договора. Но поскольку в последнее время огромное количество договоров и документов заключаются с использованием электронных и компьютерных средств, то поставить на них обычную подпись не представляется возможным. Именно для таких ситуаций и используется электронная цифровая подпись. Электронная цифровая подпись создана для того, чтобы избежать подделок, а также искажений передаваемых сообщений.
Целью данной курсовой работы является рассмотреть алгоритм электронной цифровой подписи на основе решения системы сравнений. Для достижения поставленной цели необходимо решить ряд задач:
- раскрыть основные понятия связанные с ЭЦП;
- показать назначение и применение ЭЦП;
- провести обзор алгоритмов ЭЦП;
- рассмотреть схемы ЭЦП с новым механизмом формирования подписи, а именно: схема цифровой подписи ElGamal; схема цифровой подписи RSA; схема цифровой подписи ECDSA;
- исследовать схемы с формированием подписи на основе решения системы сравнений.
Курсовая работа состоит из введения, двух глав, включающих в себя шесть параграфов, заключения и списка литературы.
ГЛАВЫ 1. ЭЛЕКТРОННАЯ ЦИФРОВАЯ ПОДПИСЬ: ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
1.1. Основные понятия связанные с ЭЦП. Назначение и применение ЭЦП
(Федеральный закон Российской Федерации от 6 апреля 2011 г. N 63-ФЗ "Об электронной подписи")1.
1) электронная подпись - информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию;
2) сертификат ключа проверки электронной подписи - электронный документ или документ на бумажном носителе, выданные удостоверяющим центром либо доверенным лицом удостоверяющего центра и подтверждающие принадлежность ключа проверки электронной подписи владельцу сертификата ключа проверки электронной подписи;
3) квалифицированный сертификат ключа проверки электронной подписи (далее - квалифицированный сертификат) - сертификат ключа проверки электронной подписи, выданный аккредитованным удостоверяющим центром или доверенным лицом аккредитованного удостоверяющего центра либо федеральным органом исполнительной власти, уполномоченным в сфере использования электронной подписи (далее - уполномоченный федеральный орган);
4) владелец сертификата ключа проверки электронной подписи - лицо, которому в установленном настоящим Федеральным законом порядке выдан сертификат ключа проверки электронной подписи;
5) ключ электронной подписи - уникальная последовательность символов, предназначенная для создания электронной подписи;
6) ключ проверки электронной подписи - уникальная последовательность символов, однозначно связанная с ключом электронной подписи и предназначенная для проверки подлинности электронной подписи;
7) удостоверяющий центр - юридическое лицо или индивидуальный предприниматель, осуществляющие функции по созданию и выдаче сертификатов ключей проверки электронных подписей, а также иные функции, предусмотренные настоящим Федеральным законом;
8) аккредитация удостоверяющего центра - признание уполномоченным федеральным органом соответствия удостоверяющего центра требованиям настоящего Федерального закона;
9) средства электронной подписи - шифровальные (криптографические) средства, используемые для реализации хотя бы одной из следующих функций - создание электронной подписи, проверка электронной подписи, создание ключа электронной подписи и ключа проверки электронной подписи;
10) средства удостоверяющего центра - программные и (или) аппаратные средства, используемые для реализации функций удостоверяющего центра;
11) участники электронного взаимодействия - осуществляющие обмен информацией в электронной форме государственные органы, органы местного самоуправления, организации, а также граждане;
12) корпоративная информационная система - информационная система, участники электронного взаимодействия в которой составляют определенный круг лиц;
13) информационная система общего пользования - информационная система, участники электронного взаимодействия в которой составляют неопределенный круг лиц и в использовании которой этим лицам не может быть отказано.
Цифровая подпись предназначена для аутентификации лица, подписавшего электронный документ. Кроме этого, использование цифровой подписи позволяет осуществить:
Контроль целостности передаваемого документа: при любом случайном или преднамеренном изменении документа подпись станет недействительной, потому что вычислена она на основании исходного состояния документа и соответствует лишь ему.
Защиту от изменений (подделки) документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев.
Невозможность отказа от авторства. Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец не может отказаться от своей подписи под документом.
Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т.д.2
Использование хэш-функций
Поскольку подписываемые документы ― переменного (и как правило достаточно большого) объёма, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хэш. Для вычисления хэша используются криптографические хэш-функции, что гарантирует выявление изменений документа при проверке подписи. Хэш-функции не являются частью алгоритма ЭЦП, поэтому в схеме может быть использована любая надёжная хэш-функция.
Использование хэш-функций даёт следующие преимущества:
Вычислительная сложность. Обычно хеш цифрового документа делается во много раз меньшего объёма, чем объём исходного документа, и алгоритмы вычисления хеша являются более быстрыми, чем алгоритмы ЭЦП. Поэтому формировать хэш документ и подписывать его получается намного быстрее, чем подписывать сам документ.
Совместимость. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хеш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.
Целостность. Без использования хеш-функции большой электронный документ в некоторых схемах нужно разделять на достаточно малые блоки для применения ЭЦП. При верификации невозможно определить, все ли блоки получены и в правильном ли они порядке.
Стоит заметить, что использование хеш-функции не обязательно при цифровой подписи, а сама функция не является частью алгоритма ЭЦП, поэтому хеш-функция может использоваться любая или не использоваться вообще.
1.2. Обзор алгоритмов ЭЦП
Технология применения системы электронной цифровой подписи (ЭЦП) предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ.
Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, используются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:
- задача факторизации (разложения на множители) больших целых чисел;
- задача дискретного логарифмирования3.
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. В Массачуссетском технологическом институте США. Алгоритм получил свое название по первым буквам фамилий его авторов: Rivest, Shamir и Adleman. Надежность алгоритма основывается на трудности факторизации больших чисел.
Более надежный и удобный для реализации на персональных компьютерах ЭЦП алгоритм был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем и получил название El Gamal Signature Algorithm (EGSA).
Идея EGSA основана на том, что для обоснования практической невозможности фальсификации ЭЦП может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа – задача дискретного логарифмирования. Кроме того Эль Гамалю удалось избежать явной слабости алгоритма ЭЦП RSA, связанной с возможностью подделки ЭЦП под некоторыми сообщениями без определения секретного ключа.
Алгоритм цифровой подписи Digital Signature Algorithm (DSA) предложен в 1991г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма ЭЦП EGSA. По сравнению с алгоритмом ЭЦП EGSA алгоритм DSA имеет ряд преимуществ: сокращен объем памяти и время вычисления подписи. Недостатком же является необходимость при подписывании и проверке подписи выполнять сложные операции деления по модулю большого числа.
Российский стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. Различие между этими стандартами заключается в использовании параметров ЭЦП разного порядка, что приводит к получению более безопасной подписи при использовании российского стандарта.
Алгоритмы цифровых подписей Elliptic Curve Digital Signature Algorithm (ECDSA) и ГОСТ Р 34.10-2001 являются усовершенствованием цифровых подписей DSA и ГОСТ Р 34.10-94 соответственно. Эти алгоритмы построены на базе математического аппарата эллиптических кривых над простым полем Галуа4.
ГЛАВА 2. СХЕМЫ ЭЦП С НОВЫМ МЕХАНИЗМОМ ФОРМИРОВАНИЯ ПОДПИСИ
2.1. Схема цифровой подписи ElGamal
История: Схема была предложена Тахером Эль - Гамалем в 1984 году.
Эль - Гамаль разработал один из вариантов алгоритма Диффи - Хеллмана. Он усовершенствовал систему Диффи - Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличии от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.
Схема Эль - Гамаля - криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль - Гамаля лежит в основе стандартов электронной цифровой подписи в США и России5.
Генерация ключей: Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе.
Генерируется случайное простое число P длины n битов.
Выбирается произвольное целое число g, являющееся первообразным корнем по модулю P.
Выбирается случайное целое число x такое, что 1 < x < P.
Вычисляется y = gx mod p.
Открытым ключом является тройка (p, g, y), закрытым ключом – x.
Подписание:
Вычисляется хэш сообщения M: m = h(M).
Выбирается случайное число 1 < k < p – 1 взаимно простое с p - 1 и вычисляется r = gk mod p.
С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению: m ≡ xr + ks (mod p – 1).
Подписью сообщения M является пара (r, s).
Проверка: Зная открытый ключ (p, g, y), подпись (r, s) сообщения M проверяется следующим образом:
Проверяется выполнимость условий: 0 < r < p и 0 < s < p - 1. Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется хэш m = h(M).
Подпись считается верной, если выполняется сравнение: gr rs mod p≡ gm mod p.
5. Схема цифровой подписи Шнорра
Проблема схемы цифровой подписи Эль - Гамаля в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифма Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи.
Генерация ключей: Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.
Алиса выбирает простое число p, которое обычно равно по длине 1024 битам.
Алиса выбирает другое простое число q, которое имеет тот же самый размер, что и хэш, созданный функцией криптографического хэширования (≥160). q | (p - 1), другими словами, (p - 1) = 0 mod q.
Алиса выбирает e1, q-тый корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e0 и вычисляет e1 = e0(p-1)/q mod p.
Алиса выбирает целое число d, как свой секретный ключ.
Алиса вычисляет e2 = e1d mod p.
Общедоступный ключ Алисы - (e1, e2, p, q), ее секретный ключ - (d).
Подписание:
Алиса выбирает случайное число r. (меняется каждый раз при новом сообщении) такое что 1 < r < q.
Алиса вычисляет первую подпись S1 = h(M | e1r mod p) . Сообщение присоединяется спереди к значению e1r mod p, затем применяется хэш-функция, чтобы создать хэш. хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М и e1r mod p.
Алиса вычисляет вторую подпись S2 = r + d * S1 mod q.
Алиса передает М, S1 и S2.
Проверка: Приемник, например Боб, получает М, S1 и S2.
Боб вычисляет V = h (М | e1S2 * e2-S1 mod p).
Если S2 сравнимо с V по модулю p, сообщение принято; иначе оно отклоняется.
2.2. Схема цифровой подписи RSA
История: Описание RSA было опубликовано в 1977 году Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT).Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса6.
Описание алгоритма: Безопасность алгоритма электронной подписи RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа — открытый и секретный, вместе открытый и соответствующий ему секретный ключи образуют пару ключей. Открытый ключ не требуется сохранять в тайне, он используется для зашифровывания данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом. RSA может также применяться для того, чтобы подписать и подтвердить сообщение. Схема цифровой подписи меняет роли секретных и открытых ключей. Первое: используются секретный и открытый ключи передатчика, а не приемника. Второе: передатчик использует свой собственный секретный ключ для подписи документа; приемник использует открытый ключ передатчика, чтобы проверить этот документ.
Генерация ключей: Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА. Алиса выбирает два простых числа p и q и вычисляет n = p * q. Алиса вычисляет φ(n) = (p - 1) (q - 1). Затем она выбирает e, для общедоступного ключа и вычисляет d для частного ключа, такое, что e * d = 1 mod φ(n). Алиса сохраняет d и публично объявляет n и e.
Подписание:
Алиса на основе сообщения M создает подпись S, используя секретный ключ (d, n): S = Md mod n.
Передает сообщение и подпись Бобу (M, S).
Проверка:
Боб получает М и S.
Применяет общедоступный ключ Алисы (n, e) к подписи, чтобы создать копию сообщения М' = Se mod n.
Боб сравнивает значение М' со значением М. Если два значения совпадают, Боб принимает сообщение7.
2.3. Схема цифровой подписи ECDSA
История: ECDSA (Elliptic Curve Digital Signature Algorithm) - алгоритм с открытым ключом для создания цифровой подписи, аналогичный по своему строению DSA, но определённый в отличие от него не над полем целых чисел, а в группе точек эллиптической кривой.
Алгоритм ECDSA в 1999 г. был принят, как стандарт ANSI, в 2000 г. - как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO.
Описание алгоритма: Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует суб-экспонециального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые.
Параметры алгоритма:
Выбор хэш-функции h(x). Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом.
Выбор большого простого числа q - порядок одной из циклических подгрупп группы точек эллиптической кривой. Если размерность этого числа в битах меньше размерности в битах значений хэш-функции h(x) то используются только левые биты значения хэш-функции.
Простым числом p обозначается характеристика поля координат Fp.
Генерация ключей:
Алиса выбирает эллиптическую кривую Ep (a, b) с простым числом p.
Алиса выбирает другое простое число q, чтобы использовать для вычисления.
Алиса выбирает секретный ключ d, целое число.
Алиса выбирает точку на кривой e1(.,….).
Алиса вычисляет e2 (..,....) = d * e1 (......), другую точку на кривой.
Общедоступный ключ Алисы - (a, b, p, q, e1, e2), ее секретный ключ - d.
Подписание: Процесс подписания состоит главным образом из выбора секретного случайного числа, создания третьей точки на кривой, вычисления двух подписей и передачи сообщения и подписей.
Алиса выбирает секретное случайное число r, между 1 и q - 1.
Алиса выбирает третью точку на кривой P (u, v) = r * e1 (......).
Алиса использует первые координаты P (u, v), чтобы вычислить первую подпись S1.: S1 = u mod q.
Алиса использует хэш сообщения, свой секретный ключ d, секретное случайное число r и S1, чтобы вычислить вторую подпись S2 = (h(M) + d * S1) r -1 mod q,
Алиса передает М, S1 и S2.
Проверка: Процесс проверки состоит главным образом из восстановления третьей точки и подтверждения, что первая координата эквивалентна S1 по модулю q. Так как третья точка была создана подписывающим лицом, использующим секретное случайное число r. А верификатор не имеет этого значения. Ему нужно создать третью точку из хэша сообщения, S1, и S2.
Боб применяет М, S1 и S2 для создания двух промежуточных результатов A и B:
A = h(M)S2-1 mod q.
B = S2-1 S1 mod q.
Затем Боб восстанавливает третью точку T(x, y) = A * e1( … , …) + B * e2( … , …)
Боб использует первую координату из T(x, y), чтобы проверить сообщение. Если x = S1 mod q, подпись принимается, иначе - отклоняется8.
2.4. Схемы с формированием подписи на основе решения системы сравнений
Генерация подписи (R, S) в схемах ЭЦП на основе сложности дискретного логарифмирования может быть осуществлена с использованием нового механизма, в котором оба элемента подписи R и S представляются в одинаковом виде R=akmod р и S=ag mod p, где значения к и g вычисляются одновременно как одно из решений системы из двух сравнений, записываемых в зависимости от вида проверочного соотношения. Идея этого механизма состоит в том, чтобы сделать вычислительно невозможным вычисление одного из параметров R или S при наперед заданном значении второго параметра. Параметры R и S используются как аргументы двух различных функций F1(R, S) и F2(R, S). При определенных ограничениях на значения аргументов их можно изменять таким образом, что значение функции F2(R, S) будет оставаться неизменным. При этом значение функции F1(R, S) должно изменяться таким образом, что можно подобрать пару значений R и S, при которых будет выполняться некоторое проверочное соотношение9.
Таким образом, в определенной области пар значений R и S мы имеем F2 = Z = const, поэтому проверочное соотношение в принципе может быть упрощено, что при определенном его виде позволит вычислить подпись (R(Z), S(Z)), зависящую от Z. При составлении конкретных вариантов подписи могут быть использованы, например, следующие пары функций (F1, F2): (R/ Smod p, RSmod p), (RSmod p, R / Smod p), (RSMmod p, RSmod p), (RSmod p, RS2mod p), (RSZmod p, RSmod p), (RSZmod p, R / Smod p), где Z = R S mod p. При этом значения R и S предполагается выражать через к и g в виде: R = a*mod p и S = mod р. Условие постоянства значения функции F2 = R/S mod р запишется в виде k – g = U mod  , где у есть некоторый показатель, к которому число а относится по модулю р, и U — случайно выбираемое число.
В случаях F2 = RS mod р и F2 = RSMmod р условие постоянства запишется в виде k+g= U mod у и к + gM = U mod соответственно. Учитывая, что в уравнение проверки подписи входит значение сообщения М или хэш-функции Н от него, можно предложить следующие варианты проверочных соотношений:
где  есть произвольное простое число длины | | 0,25 |р|. Операция F2mod определяет некоторую сжимающую функцию F2’ значение которой остается постоянным, если значение F2 = RS mod р не изменяется. Это позволяет получить и использовать в проверочном соотношении две функции, зависящие от параметров R и S, причем такие, что их значения фиксируются одновременно при условии, что параметры к и g удовлетворяют определенным условиям.
Необходимость использования пары одновременно фиксируемых функций F2 и Ғ2 связана с тем, что в проверочном соотношении требуется задать показатели степеней элементов и а, зависящие от R и S. Если это условие не выполнено, то подпись может быть легко подделана путем включения фиксированной степени или а как дополнительного множителя в представление одного из параметров R и S. Например, если проверочное соотношение имеет вид R = S (RSmod p) aHmod р, то подпись можно сформировать без использования секретного ключа. Это осуществляется следующим образом. Представим элементы подписи в виде
R = аН mod р(1)
и
S =  mod р(2)
При к + g = Umod (3)
значение Z = RS mod p = aH уUmod р является фиксированным, и мы можем обеспечить выполнимость сравнения аH уk = ygyZ aH mod p (очевидно, что при этом будет выполняться проверочное уравнение, поскольку имеет место R = SyZaНmod р ), задавая еще одно условие, которому должны удовлетворять значения kи g, а именно условие
k = g + Z mod (4).
Таким образом, следует решить систему сравнений (3) и (4) и подставить решение в качестве значений показателей степеней kи g в выражения (1) и (2), определяющие значения элементов подписи R и S10.
Если каждый из элементов у и а входит в проверочное соотношение в степенях, зависящих от вычисляемых параметров, то подделать подпись приведенным ранее способом практически невозможно, если эти степени будут представлять собой две различные нелинейно связанные функции F2и Ғ2’ (однако могут оказаться реализуемыми другие способы, которые будут рассмотрены далее). Следует подчеркнуть важность нелинейности связи между рассматриваемыми функциями. Если они будут отличаться постоянным множителем, то подделка подписи также тривиальна.
Рассмотрим схему ЭЦП с проверочным сравнением Ry(RSmodp)= SaH(RSmod р)mod р. Перепишем это сравнение в виде  и представим элементы подписи в виде
 (6)
При k + g = U mod y (7)
значение  является фиксированным и условием выполнимости проверочного сравнения является
k  g + Z mod у (8).
Действительно, если (7) и (8) выполняются, то имеем:
Таким образом, подпись может быть сформирована без использования секретного ключа путем совместного решения сравнений (7) и (8) и последующего вычисления элементов подписи по формулам (5) и (6).
Еще один вариант ЭЦП задается сравнением проверки подписи вида
в котором внесение постоянного множителя в выражение, представляющее R или S, не позволяет сформировать подпись без знания секретного ключа, поскольку каждый элемент подписи возводится в степень, которая не является заранее заданной.
Процедура формирования подписи состоит в следующем. Предполагая, что элементы подписи будут вычисляться по формулам
R = akmod р(9)
и
S= agmod р (10),
записываем условие фиксирования показателей степеней проверочного соотношения:
k + g = U mod (11)
и выбираем случайное значение U < , которое задает конкретные значения Z = RS mod р = aU= mod р и Z' = (RS mod р) mod = Z mod . Затем записываем проверочное сравнение в виде
Поскольку по предположению a относится к показателю у, то из последней формулы следует дополнительное сравнение
 (12),
которое вместе с (11) обеспечивает выполнимость проверочного сравнения. Решая совместно сравнения (11) и (12), получаем формулы
по которым вычисляем значения к и g, а затем по (9) и (10) — элементы подписи R и S.
Описанная ранее идеология построения схем ЭЦП потенциально устраняет возможность реализации скрытых каналов со сравнительно большой пропускной способностью, поскольку по секретному ключу и подписи (R, S) вычислительно сложно найти значение U, которое выбирается произвольным и могло бы быть использовано для передачи блоков шифjтекста. Для вычисления U требуется вычислить и к, и g, однако для этого требуется решить задачу дискретного логарифмирования. В рассмотренных ранее схемах потенциально устраняется и возможность экзистенциальной подделки подписи, однако предстоит решить еще одну проблему, связанную с подделкой подписи на основе замены переменных.
Идея атаки на основе замены переменных состоит в том, чтобы выбрать такую пару переменных значений (вместо переменных R и S), чтобы показатели степеней в проверочном соотношении зависели только от одной переменной. Тогда эту переменную можно выбрать произвольно, а вторую переменную вычислить как неизвестную. При этом наиболее сложной операцией процедуры подделки подписи ожидается операция извлечения корней различной степени по простому модулю, которая в общем случае является достаточно легко осуществимой. Проиллюстрируем эту атаку на примере последней из рассмотренных схем. Введем новую переменную Z = RS mod р и переменную S выразим через Z и R: S = R-1Z mod р. Теперь уравнение проверки подписи имеет вид:
где Z’ = Z mod . Из последнего сравнения непосредственно следует формула для вычисления значения элемента подписи R:
В случаях простого и составного показателя у, к которому по модулю р относится число а, достаточно легко найти значение Z, для которого сумма Z + Z' имеет значение взаимно простое с , а значит, существует обратное по отношению к ней значение (Z + Z')-1 mod . Для таких значений Z легко вычисляется R, а затем и значение S = R-1Z mod p11.
Устранение такой атаки достигается следующими двумя способами:
- вместо значения R в качестве элемента подписи следует указывать значение k, т.е. подпись приобретает вид (k, S), при этом проверочное соотношение следует модифицировать, заменяя в нем R на ak mod р (фактически предлагается сделать небольшой шаг назад, поскольку при генерации подписи в гипотетической исходной схеме предварительно определялось значение к, а потом по нему вычислялся элемент подписи R);
- вместо простого модуля р может быть использован составной RSA-модуль, в результате чего без решения сложной задачи разложения модуля на простые множители операция вычисления корней будет вычислительно невыполнимой.
Возможен также вариант, в котором указанные два способа комбинируются. Во втором случае экзистенциальная подделка подписи и эффективные скрытые каналы предотвращаются. В следующих разделах эти способы рассматриваются более подробно и раскрываются некоторые дополнительные преимущества, которые они обеспечивают при синтезе конкретных схем ЭЦП.
ЗАКЛЮЧЕНИЕ
Способов защиты информации существует очень много, но каждый из них всегда можно отнести к одному из двух видов: физическое сокрытие информации от противника и шифрование информации. Зашифрованную информацию можно свободно распространять по открытым каналам связи без боязни ее раскрытия и нелегального использования. Хотя, конечно же, такая защита не абсолютно надежна, и каждый из способов шифрования характеризуется своей стойкостью, т.е. способностью противостоять криптографическим атакам.
Экономическая, политическая, юридическая и другие сферы жизни общества сегодня не могут существовать без использования цифровых подписей. Их применение находит место и в декларировании товаров и услуг, и в регистрации различных сделок по обьектам недвижимости, очень широко цифровые подписи используются в банковских системах, в электронной торговле, госзаказах, в системах обращения к органам власти, для обязательной отчётности перед гос учереждениями и для обычного юридического электронного документооборота. Целью моей работы было рассмотреть различные алгоритмы ЭЦП, как современные, так и те что уже не используются, в силу недостаточной криптостойкости. Но не смотря на то, что данные алгоритмы не используются в своём первоначальном виде они являются базой, на которой построены все действующие схемы.
В процессе написания данной курсовой работы передо мной стояли несколько задач, сделать обзор существующих алгоритмов цифровой подписи, дать определение понятию что такое ЭЦП, также основная задача рассмотреть алгоритм электронной цифровой подписи на основе решения системы сравнений. В ходе написания курсовой работы все эти задачи выполненны.
СПИСОК ЛИТЕРАТУРЫ
Федеральный закон от 06.04.2011 N 63-ФЗ (ред. от 19.12.2022) «Об электронной подписи» – URL: https://www.consultant.ru/document/cons_doc_LAW_112701/ (дата обращения: 20.12.2022).
ГОСТ Р 34.10-2001. Информационные технологии. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи.
ГОСТ Р 34.10-94. Информационные технологии. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма
Семёнов, Г. Цифровая подпись. Эллиптические кривые. / Г. Семёнов. // Открытые системы. – № 7-8/2022. – С. 98.
Полянская, О.Ю. Инфраструктура открытых ключей. Учебное пособие. / О.Ю. Полянская, В.С. Горбатов. – Москва, 2017.
Алферов, А.П.Основы криптографии / А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. – Москва, 2020.
Шнайер, Б. Прикладная криптография. / Б. Шнайер. – Москва, 2022.
Романец, Ю.В. Защита информации в компьютерных системах и сетях. / Ю.В. Романец, П.А.Тимофеев, В.Ф. Шаньгин – М.: Радио и связь, 2021. – 376 с.
Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. / Б. Шнайер. – М.: ТРИУМФ, 2022 – 816 с.
Игоничкина Е.В. Анализ алгоритмов электронной цифровой подписи – URL: https://security.ase.md/publ/ru/pubru86/ (дата обращения: 20.12.2022).
Молдовян, Н.А. Теоретический минимум и алгоритмы цифровойподписи. / Н.А. Молдовян. — СПб.: БХВ-Петербург, 2020. — 304 с.
Макаров В.В., Луца А.В., Стародубов Д.О. Законодательная база и алгоритмы использования электронной цифровой подписи в РФ / В.В. Макаров, А.В. Луца, Д.О. Стародубов // Международный журнал гуманитарных и естественных наук. 2020. №5-4. – URL: https://cyberleninka.ru/article/n/zakonodatelnaya-baza-i-algoritmy-ispolzovaniya-elektronnoy-tsifrovoy-podpisi-v-rf (дата обращения: 21.12.2022).
Анисимов, Б.В. Распознавание и цифровая обработка изображений / Б.В. Анисимов, В.Д. Курганов, В.К. Злобин. – М., 2019. – 667 c.
Байер, В.Н. Излучение релятивистских электронов / В.Н. Байер, В.М. Катков, В.С. Фадин. – М., 2017. – 980 c.
Богнер, Р. Введение в цифровую фильтрацию / Р. Богнер, А. Константинидис. – М., 2017. – 343 c.
Бойко Схемотехника электронных систем. Цифровые устройства / Бойко. – М.: БХВ-Петербург, 2017. – 605 c.
Бонч-Бруевич, А.М. Применение электронных ламп в экспериментальной физике / А.М. Бонч-Бруевич. – М.: Москва: технико-теоретической литературы; Издание 4-е, 2019. – 655 c.
Бурцев, В.С. Сергей Алексеевич Лебедев. К 100-летию со дня рождения основоположника отечественной электронной вычислительной техники / В.С. Бурцев. – М.: [не указано], 2017. – 184 c.
1 Федеральный закон от 06.04.2011 N 63-ФЗ (ред. от 19.12.2022) «Об электронной подписи» – URL: https://www.consultant.ru/document/cons_doc_LAW_112701/ (дата обращения: 20.12.2022).
2 ГОСТ Р 34.10-2001. Информационные технологии. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи.
3 ГОСТ Р 34.10-94. Информационные технологии. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма
4 Игоничкина Е.В. Анализ алгоритмов электронной цифровой подписи – URL: https://security.ase.md/publ/ru/pubru86/ (дата обращения: 20.12.2022).
5 Семёнов, Г. Цифровая подпись. Эллиптические кривые. / Г. Семёнов. // Открытые системы. – № 7-8/2022. – С. 98.
6 Полянская, О.Ю. Инфраструктура открытых ключей. Учебное пособие. / О.Ю. Полянская, В.С. Горбатов. – Москва, 2017. – С. 123.
7 Алферов, А.П.Основы криптографии / А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. – Москва, 2020. – С. 66.
8 Шнайер, Б. Прикладная криптография. / Б. Шнайер. – Москва, 2022. – С. 199.
9 Романец, Ю.В. Защита информации в компьютерных системах и сетях. / Ю.В. Романец, П.А.Тимофеев, В.Ф. Шаньгин – М.: Радио и связь, 2021. С. 135.
10 Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. / Б. Шнайер. – М.: ТРИУМФ, 2022 – С. 408.
11 Молдовян, Н.А. Теоретический минимум и алгоритмы цифровойподписи. / Н.А. Молдовян. — СПб.: БХВ-Петербург, 2020. — 304 с.
|
Скачать 121.31 Kb.