Защита информации: цифровая подпись

САНКТ ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТФакультет технической кибернетикиКафедра информационных и управляющих системРеферат Цифровая подпись Студент Барташевич Е.Е.Преподаватель Чистяков И.В.Санкт-Петербург2001Содержание 1. Ассиметричныеалгоритмы шифрования. 1. Стандартассимметричного шифрования RSA 41.1.1.

Генерацияключей. 2. Шифрование расшифрование. 2. АлгоритмЭльГамаля. 1. Общиесведения. 2. Шифрованиесообщений. 3. Подтверждениеподлинности отправителя. 3. АлгоритмШамира. 1. Общееописание. 2. Передачасообщений. 3. Примериспользования. 4. Кpиптосистемына основе эллиптических уpавнений.

82. Электронно-цифроваяподпись. 1. Общиеположения. 93. АлгоритмDSA 1. ГенерацияЭЦП 2. ПроверкаЭЦП 124. Стандартна процедуры ЭЦП ГОСТ Р 34.10-1. ГенерацияЭЦП 2. ПроверкаЭЦП 135. Цифровыеподписи, основанные на симметричных криптосистемах. 136. Атаки наЭЦП 227. Некоторыесредства работы с ЭЦП 237.1.

PGP. 2. GNUPrivacy Guard GnuPG 3. Криптон. 4. ВербаО 248. Литератураи ссылки. 261. Ассиметричные алгоритмы шифрованияРазвитие основных типов криптографических протоколов ключевой обмен, электронно-цифровая подпись ЭЦП , аутентификация и др былобы невозможно без создания открытых ключей и построенных на их основеассиметричных протоколов шифрования. Основная идея асимметричныхкриптоалгоритмов состоит в том, что для шифрования

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

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

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

Ej и закрытый Dj, где j номер абонента. Все открытые ключи известнывсем пользователям сети, каждый закрытый ключ, наоборот, хранится только у тогоабонента, которому он принадлежит. Если абонент, скажем под номером 7,собирается передать информацию абоненту под номером 9, он шифрует данные ключомшифрования E9 и отправляет ее абоненту9. Несмотря на то, что все пользователи сети знают ключ

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

E7,а для дешифрования ключ D7 .Как мы видим, во-первых, в асимметричных системах количество существующихключей связано с количеством абонентов линейно в системе из N пользователейиспользуются 2 N ключей , а не квадратично, как в симметричных системах. Во-вторых, принарушении конфиденциальности k-ой рабочей станции злоумышленник узнает толькоключ Dk это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяетвывадавать себя за

него при отправке писем. 1. Стандарт ассимметричного шифрования RSA Самым распространенным алгоритмомассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математикамиРональдом Ривестом R.Rivest , Ади Шамиром A.Shamir и Леонардом Адльманом L.Adleman в 1977-78 годах. Разработчикам данногоалгоритма удалось эффективно воплотить идею

односторонних функций с секретом.Стойкость RSA базируется на сложностифакторизации больших целых чисел. В 1993году метод RSA был обнародован и принят в качествестандарта PKCS 1 RSA Encryption standart . RSA можно применять как для шифрования расшифрования,так и для генерации проверки электронно-цифровой подписи.1. Генерация ключей Первым этапом любого асимметричного алгоритма является создание пары ключей открытого изакрытого и распространение

открытого ключа по всему миру . Дляалгоритма RSA этап создания ключей состоит из следующих операций Выбираются два простых ! числа p и q Вычисляется их произведение n p q Выбирается произвольное число e e lt n , такое, что НОД e, p-1 q-1 1, то есть e должно быть взаимно простым с числом p-1 q-1 . Методом Евклида решается в целых числах ! уравнение e d p-1 q-1 y 1.

Здесь неизвестными являются переменные d и y метод Евклида как рази находит множество пар d,y , каждая из которых является решением уравнения вцелых числах. Два числа e,n публикуются как открытый ключ. Число dхранится в строжайшем секрете это и есть закрытый ключ, который позволитчитать все послания, зашифрованные с помощью пары чисел e,n . 2. Шифрование расшифрование Как же производится собственно шифрование с помощью этих чисел

