Криптографические протоколы с нулевым разглашением

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» (ФГБОУ ВО «ВГУ»)

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ, ИНФОРМАТИКИ И МЕХАНИКИ

КАФЕДРА ERP-СИСТЕМ И БИЗНЕС-ПРОЦЕССОВ

Курсовая работа

Криптографические протоколы с нулевым разглашением

Кудряшов Р.В.

ВОРОНЕЖ - 2020



Введение

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

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

Объект исследования: криптографические протоколы.

Предмет исследования: криптографические протоколы с нулевым разглашением.

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

Для достижения поставленной цели необходимо решить следующие задачи:

Изучить основную терминологию.

Рассмотреть симметричные алгоритмы и алгоритмы с открытым ключом.

Определить понятие криптоанализ.

Изучить аутентификацию пользователей в информационных системах.

Рассмотреть протоколы с нулевым разглашением секрета.

Изучить протоколы на основе алгоритмов открытого шифрования.

Рассмотреть протокол на основе использования криптосхемы RSA.

Изучить использование алгоритма открытого шифрования Эль-Гамаля.

Изучить протокол на основе криптосхемы Рабина.

Методы исследования: изучение и анализ научной литературы; методы обработки результатов (качественный анализ).



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

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

Отправитель и получатель

Одним из основных понятий в криптографии является понятие отправитель и получатель. Предположим, что отправитель хочет послать сообщение получателю, более того, этот отправитель хочет послать свое сообщение безопасно: он хочет быть уверен, что перехвативший это сообщение не сможет его прочесть. Стороны, обменивающиеся шифрованной информацией, обычно обозначаются А и В. Довольно часто употребляют более дружественные имена: Алиса и Боб. Но не следует думать, что стороны, участвующие в процессе, обязательно люди. Используя эти имена, мы вполне можем описывать обмен секретной информацией между двумя автономными механизмами. Подслушивающей стороне, «плохой девочке», которая взламывает шифртекст, обычно дают имя Ева [7].

Сообщения и шифрование.

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

Обозначим шифртекст как (от ciphertext), это тоже двоичные данные, иногда того же размера, что и M, иногда больше. Если шифрование сопровождается сжатием, может быть меньше чем . Однако, само шифрование не обеспечивает сжатие информации. Функция шифрования действует на , создавая .

Мы будем писать

где -- открытый текст, -- шифрующая функция, -- секретный ключ и -- шифртекст.

Обратный процесс называют расшифрованием и пишут

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

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

(( =

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

Рис. 1. Шифрование и дешифрирование

Проверка подлинности, целостность и неотрицание авторства.

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

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

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

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

Существуют жизненно важные требования к общению при помощи компьютеров, также как существуют аналогичные требования при общении лицом к лицу. Как раз это и является необходимость обеспечения проверки подлинности, целостности и неотрицания авторства [5].

Алгоритмы и ключи.

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

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

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

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

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

()=

()=

Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи. То есть ключ шифрования, К1, отличается от соответствующего ключа дешифрирования, K2.

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

При этом выполняется следующее равенство:

))

Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи. То есть ключ шифрования, К1, отличается от соответствующего ключа дешифрирования, K2. В этом случае:

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

Не имеет значения, что злоумышленнику известен алгоритм, поскольку, если ему не известен конкретный ключ, то он не сможет прочесть сообщения [8].

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



Рис. 2. Шифрование и дешифрирование с двумя различными ключами

1.2 Симметричные алгоритмы

Существует два основных типа криптографических алгоритмов: симметричные (с секретным ключом) и асимметричные (с открытым ключом). Симметричные алгоритмы, иногда называемые условными алгоритмами, представляют собой алгоритмы, в которых ключ шифрования может быть рассчитан по ключу дешифрирования и наоборот. В большинстве симметричных алгоритмов ключи шифрования и дешифрирования одни и те же. Эти алгоритмы, также называемые алгоритмами с секретным ключом или алгоритмами с одним ключом, требуется, чтобы отправитель и получатель согласовали используемый ключ перед началом безопасной передачи сообщений. Безопасность симметричного алгоритма определяется ключом, раскрытие ключа означает, что кто угодно сможет шифровать и дешифрировать сообщения. Пока передаваемые сообщения должны быть тайными, ключ должен храниться в секрете. Шифрование и дешифрирование с использованием симметричного алгоритма обозначается как [10]:

