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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ АЗЕРБАЙДЖАНСКОЙ РЕСПУБЛИКИ БАКИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Студента IV курса группы 297 дневного отделения факультета Прикладной математики и кибернетики Армизаева Константина Алексеевича ВЫПУСКНАЯ РАБОТА на тему Неоспоримые цифровые подписи в криптографии на соискание степени бакалавра Заведующий кафедрой д. ф м.н. ,проф. Мансимов

К.Б. Научный руководитель к.ф м.н. Асланова Н.Х. Б А К У - 2006 Содержание Введение.3-1. Основные понятия 5-2. Основные протоколы для цифровых подписей 11-3. Необходимый математический аппарат 12-4. Основные алгоритмы неоспоримой цифровой подписи. 4.1 Алгоритм Чаума.26-4.2 Преобразуемые неоспоримые подписи 28-29 4.3

Подписи, подтверждаемые доверенным лицом 29-4.4 Групповые протоколы для цифровых подписей 30 Используемая литература 31 Введение. Криптография как искусство скрытой передачи информации существует уже тысячелетия. Люди уже давно поняли, что информация является большой ценностью, и поэтому много усилий затрачивалось как на ее охрану, так и на ее добывание. Вообще говоря, совершенно не обязательно это связано с какими-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, теперь функции шифрования и дешифрования с ключевой структорой будут выглядит вот так EКМС DКСМ или DКEКММ. В частых случаях, для шифрования используется один ключ, а при дешифровании другой. То есть ключ шифрования, К1, отличается от соответствующего ключа дешифрования, К2. В этом случае EК1МС DК2СМ или DК2EК1ММ. Вся безопасность алгоритмов с ключом полностью основана на ключах, а не на деталях алгоритмов. То есть, не имеет значения, что злоумышленнику известен ваш алгоритм,

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

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

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

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

что лучше, получении ключаключей, использованного для шифрования сообщений, зашифрованных теми же ключами. Дано С1ЕкМ1, С2ЕкМ2 СiЕкМi Получить либо М1,М2 Мiк либо алгоритм получения Мi1 из Сi1ЕкМi1. 2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифротекстам нескольких сообщений, но и к открытому туксту этих сообщений. Его задача состоит в получении ключа или ключей, использованного для шифрования сообщений,

для дешифрования других сообщений зашифрованных тем же ключомили ключами. Дано М1, С1ЕкМ1, М2,С2ЕкМ2 Мi,СiЕкМi Получить Либо к либо алгоритм получения Мi1 из Сi1ЕкМi1. 3. Вскрытие с использованием выбранного открытого текста. У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать открытый текст для шифрования.

Это предоставлляет больше больше вариантов чем вскрытие с использованием открытого текста, что может дать больше информации о ключе. Его задача состоит в получении ключа или ключей , использованного для шифрования сообщений, или алгоритма, позволяющего дешифровать новые сообщения, зашифрованные тем же ключом или ключами. Дано М1, С1ЕкМ1, М2,С2ЕкМ2 Мi,СiЕкМi, где криптоаналитик может выбирать М1,М2 Мi Получить Либо к либо алгоритм получения Мi1 из

Сi1ЕкМi1. 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 Получатель подписывает контракт. Подпротокол с использованиием арбитравыполняется при наличии разногласий 4 Отправитель и Получатель предстают перед судьей. 5 Отправитель предоставляет свои доказательства. 6 Получатель предоставляет свои доказательства.

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

Если одна из сторон попытается смошенничать, мошенничество будет немедленно обнаружено другой стороной, и протокол прекратит выполняться. Чего бы не пыталась добиться мошенничающая сторона, этому не суждено случиться. 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 Получатель получает значение однонаправленной хэш-функции для документа, присланного

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

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

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

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

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

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

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

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

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

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

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

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

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

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

закрытым ключом и пытается проверить подпись Взломщика протоколов, дешифрируя ее с помощью открытого ключа Взломщика протоколов. В результате получается полная чепуха EАDBEBDAM EMDAM Даже в этом случае, следуя протоколу, Получатель посылает Взломщику протоколов полученное сообщение EМDBEМDAM Теперь Взломщик протоколов остается только расшифровать сообщение с помощью своего закрытого

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

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

