Реферат: Модернизация электронной подписи Эль-Гамаля
Введение
Проблема защитыинформации путем ее преобразования, исключающего ее прочтение постороннимлицом волновала человеческий ум с давних времен. История криптографии- ровесница истории человеческого языка. Более того, первоначально письменностьсама по себе была криптографической системой, так как в древних обществах еювладели только избранные.
Священныекниги Древнего Египта, Древней Индии тому примеры.
С широкимраспространением письменности криптография стала формироваться каксамостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры.Так, Цезарь в своей переписке использовал уже более менее систематический шифр,получивший его имя.
Бурное развитиекриптографические системы получили в годы первой и второй мировыхвойн. Начиная с послевоенного времени и по нынешний день появлениевычислительных средств ускорило разработку и совершенствование криптографических методов.
Почему проблемаиспользования криптографических методов в информационных системах(ИС) стала в настоящий момент особо актуальна?
С одной стороны,расширилось использование компьютерных сетей, в частностиглобальной сети Internet,по которым передаются большие объемы информации государственного,военного, коммерческого и частного характера, не допускающеговозможность доступа к ней посторонних лиц.
С другой стороны,появление новых мощных компьютеров, технологий сетевых и нейронных вычислений сделало возможнымдискредитацию криптографических систем еще недавно считавшихся практически не раскрываемыми.
В первой главеданной работы можно познакомиться с основными понятиями современнойкриптографии, требованиям к ним, возможностями ее практического применения.
Во второй главе работы с протоколами распределения криптографических ключей,понятием электронной подписи и протоколами электронной подписи..
Третья глава данной работырассказывает о хэш-функциях и (методах) алгоритмах их построения.
В четвертойглаве будет рассказано о модернизации электронной подписи Эль Гамаля и задачедискретного логарифмирования.
Глава 1. Основные понятиясовременной криптографии
Проблемойзащиты информации путем ее преобразования занимается
криптология(kryptos- тайный, logos — наука).Криптология разделяется на два
направления- криптографиюи криптоанализ.Цели этих направлений прямо
противоположны.
Криптографиязанимается поиском и исследованием математических методовпреобразования информации.
Сфера интересов криптоанализа - исследование возможностирасшифровывания информации без знания ключей.
В этойработе основное внимание будет уделенокриптографическим методам.
Современнаякриптография включает в себя четыре крупных раздела:
1.
2.
3.
4.
Основныенаправления использованиякриптографических методов — передача конфиденциальной информации по каналамсвязи (например, электронная почта), установление подлинности передаваемыхсообщений, хранение информации (документов, баз данных) на носителях взашифрованном виде.
Криптографиядает возможность преобразовать информацию таким образом, что ее прочтение(восстановление) возможно только при знании ключа.
В качествеинформации, подлежащей шифрованию и дешифрованию, будут рассматриваться тексты,построенные на некотором алфавите. Под этими терминамипонимается следующее.
Алфавит- конечное множество используемых для кодирования информации знаков.
Текст — упорядоченный набор из элементов алфавита.
В качестве примеров алфавитов, используемых в современных ИСможно привести следующие:
*<span Times New Roman"">
алфавит Z33 — 32 буквы русского алфавита и пробел;*<span Times New Roman"">
алфавит Z256 — символы, входящие в стандартные коды ASCII и КОИ-8;*<span Times New Roman"">
бинарныйалфавит — Z2 = {0,1};*<span Times New Roman"">
восьмеричныйалфавит или шестнадцатеричный алфавит;Шифрование — преобразовательный процесс: исходный текст, который носит такженазвание открытого текста, заменяетсяшифрованным текстом.
Дешифрование- обратный шифрованию процесс. На основе ключа шифрованный текст преобразуетсяв исходный.
Ключ — информация, необходимая длябеспрепятственного шифрования и дешифрования текстов.
Криптографическая система представляетсобой семейство T преобразованийоткрытого текста. Члены этого семейства индексируются, или обозначаютсясимволом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляетсобой последовательный ряд букв алфавита.
Криптосистемы разделяются на симметричные и соткрытым ключом.
В симметричных криптосистемах и дляшифрования, и для дешифрования используется одини тот же ключ.
В системах с открытым ключомиспользуются два ключа — открытый и закрытый, которые математически связаныдруг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощьюзакрытого ключа, известного только получателю сообщения.Термины распределениеключей и управление ключами относятсяк процессам системы обработки информации, содержанием которых являетсясоставление и распределение ключей между пользователями.
Электронной (цифровой) подписью называется присоединяемое ктексту его криптографическое преобразование, которое позволяет при получениитекста другим пользователем проверить авторство и подлинность сообщения.
Криптостойкостью называется характеристика шифра,определяющая его стойкость к дешифрованию без знания ключа (т.е.криптоанализу). Имеется несколько показателей криптостойкости, средикоторых:
·<span Times New Roman"">
·<span Times New Roman"">
ПреобразованиеTk определяется соответствующималгоритмом и значением параметра k.Эффективность шифрования с целью защиты информации зависит от сохранениятайны ключа и криптостойкости шифра.
Требования к криптосистемамПроцесс криптографическогозакрытия данных может осуществляться как программно, так и аппаратно.Аппаратная реализация отличается существенно большей стоимостью,однако ей присущи и преимущества: высокая производительность, простота,защищенность и т.д. Программная реализация более практична, допускаетизвестную гибкость в использовании.
Для современныхкриптографических систем защиты информации сформулированы следующиеобщепринятые требования:
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
·<span Times New Roman"">
Глава 2.Протоколы распределения криптографических ключей и протоколы электроннойподписи.
Системыс открытым ключом.
Как бы ни былисложны и надежны криптографические системы — их слабое мест при практическойреализации — проблема распределенияключей. Для того, чтобы был возможен обмен конфиденциальной информациеймежду двумя субъектами ИС, ключ должен быть сгенерирован одним изних, а затем каким-то образом опять же в конфиденциальном порядке передандругому. Т.е. в общем случае для передачи ключа опять же требуется использованиекакой-то криптосистемы.
Для решенияэтой проблемы на основе результатов, полученных классической и современнойалгеброй, были предложены системыс открытым ключом.
Сутьих состоит в том, что каждым адресатом ИС генерируются два ключа,связанные между собой по определенному правилу. Один ключ объявляетсяоткрытым, а другой закрытым. Открытый ключ публикуетсяи доступен любому, кто желает послать сообщение адресату.Секретный ключ сохраняется в тайне.
Исходныйтекст шифруется открытым ключом адресата и передается ему. Зашифрованныйтекст в принципе не может быть расшифрован тем же открытым
<img src="/cache/referats/4448/image002.jpg" v:shapes="_x0000_s1091">
ключом. Дешифрование сообщение возможно только с использованиемзакрытого ключа, который известен только самому адресату.
Криптографическиесистемы с открытым ключом используют так называемые необратимые или односторонние функции, которыеобладают следующим свойством: при заданном значении x относительно просто вычислитьзначение f(x), однако если y=f(x),то нет простого пути для вычисления значения x.
Множествоклассов необратимых функций и порождает все разнообразие систем соткрытым ключом. Однако не всякая необратимая функция годится дляиспользования в реальных ИС.
В самом определениинеобратимости присутствует неопределенность. Под необратимостью понимается нетеоретическая необратимость, а практическая невозможность вычислить обратноезначение используя современные вычислительные средства за обозримый интервалвремени.Поэтому чтобыгарантировать надежную защиту информации, к системам с открытым ключом(СОК) предъявляются два важных и очевидных требования:
1. Преобразованиеисходного текста должно быть необратимым и исключать его восстановлениена основе открытого ключа.
2. Определениезакрытого ключа на основе открытого также должно быть невозможнымна современном технологическом уровне. При этом желательна точнаянижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмышифрования с открытым ключом получили широкое распространение в современныхинформационных системах. Так, алгоритм RSA стал мировым стандартомде-факто для открытых систем и рекомендован МККТТ.
Вообще же все предлагаемые сегодня криптосистемы с открытымключом опираются на один из следующих типов необратимых преобразований:
1.
2.
3.
<span Times New Roman",«serif»"><span Times New Roman",«serif»">АлгоритмДиффи-Хеллмана<span Times New Roman",«serif»">.Диффи и Хелман предложили для созданиякриптографических систем с открытым ключом функцию дискретного возведения в степень.
Необратимость преобразования в этомслучае обеспечивается тем, что достаточно легко вычислить показательнуюфункцию в конечном поле Галуа состоящим из p элементов. (p — либопростое число, либо простое в любой степени). Вычисление же логарифмов в такихполях — значительно более трудоемкая операция.
Если y=SYMBOL97 f «Symbol» s 14ax,, 1<x<p-1, где — фиксированный элемент поля GF(p),то x=logSYMBOL97 f «Symbol» s 14ay над GF(p). Имея x, легко вычислить y. Для этого потребуется 2 ln(x+y) операций умножения.
Обратная задача вычисления x изy будет достаточно сложной. Если pвыбрано достаточно правильно, то извлечение логарифма потребует вычислений,пропорциональных
<span Times New Roman",«serif»">L(p)
<span Times New Roman",«serif»">= exp { (ln p ln ln p)0.5 }Для обмена информацией первый пользовательвыбирает случайное число x1,равновероятное из целых 1,...,p-1. Это число он держит в секрете, а другому пользователюпосылает число
<span Times New Roman",«serif»">y
<span Times New Roman",«serif»">1<span Times New Roman",«serif»">= <span Times New Roman",«serif»">SYMBOL97 f «Symbol» s 14<span Times New Roman",«serif»">a<span Times New Roman",«serif»">x1 mod pАналогично поступает и второй пользователь,генерируя x2 и вычислив y2, отправляя его первомупользователю.
В результате этого они могут вычислять k12= SYMBOL97 f «Symbol» s 14ax1x2 mod p.
Для того, чтобы вычислить k12, первый пользовательвозводит y2 в степень x1. То же делает и второйпользователь. Таким образом, у обоих пользователей оказывается общий ключ k12, который можно использоватьдля шифрования информации обычными алгоритмами. В отличие от алгоритма RSA,данный алгоритм не позволяет шифровать собственно информацию.
Не знаяx1 и x2, злоумышленник может попытаться вычислить k12, зная толькоперехваченные y1 иy2. Эквивалентность этой проблемы проблеме вычислениядискретного логарифма есть главный и открытый вопрос в системах с открытымключом. Простого решения до настоящего времени не найдено. Так, если дляпрямого преобразования 1000-битных простых чисел требуется 2000 операций, тодля обратного преобразования (вычисления логарифма в поле Галуа) — потребуетсяоколо 1030 операций.
Как видно, при всей простоте алгоритмаДиффи-Хелмана, его недостатком является отсутствие гарантированной нижнейоценки трудоемкости раскрытия ключа.
Кроме того, хотя описанный алгоритмпозволяет обойти проблему скрытой передачи ключа, необходимость аутентификацииостается. Без дополнительных средств, один из пользователей не может бытьуверен, что он обменялся ключами именно с тем пользователем, который ему нужен.Опасность имитации в этом случае остается.
В качестве обобщения сказанного ораспределении ключей следует сказать следующее. Задача управленияключами сводится к поиску такого протокола распределения ключей,который обеспечивал бы:
*<span Times New Roman""> возможность отказа от центра распределенияключей;
*<span Times New Roman""> взаимное подтверждение подлинности участниковсеанса;
*<span Times New Roman""> подтверждение достоверности сеанса механизмомзапроса-ответа,
использование для этого программныхили аппаратных средств;
*<span Times New Roman""> использование при обмене ключами минимальногочисла сообщений.
Иерархическиесхемы распределения ключей.
Рассмотримследующую задачу.
Пусть абоненты сети связи неравноправны между собой, а разделены на «классы безопасности» C1,C2,…,Cn. На множестве этих классов определен некоторый частичныйпорядок; если Cj < Ci,то говорят, что Ci доминирует Cj , т.е. имеет более высокий уровень безопасности, чем Cj .Задача состоит в том, чтобы выработать секретные ключи ki длякаждого класса Ciтакимобразом, чтобы абонент из Ciмог вычислить kj в том итолько в том, когда Ci <span Times New Roman";mso-hansi-font-family:«Times New Roman»; color:black;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">³
Cj.Эта задача быларешена в общем виде Эклом и Тейлором в связи с проблемой контроля доступа. В ихметоде каждый класс безопасности получает, кроме секретного, также и открытыйключ, который вместе с секретным ключом класса, доминирует данный, позволяетпоследнему вычислить секретный ключ данного класса.
<img src="/cache/referats/4448/image004.gif" align=«left» hspace=«12» v:shapes="_x0000_s1078">Для случая, когдачастичный порядок является деревом,имеется схема Сандху [San], которая позволяет добавлять новые классы безопасности безизменения ключей существующих классов.
<img src="/cache/referats/4448/image004.gif" align=«left» hspace=«12» v:shapes="_x0000_s1077"> Приведем описание иерархической схемыраспределения ключей, предложенной Ву и Чангом для случая, когда частичныйпорядок является деревом.
<img src="/cache/referats/4448/image006.gif" v:shapes="_x0000_s1080">
Пусть p – большое простоечисло, V = Zp<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;color:black;mso-ansi-language:EN-US; mso-char-type:symbol;mso-symbol-font-family:Symbol">´
Предположим, чтокаждому классу безопасности сопоставлен идентификатор
i <span Times New Roman";mso-hansi-font-family:«Times New Roman»;color:black; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Î
Zp {0};класс с идентификатором i мы будем обозначатьчерез Ci . Ввиду того, что частичный порядок на множестве классовбезопасности является деревом, для описания протокола достаточно описатьпроцедуры выработки секретного ключа для корневого класса безопасности (т.е.класса с наиболее высоким уровнем безопасности) и для произвольного класса Cj приусловии, что секретный ключ для класса Ci ,непосредственно доминирующего Cj (т.е.такого, что Cj < Ciи не существует класса Cr такого,что Cj < Cr< Ci), уже выработан.1.<span Times New Roman""> Для корневого классабезопасности (например
C1) выбирается произвольный секретный ключ Ki <span Times New Roman";mso-hansi-font-family:«Times New Roman»; color:black;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">ÎV {(0,0,0)}.2.<span Times New Roman""> Пусть класс
Ciдоминируеткласс Cjидля Ci уже выработан секретный ключKi <span Times New Roman";mso-hansi-font-family:«Times New Roman»; color:black;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">ÎV. Тогда в качестве секретного ключа для Cj выбираетсявектор <img src="/cache/referats/4448/image008.gif" v:shapes="_x0000_s1081">
<img src="/cache/referats/4448/image010.gif" align=«left» hspace=«12» v:shapes="_x0000_s1082">где Pj –вектор из V, выбранный случайно так, чтобыбыло определено.
После чего вектор Pj делаетсяобщедоступным.
Таким образом, впроцессе выполнения протокола для каждого класса безопасности Ci вырабатываетсясекретный ключ Ki и открытый ключ Pj (кромекорневого класса). Если теперь Cj < Ci, то абонент из Ci можетвычислить Kj следующим образом.
Существует цепьклассов безопасности Ci= Cro>Cr1>…>Crn = Cj, где Cl-1непосредственно доминирует Clдлявсех L = 1,…,n. Абонент Ci,зная Ki и Pr1, вычисляет по формуле (**), затем, знаяKr1 и Pr2, вычисляетKr2по той же формуле и т.д.; после n шагов будетвычислен Krn = Kj.
Электроннаяподпись
В чем состоитпроблема аутентификации данных?
Вконце обычного письма или документа исполнитель или ответственноелицо обычно ставит свою подпись. Подобное действие обычно преследуетдве цели.
Во-первых, получатель имеетвозможность убедиться в истинности письма,
сличивподпись с имеющимся у него образцом. Во-вторых, личная подпись являетсяюридическим гарантом авторства документа. Последний аспект особенноважен при заключении разного рода торговых сделок, составлении доверенностей,обязтельств и т.д.
Если подделатьподпись человека на бумаге весьма непросто, а установить авторствоподписи современными криминалистическими методами — техническаядеталь, то с подписью электронной дело обстоит иначе. Подделать цепочкубитов, просто ее скопировав, или незаметно внести нелегальные исправленияв документ сможет любой пользователь.
Сшироким распространением в современном мире электронных форм документов(в том числе и конфиденциальных) и средств их обработки особо актуальнойстала проблема установления подлинности и авторства безбумажнойдокументации.
<span Times New Roman",«serif»">Итак, пусть имеются два пользователяАлександр и Борис.
<span Times New Roman",«serif»">От каких нарушений и действийзлоумышленника должна защищать система аутентификации.
<span Times New Roman",«serif»">Отказ (ренегатство).
Александрзаявляет, что он не посылал сообщение Борису, хотя на самом деле онвсе-таки посылал.
Дляисключения этого нарушения используется электронная (или цифровая)подпись.
<span Times New Roman",«serif»">Модификация (переделка).
Борисизменяет сообщение и утверждает, что данное (измененное) сообщение послал емуАлександр.
<span Times New Roman",«serif»">Подделка.
Борисформирует сообщение и утверждает, что данное (измененное) сообщение послал емуАлександр.
<span Times New Roman",«serif»">Активный перехват.
Владимирперехватывает сообщения между Александром и Борисом с целью их скрытоймодификации.
Длязащиты от модификации, подделки и маскировки используются цифровые сигнатуры.
<span Times New Roman",«serif»">Маскировка (имитация).
Владимирпосылает Борису сообщение от имени Александра.
Вэтом случае для защиты также используется электронная подпись.
<span Times New Roman",«serif»">Повтор.
Владимирповторяет ранее переданное сообщение, которое Александра посылалранее Борису. Несмотря на то, что принимаются всевозможные меры защитыот повторов, именно на этот метод приходится большинство случаев незаконногоснятия и траты денег в системах электронных платежей.
Наиболее действеннымметодом защиты от повтора являются
*<span Times New Roman"">
использование имитовставок,*<span Times New Roman"">
учет входящих сообщений.Протоколы электроннойподписи
Протоколы(схемы) электронной подписи являются основными криптографическим средствомобеспечения целостности информации.
Схема Эль Гамаля.
Пусть обоимучастникам протокола известны некоторое простое число p, некоторой порождающейg группы Z*p и некоторая хэш-функция h.
Подписывающийвыбирает секретный ключ x <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">Î
R Z*p-1 ивычисляет открытый ключ y = g-xmod p. Пространством сообщений в данной схеме является Zp-1 .Длягенерации подписи нужно сначала выбрать u<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">Î
R Zp-1.Если u<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">ÏRZ*p-1(что проверяетсяэффективно), то необходимо выбрать новое u. Если же u <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">ÎR Z*p-1 , то искомой подписью для сообщения m является пара (r,s),где r = gu mod p иs = u-1(h(m)+xr) mod (p-1). Параметр u должен быть секретным и может быть уничтожен послегенерации подписи.
Для проверкиподписи (r,s) для сообщения m необходимо сначала проверить условия r <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">ÎZ*p и s
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">ÎZp-1 . Если хотя бы одно из нихложно, то подпись отвергается. В противном случае подпись принимается и толькотогда, когда gh(m)<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;color:black;mso-char-type:symbol; mso-symbol-font-family:Symbol">ºyrrs(modp ).Вера в стойкостьсхемы Эль Гамаля основана на (гипотетической) сложности задачи дискретногологарифмирования по основанию g.
Схема Фиата – Шамира.
Для ееобеспечения центр обеспечения безопасности должен выбрать псевдослучайнуюфункцию f, криптографическую хэш-функцию h, а также выбрать различные большие простые числа p, q и вычислить n = pq. Число nи функции fи hявляются общедоступными и публикуются центром, а числа pиqдолжны быть секретными. Кроме того, схема использует дванатуральных параметра lи t.
Для каждого пользователя центр обеспечениябезопасности генерирует идентификационную информацию I, содержащую, например, имя пользователя, его адрес,идентификационный номер и т. п., и для каждого j= 1,…,l вычисляет
yi = f(I,j), отбирает среди них квадратичные вычеты по модулю n(изменив обозначения, мы считаем, что yiдля всех j= 1,…,l являются квадратичными вычетами по млдулю n), и вычисляет xi– наименьший квадратичный корень по модулю nиз yi-1mod n. Числа yi играют рольоткрытого ключа, а xi– секретного. Так как эти ключи вычисляются сиспользованием I, схема Фивта – Шамира относится к схемам, основаннымна идентификационной информации (identitybased). В другом варианте схемы Фиата – Шамира сразу выбираются(псевдослучайным образом) параметру yi. На практике идентификационная информация Iи/или открытый ключ (y1,…,yl) каждого пользователя помещаются в некоторыйсправочник, доступный всем пользователям для чтения, но не доступный длязаписи. Для обеспечения аутентичности, данные в этом справочнике заверяютсяподписью центра обеспечения безопасности. Секретный ключ (x1,…,xl)и идентификационная информация Iмогут быть помещены на интеллектуальную карточкупользователя.
Для генерации подписи для обеспечения mподписывающий
1.<span Times New Roman""> выбирает
ui<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">ÎR<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Zn(каждое ui