Отправитель разбивает свое сообщение на блоки, равные k log2 n бит, где квадратные скобки обозначают взятиецелой части от дробного числа. Подобный блок, как Вы знаете, может быть интерпретирован как число издиапазона 0 2k-1 . Для каждого такого числа назовем его mi вычисляетсявыражение ci mi e mod n. Блокиci и есть зашифрованное сообщение, иих можно спокойно передавать по открытому каналу, поскольку

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

число d. Достаточно давно была доказана теорема Эйлера,частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство x p-1 q-1 mod n 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень -y x -y p-1 q-1 mod n 1 -y 1. Теперь умножим обе ее части на x x -y p-1 q-1 1 mod n 1 x x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбиралис помощью алгоритма Евклида d такое, что e d p-1 q-1 y 1, то есть e d -y p-1 q-1 1. А следовательно в последнем выражениипредыдущего абзаца мы можем заменить показатель степени на число e d . Получаем xe d mod n x. То есть для того чтобы прочесть сообщение ci mi e mod n достаточно возвести егов степень dпо модулю m ci d mod n mi e d modn mi.

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

Общие сведенияКриптографы со своей стороны вели поиски более эффективных систем открытогошифрования и в 1985 году Т.Эль-Гамаль США предложил следующую схему наоснове возведения в степень по модулю большого простого числа P.Задается большое простое число P и целое число A, 1 lt A lt P. Сообщения представляются целыми числами M из интервала 1 lt M lt P.1.2.2. Шифрование сообщенийПротокол передачи сообщения

M выглядит следующим образом.абоненты знают числа A и P абоненты генерируют независимо друг от друга случайные числа Ka, Kbудовлетворяющих условию 1 lt K lt Pполучатель вычисляет и переда т отправителю число B, определяемое последовательностью В A Kb mоd P отправитель шифрует сообщение M и отправляет полученную последовательностьполучателю

C M B Ka mоd P получатель расшифровывает полученное сообщение D A Ka -Kb mоd P M C D mоd P В этой системе открытого шифрования та же степень защиты, что для алгоритмаRSA с модулем N из 200 знаков, достигается уже при модуле P из 150знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации.Однако, в таком варианте открытого шифрования нет подтверждения подлинностисообщений.1.2.3.

Подтверждение подлинностиотправителяДля того, чтобы обеспечить при открытом шифровании по модулю простого числаP также ипроцедуру подтверждения подлинности отправителя Т.ЭльГамаль предложилследующий протокол передачи подписанного сообщения M абоненты знают числа A и P отправитель генерирует случайное число и хранит его в секрете Kaудовлетворяющее условию 1 lt Ka lt Pвычисляет и переда т получателю число

B, определяемое последователньостью В A Ka mоd P Для сообщения M 1 lt M lt P выбирает случайное число L 1 lt L lt P ,удовлетворяющее условию L , P - 1 1вычисляет число R A L mоd P решает относительно S M Ka R L S mоd P переда т подписанное сообщение M, R, S получатель проверяет правильность подписи A

M B R R S mоd P В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом дляпроверки достоверности подписи число B. Процедура проверки подписи служит также и дляпроверки правильности расшифрования, если сообщения шифруются.1.3. Алгоритм Шамира1.3.1. Общее описаниеЕще один интересный пример использования возведения в степень по модулюбольшого простого числа P для открытого шифрования предложил

А.Shamir один из авторов RSA . Как и в системе ЭльГамаля сообщения M представляются целымичислами из интервала 1 lt M lt P.1.3.2. Передача сообщенийПередача сообщения происходит следующим образом абоненты знают числа P абоненты генерируют независимо друг от друга случайные числа Ka, Kbудовлетворяющих условию 1 lt K lt Pотправитель вычисляет значение и переда т получателю

C M Ka mоd P получатель вычисляет и переда т отправителю число B, определяемое последовательностью D C Kb mоd P отправитель аннулирует свой шифр и отправляет полученную последовательностьполучателю E D X-1 mоd P E D Fa mоd P где Fa Ka -1получатель расшифровывает полученное сообщение M E Fb mоd P где Fb Kb 11.3.3. Пример использованияЭта процедура