и закрытого ключа человека, подписавшего документ. Но в отличии от обычных подписей, неотрицаемая подпись не может быть проверена без разрешения подписавшего. Несмотря на идею математики основная идея проста 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 bmod m. Сравнимость чисел а и b по модулю m равносильна 1.Возможности представить а в виде аbmt, где t- целое. 2. Делимости а-b на m. 3. Если a bmod m, то a ,т b ,m. Числа, равноостаточные образуют класс чисел по модулю т. Обозначим через Zт класс, состоящий из т элементов.

Zт 0, 1 m1 Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mqr заставим q пробегать все целые числа. Соответственно, m различным значениям r имеем m классов чисел по модулю m. Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса. Вычет, получаемый при q0, равный самому остатку 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,цpn pn1p 1 Если npq, где p и q простые числа, то цп цpqp-1q-1. Эти числа появляются в некоторых алгоритмах с открытым ключом. Эти свойства позволяют быстро вычислять функцию Эйлера, если известно разложение числа n на простые

множители. Доказывается формула2 цnn1-1 p11-1 ps Теорема Эйлера и малая теорема Ферма. В последние годы основные положения теории чисел стали широко применятся в криптографии. Приведем без доказательств некоторые важные теормы, неоюходимые для понимания дальнейшего материала. Теорема Эйлер. 2 При n 1 и НОД a, n 1 верно следующее aцn 1 mod n, для любого a Zn При простом n эта теорема превращается в малую теорему

Ферма Теорема Ферма. 2 Для любого простого p и любого натурального a верно следующее ap a mod p , для любого a Zp Первообразные корни. Пусть p простое число. Тогда, как известно, Zp является полем. Порядком вычета a 0 называется наименьшее натуральное число m такое, что am 1 mod p Согласно малой теореме Ферма, хотя бы одно такое m существует и равно p1. Теорема. Для любого простого p существует вычет образующая группы

Zp g порядка p1. Такой вычет g называется первообразным корнем по модулю p. Несложно также показать, что таких вычетов существует ровно цp1. Первообразные корни по модулям рб и 2рб. Я приведу, лишь, вспомогательный факт без доказательствa. Но доказательствo есть в 2. Теорема. 2 Пусть с цp и q1, q2, ,qk - различные простые делители числа с. Для того чтобы число g, взаимно простое с т, было первообразным корнем по модулю т, необходимо и

достаточно, чтобы это g не удовлетворяло ни одному из сравнений gсq11mod m, gсq21mod m, gсqk1mod m. Введем обозначение Zn, n аддитивная группа вычетов по модулю n, здесь n операция сложения по модулю n. Zn, 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 n1n2nk. Причем числа n1, n2 nk попарно взаимно просты. Рассмотрим соответствие a - a1, a2 ak , где ai остаток от деления a на ni. Тогда оно задает взаимно однозначное соответствие между классом

Zn и декартовым произведением Zn1Ч Ч Znk. При этом операция сложения , вычитания и умножения в Zn соответствуют покомпонентные операции над к-элементными кортежами если a - a1, a2 ak и b - b1,b2 bk, то ab mod n - a1 b1 mod n1 ak bk mod nk a-b mod n - a1- b1 mod n1 ak- bk mod nk ab mod n - a1 b1 mod n1 ak bk mod nk . Рассмотрим систему сравнений x b1mod m1, x b2mod m2 x bkmod mk. Решить эту систему, т.е. найти все значения х , ей удовлетворяющие, можно, применяя следующее утверждение 2

Пусть числа Ms и Ms определены из условий m1m2 mk Msmk, Ms Ms 1 mod ms, и пусть х0 M1 M1 b1 M2 M2 b2 Mк Mк bк. Тогда совокупность значений х, удовлетворяющих системе определяются сравнением x х0 mod m1m2 mk . П р и м е р Решим систему x 2mod 3, x 3mod 5, x 5mod 11. Здесь 35115533351511165, причем 551 1mod 3, 332 1mod 5, 153 1mod 11.

