Неоспоримые цифровые подписи

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

АЗЕРБАЙДЖАНСКОЙ РЕСПУБЛИКИ

БАКИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Студента IV курса группы 297

дневного отделения факультета

«Прикладной математики и кибернетики»

Армизаева Константина Алексеевича

ВЫПУСКНАЯ РАБОТА

на тему:

«Неоспоримые цифровые подписи в криптографии»

на соискание степени бакалавра

Заведующий кафедрой: д. ф.-м.н. ,проф. Мансимов К.Б.

Научный руководитель: к.ф.-м.н. Асланова Н.Х.

Б А К У - 2006

Содержание

Введение…………………………………………………………………….3-4

1. Основные понятия………………………………………………………..5-10

2. Основные протоколы для цифровых подписей……………………..11-16

3. Необходимый математический аппарат.…………………………….12-25

4. Основные алгоритмы неоспоримой цифровой подписи.

4.1 Алгоритм Чаума…………………………………………………….26-27

4.2 Преобразуемые неоспоримые подписи…………………………..28-29

4.3 Подписи, подтверждаемые доверенным лицом………………...29-30

4.4 Групповые протоколы для цифровых подписей…………………..30

Используемая литература………………………………………………..31

Введение.

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

• государственная тайна;

• военная тайна;

• коммерческая тайна;

• юридическая тайна;

• врачебная тайна и т. д.

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

• имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;

• имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.

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

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

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

Рис. 1

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

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

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

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

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

В настоящее время криптографами разработано множество различных алгоритмов и методов защиты. Цель настоящей работы - это рассмотрение способов защиты с помощью методов, называемых неоспоримыми цифровыми подписями. Оказывается такое уникальное явление как подпись присуще и криптографии. Рассматривается отличие неоспоримых цифровых подписей от обычных цифровых подписей. В данной работе приводятся факты из модулярной арифметики (также она называется арифметикой остатков). Это направление математики было заложено в трудах Евклида еще в античные времена. Далее, основной вклад был внесен французским ученым Галуа(он жил и творил в 18 веке). Разработанная им теория конечных полей и колец на протяжении долгого времени не находила себе в применения. В 20-м веке теория полей Галуа стала применяться в таких областях как кодирование информации и криптография.

§ 1. Основные понятия.

Терминология.

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

Назовем сообщение, которое нужно послать, открытым текстом. Процесс изменения вида сообщения так, чтобы спрятать его суть называется шифрованием. Шифрованное сообщение называется шифротекстом. Процесс преобразования шифротекста в открытый текст называется дешифрованием. [1]

Обозначим открытый текст как М, а шифротекст С. Открытый текст и шифротекст это двоичные данные, иногда того же размера, что и М, иногда больше. Функция шифрования E действует на М, создавая С. Математически это выглядит так:

E(М)=С

В обратном процессе функция дешифрования D действует на С, восстанавливая М:

D(С)=М , или Е^-1(С)=D(С)=D(E(М))= М.

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

Помимо сохранения информации в секрете при ее передаче, криптография также используется для других функций :

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

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

Неотрицание авторства. Отправитель не сможет ложно отрицать отправку сообщения.

Понятия об алгоритмах и ключах.

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

Таким образом, решение этой проблемы нашли в изобретении алгоритмов с ключом К.

К – может быть числом и принимать произвольное целочисленное значение.

Итак, теперь функции шифрования и дешифрования с ключевой структорой будут выглядит вот так:

E_К(М)=С

D_К(С)=М или D_К(E_К(М))=М.

В частых случаях, для шифрования используется один ключ, а при дешифровании другой. То есть ключ шифрования, К₁, отличается от соответствующего ключа дешифрования, К₂.

В этом случае :

E_К1(М)=С

D_К2(С)=М или D_К2(E_К1(М))=М.

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

Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом.

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

Эти алгоритмы делятся на две категории. Одни алгоритмы обрабатывают открытый текст побитно, они называются потоковыми шифрами. Другие работают с группами битов открытого текста. Группы битов называются блоками, а алгоритмы – блочными шифрами.

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

Криптоанализ - это наука получения открытого текста, не имея ключа[1]. Тогда получается, что это не что иное как взлом. Точнее взлом инструментами математики. Успешно проведенный криптоанализ может раскрыть открытый текст или ключ. Существует четыре основных типа криптоаналитического вскрытия. Для каждого из них, конечно, предполагается, что криптоаналитик обладает всей полнотой знания об используемом алгоритме шифрования:

1. Вскрытие с использованием только шифротекста. У криптоаналитика есть шифротексты нескольких сообщений, зашифрованных одним и тем же алгоритмом шифрования. Задача криптоаналитика состоит в раскрытии открытого текста как можно большего числа сообщений или, что лучше, получении ключа(ключей), использованного для шифрования сообщений, зашифрованных теми же ключами. Дано : С₁=Е_к(М₁), С₂=Е_к(М₂),..., С_i=Е_к(М_i); Получить: либо М₁,М₂,...,М_i;к; либо алгоритм получения М_i+1 из С_i+1=Е_к(М_i+1).

2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифротекстам нескольких сообщений, но и к открытому туксту этих сообщений. Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, для дешифрования других сообщений зашифрованных тем же ключом(или ключами). Дано: М_1­, С₁=Е_к(М₁), М₂,С₂=Е_к(М₂),...,М_i,С_i=Е_к(М_i); Получить : Либо к; либо алгоритм получения М_i+1 из С_i+1=Е_к(М_i+1).

3. Вскрытие с использованием выбранного открытого текста. У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать открытый текст для шифрования. Это предоставлляет больше больше вариантов чем вскрытие с использованием открытого текста, что может дать больше информации о ключе. Его задача состоит в получении ключа (или ключей ), использованного для шифрования сообщений, или алгоритма, позволяющего дешифровать новые сообщения, зашифрованные тем же ключом (или ключами). Дано: М_1­, С₁=Е_к(М₁), М₂,С₂=Е_к(М₂),...,М_i,С_i=Е_к(М_i), где криптоаналитик может выбирать М₁,М₂,...,М_i; Получить : Либо к; либо алгоритм получения М_i+1 из С_i+1=Е_к(М_i+1).

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

Подстановочные и перестановочные шифры.

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

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

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

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

Полиграмный подстановочный шифр – это шифр, который блоки символов шифрует по группам.

Полиграмные подстановочные шифры – это шифры, которые кодируют сразу группы символов.

Полиалфавитный подстановочный шифр состоит из нескольких простых шифров.

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

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

Перестановочные шифры.

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

Роторные машины.