ОШ может быть использована, например, для таких экзотических целей как игра в карты по телефону.Действительно, если игрок A желает сдать игроку B, скажем, 5 карт из 52как при игре в покер, он зашифровывает обозначения всех карт и передает ихигроку B Ca Ma Ka mоd P гдеI 1,2 52Игрок Bвыбирает из них 5, зашифровывает своим ключом 22 и возвращает игроку А Da Ca Kb mоd P гдеI 1,2 5Игрок Aснимает с этих 5 карт свой шифр и выдает их игроку

B.Игрок Bрасшифровывает полученные карты Ma Ea Fb mоd P При этом оставшаяся часть колоды C 6 C 52 теперь находится у игрока B, но он не может раскрытьэти карты, т.к. они зашифрованы на ключе его партнера A. Остальные процедуры игры проделываютсяаналогично.1.4. Кpиптосистемы на основе эллиптических уpавненийЭллиптические кpивые - математический объект, котоpый

может опpеделен над любым полем конечным, действительным, pациональным иликомплексным . В кpиптогpафииобычно используются конечные поля. Эллиптическая кpивая есть множество точек x,y , удовлетвоpяющее следующему уpавнению y2 x3 ax b,а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA и Эль-Гамаля.В pеальныхкpиптосистемахна базе эллиптических уpавнений

используется уpавнениеy2 x3 ax b mod p,где p - пpостое.Пpоблемадискpетногологаpифма наэллиптической кpивой состоит в следующем дана точка G на эллиптической кpивой поpядка r количество точек на кpивой и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y xG, то есть Y есть х-я степень G.2. Электронно-цифровая подпись2.1.

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

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

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

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

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

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

частного случая задачи вычислениядискретного логарифма. Современные методы решения этой задачи имеютприблизительно ту же эффективность, что и методы решения задачи факторизации всвязи с этим предлагается использовать ключи длиной от 512 до 1024 бит с темиже характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит. С момента опубликования проект получил много критических

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

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

SHA Secure Hash Algorithm ,рекомендованную для использования вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного вкриптографической литературе. 3.1. Генерация ЭЦППри генерации ЭЦП используютсяпараметры трех групп - общиепараметры- секретныйключ- открытый ключОбщие параметры необходимы для функционирования системы в целом.

Секретныйключ используется для формирования ЭЦП, а открытый для проверки ЭЦП. Общимипараметрами системы являются простые целые числа p,q,g, удовлетворяющие следующим условиям p 2 511 lt p lt 2 512q простой делитель числа p-1 , который удовлетворяет условию 2 159 lt q lt 2 160g так называемый генератор,удовлетворяющий равенству g h p-1 q mod p gt 1.Парараметры p,q,g публикуются для всех участников обмена ЭД сЭЦП.Секретный ключ x случайно выбирается из диапазона 1,q и держится

в секрете.Открытый ключ вычисляется y g xmod p.Также при описании данной схемы будут использоваться следующие обозначенияи доролнительные параметры m входное сообщение пользователя для схемы сЭЦП k - случайное число, удовлетворяющее условию 0 lt k lt q,хранящееся в секрете и меняющееся от одной подписи к другой H хэш-функция, h хэш-код сообщения.Процесс генерации ЭЦП состоит из нескольких этапов 1.Вычисляется хэш-код сообщения m h

H m 2.Из диапазона 1,q случайным образом выбираетсязначение k ивычисляется r g k mod p mod q3. Вычисляется S k -1 h xr mod q, где k -1удовлетворяет условию k -1 k mod q 1Значения r,s являются ЭЦП сообщения m ипередаются вместе с ним по каналам связи.3.2. Проверка ЭЦППусть принято сообщение m1 и его подпись s1,r1.Проверка ЭЦП происходит следующим образом - проверяетсявыполнений условий 0 lt r1 lt q,