Поэтому х0 5512332315311, и , следовательно, совокупность значений х, удовлетвряющих системе x 2mod 3, x 3mod 5, x 5mod 11, будет x 110 198225533 38mod 165. О дискретном логарифме. Пусть g является образующей группы Zn ,тогда для всякого a Zp найдется z, для которого gz amod n. Такое z называется дискретным логарифмом. Теоремао дискретном логарифме.

Пусть g является вычетом. Тогда сравнение gx gymod p равносильно сравнению x y mod цp . Целые числа a и b являются взаимно простыми,если НОДa ,b1 Теорема. Если НОДa,p1 и НОД b,p1,то НОДаb,p1 для любых простых чисел а,b,p. Алгоритм вычисления ad mod m. Как мы знаем , вычисление ad mod m при достаточно большом а, довольно таки, трудоемкое занятие. Я даже не говорю о буковке d, точнее о том, какие значения она принимает.

Таким образом , чтобы облегчить это вычисления мы приведем алгоритм. 1. Представим d в двоичной системе счисления d d0 2r dr-12 dr ,где di-цифры в двоичном представлении равны 0 или 1, d01. 2. Положим а0а и затем для i1 r вычислим аi a2i-1adi mod m 3. аr есть искомый вычет admod m. сложность алгоритма 0ln m П р и м е р Найдем 57207mod 3313 a057, d207272623222120. Таким образом, d01 d11 d20 d30 d41 d51 d61 d71 а157257 mod 3313 2978 а229782 mod 3313 2896 а328962 mod 3313 1613

а41613257 mod 3313 1014 а51014257 mod 3313 202 а6202257 mod 3313 102 а7102257 mod 3313 1 Т.о. 57207mod 3313 1. Разложение на простые множители. Теорема. Если простое число p делит произведение двух целых чисел а и b , то pa или pb. Теорема существование и единственность разложения. Всякое составное число а p1 E1p2 E2 prEr, где p1 p2 pr -простые числа, а

Ei- положительные целые числа. Теорема рекуррентная формула для НОД. Пусть а целое неотрицательное число, а b- целое положительное число. Тогда НОДa,bНОДb,а mod b. Расширенный алгоритм Евклида. Немного дополнив известный алгоритм нахождения НОД двух натуральных чисел, можно получить с его помощью коэффициенты х и у, для которых НОДa,bахby1, при a,b1.Итак, этот алгоритм используется для решения уравнения

ax 1mod b или bу 1mod a, при a,b1. Определим матрицу 1. Вычислим остаток r от деления числа a на b, abqr,0r b. 2. Если r0, то второй столбец матрицы Е дает вектор решений уравнения 3. Если r0, то заменим матрицу Е матрицей 4. Заменим пару чисел a,b парой b,r и перейдем к шагу 1. Сравнения второй степени. Рассмотрим сравнение х2 а mod р, при a, р 1. 1

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

Это второе решение отлично от первого, т.к. из х1 х1 mod р мы имели бы х1 0 mod р, что невозможно, ввиду 2,рх1,р1. Приведенная система вычетов по модулю р состоит из р-12 квадратичных вычетов, сравнимых с числами 12,22 р-122 и р-12 квадратичных невычетов. О символе Лежандра Рассмотрим La,p, называемый символом Лежандра, с помощью, которого можно определить, является ли а квадратичным вычетом по модулю р для простого

р. Вычислить символ Лежандра La,p и определить является ли а квадратичным вычетом, либо не является позволяет следующее утверждение Теоремакритерий Эйлера. При а, не делящемся на р, имеем ap-12 La,pmod p. Итак, символ Лежандра определяется следущим образом La,p0, если а делится на р. La,p1,если а-квадратичный вычет по модулю р. La,p-1,если а-квадратичный невычет по модулю р.

La,p можно рассчитать следующим образом La,p ap-12 mod p. Или можно воспользоваться следующим алгоритмом 1. Если а1, то La,p1. 2. Если а четно, то La,p La2,p-1 p-18 3. Если а нечетно и1, то La,p Lр mod a,p-1q-1p-14 О символе Якоби Ja,р Символ Якоби Ja,р представляет собой обобщение символа