()=

()=

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

1.3 Алгоритмы с открытым ключом

Алгоритмы с открытым ключом (называемые асимметричными алгоритмами) устроены таким образом, что ключ, используемый для шифрования, отличается от ключа дешифрирования. Более того, ключ дешифрирования не может быть рассчитан по ключу шифрования. Алгоритмы называются "с открытым ключом", потому что ключ шифрования может быть открытым: кто угодно может использовать ключ шифрования для шифрования сообщения, но только конкретный человек, знающий соответствующий ключ дешифрирования, может расшифровать сообщение.

В этих системах ключ шифрования часто называется открытым ключом, а ключ дешифрирования - закрытым [8].

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

сообщение + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ШИФРТЕКСТ

ШИФРТЕКСТ + секретный ключ Алисы = сообщение.

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

Шифрование с открытым ключом обозначается как:

()=

Хотя открытый и закрытый ключи различны, дешифрирование с соответствующим закрытым ключом обозначается как:

()=

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

1.4 Криптоанализ

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

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

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

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

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

Дано

Получить: Либо , , . . . ; ; либо алгоритм, как получать из = ().

2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифртекстам нескольких сообщений, но и к открытому тексту этих сообщений. Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, для дешифрирования других сообщений, зашифрованных тем же ключом (ключами) [16].

Дано=(),, C2=(), . . ., . , . ,= ()

Получить: Либо ; либо алгоритм, как получать

из = ().

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

Дано=(),, C2=(), . . ., . , . ,= ()

Получить: Либо ; либо алгоритм, как получать

из = ().



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

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

Дано =(),, =(), . . .,,,= ()

Получить:

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

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

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

Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода: функции, циклические структуры и так далее. Вскрытия на основе известного открытого текста (и вскрытия на основе выбранного шифртекста) успешно использовались для чтения немецких и японских секретных сообщений, передаваемых в виде криптограмм по радиоканалу, в ходе Второй мировой войны [16].

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

В данном учебном пособии будут подробно рассмотрены протоколы аутентификации пользователей. Аутентификация является процедурой проверки подлинности и имеет огромное значение для информационных систем в настоящее время [20].



2. Аутентификация пользователей в информационных системах

алгоритм информационный криптоанализ шифрование

2.1 Простая аутентификация по паролю

В современных информационно-телекоммуникационных системах процедуры аутентификации удаленных пользователей весьма широко применяются. Можно выделить следующие типы протоколов аутентификации пользователей:

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

- протоколы строгой аутентификации (обеспечивает аутентификацию удаленных пользователей без явного разглашения секретного ключа);

- протоколы с нулевым разглашением (протоколы данного типа основанные на предварительном распределении открытых ключей и их аутентификации; каждый из взаимодействующих субъектов убеждается в подлинности другого субъекта с использованием открытого ключа последнего, причем после процедуры аутентификации никакой из субъектов не получает новой информации о секретном ключе субъекта, подлинность которого подтверждена в ходе осуществления протокола; до выполнения протокола общедоступна информация о секретном ключе, которая состоит в том, что секретный ключ связан с открытым ключом, однако его вычисление невыполнимо за обозримое время) [18].

Частным вариантом использования процедуры простой аутентификации является парольная защита входа в компьютерную систему. Например, пользователь формирует некоторую случайную информацию и, сохраняя ее в секрете, использует как пароль. Пароль в явном виде не хранится в памяти ЭВМ (или другого устройства, применяемого для выполнения аутентификации). Это требование направлено на то, чтобы потенциальный внутренний нарушитель не имел возможности извлечь из машинной памяти чужой пароль и присвоить себе полномочия другого пользователя. Для того, чтобы система защиты могла идентифицировать легальных (санкционированных) пользователей, в памяти ЭВМ хранятся образы их паролей, вычисленные по специальному криптографическому алгоритму, реализующему, так называемую, одностороннюю функцию y = где криптографический алгоритм - односторонняя функция. Основное требование к односторонней функции состоит в том, чтобы сложность вычисления значения функции по аргументу (по входу) была низкой, а сложно ость определения значения аргумента, для которого значение функции (значение выхода) было бы равно случайно выбранному значению, была высокой (неосуществимой за обозримое время при использовании всех вычислительных ресурсов доступных предполагаемому нарушителю).

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