0 lt s1 lt q, иесли хотя бы одно из них нарушено, подпись отвергается Вычисляютсязначения w s1 -1 modqu1 H m1 w mod qu2 r1 w mod qv g u1y u2 mod p mod q- проверяетсяравенство v r1Если последнее равенство выполняется, то подпись принимается. В данномстандарте специфицируется также процедура генерации основных параметров системыи проводится доказательство того, что если v r1, то m1 m, r1 r, s1 s.4.

Стандарт на процедуры ЭЦП ГОСТ Р 34.10-94Отечественным стандартом на процедуры выработки и проверки ЭЦП являетсяГОСТ Р 34.10-94. Схема ЭЦП, предложеннаяв данном стандарте, во многом напоминает подпись в DSA.Цифровая подпись представляет собой два больших целых простых числа. Общедоступные параметры схемы ЭЦП p,q,a должны удовлетворять следующим условиям p 2 501 lt p lt 2 512 или 2 1020 lt p lt 2 1020q простой делитель числа p-1 , который удовлетворяет условию 2 254 lt q lt 2 256a 1

lt a lt p-1, a q mod p 1Секретный ключ x случайно выбирается из диапазона 1,q и держится в секрете.Открытый ключ вычисляется y a xmod p.4.1. Генерация ЭЦППроцесс генерации ЭЦП состоит из нескольких этапов 1.Вычисляется хэш-код сообщения m h H m хэш-функция, используемая в данном стандарте в соответствии с ГОСТ Р 34.10-94 , если h m mod p 0, то h m присваевается значение 0 025512.Из диапазона 1,q случайным

образом выбираетсязначение k 3. вычисляется r a k mod p , r1 r mod p если r1 0, следует вернуться кпредыдущему этапу и выработать другое значение k.3. Вычисляется s xr1 kh m mod p если s 0, тонеобходимо выработать другое значение k.Значения r1,s1 являются ЭЦП сообщения m ипередаются вместе с ним по каналам связи.4.2. Проверка ЭЦППроверка ЭЦП происходит следующим образом - проверяетсявыполнений условий 0 lt r lt q, 0 lt s lt q, иесли хотя бы одно из них нарушено, подпись отвергается

Вычисляетсяхэш-код данного сообщения h H m Если h m mod p 0, то битовое представление h m 0 02551- Вычисляетсязначение v h m q-2 mod p Вычисляетсязначения z1 sv mod p z2 q-r1 v mod p Вычисляетсязначение u a z1y z2 mod p mod q - проверяетсяравенство u r1Если последнее раенство выполняется, то подпись принимается.5. Цифровые подписи, основанные на симметричныхкриптосистемахНа первый взгляд, самаэта идея может показаться абсурдом. Действительно, общеизвестно, что такназываемая современная

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

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

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

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

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

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

шифре. Предположим, в нашемраспоряжении есть алгоритм зашифрования EK, оперирующий блоками данных X размера n и использующий ключразмером nK X n, K nK. Структура ключевой информации в схеме следующая секретный ключ подписи kS выбирается как произвольная случайная пара ключей k0,k1 используемого блочногошифра kS k0,k1 Таким образом, размер ключа подписи равен удвоенному размеру ключаиспользованного блочного шифра

KS 2 K 2nK.Ключ проверки представляет собой результат шифрования двух блоков текстаX0 и X1 с ключами k0 и k1соответственно kV C0,C1 где являющиеся параметром схемы блоки данных несекретны и известныпроверяющей подпись стороне. Таким образом, размер ключа проверки подписи равенудвоенному размеру блока использованного блочного шифра kV 2 X 2n.Алгоритм Sig выработки цифровойподписи для бита t t

О 0,1 заключается просто в выборе соответствующей половины из пары,составляющей секретный ключ подписи s S t kt.Алгоритм Ver проверки подписисостоит в проверке уравнения Ekt Xt Ct, которое, очевидно, должно выполняться для нашего t. Получателю известнывсе используемые при этом величины.Таким образом, функцияпроверки подписи будет следующей .