Лежандра на составные модули, он определяется для любого целого а и любого нечетного р. Ja,р определен только, если р нечетно. J0,р 0 Если p простое число, то 1 Ja,p 0, если a делится на p 2 Ja,p1, если a - квадратичный вычет по модулю p 3 Ja,p-1, если a - квадратичный невычет по модулю p Если p составное число, то Ja,р Ja, p1 Ja, p2 Ja, pm, где p1 pm простые множители все p.

Правило 1 J1,р1 Правило 2 Jab,р Ja,р Jb,р Правило 3 J2,p1, если p2 -18 четно и J2,p-1, если p2 -18 нечетно Правило 4 Ja,p Ja mod p,p Правило 5 Ja, b1 b2 Ja, b1 Ja, b2 Правило 6 Если НОДa,b1 и a и b нечетны, то Ja,bJb,a, если a-1b-14 четно, Ja,b-Jb,a, если a-1b-14 нечетно. П р и м е р Вычислим

J21,109 По правилу 2 имеем J21,109J37,109 J3,109 J7,109 По правилу 6 имеем НОД3,1091, НОД7,109 и 3 и 7 и 109 нечетны, тогда 2108454, то J3,109 J109,3 61084162, то J7,109 J109,7 По правилу 4 имеем J109 mod 3,3 J1,31 J109 mod 7,3 J4,7 По правилу 2 J4,7 J2,7 J2,7 По правилу 3 72 -186 - четно, то J2,71 Получаем, что

J21,109 J1,3J2,7 J2,71. Итак, 21 является квадратичным вычетом. Проверка чисел на простоту. Тест Соловея-Штрассена. Для проверки простоты числа p в этом алгоритме используется символ Якоби. p нечетное, большое число 1. Выберите случайное число a, меньше р. 2. Если НОДa,p 1, то р - составное число и не проходит тест.

3. Вычислите j ap-12 mod p. 4. Вычислите символ Якоби Ja,p. 5. Если j Ja,p,то число р определенно не простое. a-свидетель 6. Если j Ja,p,то вероятность того, что число р не является простым и не превышает . Повторить эту процедуру t раз. 5 П р и м е р Пусть требуется проверить на простоту число 109. 1. Выберем случайно а21. 2. НОДа,рНОД21,1091 вычисляем по алгоритму

Евклида. 3. Вычисляем j ap-12 mod p 2154 mod 1091 вычисляем по быстрому алгоритму ad mod m. 4. Вычисляем символ Якоби Ja,р J21,1091это мы уже вычислили, можно посмотреть выше. 5. jJ21,1091, число а21 прошло тест. 1. Теперь выберем случайно а49. 2. НОДа,рНОД49,1091вычисляем по алгоритму Евклида. 3. Вычисляем j4954mod 1091 вычисляем по быстрому алгоритму.

4. Вычисляем символ Якоби Ja,р J49,1091. 5. jJ49,1091, число а49 прошло тест. 1. Выберем случайно а9. 2. НОДа,рНОД9,1091 вычисляем по алгоритму Евклида. 3. Вычисляем j ap-12 mod p 954 mod 1091 4. Вычисляем символ Якоби Ja,р J9,1091 5. jJ9,1091, число а21 прошло тест. Числа Кармайкла. Неподходящими для теста Соловея-Штрассена являются так называемые числа

Кармайкла. Они обладают следующим свойством для любого a такого, что НОДa, p 1 верно an1 1 mod n Первые три числа Кармайкла таковы 561, 1105, 1729. Среди первых 10 чисел их всего 255. Лишь недавно 1994 г. было доказано, что таких чисел бесконечно много. 5 Тест Миллера-Рабина. Вычислить b-число делений p-1 на 2 т.е. 2b это наибольшая степень числа 2, на которую делится p-1.

Вычислить m,такое,что p12b m, m-нечетно. 1. Выберите случайное число а, меньшее р. 2. Установите j0 и z am mod p. 3. Если z1 или если zp-1, то p проходит тест и может быть простым числом. 4. Если j 0 и z1,то р не относится к простым числам. 5. Установите jj1. Если j b и zp-1,установите z z 2 mod p и вернитесь на этап 4. Если zp-1, то p проходит тест и может быть простым числом.