Запрос на ввод идентификатора со стороны системы защиты.

Ввод пользователем своего идентификатора (имени) NAME.

Запрос на ввод пароля со стороны системы защиты.

Ввод пользователем пароля .

Вычисление системой защиты значения односторонней функции ,соответствующей значению аргумента

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

Если , то система защиты предоставляет пользователю права доступа (полномочия), соответствующие идентификатору NAME. В противном случае в журнале учета работы пользователей регистрируется событие попытки несанкционированного доступа. Для того, чтобы выдать себя за санкционированного пользователя нарушитель должен ввести правильный пароль. Зная образ вычислительно невозможно определить пароль . Если в системе защиты предусмотрены механизмы противодействия перехвату пароля с помощью программных или аппаратных закладок, а также через побочные электромагнитные излучения и наводки (ПЭМИН), акустический и оптический канал, то данный способ аутентификации пользователей обеспечивает высокую надежность защиты от узурпирования чужих полномочий. Рассмотренный пример относится к аутентификации пользователей на рабочих станциях, т. е. к задаче защиты входа в ЭВМ [13].

2.2 Протокол рукопожатия

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

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



3. Протоколы с нулевым разглашением секрета

3.1 Толкование понятия «нулевое разглашение секрета»

При изучении протоколов с нулевыми знаниями важным методическим аспектом является разъяснение термина «нулевое разглашение секрета». С понятием нулевого разглашения секрета можно связать понятие стойкости протокола к атакам различного типа. Стойкость криптографических схем (алгоритмов и протоколов) является одним из центральных понятий в криптографии. При этом для симметричных криптосистем различают условную (практическую) и безусловную (теоретическую) стойкость. Практическая стойкость связана с тем, что имеющиеся в настоящее время вычислительные ресурсы (уровень развития вычислительной техники) не позволяют за обозримое время взломать криптосистему, тогда как это принципиально возможно. Теоретическая стойкость предполагает стойкость криптосистемы при наличии у атакующего бесконечных вычислительных ресурсов. По своей природе двухключевые криптосхема не могут обладать теоретической стойкостью и относятся к классу практически стойких криптосхем. Для двухключевых криптосхем используется понятие доказуемой стойкости. Двухключевая криптосхема называется доказуемо стойкой, если можно формально доказать, что взлом криптосхемы не проще, чем решение вычислительно трудной задачи, лежащей в ее основе [16].

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

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

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

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

Доказывающий передает проверяющему случайные значения.

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

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

Пусть, например, используется проверочное соотношение вида

где p - достаточно большое простое число; б ? число простого порядка r по модулю p; y - открытый ключ доказывающего, вычисляемый по личному секретному ключу и формуле R ? значение фиксатора (разового открытого ключа), вырабатываемого по случайному равновероятному секретному значению и формуле R =. w ? ответ доказывающего, направляемый по открытому каналу связи.

Множество значений , где i = 1, 2, …, q, охватывает все возможные значения фиксатора R. При равновероятном случайном выборе значения k, удовлетворяющего условию k < q, случайное значение R является равновероятным, т.е. принимает с одинаковой вероятностью любое значение из множества Нетрудно видеть, что ответ w вычисляется доказывающим по формуле , поэтому при равновероятном выборе k значение w является равновероятным, т.е. всевозможные значения w имеют одну и ту же вероятность, равную . Всевозможные пары значений (w, R), генерируемых доказывающим и удовлетворяющих соотношению (1), имеют одну и ту же вероятность, равную .

Такие же равновероятные пары (w, R) может сгенерировать и нарушитель. Для этого он генерирует случайное равновероятное значение w < q и вычисляет значение При таком способе генерации пар (w, R), удовлетворяющих соотношению (1), всевозможные значения этих пар имеют одну и ту же вероятность . Таким образом, если наличие равновероятных случайных пар (w, R) из области их возможных значений как-то упрощают задачу дискретного логарифмирования по простому модулю, то нарушитель может самостоятельно сгенерировать равновероятные случайные пары (w, R) в нужном ему количестве без того, чтобы тратить время на ожидание выполнения протокола с нулевым разглашением [16].