Покажем, что данная схемаработоспособна, для чего проверим выполнение необходимых свойств схемы цифровойподписи 1. Невозможностьподписать бит t, если неизвестен ключ подписи. Действительно, для выполнения этогозлоумышленнику потребовалось бы решить уравнение Es Xt Ct относительно s, что эквивалентно определению ключа для известныхблоков шифрованного и соответствующего ему открытого текста, что вычислительноневозможно в силу использования стойкого шифра.2.

Невозможностьподобрать другое значение бита t, которое подходило бы под заданную подпись,очевидна число возможных значений бита всего два и вероятность выполнения двухследующих условий одновременно пренебрежимо мала в просто в силу использованиякриптостойкого алгоритма Es X0 C0,Es X1 C1.Таким образом,предложенная Диффи и Хеллманом схема цифровой подписи на основе классическогоблочного шифра обладает такой же стойкостью,

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

размер подписываемого блока.Предположим, что в схеме используется криптографический алгоритм EK сразмером блока и ключа, соответственно n и nK. Предположим также, что используется функцияхэширования с размером выходного блока nH. Тогдаразмеры основных рабочих блоков будут следующими размер ключа подписи nkS 2nHЧnK.размер ключа проверкиподписи nС 2nHn.размер подписи nS nHЧnK.Если, например, вкачестве основы в данной схеме будет

использован шифр ГОСТ 28147 89 с размеромблока n 64 бита иразмером ключа nK 256 бит, и для выработкихэш блоков будет использован тот же самый шифр в режиме выработки имитовставки,что даст размер хэш блока nH 64 то размеры рабочих блоков будут следующими размер ключа подписи nkS 2nHЧnK 2Ч64Ч256бит 4096 байт размер ключа проверкиподписи nС 2nHn 2Ч64Ч64 бит 1024 байта.размер подписи nS nHЧnK 64Ч256 бит 2048 байт.Второй недостаток даннойсхемы, быть может, менее заметен, но столь же серьезен.

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

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

Какобычно, предположим, что в нашем распоряжении имеется криптографическийалгоритм EK с размером блока данных и ключа соответственно n и nK бит,причем n nK. Пусть в нашемраспоряжении также имеется некоторая функция отображения n битовых блоковданных в nK битовые Y Pn nK X , X n, Y nK. Определим рекурсивную функцию Rk односторонней прокрутки блока данных T размером n бит k раз k 0 при помощи следующей формулы где

X произвольный несекретный n-битовый блок данных,являющийся параметром процедуры прокрутки. По своей идее функция односторонней прокруткичрезвычайно проста, надо всего лишь нужное количество раз k выполнитьследующие действия расширить n-битовый блок данных T до размераключа использованного алгоритма шифрования nK , наполученном расширенном блоке как на ключе зашифровать блок данных X,результат зашифрования занести на место исходного блока данных

T .По определению операция Rk T обладает двумя важными для нассвойствами 1. Аддитивностьи коммутативность по числу прокручиваний Rk k T Rk Rk T Rk Rk T .2. Односторонностьили необратимость прокрутки если известно только некоторое значение функции Rk T , то вычислительно невозможно найти значение Rk T для любого k lt k еслибы это было возможно, в нашем распоряжении был бы способ определить ключшифрования

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

размеру блока данных использованного блочного шифра kS 2n Ключ проверки подписивычисляется как пара блоков, имеющих размер блоков данных использованногоалгоритма по следующим формулам kC C0,C1 R2nT 1 K0 ,R2nT 1 K1 .В этих вычислениях также используются несекретные блоки данных X0и X1, являющиеся параметрами функции одностороннейпрокрутки , они обязательно должны быть различными.

Таким образом, размер ключапроверки подписи также равен удвоенному размеру блока данных использованногоблочного шифра kC 2n.Вычисление и проверка ЭЦП будут выглядеть следующим образом Алгоритм SignT выработки цифровой подписи для nT-битового блока Tзаключается в выполнении односторонней прокрутки обеих половин ключа подписи Tи 2nT 1 T раз соответственно s SignT T s0,s1 .Алгоритм