6. Если jb и zp-1, то р не относится к простым числам. То а, при котором обнаруживается, что р составное, называется свидетелем. Гарантируется, что возможных значений а окажутся свидетелями. Это означает, что составное число ошибочно пройдет t тестов с вероятностью не более t , где t число итераций. Для большинства случайных чисел свидетелями служат около 99,9 возможных значений а.

5 Если р-простое число, p-12b m, m-нечетно, то согласно малой теореме Ферма для каждого а, такого, что а,р1 хотя бы одна из скобок в произведении am-1am1 a2m1 a2bm1 ap-1-1 делится на p.5 П р и м е р ы 1 Проверим, является ли число 2031 простым. Итак, 203021015 т.о. b1 m1015 1. Выберем случайное a, a p а43 2. Установим j0 и z 431015 mod 20311406. 3. z1, z2030. 4. j 0 нет.

5. j1 j b нет, т.к. j1 6. j1 и z2030 Не является простым числом действительно, 20316773. 2 Проверим, является ли 109-1108 1082227 b2 m27. 1. Выберем случайное a15 2. Установим j0 и z1727 mod 1091 3. z1, то р109 проходит тест и может быть простым. 4. Основные алгоритмы неоспоримой цифровой подписи. 4.1 Алгоритм Чаума. Сначала опубликовывается большое простое число р и примитивный элемент g, которые

будут совместно использоваться группой подписывающих. У Отправителя есть закрытый ключ х и открытый ключ gх mod p. Чтобы подписать сообщение, Отправитель вычисляет z тх mod p. Это все, что ему нужно сделать. Проверка подписи немного сложнее. 1 Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет

Отправителю c zagхb mod p 2 Отправитель вычисляет t x-1mod p-1, и отправляет Получателю d ct mod p. 3 Получатель проверяет, что d тagb mod p Если это так, он считает подпись истинной. 1 П р и м е р Для простоты вычисления используем небольшие числа. Пусть р23, g5. Заметим, что g5 действительно примитивный корень, т.к. по теореме 2 с цp22 q12, q211 52

mod 2321 511 mod 23221 Закрытый ключ выбираем х7. Пусть т3. Открытый ключ 57mod 2317 Чтобы подписать сообщение, Отправитель вычисляет z тх mod p 37 mod 232. Проверка подписи Получателем 1 Получатель выбирает два случайных числа, a4 и b2, и отправляет Отправителю c zagхb mod p 24572 mod 231 2 Отправитель вычисляет t 7-1mod 223, и отправляет

Получателю d ct mod p13 mod 231. 3 Получатель проверяет, что d3452 mod 231. Поскольку d совпадает с тagb, то подпись Получатель считает истинной. Представим, что Отправитель и Получатель выполнили этот протокол, и Получатель теперь считает, что Отправитель подписал сообщение. Получатель хочет убедить в этом Участника 3, поэтому он показывает ему запись протокола.

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

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

Как и предыдущий протокол група подписывающих использует общедоступное большое простое число p и примитивный элемент g.2 У Отправителя есть закрытый х и открытый ключ gх mod p. Чтобы подписать, сообщение Отправитель вычисляет z тх mod p. Чтобы проверить подпись 1 Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет Отправителю c тagb mod p 2 Отправитель выбирает случайное число q, меньшее p, а затем вычисляет и отправляет

Получателю s1 cgq mod p, s2 cgqx mod p 3 Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что Получатель не мошенничал на этапе 1. 4 Отправитель посылает Получателю q, чтобы он мог воспользоваться тх и восстановить s1 и s2. Если s1 cgq mod p, s2 cgхbq mod p, то подпись правильна.

Отправитель может также отказаться от подписи z под сообщением m. П р и м е р Для простоты вычисления используем небольшие числа. Пусть р29, g3. Заметим, что g3 действительно примитивный корень, т.к. по теореме 2 с цp28 q12, q27 314 mod 29281 3 4mod 29231 Закрытый ключ выбираем х3. Пусть т4. Открытый ключ 33mod 296 Чтобы подписать сообщение,