3.2 Многораундовые протоколы

Многораундовые протоколы с нулевым разглашением включают многократное повторения трех типовых шагов:

- генерация доказывающим разового случайного секретного ключа и вычисление по нему разового открытого ключа, который передается (объявляется) проверяющему и часто называется фиксатором;

- генерация проверяющим нулевого (r = 0) или единичного (r = 1) запроса с вероятностью 0,5 и направление бита запроса r доказывающему;

- вычисление доказывающим ответа w и направление w проверяющему.

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

Протокол Фиата-Шамира.

Протокол Фиата-Шамира основан на сложности извлечения квадратного корня по составному модулю, включающему не менее двух больших простых множителей, при условии, что разложение неизвестно. Доказывающий выбирает два больших простых числа p и q и вычисляет модуль n = pq. Затем выбирает в качестве своего личного секретного ключа случайное число s, такое, что 1 ? s ? n - 1, и вычисляет значение (В дальнейшем он будет доказывать проверяющему то, что он знает квадратный корень из y.) Значение y, которое объявляется всем участникам протокола, играет роль открытого ключа в смысле его использования для проверки того, что доказывающий знает s.

Протокол состоит из z-кратного повторения раунда, включающего следующие три шага:

Доказывающий выбирает случайное число k, такое, что 1 ? k ? n - 1, вычисляет значение , называемое фиксатором, и посылает его проверяющему. (Число k играет роль разового секретного ключа и обеспечивает защиту личного секретного ключа от разглашения при направлении ответа, зависящего от s.)

Проверяющий отправляет доказывающему равновероятный случайный бит r (r = 1 или r = 0).

3. Доказывающий вычисляет значение и направляет его проверяющему. (Если r = 1, то . Если r = 0, то w = k. Видно, что по этим двум результатам легко вычисляется секрет s, поэтому значения k должны уничтожаться после каждого раунда или после выполнения всего протокола) [11].

Проверяющий считает ответ верным, если выполняется соотношение



Если r = 1, то должно выполняться . Если r = 0, то получаем . В ходе осуществления протокола выполняется z шагов. Вероятность того, что нарушитель (который не знает секрета s) при выполнении одного раунда может дать положительный ответ, равна , следовательно, вероятность того, что нарушитель может быть принят за пользователя, знающего секрет s, составляет. Выбирая в протоколе достаточно большое число раундов проверки, можно сделать сколь угодно низкой вероятность обмана.

Рассмотрим два возможных варианта действий нарушителя в одном раунде.

В первом варианте он выбирает произвольное число k и передает проверяющему значение . Если он получит от проверяющего запрос r = 0, то направит правильный ответ w = k. Однако правильно ответить на запрос r = 1 нарушитель не имеет возможности.

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

Однако, на запрос r = 0 нарушитель правильно ответить не сможет.

Таким образом, нарушитель в лучшем случае может правильно ответить только на один вопрос, и в одном раунде с вероятностью 1/2 попытка обмана обнаруживается.

В протоколе нет утечки информации о ключе. Действительно, по запросу проверяющего r = 0 доказывающий направляет ему случайное число k, но проверяющий самостоятельно мог бы сгенерировать случайное число, возвести его в квадрат, получив значение . Самостоятельно полученная пара случайных чисел ничем не хуже, чем пара случайных чисел , полученных от доказывающего. По запросу проверяющего доказывающий направляет ему случайное число w, но проверяющий самостоятельно мог бы сгенерировать случайное число и вычислить случайное значение . Нетрудно видеть, что, если проверяющий сможет вычислить квадратный корень из случайного , то потом он легко вычислит секретный ключ. Идентичную возможность имеет проверяющий при получении пары случайных чисел , связанных соотношением , т. е. если проверяющий сможет вычислить квадратный корень из случайного числа u, то затем он легко вычислит секретное значение s. Таким образом, данные, полученные в процессе выполнения описанного протокола проверяющим от доказывающего, не дают никаких новых возможностей проверяющему для вычисления секретного ключа. В этом смысле следует понимать то, что утечки информации о секрете, в ходе протокола, не происходит [11].