Каждый ротор представляет собой произвольное размещение алфавита, имеет 26 позиций и выполняет простую подстановку. Например, в четырехротоорной машине первый ротор может заменять «А» на «F», второй- «F» на «Y», третий- «Y» на «E» и четвертый «E» на «С», «С» и будет конечным шифротекстом. Затем некоторые роторы смещаются, и в следующий раз подстановки будут другими. Именно комбинация нескольких роторов и механизмов, движущих роторами, и обеспечивает безопасность машины.

Одноразовые блокноты.

Невероятно, но факт : идеальный способ шифрования существует и называется он одноразовым блокнотом. [1]В классическом понимании одоноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и прикрепленных к листу блокнота. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю 26 открытого текста и символа ключа из одноразового блокнота. Каждый символ используется лишь единожды и для единственного сообщения. Отправитель шифрует сообщения и уничтожает использованные страницы блокноты. Получатель, в свою очередь используя точно такой же блокнот, дешифрует каждый символ шифротекста. Расшифровав сообщение, получатель уничтожает соответствующие страницы блокнота. Т.к. все ключевые последовательности совершенно одинаковы (символы ключа генерируется случайным образом), у противника отсутсвует информация, позволяющая подвергнуть шифротекст криптоанализу.

Компьютерные алгоритмы.

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

AES (Advanced Encription Standart) - симметричный компьютерный алгоритм шифрования, является американским и международным стандартом.

RSA (Rivest, Shamir, Adleman - создатели) - самый популярный компьютерный алгоритм с открытым ключом.Исполюзуется для шифрования и цифровой подписи.

DSA (Digital Signature Algorithm) – другой алгоритм с открытым ключом. Используется только для цифровой подписи, не может быть использован для шифрования.

Понятия о протоколах.

Протокол- это порядок действий, предпринимаемых двумя или более сторонами, предназначенный для решения определенной задачи.[1] «Порядок действий» означает, протокол выполняется в определенной последовательности, с начала до конца. Каждое действие должно выполняться в свою очередь и только после окончания предыдущего. «Предпринимаемых двумя или более сторонами» означает, что для реализации протокола требуется по крайней мере два человека, один человек не сможет реализовать протокол. Человек в одиночку может выполнить некоторые действия, решая задачу, но это протокол. Наконец, «предназначенный для решения определенной задачи» означает, что протокол должен приводить к какому-то результату. У протоколов есть и другие характеристики :

• Каждый участник протокола должен знать протокол и последовательность составляющих его действий.

• Каждый участник протокола должен согласиться следовать протоколу.

• Протокол должен быть быть непротиворечивым, каждое действие должно быть определено так, чтобы не было возможности ненапоминания.

• Протокол должен быть полным, каждой возможной ситуации должно соответствовать определенное действие.

Выполнение протокола происходит по действиям, линейно, пока не будет команды перейти к следующему действию. Каждое действие включает по крайней мере одно из двух : вычисления, выполняемые одной или несколькими сторонами, или сообщения, которыми обмениваютсястороны.

Криптографический протокол- это протокол, использующий криптографию.[1] Стороны могут быть друзьями и слепо доверять друг другу или врагами и не верить друг другу даже при сообщении времени суток. Участники протокола могут захотеть поделиться секретом друг с другом, совместно генерировать случайную последовательность, подтвердить друг другу свою подлинность или подписать контракт в один и тот же момент времени. Смысл использования криптографии в протоколе – в предотвращении или обнаружении вредительства и мошенничества. Если вы никогда не сталкивались с подобными протоколами, они могут радикально изменить ваше представление о том, что недоверяющие друг дждругу стороны могут выполнить, используя компьютерную сеть. Общее правило можно сформулировать следующим образом :

Невозможно сделать или узнать больше, чем определено в протоколе.

Протоколы с посредником.

Посредник- это незаинтересованная третья сторона, которой доверено завершение протокола. [1] «Незаинтересованность» означает, что у посредника нет заинтересованности в результате работы протокола и склонности к одной из сторон. «Доверено» означает, что все участники протокола принимают все, что скажет посредник за истину, все его действия- как правильные, уверены в том, что посредник выполнит свою часть протокола. Посредники помогают реализовать работу протоколов взаимодействия недоверяющих друг другу сторон.

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

Компьютерная сеть должна обеспечить поддержку посредника. Занятость юристов общезвестна, на кого в сети лягут дополнительные накладные расходы?

Существует задержка, присущая всем протоколам с посредником.

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

Так как каждый в сети должен доверять посреднику, то посредник представляет собой слабое место сети при попытке ее взлома.

Арбитражные протоколы.

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

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

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

Подпротокол без посредника.

1. Отправитель и Получатель договариваются об условии контракта.

2. Отправитель подписывает контракт.

3. Получатель подписывает контракт.

Подпротокол с использованиием арбитра(выполняется при наличии разногласий):

1. Отправитель и Получатель предстают перед судьей.

2. Отправитель предоставляет свои доказательства.

3. Получатель предоставляет свои доказательства.

4. Судья принимает решение на основании доказательств.

Заметим, что обращаются к судье только при разногласиях.

Самодостаточные протоколы.

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

§ 2.Основные протоколы для цифровых подписей.

Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере согласия с ним. А притягательно в подписи следующее:

1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.

2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.

3. Подпись не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ.

4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.

5. От подписи невозможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.

Подпись документа с помощью симметричых криптосистем и посредника.

Посредник может связываться и с Отправителем, и с Получателем. Он выдает секретный ключ, К_А, Отправителю и другой секретный ключ, К_В – Получателю. Эти ключи определяются задолго до начала действия протокола и могут быть использованы многократно для многих подписей.

1. Отправитель шифрует свое сообщение Получателю ключом К_А и посылает его Посреднику.

2. Посредник зная ключ К_А, расшифровывает сообщение.

3. Посредник добавляет к расшифрованному сообщению утверждение, что он получил это новое сообщение ключом К_В .

4. Посредник посылает новое сообщение Получателю.

5. Получатель расшифровывает сообщение ключом К_В. Он может прочитать и сообщение Отправителя, и подтверждение Посредника, что сообщение отправлено именно Отправителем.

Если Получатель захочет показать Участнику 3 документ, подписанный Отправителем, он не сможет раскрыть ему свой секретный ключ. Получателю придется снова обратиться к Посреднику :

1. Получатель берет сообщение и утверждение Посредника, что сообщение получено от Отправителя, шифрует их ключом К_В и посылает обратно Посреднику.

2. Посредник расшифровывает полученный пакет с помощью ключа К_В .

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

4. Посредник шифрует полученный от Получателя пакет с помощью ключа К_С, который он выделил для Участника 3, и посылает Участнику 3 шифрованный пакет.