VernT проверки подписи состоит в проверкеистинности соотношений , которые,очевидно, должны выполняться для подлинного блока данных T R2nT 1 T s0 R2nT 1 T RT k0 R2nT 1 T T k0 R2nT 1 k0 C0,RT s1 RT R2nT 1 T k1 RT 2nT 1 T k1 R2nT 1 k1 C1.Таким образом, функция проверки подписи будетследующей Покажем, что для даннойсхемы выполняются необходимые условия работоспособности схемы подписи

Предположим, что враспоряжении злоумышленника есть nT-битовый блок T, его подпись s s0,s1 ,и ключ проверки kC C0,C1 . Пользуясь этой информацией, злоумышленникпытается найти правильную подпись s s 0,s 1 для другого nT-битового блока T .Для этого ему надо решить следующие уравнения относительно s 0 и s 1 R2nT 1 T s 0 C0,RT s 1 C1.В распоряжениизлоумышленника есть блок данных

T с подписью s s0,s1 ,что позволяет ему вычислить одно из значений s 0,s 1,даже не владея ключом подписи a если T lt T , то s 0 RT k0 RT T RT k0 RT T s0 , b если T gt T , то s 1 R2nT 1 T k1 RT T R2nT 1 T k1 RT T s1 .Однако для нахождениявторой половины подписи s 1и s 0 в случаях a и b соответственно емунеобходимо выполнить прокрутку в обратную сторону, т.е. найти Rk X , располагая только значением для большего k, что является

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

SnT T s0,s1 RT k0 , R2nT 1 T k1 ,s SnT T s 0,s 1 RT k0 , R2nT 1 T k1 ,но s s , следовательно RT k0 RT k0 и R2nT 1 T k1 R2nT 1 T k1 .Положим дляопределенности T T , тогда справедливо следующее RT T k0 k0 ,RT T k1 k1 ,где k0 RT k0 ,k1 R2nT 1 T k1 Последнее условиеозначает, что прокручивание двух различных блоков данных одно

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

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

n, а размерподписываемых битовых групп равен nT. Предположим также, что если последняя группасодержит меньшее число битов, обрабатывается она все равно как полная nT-битоваягруппа. Тогда размеры ключей подписи проверки и самой подписи совпадают и равныследующей величине бит,где йxщобозначает округление числа x до ближайшего целого в сторонувозрастания. Число операций шифрования EK X , требуемое для реализации процедурсхемы, определяются нижеследующими

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

Например, если схема подписибудет построена на алгоритме ГОСТ 28147-89, то размер ключа подписи будет равен256 битам.2. Аналогично,нет необходимости хранить массив ключей проверки подписи отдельных битовыхгрупп блока, достаточно хранить его значение хэш-функции этого массива. Приэтом алгоритм выработки ключа подписи и алгоритм проверки подписи будутдополнены еще одним шагом вычислением хэш-функции массива проверочныхкомбинаций

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

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

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

комбинациймладшего уровня. Чем выше уровень комбинации, тем больше отдельных ключейпроверки учитывается в ней. Предположим, что нашасхема рассчитана на 2L сообщений. Обозначим через i-тую комбинацию l-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, тосправедливо следующее условие 0 i lt 2L l, а i-ая проверочная комбинация l-того уровнярассчитана на 2l сообщений с номерами от iЧ2l до i 1 Ч2l 1 включительно.

Число комбинаций нижнего, нулевого уровня равно 2L, а самоговерхнего, L-того уровня одна, она и является контрольной комбинацией всех 2L сообщений,на которые рассчитана схема. На каждом уровне, начинаяс первого, проверочные комбинации рассчитываются по следующей формуле ,где через A B обозначен результат конкатенациидвух блоков данных A и B, а через H X процедура вычисления хэш-функцииблока данных

X. При использованииуказанного подхода вместе с подписью сообщения необходи мо передать не N 1, как в исходномварианте, а только log2N контрольныхкомбинаций. Передаваться должны комбинации, соответствующие смежным ветвямдерева на пути от конечной вершины, соответствующей номеру использованнойподписи, к корню.Пример организациипроверочных комбинаций в виде двоичного дерева в схеме на восемь сообщений при веденана рисунке 4.1.