3.3 Трёхшаговые протоколы

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

Некоторые многораундовые протоколы могут быть преобразованы в трехшаговые более практичным способом. Последний способ реализуется за счет использования открытого ключа, представляющего собой z упорядоченных значений, вычисляемых как независимые открытые ключи исходного многораундового протокола [11].

Трехшаговый вариант протокола Фиата?Шамира.

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

.

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

Доказывающий выбирает случайное число k, такое, что , вычисляет значение и посылает его проверяющему.

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

Доказывающий вычисляет свой ответ в виде значения и направляет его проверяющему.

Проверяющий считает ответ положительным, если выполняется соотношение

Легко показать, что вероятность обмана проверяющего в этом протоколе составляет .



4. Двухшаговые протоколы с нулевым разглашением секрета

4.1 Протоколы на основе алгоритмов открытого шифрования

Построение протоколов с нулевым разглашением можно реализовать, используя известные алгоритмы открытого шифрования. Для этого будет использоваться секретный ключ. Для того, кто выполнил процедуру шифрования правильно, восстановленное сообщение будет нести только информацию о том, что тот, кто восстановил зашифрованное сообщение, знает секретный ключ, связанный с открытым ключом. Однако, потенциальный нарушитель может выбрать произвольное значение и объявить его криптограммой, полученной в результате шифрования сообщения M, и попросить владельца открытого ключа выполнить процедуру расшифрования криптограммы. Если последний это сделает и раскроет восстановленное сообщение, то уже потенциально может иметь место утечка информации о секретном ключе. Говорить, что сообщение не несет в себе информацию о секретном ключе нельзя, так как была раскрыта информация. Поэтому, при построении протоколов с нулевым разглашением секрета, нужен некоторый механизм, который позволяет владельцу открытого ключа (доказывающему) убедиться до раскрытия восстановленного сообщения в том, что последнее уже известно (проверяющему) [17].

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

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

В соответствии с [3] двухшаговый протокол с нулевым разглашением секрета (с нулевыми знаниями) включает следующие шаги:

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

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

Поучив ответ , проверяющий сравнивает и Если , то он делает вывод о подлинности доказывающего.

В работе [4] предложено построения двухшаговых протоколов с использованием механизма меток включаемых в шифруемое сообщение. Наличие таких меток в восстановленном сообщение используется как свидетельство о том, что было известно проверяющему в момент формирования запроса ша первом шаге протокола. Размер меток | | выбирается равным от 80 до 512 бит, благодаря чему вероятность () того, что расшифрование некорректно сформированного запроса даст текст, в котором будет присутствовать метка m является пренебрежимо малой: () = 2?|m|. Использование меток устраняет необходимость дополнительного использования хэш-функций и выполнения вычисления хэш-кода как проверяющим, так и доказывающим [17].

4.2 Протокол на основе использования криптосхемы RSA

Рассмотрим случай построения протокола с нулевым разглашением с использованием алгоритма открытого шифрования RSA [19], в котором открытый ключ формируется в виде пары чисел (n, e). Первое число представляет собой произведение двух сильных простых чисел и генерируемых по случайному закону, а второе число представляет собой 32-битовое значение, которое выбирается таким, чтобы оно было взаимно простым с числом = где НОК ? наименьшее общее кратное ? значение обобщенной функции Эйлера от числаn. Секретный ключ вычисляется по формуле

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

Процедура расшифрования криптограммы C описывается формулой

Корректность процедуры расшифрования легко доказывается с использованием обобщенной теоремы Эйлера, согласно которой для любого числа M, взаимно простого с n имеет место соотношение

Рассмотрим двухпроходный протокол с нулевым разглашением на основе данного алгоритма открытого шифрования при использовании 128-битовой метки m = n mod 2128. В качестве метки берутся 128 младших битов открытого ключа доказывающего. Протокол описывается следующими шагами:

1. Проверяющий генерирует случайное сообщение размером удовлетворяющим условию. Затем он зашифровывает сообщение с присоединенной к нему меткой , т.е. зашифровывает битовую строку по открытому ключу доказывающего (n, e), т.е. по формуле = и направляет доказывающему значение C в качестве своего запроса, на который он ожидает ответ доказывающего.