5. Посредник расшифровывает полученный пакет с помощью ключа К_С. Теперь он может прочитать и сообщение, и подтверждение Посредника , что сообщение отправлено Отправителем.

Деревья цифровых подписей.

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

Подпись документа с помощью криптографии с открытыми ключами.

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

Основной протокол прост :

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

2. Отправитель посылает подписанный документ Получателю.

3. Получатель расшифровывает документ, используя открытый ключ Отправителя, таким образом проверяя подпись.

В этом протоколе посредник не нужен ни для подписи документов, ни для ее проверки.

Подпись документа и метки времени.

На самом деле, при определенных условиях Получатель сможет смошенничать. Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Отправитель подписал контракт. А если предположить, что Отправитель послал Получателю подписанный чек на $100. Получатель отнес чек в банк, который проверил подпись и перевел деньги с одного счета на другой. Получатель, выступающий в роли жулика, сохранил копию электронного чека. На следующей неделе он снова отнес его в этот или другой банк. Если Отправитель не проверяет свою чековую книжку, Получатель сможет проделывать это годами.

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

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

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

1. Отправитель получает значение однонаправленной хэш-функции для документа.

2. Отправитель шифрует это значение своим закрытым ключом, таким образом подписывая документ.

3. Отправитель посылает Получателю документ и подписанное значение хэш-функции.

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

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

Алгоритмы и терминология.

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

Строку битов, присоединенную к документу после его подписания, назовем цифровой подписью.

Подпись сообщения с закрытым ключом К обозначим как : S_k(M), а проверка подписи с помощью соответствующего открытого ключа как : V_k(M).

Невозможность отказаться от цифровой подписи.

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

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

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

1. Отправитель подписывает сообщение.

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

3. Посредник проверяет внешнюю подпись и подтверждает идентификационную информацию. Он добавляет метку времени к подписанному сообщению Отправителя и идентификационной информации. Затем он подписывает все вместе и посылает Отправителю и Получателю.

4. Получатель проверяет подпись Посредника, идентификационную информацию и подпись Отправителя.

5. Отправитель проверяет сообщение, которое Посредник послал Получателю. Если он не признает авторство, он быстро заявляет об этом.

Цифровые подписи и шифрование.

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

1. Отправитель подписывает сообщение с помощью своего закрытого ключа S_A(M).

2. Отправитель шифрует подписанное сообщение открытым ключом Получателя и посылает его Получателю. E_B(S_A(M))

3. Получатель расшифровывает сообщение с помощью своего закрытого ключа. D_B(E_B(S_A(M)))= S_A(M)

(4) Получатель проверяет подпись с помощью открытого ключа Отправителя и восстанавливает сообщение. V_A(S_A(M))=M

Подпись перед шифрованием выглядит естественно. Когда Отправитель пишет письмо, он подписывает его и затем кладет в конверт. Если он положит письмо в конверт неподписанным, то Получатель может забеспокоится, вдруг письмо было тайно подменено.

Если Получатель покажет Участнику 3 письмо Отправителя и конверт, Участник 3 может обвинить Получателя, что он врет о том, какое письмо в каком конверте пришло.

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

Возвращение сообщения при приеме.

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

1. Отправитель подписывает собщение с помощью своего закрытого ключа, шифрует подписанное сообщение открытым ключом Получателя и посылает его Получателю. E_B(S_A(M))

2. Получатель расшифровывает сообщение с помощью своего закрытого ключа, проверяет подпись с помощью открытого ключа Отправителя и восстанавливает сообщение. V_A(D_B(E_B(S_A(M))))=M

3. Получатель подписывает сообщение с помощью своего закрытого ключа, шифрует подписанное сообщение открытым ключом Отправителя и посылает его обратно. E_А(S_В(M))

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

Пусть «Взломщик протоколов» – зарегистрированный пользователь со своей парой ключей : открытым и закрытым. Теперь посмотрим, как он сможет читать почту Получателя. Сначала он запишет сообщение Отправителя Получателю – этап (1). Затем, немного погодя, он пошлет это сообщение Получателю, утверждая, что оно отправлено самим «Взломщиком протоколов». Получатель, думая, что это обычное сообщение от «Взломщика протоколов», дешифрируя это сообщение своим закрытым ключом и пытается проверить подпись «Взломщика протоколов», дешифрируя ее с помощью открытого ключа «Взломщика протоколов». В результате получается полная чепуха : E_А(D_B(E_B(D_A(M))))= E_M(D_A(M))

Даже в этом случае, следуя протоколу, Получатель посылает «Взломщику протоколов» полученное сообщение:

E_М(D_B(E_М(D_A(M))))

Теперь «Взломщик протоколов» остается только расшифровать сообщение с помощью своего закрытого ключа, зашифровать его открытым ключом Получателя, расшифровать снова с помощью своего закрытого ключа и зашифровать с помощью открытого ключа Отправителя. И вот, «Взломщик протоколов» получает сообщение М.

Неотрицаемые цифровые подписи.

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

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

Несмотря на идею математики основная идея проста :

1. Отправитель предъявляет Получателю подпись.

2. Получатель создает случайное число и посылает его Отправителю.

3. Отправитель выполняет вычисления, используя случайное число и свой закрытый ключ, и посылает Получателю результат. Отправитель может выполнить только, если эти вычисления правильны.

4. Получатель проверяет это.

Также существует дополнительный протокол, позволяющий Отправителю доказать, что он не подписывал документ, и не допускающий возможности ложно отказаться от подписи.

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

Удостоверение подлинности.

Когда Получатель получает сообщение от Отправителя, как ему узнать, что это сообщение подлинно? Если Отправитель подписал свое сообщение, то все просто. Цифровая подпись Отправителя достаточна, чтобы подтвердить кому угодно подлиннность ее сообщения.

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

§3. Необходимый математический аппарат.

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

Для начала введем некоторые определения:

Группой называется множество G с заданной на нем бинарной операцией •, которая удовлетворяет следующим условиям:

1. Выполняется замкнутость: для любой пары a , b ? G

2. (a • b) • c = a • (b • c) для всех a, b, c ? G (ассоциативность)

3. Существует элемент e, называемый нейтральным элементом ( либо единицей), такой, что a • e = e • a = a для любого a ? G

4. Для любого элемента a ? G существует элемент b, такой, что a • b = b • a = e (существование обратного элемента) . [4]

Кольцом (или коммутативным кольцом) называется множество R с двумя заданными на нем замкнутыми бинарными операциями • и +, которые удовлетворяют следующим условиям:

1. Существует элемент 0 и 1, называемые нулем и единицей соответственно, такие, что a + 0 = a • 1 = a для любого a ? R

