Реферат: Защита информации: цифровая подпись
САНКТ – ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Факультет технической кибернетики
Кафедра информационных иуправляющих систем
Реферат
«Цифроваяподпись»
Студент Барташевич Е.Е.
Преподаватель Чистяков И.В.
Санкт-Петербург
2001
Содержание
TOC o «1-3» h z 1. Ассиметричныеалгоритмы шифрования. PAGEREF _Toc512837849 h 3
1.1. Стандартассимметричного шифрования RSA… PAGEREF _Toc512837850 h 4
1.1.1. Генерацияключей. PAGEREF _Toc512837851 h 4
1.1.2. Шифрование/расшифрование. PAGEREF _Toc512837852 h 5
1.2. АлгоритмЭльГамаля. PAGEREF _Toc512837853 h 6
1.2.1. Общиесведения. PAGEREF _Toc512837854 h 6
1.2.2. Шифрованиесообщений. PAGEREF _Toc512837855 h 6
1.2.3. Подтверждениеподлинности отправителя. PAGEREF_Toc512837856 h 6
1.3. АлгоритмШамира. PAGEREF _Toc512837857 h 7
1.3.1. Общееописание. PAGEREF _Toc512837858 h 7
1.3.2. Передачасообщений. PAGEREF _Toc512837859 h 7
1.3.3. Примериспользования. PAGEREF _Toc512837860 h 8
1.4. Кpиптосистемына основе эллиптических уpавнений. PAGEREF _Toc512837861 h 8
2. Электронно-цифроваяподпись. PAGEREF _Toc512837862 h 9
2.1. Общиеположения. PAGEREF _Toc512837863 h 9
3. АлгоритмDSA… PAGEREF _Toc512837864 h 10
3.1. ГенерацияЭЦП… PAGEREF _Toc512837865 h 11
3.2. ПроверкаЭЦП… PAGEREF _Toc512837866 h 12
4. Стандарт на процедуры ЭЦП ГОСТ Р 34.10-94. PAGEREF _Toc512837867 h 12
4.1. ГенерацияЭЦП… PAGEREF _Toc512837868 h 13
4.2. ПроверкаЭЦП… PAGEREF _Toc512837869 h 13
5. Цифровыеподписи, основанные на симметричных криптосистемах. PAGEREF _Toc512837870 h 13
6. Атаки наЭЦП… PAGEREF _Toc512837871 h 22
7. Некоторыесредства работы с ЭЦП… PAGEREF _Toc512837872 h 23
7.1. PGP. PAGEREF _Toc512837873 h 23
7.2. GNUPrivacy Guard (GnuPG) PAGEREF _Toc512837874 h 24
7.3. Криптон. PAGEREF _Toc512837875 h 24
7.4. ВербаО… PAGEREF _Toc512837876 h 24
8. Литератураи ссылки. PAGEREF _Toc512837877 h 26
1.Развитие основных типов криптографических протоколов(ключевой обмен, электронно-цифровая подпись (ЭЦП), аутентификация и др) былобы невозможно без создания открытых ключей и построенных на их основеассиметричных протоколов шифрования.
Основная идея асимметричныхкриптоалгоритмов состоит в том, что для шифрования сообщения используется одинключ, а при дешифровании – другой. Кроме того, процедура шифрования выбранатак, что она необратима даже по известному ключу шифрования – это второенеобходимое условие асимметричной криптографии. То есть, зная ключ шифрования изашифрованный текст, невозможно восстановить исходное сообщение – прочесть егоможно только с помощью второго ключа – ключа дешифрования. А раз так, то ключшифрования для отправки писем какому-либо лицу можно вообще не скрывать – знаяего все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключшифрования называют в асимметричных системах «открытым ключом», а вотключ дешифрования получателю сообщений необходимо держать в секрете – онназывается «закрытым ключом».
Таким образом, мы избавляемся отнеобходимости решать сложную задачу обмена секретными ключами.
Напрашивается вопрос : «Почему, зная открытый ключ, нельзявычислить закрытый ключ ?» – это третье необходимое условие асимметричнойкриптографии – алгоритмы шифрования и дешифрования создаются так, чтобы знаяоткрытый ключ, невозможно вычислить закрытый ключ.
В целом система переписки при использовании асимметричного шифрованиявыглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя параключей :«открытый» Ej и «закрытый» Dj, где j – номер абонента. Все открытые ключи известнывсем пользователям сети, каждый закрытый ключ, наоборот, хранится только у тогоабонента, которому он принадлежит. Если абонент, скажем под номером 7,собирается передать информацию абоненту под номером 9, он шифрует данные ключомшифрования E9 и отправляет ее абоненту9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которомуидет зашифрованное послание, они не могут прочесть исходный текст, так какпроцедура шифрования необратима по открытому ключу. И только абонент №9,получив послание, производит над ним преобразование с помощью известного толькоему ключа D9 и восстанавливает текстпослания. Заметьте, что если сообщение нужно отправить в противоположномнаправлении (от абонента 9 к абоненту 7), то нужно будет использовать ужедругую пару ключей (для шифрования ключ E7,а для дешифрования – ключ D7).
Как мы видим, во-первых, в асимметричных системах количество существующихключей связано с количеством абонентов линейно (в системе из N пользователейиспользуются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, принарушении конфиденциальности k-ой рабочей станции злоумышленник узнает толькоключ Dk : это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяетвывадавать себя за него при отправке писем.
1.1.Самым распространенным алгоритмомассиметричного шифрования является алгоритм RSA. Он был предложен тремяисседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идеюодносторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. В 1993 году метод RSA былобнародован и принят в качестве стандарта (PKCS #1: RSA Encryption standart). RSA можно применять как для шифрования/расшифрования,так и для генерации/проверки электронно-цифровой подписи.
1.1.1. Генерация ключейПервым этапом любого асимметричного алгоритма является создание пары ключей : открытого изакрытого и распространение открытого ключа «по всему миру». Дляалгоритма RSA этап создания ключей состоит из следующих операций :
Выбираются два простых (!) числа p и q
Вычисляется их произведение n(=p*q)
Выбирается произвольное число e (e<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).
1.1.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 < A < P. Сообщенияпредставляются целыми числами M из интервала 1 < M < P.
Протокол передачи сообщения M выглядит следующимобразом.
абоненты знают числа A и P;
абоненты генерируют независимо друг от другаслучайные числа:
Ka, Kb
удовлетворяющих условию:
1 < K < 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 < Ka < P
вычисляет и передаёт получателю число B, определяемое последователньостью:
В = A Ka mоd(P)
Для сообщения M (1 < M < P):
выбирает случайное число L (1 < L < 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 < M < P.
1.3.2. Передача сообщенийПередача сообщения происходит следующим образом:
абоненты знают числа P;
абоненты генерируют независимо друг от другаслучайные числа:
Ka, Kb
удовлетворяющих условию:
1 < K < 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 –1
1.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ивая есть множество точек (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.В 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<p<2^512
q: простой делитель числа (p-1), который удовлетворяет условию
2^159<q<2^160
g: так называемый генератор, удовлетворяющий
равенству g=h^((p-1)/q)mod p >1.
Парараметры p,q,g публикуются для всех участников обмена ЭД сЭЦП.
Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.
Открытый ключ вычисляется: y=g^xmod p.
Также при описании данной схемы будут использоваться следующие обозначенияи доролнительные параметры: m – входное сообщение пользователя для схемы сЭЦП; k - случайное число, удовлетворяющее условию 0<k<q,хранящееся в секрете и меняющееся от одной подписи к другой; H – хэш-функция, h – хэш-код сообщения.
Процесс генерации ЭЦП состоит из нескольких этапов:
1.Вычисляется хэш-код сообщения m h=H(m)
2.Из диапазона [1,q] случайным образом выбираетсязначение k ивычисляется r= (g^k mod p) mod q
3. Вычисляется S= (k^-1(h+xr)) mod q, где k^-1удовлетворяет условию
(k^-1*k)mod q =1
Значения r,s являются ЭЦП сообщения m ипередаются вместе с ним по каналам связи.
3.2.Пусть принято сообщение m1 и его подпись s1,r1.
Проверка ЭЦП происходит следующим образом:
- проверяетсявыполнений условий 0<r1<q, 0<s1<q, иесли хотя бы одно из них нарушено, подпись отвергается.
- Вычисляютсязначения:
w= s1^-1 modq
u1 = (H(m1)w)mod q
u2 = ((r1/w)mod q
v = ((g^u1y^u2) mod p ) mod q
- проверяетсяравенство v =r1
Если последнее равенство выполняется, то подпись принимается. В данномстандарте специфицируется также процедура генерации основных параметров системыи проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s.
4. Стандарт на процедуры ЭЦП ГОСТ Р34.10-94Отечественным стандартом на процедуры выработки и проверки ЭЦП являетсяГОСТ Р 34.10-94. Схема ЭЦП, предложеннаяв данном стандарте, во многом напоминает подпись в DSA.
Цифровая подпись представляет собой два больших целых простых числа. Общедоступные параметры схемы ЭЦП (p,q,a) должны удовлетворять следующим условиям:
p: 2^501<p<2^512 или 2^1020<p<2^1020
q: простой делитель числа (p-1), который удовлетворяет
условию 2^254<q<2^256
a:1<a<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…02551
2.Из диапазона [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<r<q, 0<s<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) = <img src="/cache/referats/11297/image002.gif" v:shapes="_x0000_i1025">
где являющиеся параметром схемы блоки данныхнесекретны и известны проверяющей подпись стороне. Таким образом, размер ключапроверки подписи равен удвоенному размеру блока использованного блочного шифра:
|kV|=2|X|=2n.
Алгоритм Sig выработки цифровой подписи для бита t (t SYMBOL 206 f«Symbol» s 11О{0,1}) заключается просто в выборе соответствующейполовины из пары, составляющей секретный ключ подписи:
s = S(t) = kt.
Алгоритм Ver проверки подписи состоит в проверке уравнения Ekt(Xt)=Ct, которое, очевидно, должно выполняться для нашегоt. Получателю известны все используемые при этомвеличины.
Таким образом, функцияпроверки подписи будет следующей:
<img src="/cache/referats/11297/image004.gif" v:shapes="_x0000_i1026">.
Покажем, что данная схемаработоспособна, для чего проверим выполнение необходимых свойств схемы цифровойподписи:
1. Невозможностьподписать бит t, если неизвестен ключ подписи. Действительно, длявыполнения этого злоумышленнику потребовалось бы решить уравнение Es(Xt)=Ct относительно s, чтоэквивалентно определению ключа для известных блоков шифрованного исоответствующего ему открытого текста, что вычислительно невозможно в силуиспользования стойкого шифра.
2. Невозможностьподобрать другое значение бита t, которое подходилобы под заданную подпись, очевидна: число возможных значений бита всего два ивероятность выполнения двух следующих условий одновременно пренебрежимо мала впросто в силу использования криптостойкого алгоритма:
Es(X0)=C0,
Es(X1)=C1.
Таким образом,предложенная Диффи и Хеллманом схема цифровой подписи на основе классическогоблочного шифра обладает такой же стойкостью, что и лежащий в ее основе блочныйшифр, и при этом весьма проста. Однако, у нее есть два существенных недостатка.
Первый недостатокзаключается в том, что данная схема позволяет подписать лишь один битинформации. В блоке большего размера придется отдельно подписывать каждый бит,поэтому даже с учетом хэширования сообщения все компоненты подписи – секретныйключ, проверочная комбинация и собственно подпись получаются довольно большимипо размеру и более чем на два порядка превосходят размер подписываемого блока.Предположим, что в схеме используется криптографический алгоритм EK с размером блока и ключа, соответственно n и nK.Предположим также, что используется функция хэширования с размером выходногоблока nH. Тогдаразмеры основных рабочих блоков будут следующими:
размер ключа подписи: nkS=2nHSYMBOL 215 f «Symbol» s 10ЧnK.
размер ключа проверкиподписи: nС=2nHn.
размер подписи: nS=nHSYMBOL 215 f «Symbol» s 10ЧnK.
Если, например, в качествеосновы в данной схеме будет использован шифр ГОСТ 28147–89 с размером блока n=64 бита иразмером ключа nK=256 бит,и для выработки хэш–блоков будет использован тот же самый шифр в режимевыработки имитовставки, что даст размер хэш–блока nH=64 то размеры рабочих блоков будут следующими:
размер ключа подписи: nkS=2nHSYMBOL 215 f «Symbol» s 10ЧnK =2SYMBOL 215 f «Symbol» s 10Ч64SYMBOL 215 f «Symbol» s 10Ч256бит=4096 байт;
размер ключа проверкиподписи: nС=2nHn = 2SYMBOL 215 f «Symbol» s 10Ч64SYMBOL 215 f «Symbol» s 10Ч64 бит =1024 байта.
размер подписи: nS=nHSYMBOL 215 f «Symbol» s 10ЧnK = 64SYMBOL 215 f «Symbol» s 10Ч256 бит= 2048 байт.
Второй недостаток даннойсхемы, быть может, менее заметен, но столь же серьезен. Дело в том, что параключей выработки подписи и проверки подписи могут быть использованы только одинраз. Действительно, выполнение процедуры подписи бита сообщения приводит краскрытию половины секретного ключа, после чего он уже не является полностьюсекретным и не может быть использован повторно. Поэтому для каждого подписываемогосообщения необходим свой комплект ключей подписи и проверки. Это практическиисключает возможность использования рассмотренной схемы Диффи–Хеллмана в первоначальнопредложенном варианте в реальных системах ЭЦП.
Однако, несколько летназад Березин и Дорошкевич предложили модификацию схемы Диффи–Хеллмана,фактически устраняющую ее недостатки.
Центральным в этомподходе является алгоритм «односторонней криптографической прокрутки», которыйв некотором роде может служить аналогом операции возведения в степень. Какобычно, предположим, что в нашем распоряжении имеется криптографическийалгоритм EK с размером блока данных и ключа соответственно n и nK бит,причем nSYMBOL 163 f «Symbol»s 10ЈnK.
Пусть в нашемраспоряжении также имеется некоторая функция отображения n–битовых блоковданных в nK–битовые Y=PnSYMBOL174 f«Symbol» s9®nK(X), |X|=n, |Y|=nK. Определим рекурсивную функцию Rk «односторонней прокрутки» блока данных T размером n бит k раз (k SYMBOL 179 f «Symbol»s 10і 0) при помощи следующей формулы:
<img src="/cache/referats/11297/image006.gif" v:shapes="_x0000_i1027">
где 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'<k – если бы это было возможно, в нашемраспоряжении был бы способ определить ключ шифрования по известному входному ивыходному блоку алгоритма EK. чтопротиворечит предположению о стойкости шифра.
Теперь покажем, какуказанную операцию можно использовать для подписи блока T, состоящего из nT битов.
Секретный ключ подписи kS выбирается как произвольная пара блоков k0,k1,имеющих размер блока данных используемого блочного шиф