2. Доказывающий расшифровывает криптограмму по своему личному секретному ключу по формуле = где ? битовая строка, заданная младшими 256 битами расшифрованного значения, и проверяет выполнимость равенства = m. Если = m., то полученное значение доказывающий направляет проверяющему в качестве своего ответа на полученный запрос. В противном случае доказывающий отправляет ответ «Некорректный запрос» [17].

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

В описанном протоколе важным является использование заранее специфицированной метки m, благодаря чему обеспечивается возможность доказывающему удостовериться в том, что отправляемое им значение ответа ? уже известно проверяющему. Тот факт, что оно уже известно проверяющему, означает, что проверяющий не пытается получить подпись к некоторому сообщению, используя механизм слепой подписи [5,6], и не пытается выполнить атаку при адаптивно выбираемом шифртексте (adaptive chosen cipher text attack), описанную в работе [7] или какую-то другую атаку.

4.3 Использование алгоритма открытого шифрования Эль-Гамаля

Рассмотрим реализацию прокола с нулевым разглашением секрета, основанном на использовании алгоритма открытого шифрования Эль-Гамаля [2]. В алгоритме используются открытый ключ вида p, где - большое простое число (размером 1024 бит и более), такое, что разложение числа p - 1 содержит простой делитель разрядностью не менее 160 бит; - примитивный элемент по модулю . Этот способ фактически представляет собой гибридную криптосистему, в которой секретные ключи распределяются в соответствии с протоколом Диффи-Хеллмана [8], а шифрование сообщения выполняется путем модульного умножения сообщения на секретный ключ. Шифрование сообщения , отправляемого владельцу открытого ключа, осуществляется с помощью следующего алгоритма:

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

Вычислить числоp - разовый открытый ключ отправителя

Используя открытый ключ получателя , вычислить разовый общий секретный ключ

Зашифровать сообщение путем умножения сообщения на разовый секретный ключ:

5. Отправить получателю криптограмму в виде пары чисел (R, C).

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

Вычислить разовый общий секретный ключ

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

Расшифровать сообщение путем умножения значения на целое число: =

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

По аналогии с протоколом, предложенным в [4], построим протокол аутентификации с нулевым разглашением на основе алгоритма Эль-Гамаля при использовании 256-битовой метки , в качестве которой берутся младшие 160 бит открытого ключа доказывающего y (т.е. специфицируется значение , который описывается следующим образом:

1. Проверяющий генерирует случайное сообщение M размером |M|, удовлетворяющим условию . Затем он зашифровывает сообщение с присоединенной к нему меткой ??, т.е. зашифровывает битовую строку , по открытому ключу доказывающего y в соответствии с формулой = Gamal_Encr(,y). Затем он направляет доказывающему пару в качестве своего запроса, на который доказывающий должен дать ответ.

2. Доказывающий расшифровывает криптограмму по своему личному секретному ключу где ? битовая строка, заданная младшими 160 битами расшифрованного значения, и проверяет выполнимость равенства. Если то полученное значение доказывающий направляет проверяющему в качестве своего ответа на полученный запрос. В противном случае доказывающий отправляет ответ «Некорректный запрос».

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

4.4 Протокол на основе криптосхемы Рабина

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

Шифрование сообщения выполняется возведением числа в квадрат по модулю

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

Из этих четырех значений вычисляются четыре возможных корня из по модулю :

где



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

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

2. Доказывающий расшифровывает криптограмму по своему секретному ключу путем вычисления четырех значений квадратного корня из : . Каждое из последних значений он представляет в виде ? битовая строка, заданная младшими 128 битами -го корня . Затем он проверяет, выполняется ли равенство mi? = m для одного из четырех значений Если да, то соответствующее значение доказывающий направляет проверяющему в качестве своего ответа на полученный запрос. Если , то доказывающий отправляет ответ «Некорректный запрос».

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



Заключение

алгоритм информационный криптоанализ шифрование

Таким образом, в курсовой работе:

Изучена основная терминология.

Рассмотрены симметричные алгоритмы и алгоритмы с открытым ключом.

Изучена аутентификация пользователей в информационных системах.

Рассмотрены протоколы с нулевым разглашением секрета.

Изучены протоколы на основе алгоритмов открытого шифрования.