2. Для любого элемента a ? R существует элемент b, такой, что a + b = 0 (существование аддитивного обратного)

3. (a + b) + c = a + (b + c) и (a • b) • c = a • (b • c) для всех a, b, c ? R (ассоциативность)

4. a + b = b + a и a • b = b • a для всех a, b ? R (коммутативность)

5. a • (b + c) = a • b + a • c для всех a, b, c ? R (дистрибутивность) [4]

Полем называется множество K с двумя заданными на нем замкнутыми бинарными операциями • и +, которые удовлетворяют следующим условиям:

1. (a + b) + c = a + (b + c) и (a • b) • c = a • (b • c) для всех a, b, c ? K (ассоциативность)

2. a + b = b + a и a • b = b • a для всех a, b ? K (коммутативность)

3. a • (b + c) = a • b + a • c для всех a, b, c ? K (дистрибутивность)

4. Существуют элементы 0 и 1, называемые нулем и единицей соответственно, такие, что a + 0 = a • 1 = a для любого a ? K

5. Для любого элемента a ? K существует элемент b, такой, что a + b = 0 (существование аддитивного обратного)

6. Для любого элемента a ? K, не равного нулю, существует элемент c, такой,

что a • c = 1 (существование мультипликативного обратного). [4]

Модулярная арифметика.

Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое называется модулем. Каждому целому числу отвечает определенный остаток от деления его на m ; если двум целым a и b отвечает один и тот же остаток r , то они называются равноостаточными по модулю m или сравнимыми по модулю m и записывается это так:

a? b(mod m).

Сравнимость чисел а и b по модулю m равносильна:

1.Возможности представить а в виде а=b+mt, где t- целое.

2. Делимости а-b на m.

3. Если a? b(mod m), то (a ,т)= (b ,m).

Числа, равноостаточные образуют класс чисел по модулю т. Обозначим через Z_т класс, состоящий из т элементов. Z_т = {0, 1, …, m?1} Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq+r заставим q пробегать все целые числа. Соответственно, m различным значениям r имеем m классов чисел по модулю m.

Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса. Вычет, получаемый при q=0, равный самому остатку r называется наименьшим неотрицательным вычетом. Взяв, от каждого класса по одному вычету, получим полную систему вычетов по модулю т.

Любые m чисел попарно несравнимые по модулю т, образуют полную систему вычетов по этому модулю.

Если (a ,т)=1 и х пробегает полную систему вычетов по модулю т, то ах+b, где b-любое целое,тоже пробегает полную систему вычетов по модулю т. Взяв от каждого класса по одному вычету, получим приведенную систему вычетов по модулю т.

Любые ?(m) чисел попарно несравнимые по модулю т и взаимно простые с модулем, образуют приведенную систему вычетов по этому модулю. Если привести обозначения, то это будет выглядить так: Z^*_т – множество состоящее из элементов Z_т, взаимно простых с m.

Число элементов в Z^*_т - определяет ?(т). Эта функция называется функцией Эйлера . Она определяется для всех натуральных т и представляет собою количество чисел от 1 до n взаимно простых с m.

П р и м е р ы :

?(1) = 1, ?(4) = 2,
?(2) = 1, ?(5) = 4,
?(3) = 2, ?(6) = 2.

Несложно показать, что функция Эйлера мультипликативна, то есть, для любых n и m таких, что (n, m) = 1 выполняется

?(nm) = ?(n)?(m)

Очевидно, что для простого p выполняются равенства:

?(p) = p ? 1,
?(pⁿ) = p^n?1(p ? 1)

Если n=pq, где p и q – простые числа, то ?(п)= ?(pq)=(p-1)(q-1). Эти числа появляются в некоторых алгоритмах с открытым ключом.

Эти свойства позволяют быстро вычислять функцию Эйлера, если известно разложение числа n на простые множители. Доказывается формула[2] : ?(n)=n(1-1/ p₁)…(1-1/ p_s)

Теорема Эйлера и малая теорема Ферма.

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

Теорема (Эйлер). [2]

При n > 1 и НОД (a, n) = 1 верно следующее:

a^?(n) ? 1 (mod n), для любого a ? Z^*_n

При простом n эта теорема превращается в «малую теорему» Ферма

Теорема (Ферма). [2]

Для любого простого p и любого натурального a верно следующее:

a^p ? a (mod p) , для любого a ? Z^*_p

Первообразные корни.

Пусть p — простое число. Тогда, как известно, Z_p является полем. Порядком вычета a > 0 называется наименьшее натуральное число m такое, что

a^m ? 1 (mod p)

Согласно малой теореме Ферма, хотя бы одно такое m существует (и равно p?1).

Теорема.

Для любого простого p существует вычет (образующая группы Z^*_p)

g порядка p?1.

Такой вычет g называется первообразным корнем по модулю p.

Несложно также показать, что таких вычетов существует ровно ?(p?1).

Первообразные корни по модулям р^? и 2р^?.

Я приведу, лишь, вспомогательный факт без доказательствa. Но доказательствo есть в [2].

Теорема. [2]

Пусть с= ?(p) и q₁, q₂, … ,q_k - различные простые делители числа с. Для того чтобы число g, взаимно простое с т, было первообразным корнем по модулю т, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений

g^с/q₁?1(mod m), g^с/q₂?1(mod m),… g^с/q_k?1(mod m).

Введем обозначение :

(Z_n, +_n) – аддитивная группа вычетов по модулю n, здесь +_n – операция сложения по модулю n.

(Z^*_n, • _n) – мультипликативная группа вычетов по модулю n, здесь • _n – операция умножения по модулю n.

Сравнения первой степени.

Рассмотрим следующее соотношение ax ? b (mod m), называемое, сравнением первой степени.Это сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда х пробегает полную систему вычетов по модулю т, то ах пробегает полную систему вычетов. Следовательно, при одном и только одном значении х, взятом из полной системы ах будет сравнимо с b. Итак, при (а,т)=1 наше сравнение имеет одно решение.

Пусть (а,т)=d, при d>1. Сравнение ax ? b (mod m) невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.

Модулярная арифметика основывается на так называемой Китайской теореме об остатках (КТО). Около 100 г. до н. э. китайский математик Сун Цу (Sun-Tsu) решил такую задачу: найти число, дающее при делении на 3, 5, 7, остатки 2, 3, 2 соответственно.

Китайская теорема об остатках.

Пусть n = n₁n₂…n_k. Причем числа n₁, n₂, …, n_k попарно взаимно просты. Рассмотрим соответствие a ? (a₁, a₂, …, a_k) , где a_i — остаток от деления a на n_i.