Так, при передаче сообще ния 5 контрольная комбинациявыделена рамкой вместе с его под писью должны быть переданы кон трольнаякомбинация сообщения 4 C4 0 , общая для сообщений 6 7 C3 1 и общая для сообще ний 0 3 C0 2 , все они выделе ны на рисунке другим фоном. При проверкеподписи значение C5 0 будет вычислено из сообщения и его подписи, а итоговая контрольнаякомбинация, подлежащая сравнению с эталонной, по следующей формуле

C C0 3 H C0 2 H H C4 0 C5 0 C3 1 .Необходимость отправлятьвместе с подписью сообщения дополнительную информацию, нужную для проверкиподписи, на самом деле не очень обременительна. Действительно, в системе на1024 210 подписей вместе с сообщением и его подписью необходимодополнительно передавать 10 контрольных комбинаций, а в системе на 1048576 220 подписей всего 20комбинаций. Однако, при большом числе подписей, на которые рассчитана система,возникает другая проблема хранение

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

всех уровней, а второйтребует большого объема вычислений в момент формирования подписи. Можноиспользовать и компромиссный подход хранить все хэш-комбинации начиная снекоторого уровня l , а комбинации меньшего уровня вычислять приформировании подписи. В рассмотренной вышесхеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций,используемых при проверки всего их 15, но самая верхняя не используется ,тогда при проверке подписи их не надо будет

вычислять заново. Можно хранить 6комбинаций начиная с уровня 1 C0 1 , C1 1 , C2 1 , C3 1 , C0 2 , C1 2 , тогда при проверке подписи сообщения 5необходимо будет заново вычислить комбинацию C4 0 , а остальные C0 2 ,C3 1 взять из таблицы, и т.д Указанный подходпозволяет достичь компромисса между быстродействием и требованиям к занимаемомуколичеству дискового пространства. Отметим, что отказ от хранения комбинаций одного уровня приводит к экономиипамяти

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

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

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

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

Приведем некоторые из них 7.1. PGPНаиболее известный - этопакет PGP Pretty Good Privacy www.pgpi.org , без сомнений являетющийся насегодня самым распространенным программным продуктом, позволяющим использоватьсовременные надежные криптографические алгоритмы для защиты информации вперсональных компьютерах.К основным преимуществамданного пакета, выделяющим его среди других аналогичных продуктов следуетотнести следующие 1. Открытость.Исходный код всех версий программ

PGP доступен в открытом виде. Любой эксперт можетубедиться в том, что в программе эффективно реализованы криптоалгоритмы. Таккак сам способ реализации известных алгоритмов был доступен специалистам, тооткрытость повлекла за собой и другое преимущество - эффективность программногокода.2. Стойкость. Дляреализации основных функций использованы лучшие по крайней мере на начало90-х из известных алгоритмов, при этом допуская использование достаточнобольшой длины ключа для надежной защиты данных3.

Бесплатность. Готовые базовые продукты PGP равно как и исходныетексты программ доступны в Интернете в частности на официальном сайте PGP Inc. www.pgpi.org .4. Поддержка какцентрализованной через серверы ключей так и децентрализованной через сеть доверия модели распределения открытых ключей. 5.Удобство программногоинтерфейса. PGP изначально создаваласькак продукт для широкого круга пользователей, поэтому освоение основных приемовработы

отнимает всего несколько часовТекущая версия 7.0.3для платформ Windows 9x NT 2000, MacOS.7.2. GNU Privacy Guard GnuPG GnuPG www.gnupg.org - полная и свободно распространяемая замена для пакета PGP. Этот пакет неиспользует патентованый алгоритм IDEA, и поэтому может быть использован безкаких-нибудь ограничений.

GnuPG соответсвует стандарту RFC2440 OpenPGP .Текущая версия 1.0.4,платформы Unices, Windows 9x NT 7.3. КриптонПакет программКРИПТОН Подпись http www.ancud.ru crypto crpodpis.htm предназначен для использования электронной цифровой подписи ЭЦП электронныхдокументов.Программы пакетаКРИПТОН Подпись функционируют на компьютере, удовлетворяющем следующимтребованиям наличие операционной системы Windows-95 98 или