Отправитель вычисляет z тх mod p 43 mod 296. Чтобы проверить подпись 1 Получатель выбирает два случайных числа, a10 и b16, и отправляет Отправителю c тagb mod p 410316 mod 2925. 2 Отправитель выбирает случайное число q2, а затем вычисляет и отправляет Получателю s1 cgq mod p2532mod 2922, s2 cgqx mod p 25323 mod 295. 3 Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что

Получатель не мошенничал на этапе 1. 4 Отправитель вычисляет cgq, получает s1. gхbqza331626105mod 29. Действительно, s25mod 29. Подпись правильна. 4.2 Преобразуемые неоспоримые подписи. Сначала выбираются два простых числа, p и q так чтобы q было делителем p-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до p-1 выбирается случайное число h и вычисляется ghp-1q mod p. Если g1, выбирается другое случайное число 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, для которого тrxRsmod q. Подписью служат подпись ElGamal r,s и Т. Вот как Отправитель подтверждает свою подпись Получателю 1 Получатель генерирует два случайных числа, а и b, и вычисляет c

T Tma g b mod p и посылает результат Отправителю. 2 Отправитель генерирует случайное число к и вычисляет h1 cgk mod p и h2 h1z mod p, а затем посылает оба числа Получателю . 3 Получатель посылает Отправителю a и b. 4 Отправитель проверяет, что c T Tma g b mod p. Он посылает к Получателю. 5 Получатель проверяет, что c T Tma g bк mod p, и что h2 y ra rsa u bk mod p.

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

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

В этом протоколе Отправитель может подписать т так, чтобы Получатель мог проверить правильность его подписи, но не мог убедить в этом третью сторону. 1 Отправитель выбирает случайное число х и вычисляет аgх mod p, bhх mod p. Он вычисляет хэш- значение т, Нт, и хэш-значение объединения a и b, На,b jНт Нa, b13 mod n и посылает a, b и j Получателю.

2 Получатель выбирает два случайных числа, s и t, меньших р, и посылает Отправителю с gs ht mod p. 3 Отправитель выбирает случайное q, меньшее p, и посылает Получателю dgq mod p, e cdх mod p 4 Получатель посылает Отправителю s и t. 5 Отправитель проверяет, что gs ht стod p затем он посылает Получателю q. 6 Получатель проверяет dgq mod p, е аqas btтod p,

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

1 Участник 4 выбирает случайные u v k gu av mod p 2 Участник 3 выбирает случайное w, меньшее р, и посылает Участнику 4 l gw mod p, y kl z mod p 3 Участник 4 посылает Участнику 3 u и v. 4 Участник 3 проверяет, что gu av kтod p. Затем она посылает Участнику 4 w. 5 Участник 4 проверяет, что gw lmod p, yhwhu bvтod p.

Если все тождества выполняются, то Участник 4 считает подпись истинной. 11 4.4 Групповые протоколы для цифровых подписей. Понятие групповой подписи было предложено Чаумом в работе 5. Схема подписи для группы подписывающих и одного проверяющего называется схемой групповой подписи group signature scheme, если 1 подписывать сообщения могут только члены группы подписывающих 2 проверяющий

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

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

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

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

public keys, смысл которых заключается в следующем 1 Пусть в используемой схеме электронной подписи секретные ключи выбираются из Zp-1, где p - простое число, и каждому секретному ключу x соответствует открытый ключ g х mod p, где g - некоторый порождающий группы Zp. 2 Каждый подписывающий скажем, i-й выбирает si Zp-1 3 и посылает g si mod p Посреднику. 4 После этого

Посредник выбирает ri Zp-1 5 И, затем, дает его подписывающему и публикует g siri mod p в качестве открытого ключа. Соответствующий секретный ключ может быть вычислен подписывающим в виде siri 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. EUROCRYPT90, Lect. Notes. in Comp. Sci v. 473, 1991, 458-464 7

Chaum D van Heyst E Group signatures, Proc. EUROCRYPT91, 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. EUROCRYPT95, 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. EUROCRYPT94, 1994 11 W.F.Friedman, Methods for the Solution of Running-Key Ciphers, Riverbank publication No. 16, Riverbank Labs, 1918.