Тогда оно задает взаимно однозначное соответствие между классом Z_n и декартовым произведением Z_n1? … ? Z_nk.

При этом операция сложения , вычитания и умножения в Z_n соответствуют покомпонентные операции над к-элементными кортежами:

если a ? (a₁, a₂, …, a_k) и b ? (b₁,b₂, …, b_k), то

(a+b) mod n ? ((a₁+ b₁) mod n₁, …, (a_k+ b_k) mod n_k )

(a-b) mod n ? ((a₁- b₁) mod n₁, …, (a_k- b_k) mod n_k )

(ab) mod n ? ((a₁ b₁) mod n₁, …, (a_k b_k) mod n_k ).

Рассмотрим систему сравнений x ? b₁(mod m₁), x ? b₂(mod m₂),…, x ? b_k(mod m_k). Решить эту систему, т.е. найти все значения х , ей удовлетворяющие, можно, применяя следующее утверждение: [2]

Пусть числа M_s и M'_s определены из условий m₁m_2...m_k= M_sm_k, M_s M'_s ? 1 (mod m_s),

и пусть х₀ = M₁ M'₁ b₁+ M₂ M'₂ b₂ +...+M_к M'_к b_к.

Тогда совокупность значений х, удовлетворяющих системе определяются сравнением

x ? х₀ (mod m₁m_2...m_k ).

П р и м е р :

Решим систему x ? 2(mod 3), x ? 3(mod 5), x ? 5(mod 11).

Здесь 3·5·11=55·3=33·5=15·11=165, причем 55·1? 1(mod 3),

33·2 ? 1(mod 5), 15·3? 1(mod 11).

Поэтому х₀ = 55·1·2+33·2·3+15·3·11, и , следовательно, совокупность значений х, удовлетвряющих системе x ? 2(mod 3), x ? 3(mod 5), x ? 5(mod 11), будет

x ? 110+ 198+225=533 ? 38(mod 165).

О дискретном логарифме.

Пусть g является образующей группы Z^*_n ,тогда для всякого a ? Z^*_p найдется z, для

которого g^z ? a(mod n). Такое z называется дискретным логарифмом.

Теорема(о дискретном логарифме).

Пусть g является вычетом. Тогда сравнение g^x ? g^y(mod p) равносильно

сравнению x ? y (mod ?(p) ).

Целые числа a и b являются взаимно простыми,если НОД(a ,b)=1

Теорема.

Если НОД(a,p)=1 и НОД (b,p)=1,то НОД(аb,p)=1 (для любых простых чисел а,b,p).

Алгоритм вычисления a^d (mod m).

Как мы знаем , вычисление a^d (mod m) при достаточно большом а, довольно таки, трудоемкое занятие. Я даже не говорю о буковке d, точнее о том, какие значения она принимает. Таким образом , чтобы облегчить это вычисления мы приведем алгоритм.

1. Представим d в двоичной системе счисления d= d₀ 2^r +… +d_r-12+ d_r ,где d_i-цифры в двоичном представлении равны 0 или 1, d₀=1.

2. Положим а₀₌а и затем для i=1...r вычислим а_i= a²_i-1·a^di (mod m)

3. а_r есть искомый вычет a^d(mod m).

(сложность алгоритма 0(ln m))

П р и м е р :

Найдем 57²⁰⁷(mod 3313)

a₀=57, d=207=2⁷+2⁶+2³+2²+2¹+2⁰.

Таким образом, d₀=1; d₁=1; d₂=0; d₃=0; d₄=1; d₅=1; d₆=1; d₇=1;

а₁=57²·57 mod 3313 ?2978;

а₂=2978² mod 3313 ?2896;

а₃=2896² mod 3313 ?1613;

а₄=1613²·57 mod 3313 ?1014;

а₅=1014²·57 mod 3313 ?202;

а₆=202²·57 mod 3313 ?102;

а₇=102²·57 mod 3313 ?1;

Т.о. 57²⁰⁷(mod 3313) =1.

Разложение на простые множители.

Теорема.

Если простое число p делит произведение двух целых чисел а и b ,

то p|a или p|b.

Теорема (существование и единственность разложения).

Всякое составное число а= p₁ ^E1p₂ ^E2… p_r^Er, где p₁ < p₂ <…< p_r -простые числа, а E_i- положительные целые числа.

Теорема (рекуррентная формула для НОД).

Пусть а – целое неотрицательное число, а b- целое положительное число.

Тогда НОД(a,b)=НОД(b,а mod b).

Расширенный алгоритм Евклида.

Немного дополнив известный алгоритм нахождения НОД двух натуральных чисел, можно получить с его помощью коэффициенты х и у, для которых НОД(a,b)=ах+by=1, при (a,b)=1.Итак, этот алгоритм используется для решения уравнения ax? 1(mod b) или bу? 1(mod a), при (a,b)=1.

Определим матрицу

1. Вычислим остаток r от деления числа a на b, a=bq+r,0?r<b.

2. Если r=0, то второй столбец матрицы Е дает вектор  решений уравнения

3. Если r?0, то заменим матрицу Е матрицей

4. Заменим пару чисел (a,b) парой (b,r) и перейдем к шагу 1.

Сравнения второй степени.

Рассмотрим сравнение х² ? а (mod р), при (a, р) = 1. (1)

Если (1) имеет решение, то а называется квадратичным вычетом по модулю т. В противном случае а называется квадратичным невычетом по модулю р. Несложно показать, что если а-квадратичный вычет, то данное сравнение имеет два решения.

Действительно, если а- квадратичный вычет по модулю р, то сравнение (1) имеет, по крайней мере, одно решение х ? х₁ (mod р). Но тогда, ввиду(-х₁)²= х₁², то же сравнение имеет и второе решение х ? -х₁ (mod р). Это второе решение отлично от первого, т.к.

из х₁ ? х₁ (mod р) мы имели бы х₁ ? 0 (mod р), что невозможно, ввиду (2,р)=(х₁,р)=1.

Приведенная система вычетов по модулю р состоит из (р-1)/2 квадратичных вычетов, сравнимых с числами 1²,2²,...,((р-1)/2)² и (р-1)/2 квадратичных невычетов.

О символе Лежандра:

Рассмотрим L(a,p), называемый символом Лежандра, с помощью, которого можно определить, является ли а квадратичным вычетом по модулю р (для простого р).

Вычислить символ Лежандра L(a,p) (и определить является ли а квадратичным вычетом, либо не является) позволяет следующее утверждение:

Теорема(критерий Эйлера).

При а, не делящемся на р, имеем a^(p-1)/2? L(a,p)(mod p).

Итак, символ Лежандра определяется следущим образом:

L(a,p)=0, если а делится на р.