Windows NT 4.0 наличие УКЗД серии КРИПТОН с соответствующим драйвером для Windows-95 98 NT или его программного драйвера-эмулятора для Windows - Crypton Emulator версии 1.3 или выше. наличие Crypton API для Windows версии 2.2 или выше входит в поставку УКЗД серии КРИПТОН и содержит также драйвер поставляемого

УКЗД наличие манипулятора мышь . В стандартной поставкедля хранения файлов открытых ключей используются дискеты. Помимо дискет, пакетКРИПТОН Подпись дает возможность использования всех типов ключевых носителей смарт-карт, электронных таблеток Touch Memory и др поддерживаемых текущей версией интерфейсаSCApi,входящего в поставку Crypton API v2.2 и выше.7.4. ВербаО http www.ntc.spb.ru def verbao.htm Система криптографической защиты информации Верба -

О Система криптографической защиты информации СКЗИ Верба - О разработана Московским отделением Пензенского научно - исследовательского электротехнического института МО ПНИЭИ , полномочным представителем которого в регионе является наш филиал. СКЗИ Верба-О представляет собой программный комплекс, предназначенный для защиты информации при ее хранении на дисках и или передаче по каналам связи.

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

MS DOS v5.0 и выше, Windows95, Windows NT, UNIX HP UX на персональных ЭВМ, совместимых с IBM PC AT. Требуемый объем оперативной памяти не более 155 Кбайт. Кроме того, необходим накопитель на гибком магнитном диске НГМД . Алгоритм шифрования выполнен в соответствии с требованиями ГОСТ 28147-89 СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ. ЗАЩИТА

КРИПТОГРАФИЧЕСКАЯ . Цифровая подпись выполнена в соответствии с требованиями ГОСТ Р34.10-94 ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. ПРОЦЕДУРЫ ВЫРАБОТКИ И ПРОВЕРКИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА БАЗЕ АССИМЕТРИЧНОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА. Функция хэширования выполнена в соответствии с требованиями

ГОСТ Р 34.11-94 ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. ФУНКЦИЯ ХЭШИРОВАНИЯ . Ключи шифрования симметричные. Ключи для подписи асимметричные. При обработке информации на ПЭВМ СКЗИ Верба - О обеспечивает следующие показатели Операции PC AT 486 33, ISA PC AT 486 100 VESA Шифрование 200

Кб с 520 Кб с Вычисление хэш-функции 120 Кб с 330 Кб с Формирование ЭЦП 0.3с 0.04 с Проверка ЭЦП 0.7 с 0.2 с СКЗИ Верба - О имеет сертификат ФАПСИ 124-0264 от 10.04.99г. 8. Литература и ссылки1. Петров А.А Компьютерная безопасность.Криптографические методы защиты. ДМК Москва, 2000 г.2.

Методы и средства защитыинформации курс лекций Авторские права Беляев А.В. http www.citforum.ru internet infsecure index.shtml 3. Криптография http www.citforum.ru internet securities crypto.shtml 4. http www.e-sign.ru5. Александр Володин Кто заверит ЭЦП - журнал Банковские системы - ноябрь 2000 http www.bizcom.ru system 2000-11 04.html 6. Теоретические основы -Безопасность информационных систем

Криптографические системы http argosoft.webservis.ru Base Crypt.html Механизмы шифрования 7. Криптографические алгоритмы с открытым ключом http argosoft.webservis.ru Base RSAintro.html Криптографическиеалгоритмы с открытым ключом 8. Совpеменныекpиптогpафические методы защиты инфоpмации Системы с откpытым ключом http ppt.newmail.ru crypto04.htm

Heading20 9. Криптография соткрытым ключом от теории к стандарту А.Н.Терехов, А.В.Тискин Программирование РАН , N 5 сентябрь-октябрь ,1994, стр. 17 22 http www1.tepkom.ru users ant Articles Pkcstand.html 10.Баричев С.Г Гончаров В.В Серов Р.Е. Основы современной криптографии Москва, Горячая линия Телеком, 2001