L(a,p)=1,если а-квадратичный вычет по модулю р.

L(a,p)=-1,если а-квадратичный невычет по модулю р.

L(a,p) можно рассчитать следующим образом : L(a,p)= a^(p-1)/2 mod p.

Или можно воспользоваться следующим алгоритмом :

1. Если а=1, то L(a,p)=1.

2. Если а – четно, то L(a,p)= L(a/2,p)*(-1) ^(p?-1)/8

3. Если а – нечетно (и?1), то L(a,p)= L(р mod a,p)*(-1)^(q-1)(p-1)/4

О символе Якоби J(a,р):

Символ Якоби J(a,р) представляет собой обобщение символа Лежандра на составные модули, он определяется для любого целого а и любого нечетного р.

J(a,р) определен только, если р – нечетно.

J(0,р) =0

Если p – простое число, то

1. J(a,p) =0, если a делится на p;

2. J(a,p)=1, если a - квадратичный вычет по модулю p;

3. J(a,p)=-1, если a - квадратичный невычет по модулю p;

Если p – составное число, то:

J(a,р)= J(a, p₁)* J(a, p₂)*…* J(a, p_m), где p_1,... p_m – простые множители (все) p.

Правило 1: J(1,р)=1;

Правило 2: J(a*b,р)= J(a,р)* J(b,р);

Правило 3: J(2,p)=1, если (p² -1)/8 четно и

J(2,p)=-1, если (p² -1)/8 нечетно

Правило 4: J(a,p)= J((a mod p),p);

Правило 5: J(a, b₁* b₂)= J(a, b₁)* J(a, b₂);

Правило 6: Если НОД(a,b)=1 и a и b нечетны, то:

J(a,b)=J(b,a), если (a-1)(b-1)/4 четно,

J(a,b)=-J(b,a), если (a-1)(b-1)/4 нечетно.

П р и м е р :

Вычислим J(21,109):

• По правилу 2 имеем: J(21,109)=J(3·7,109)= J(3,109)* J(7,109)

• По правилу 6 имеем НОД(3,109)=1, НОД(7,109) и 3 и 7 и 109 – нечетны, тогда 2·108/4=54, то J(3,109)= J(109,3); 6·108/4=162, то J(7,109)= J(109,7);

• По правилу 4 имеем : J((109 mod 3),3)= J(1,3)=1; J((109 mod 7),3)= J(4,7);

• По правилу 2 : J(4,7)= J(2,7)* J(2,7)

• По правилу 3 : (7² -1)/8=6 - четно, то J(2,7)=1

Получаем, что J(21,109)= J(1,3)*J(2,7)* J(2,7)=1. Итак, 21 является квадратичным вычетом.

Проверка чисел на простоту.

Тест Соловея-Штрассена.

Для проверки простоты числа p в этом алгоритме используется символ Якоби.

(p – нечетное, большое число)

1. Выберите случайное число a, меньше р.

2. Если НОД(a,p) ? 1, то р - составное число и не проходит тест.

3. Вычислите j= a^(p-1)/2 (mod p).

4. Вычислите символ Якоби J(a,p).

5. Если j? J(a,p),то число р определенно не простое. (a-свидетель)

6. Если j= J(a,p),то вероятность того, что число р не является простым

и не превышает ?. Повторить эту процедуру t раз. [5]

П р и м е р :

Пусть требуется проверить на простоту число 109.

1. Выберем случайно а=21.

2. НОД(а,р)=НОД(21,109)=1 (вычисляем по алгоритму Евклида).

3. Вычисляем j= a^(p-1)/2 (mod p)= 21⁵⁴ mod 109=1 (вычисляем по быстрому алгоритму a^d (mod m)).

4. Вычисляем символ Якоби J(a,р)= J(21,109)=1(это мы уже вычислили, можно посмотреть выше).

5. j=J(21,109)=1, число а=21 прошло тест.

1. Теперь выберем случайно а=49.

2. НОД(а,р)=НОД(49,109)=1(вычисляем по алгоритму Евклида).

3. Вычисляем j=49⁵⁴(mod 109)=1 (вычисляем по быстрому алгоритму).

4. Вычисляем символ Якоби J(a,р)= J(49,109)=1.

5. j=J(49,109)=1, число а=49 прошло тест.

1. Выберем случайно а=9.

1. НОД(а,р)=НОД(9,109)=1 (вычисляем по алгоритму Евклида).

2. Вычисляем j= a^(p-1)/2 (mod p)= 9⁵⁴ mod 109=1

3. Вычисляем символ Якоби J(a,р)= J(9,109)=1

4. j=J(9,109)=1, число а=21 прошло тест.

Числа Кармайкла.

Неподходящими для теста Соловея-Штрассена являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что НОД(a, p) = 1 верно

a^n?1 ? 1 (mod n)

Первые три числа Кармайкла таковы: 561, 1105, 1729. Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много. [5]

Тест Миллера-Рабина.

Вычислить b-число делений p-1 на 2 (т.е. 2^b –это наибольшая степень числа 2,

на которую делится p-1). Вычислить m,такое,что p=1+2^b *m, m-нечетно.

1. Выберите случайное число а, меньшее р.

2. Установите j=0 и z= a^m (mod p).

3. Если z=1 или если z=p-1, то p проходит тест и может быть простым числом.

4. Если j>0 и z=1,то р не относится к простым числам.

5. Установите j=j+1. Если j<b и z?p-1,установите z= z ² mod p и вернитесь на этап 4. Если z=p-1, то p проходит тест и может быть простым числом.

6. Если j=b и z?p-1, то р не относится к простым числам.

То а, при котором обнаруживается, что р –составное, называется свидетелем. Гарантируется, что ? возможных значений а окажутся свидетелями. Это означает, что составное число ошибочно пройдет t тестов с вероятностью не более (?)^t , где t –число итераций. Для большинства случайных чисел свидетелями служат около 99,9% возможных значений а. [5]

Если р-простое число, p-1=2^b *m, m-нечетно, то согласно малой теореме Ферма для каждого а, такого, что (а,р)=1 хотя бы одна из скобок в произведении

(a^m-1)(a^m+1) (a^2m+1)… (a^2b*m+1)= (a^p-1-1) делится на p.[5]

П р и м е р ы :

1) Проверим, является ли число 2031 простым. Итак, 2030=2*1015 ;

т.о. b=1; m=1015;

1. Выберем случайное a, a<p; а=43

2. Установим j=0 и z= 43¹⁰¹⁵ mod 2031=1406.

3. z?1, z?2030.

4. j>0; нет.

5. j=1; jнет, т.к. j=1;

6. j=1 и z=2030: Не является простым числом (действительно, 2031=677·3).

2) Проверим, является ли 109-1=108; 108=2²·27; b=2; m=27.

1. Выберем случайное a=15;

2. Установим j=0 и z=17²⁷ mod 109=1

3. z=1, то р=109 проходит тест и может быть простым.

§ 4. Основные алгоритмы неоспоримой цифровой подписи.

4.1 Алгоритм Чаума.

Сначала опубликовывается большое простое число р и примитивный элемент g, которые будут совместно использоваться группой подписывающих. У Отправителя есть закрытый ключ х и открытый ключ g^х mod p.

Чтобы подписать сообщение, Отправитель вычисляет z= т^х mod p. Это все, что ему нужно сделать. Проверка подписи немного сложнее.

(1) Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет Отправителю :

c= z^a(g^х)^b mod p

(2) Отправитель вычисляет t= x^-­1mod (p-1), и отправляет Получателю : d= c^t mod p.

(3) Получатель проверяет, что d? т^ag^b (mod p)

Если это так, он считает подпись истинной. [1]

П р и м е р :

(Для простоты вычисления используем небольшие числа).

Пусть р=23, g=5. Заметим, что g=5 действительно примитивный корень, т.к. по теореме [2] с= ?(p)=22; q₁=2, q₂=11;

5² mod 23=2?1; 5¹¹ mod 23=22?1;

Закрытый ключ выбираем х=7. Пусть т=3. Открытый ключ 5⁷mod 23=17

Чтобы подписать сообщение, Отправитель вычисляет z= т^х mod p= 3⁷ mod 23=2.

Проверка подписи Получателем:

(1) Получатель выбирает два случайных числа, a=4 и b=2, и отправляет Отправителю :

c= z^a(g^х)^b mod p= 2⁴(5⁷)² mod 23=1

(2) Отправитель вычисляет t= 7^-­1mod 22=3, и отправляет Получателю :

d= c^t mod p=1³ mod 23=1.

(3) Получатель проверяет, что d?3⁴·5² mod 23=1.

Поскольку d совпадает с т^ag^b, то подпись Получатель считает истинной.

Представим, что Отправитель и Получатель выполнили этот протокол, и Получатель теперь считает, что Отправитель подписал сообщение. Получатель хочет убедить в этом Участника 3, поэтому он показывает ему запись протокола. Сначала он генерирует сообщение на этапе (1). Затем на этапе (3) он генерирует d и ложную передачу от другого человека на этапе (2). Наконец, он создает сообщение этапа (2). Для Участника 3 записи Получателя и Участника 4 одинаковы. Его невозможно убедить в правильности подписи, пока он не выполнит протокол самостоятельно.

Конечно, если бы Отправитель следил из-за плеча Получателя за тем, как он выполняет протокол, он был бы убежден. Участнику 3 нужно увидеть выполнение этапов по порядку, так, как это делал Получатель.

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

Как и предыдущий протокол група подписывающих использует общедоступное большое простое число p и примитивный элемент g.[2] У Отправителя есть закрытый х и открытый ключ g^х mod p. Чтобы подписать, сообщение Отправитель вычисляет z= т^х mod p. Чтобы проверить подпись :

1. Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет Отправителю :

c= т^ag^b mod p

1. Отправитель выбирает случайное число q, меньшее p, а затем вычисляет и отправляет Получателю

s₁= cg^q mod p, s₂= (cg^q)^x mod p

1. Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что Получатель не мошенничал на этапе (1).

2. Отправитель посылает Получателю q, чтобы он мог воспользоваться т^х и восстановить s₁ и s₂. Если s₁? cg^q mod p, s₂= (cg^х)^b+q (mod p), то подпись правильна.

Отправитель может также отказаться от подписи z под сообщением m.

П р и м е р :

(Для простоты вычисления используем небольшие числа).

Пусть р=29, g=3. Заметим, что g=3 действительно примитивный корень, т.к. по теореме [2] с= ?(p)=28; q₁=2, q₂=7;

3¹⁴ mod 29=28?1; 3 ⁴mod 29=23?1;

Закрытый ключ выбираем х=3. Пусть т=4. Открытый ключ 3³mod 29=6

Чтобы подписать сообщение, Отправитель вычисляет z= т^х mod p= 4³ mod 29=6.

Чтобы проверить подпись :

1. Получатель выбирает два случайных числа, a=10 и b=16, и отправляет Отправителю : c= т^ag^b mod p= 4¹⁰3¹⁶ mod 29=25.

2. Отправитель выбирает случайное число q=2, а затем вычисляет и отправляет Получателю:

s₁= cg^q mod p=25·3²mod 29=22, s₂= (cg^q)^x mod p= (25·3²)³ mod 29=5.

(3) Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что Получатель не мошенничал на этапе (1).

(4) Отправитель вычисляет cg^q, получает s_1.

(g^х)^b+q·z^a?(3³)¹⁶⁺²·6¹⁰=5(mod 29).

Действительно, s₂?5(mod 29).

Подпись правильна.

4.2 Преобразуемые неоспоримые подписи.

Сначала выбираются два простых числа, p и q так чтобы q было делителем p-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до p-1 выбирается случайное число h и вычисляется g=h^(p-1)/q mod p.

Если g=1, выбирается другое случайное число h. Если нет, используется полученное значение g. Закрытыми ключами служат два различных случайных числа, x и z,меньшие q. Открытыми ключами являются p, q, g, y и u, где y= g ^х mod p, u = g ^z mod p.

Для вычисления преобразуемой неотрицательной подписи сообщения т (которое в действительности является хэш-значением сообщения), сначала в диапазоне от 1 до q-1 выбирается случайное число t. Затем вычисляется Т= g ^r mod p и т'=Ttzm mod q.

Теперь вычисляется обычная подпись ElGamal для т'. Выбирается случайное число R, меньшее р-1 и взаимно простое с ним. Затем вычисляется r= g ^R mod p и, с помошью расширенного алгоритма Эвклида, вычисляется s, для которого т'?rx+Rs(mod q).

Подписью служат подпись ElGamal (r,s) и Т. Вот как Отправитель подтверждает свою подпись Получателю:

1. Получатель генерирует два случайных числа, а и b, и вычисляет c= T ^Tma g ^b mod p и посылает результат Отправителю.

2. Отправитель генерирует случайное число к и вычисляет h₁= cg^k mod p и h₂= h₁^z mod p, а затем посылает оба числа Получателю .

3. Получатель посылает Отправителю a и b.

4. Отправитель проверяет, что c= T ^Tma g ^b mod p. Он посылает к Получателю.

5. Получатель проверяет, что c= T ^Tma g ^b+к mod p, и что h₂= y ^ra r^sa u ^b+k mod p. [1]

Отправитель может преобразовать все свои неоспоримые подписи в обычные, опубликовав z. Теперь любой может проверить его подпись без его помощи.

Схемы неоспоримых подписей можно объединить со схемами разделения секрета, создав распределенные преобразуемые неоспоримые подписи. Кто–нибудь может подписать сообщение, а затем распределить возможность подтверждения правильности подписи. Он может, например, потребовать, чтобы в протоколе убеждения Получателя в правильности подписи участвовали трое из пяти обладателей возможность подтверждения правильности.

4.3 Подписи, подтверждаемые доверенным лицом .

Сначала опубликовываются большое простое число р и примитивный элемент g, которые будут совместно использоваться группой пользователей. Также опубликовывается п, произведение двух простых чисел. У Участника 3 есть закрытый ключ z и открытый ключ h=g^хmod p.

В этом протоколе Отправитель может подписать т так, чтобы Получатель мог проверить правильность его подписи, но не мог убедить в этом третью сторону.

1. Отправитель выбирает случайное число х и вычисляет а=g^х mod p, b=h^х mod p. Он вычисляет хэш- значение т, Н(т), и хэш-значение объединения a и b, Н(а,b) j=(Н(т) Н(a, b))^1/3 mod n и посылает a, b и j Получателю.

2. Получатель выбирает два случайных числа, s и t, меньших р, и посылает Отправителю с= g^s h^t mod p.

3. Отправитель выбирает случайное q, меньшее p, и посылает Получателю

d=g^q mod p, e= (cd)^х mod p

1. Получатель посылает Отправителю s и t.

2. Отправитель проверяет, что g^s h^t ?с(тod p) затем он посылает Получателю q.

3. Получатель проверяет d?g^q mod p, е/ а^q?a^s b^t(тod p),

(Н(т) Н(a, b))= j ^1/3 mod n

Если все тождества выполняются, то Получатель считает подпись истиной. [10]

Получатель не может использовать запись этого доказательства для убеждения Участника 4 в истиности подписи, но Участник 4 может выполнить протокол с доверенным лицом Отправителя, Участник 3. Вот как Участник 3 убеждает Участника 4 в том, что a и b образуют правильную подпись.

1. Участник 4 выбирает случайные u v k= g^u a^v mod p

2. Участник 3 выбирает случайное w, меньшее р, и посылает Участнику 4

l= g^w mod p, y= (kl) ^z mod p

1. Участник 4 посылает Участнику 3 u и v.

2. Участник 3 проверяет, что g^u a^v ?k(тod p). Затем она посылает Участнику 4 w.

3. Участник 4 проверяет, что g^w ?l(mod p), y/h^w?h^u b^v(тod p).

Если все тождества выполняются, то Участник 4 считает подпись истинной. [11]

4.4 Групповые протоколы для цифровых подписей.

Понятие групповой подписи было предложено Чаумом в работе [5]. Схема подписи для группы подписывающих и одного проверяющего называется схемой групповой подписи (group signature scheme), если     

1) подписывать сообщения могут только члены группы подписывающих

2) проверяющий может проверить, что подпись была сгенерирована некоторым подписывающим, но не может установить, кем именно (анонимность подписывающего);

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

В той же работе [6] предложено четыре схемы групповой подписи. Приведем для примера краткое описание первой схемы:

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

2. Соответствующие открытые ключи публикует в случайном порядке в некотором общедоступном сертифицированном справочнике.

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

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

5. Так как открытые ключи опубликованы в этом справочнике в случайном порядке, проверяющий не может узнать, кому из подписывающих принадлежит тот или иной открытый ключ. Только Посредник, зная соответствие между открытыми ключами и подписывающими, может "открыть" данную подпись.

Одним из недостатков данной схемы является то, что Посредник знает секретные ключи подписывающих и, следовательно, может сам подписывать сообщения вместо них. Авторы [6] предлагают для предотвращения этой угрозы использовать затемненные открытые ключи (blinded public keys), смысл которых заключается в следующем:

1. Пусть в используемой схеме электронной подписи секретные ключи выбираются из Z_p-1, где p - простое число, и каждому секретному ключу x соответствует открытый ключ g ^х mod p, где g - некоторый порождающий группы Z^*_p.

2. Каждый подписывающий (скажем, i-й) выбирает s_i? Z_p-1

3. и посылает g ^si mod p Посреднику.

4. После этого Посредник выбирает r_i? Z_p-1

5. И, затем, дает его подписывающему и публикует (g ^si)^ri mod p в качестве открытого ключа.

Соответствующий секретный ключ может быть вычислен подписывающим в виде

s_ir_i mod p.

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

В работе Чена и Педерсена [7] описана модификация этой схемы, в которой ключи выбирает не Посредник, а подписывающие. Каждый подписывающий свои секретные ключи сохраняет в секрете, а открытые - посылает Посреднику. После получения открытых ключей от всех подписывающих Посредник публикует эти ключи в случайном порядке в некотором общедоступном сертифицированном справочнике. В остальном схема совпадает с описанной выше. Другие схемы групповой подписи предложены в работах Чена и Педерсена [8] и [9].

Используемая литература.

[1] Брюс Шнайер, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке С, 2003 М. Издательство ТРИУМФ.

[2] Виноградов И.М. Основы теории чисел . — M.: Наука, 1972.

[3] Введение в криптографию, 2-е изд., испр. / Под общ. ред. В.В.Ященко. — М.: МЦНМО-«ЧеРо», 1999.

[4] Блейхут Р. Теория кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986. -576 с.

[5] B. Beauchemin , G. Brassard, C. Crepeau, C.Goutier, and C. Pomerance, “ The Generation of Random Numbers that are Probably Prime”. Journal of Cryptology, v.1, 1988, pp.53-64.

[6] Chaum D., Zero-knowledge undeniable signatures, Proc. EUROCRYPT'90, Lect. Notes. in Comp. Sci., v. 473, 1991, 458-464

[7] Chaum D., van Heyst E., Group signatures, Proc. EUROCRYPT'91, Lect. Notes in Comp. Sci., v. 547, 1991, 257-265

[8] Chen L., Pedersen T. P., On the efficiency of group signatures providing information-theoretic anonymity, Proc. EUROCRYPT'95, 39-49

[9] Crandall R. E., Penk M. A., A search for large twin pairs, Math. Comput., v. 38, 1979, 383-388

[10] Chen L., Pedersen T. P., New group signature schemes, Proc. EUROCRYPT'94, 1994

[11] W.F.Friedman, Methods for the Solution of Running-Key Ciphers, Riverbank publication No. 16, Riverbank Labs, 1918.