Схема фейге фиата шамира

Добавил пользователь Дмитрий К.
Обновлено: 04.10.2024

Базовые конструкции протоколов аутентификации

Идентификатор (англ. acess identifier) - уникальный признак субъекта или объекта доступа.

Идентификация (англ. identification) - присвоение субъектам и объектам доступа идентификатора и (или) сравнение предъявляемого идентификатора с перечнем присвоенных идентификаторов.

Аутентификация (англ. authentication) - проверка принадлежности субъекту доступа предъявленного им идентификатора; подтверждение подлинности.

Заметим, что аутентификация без идентификации невозможна.

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

Аутентификация бывает односторонней (обычно клиент доказывает свою подлинность серверу) и двусторонней (взаимной). Пример односторонней аутентификации – процедура входа пользователя в систему.

Субъект может подтвердить свою подлинность, предъявив один из следующих аутентификаторов:

- нечто, что он знает (пароль, личный идентификационный номер, криптографический ключ и т.п.);

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

- нечто, что есть часть его самого (голос, отпечатки пальцев, образец ДНК и т.п.).

Классификация методов реализации аутентификации

Пароли

С использованием hash-функции

На основе шифрования с открытым ключом

Сервер аутентификации Kerberos

Биометрия

Идентификационные карты и электронные ключи

Парольная аутентификация

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

Одноразовые пароли

Пароли со сроком действия

Бессрочные пароли

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

Главное достоинство парольной аутентификации – простота и привычность. Пароли давно встроены в ОС, СУБД и программные продукты. При правильном использовании пароли могут обеспечить приемлемый для многих организаций уровень безопасности. Тем не менее, по совокупности характеристик их следует признать самым слабым средством проверки подлинности.

Парольная аутентификация имеет массу недостатков:

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

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

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

В Windows NT/2000/XP учетные записи (пользователи и пароли) хранятся в файле «%System Root% \ System32 \ Config \ sam». При работающем ОС пользователь не может выполнять операции чтения/записи с данным файлом (блокируется процессом lsass.exe, завершить который вручную невозможно). Получить доступ к файлу можно, загрузив ОС с другого носителя. Другой вариант заключается в использовании файла «%System Root% \ Repair \ sam». Он доступен для чтения/записи, но, как правило, содержит устаревшие пароли;

В ранних версиях Unix файл с учетными записями «/etc/passwd» был доступен для чтения любым желающим. В современных разновидностях Unix файл с паролями «/etc/shadow» или «etc/secure» доступен только с привилегиями суперпользователя. Другой способ получения доступа к паролям – «обрушение» процесса, обращающегося к файлу с паролями. При этом Unix создает файл «core dump», содержащий дамп памяти (с паролями);

После получения файла с зашифрованными паролями можно воспользоваться многочисленными программами-взломщиками. Одними из самых популярных взломщиков являются: для Windows – L0phtCrack, для Unix – John the Ripper. Время, требуемое для взлома пароля, зависит от его качества. Так, например, взлом пароля для L0phtCrack на компьютере с процессором Xeon 400 МГц при использовании:

1. Цифр и латиницы – 5,5 часов;

2. Всех символов – 480 часов.

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

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

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

Ограничение доступа к файлу с паролями;

Удаление резервных копий файлов с паролями («%System Root% \ Repair \ sam»);

Использование защищенных протоколов обмена ключами (например, основанные на алгоритме обмена ключами Диффи-Хеллмана);

Ограничение числа неудачных попыток входа в систему (это затруднит применение «метода грубой силы»). В Windows 2000 и XP этот параметр устанавливается по пути «Администрирование / Локальная политика безопасности / Политики учетных записей / Политика блокировки учетной записи / Пороговое значение блокировки». Там же («Политики учетных записей») можно настроить срок блокировки учетной записи, минимальную длину пароля, сроки его действия и т.п.;

Управление сроком действия паролей, их периодическая смена, использование сеансовых ключей;

Удаление паролей уволенных или лишенных полномочий пользователей.

Протоколы аутентификации с использованием hash-функций

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

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

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

Протокол аутентификации на основе шифрования с открытым ключом

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

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

Протокол на основе алгоритма RSA

Один из наиболее известных протоколов аутентификации - протокол на основе алгоритма RSA. Протокол состоит из следующих этапов:

Этап 1: Генерация ключей

Этап 2: Аутентификация

Протокол на основе схемы Фейге-Фиата-Шамира

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

'Этап 1. Генерация ключей (выполняет Посредник)

'Этап 2. Аутентификация

Рассмотренный порядок операций, выполненный 1 раз называется аккредитацией. Если первую операцию поменять местами со второй, то А, даже не зная закрытого ключа s, может подобрать такое значение r, которое будет приводить к успешной аккредитации в обоих случаях (b=0 и b=1). Подобрать же такое r, которое будет приводить к успешной аккредитации в обоих случаях одновременно невозможно. Таким образом, если А не знает закрытого ключа s, то вероятность успешной аккредитации (подбора r) равна 1/2. Аккредитация повторятся t раз, пока не будет достигнута требуемая вероятность 1/2^t, чтоА не знает закрытого ключа s.

Протокол на основе схемы Эль-Гамаля

Протокол аутентификации основан на протоколе шифрования Эль-Гамаля. Основные этапы протокола аутентификации:

Этап 1: Генерация ключей

Этап 2: Аутентификация

Протокол на основе схемы Шнорра

Этап 1: Генерация ключей (выполняет A)

Этап 2: Аутентификация

Для обеспечения стойкости протокола в 1989 г. Шнорр рекомендовал использовать p длиной 512 бит, q длиной 140 бит и t = 52.

Сервер аутентификации Kerberos

Kerberos – программный продукт, разработанный в середине 1980-х годов в Массачусетском технологическом институте и претерпевший с тех пор ряд принципиальных изменений. Клиентские компоненты Kerberos присутствуют в большинстве современных ОС.

Kerberos предназначен для решения следующей задачи. Имеется открытая (незащищенная) сеть, в узлах которой сосредоточены субъекты – пользователи, а также клиентские и серверные программные системы. Каждый субъект обладает секретным ключом. Чтобы субъект C мог доказать свою подлинность субъекту S (без этого S не станет обслуживать C), он должен не только назвать себя, но и продемонстрировать знание секретного ключа. C не может просто послать S свой секретный ключ, во-первых, потому, что сеть открыта (доступна для пассивного и активного прослушивания), а, во-вторых, потому, что S не знает (и не должен знать) секретный ключ C. Требуется менее прямолинейный способ демонстрации знания секретного ключа.

Последовательность аутентификации с помощью Kerberos:

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

Идентификация/аутентификация с помощью биометрических данных

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

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

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

Классификация наиболее распространенных биометрических характеристик представлена на рисунке 1.

Недостатки биометрических средств:

- биометрический шаблон сравнивается не с результатом первоначальной обработки характеристик пользователя, а с тем, что пришло к месту сравнения. А, как известно, за время пути может много чего произойти;

- база шаблонов может быть изменена злоумышленником;

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

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

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

- биометрические характеристики являются уникальными идентификаторами, но их нельзя сохранить в секрете.

Идентификационные карты и электронные ключи

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

В настоящее время наиболее распространенными разновидностями карт и ключей являются:

- карты с магнитной полосой;

- контактные смарт-карты и USB-ключи;

- бесконтактные RFID-карты.

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

ISO 7810 — «Идентификационные карты — физические характеристики»;

ISO 7811 — «Идентификационные карты — методы записи»;

ISO 7812 — «Идентификационные карты — система нумерации и процедура регистрации идентификаторов эмитентов» (5 частей);

ISO 7813 — «Идентификационные карты — карты для финансовых транзакций»;

ISO-4909 — «Банковские карты — содержание третьей дорожки магнитной полосы»;

ISO-7816 — «Идентификационные карты — карты с микросхемой с контактами» (10 частей)

Формат записи данных для первой и второй дорожки банковских карт представлен на следующем рисунке 2.

PAN (номер карточного счета, номер платежной карты) обычно представляет собой 16-значный номер карты, напечатанный на лицевой стороне карты.

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

PVKI (номер ключа проверки PIN-кода) представляет собой значение от 1 до 6 и определяет ключ расшифрования PVV.

PVV (значение проверки PIN-кода) и IBM 3624-offset представляют собой зашифрованное значение PIN-кода . В частности, алгоритм VISA PVV представляет собой следующую последовательность операций.

1. Определяется TSP (Transformed Security Parameter – преобразованный параметр безопасности), как последние 12 цифр PAN (за исключением крайней правой цифры) плюс PVKI плюс введенные 4 цифры PIN-кода. Например, PAN = 123456789012344510, PVKI = 110, PIN-код = 909010 -> TSP = 56789012344 1 909010.

2. TSP шифруется с помощью банковского ключа, соответствующего PVKI, по алгоритму тройного DES (DES-EDE2). Например, DES-EDE2 = 0FAB9CDEFFE7DCBA16.

3. Определяется PVV путем сканирования шестнадцатеричной строки DES-EDE2 слева-направо, пока не будет выбрано 4 цифры. Если после первого сканирования будут найдены менее 4 цифр, то при повторном сканировании выбираться будут только шестнадцатеричные цифры, которые конвертируются в цифры путем вычитания из них 10. Например, PVV = 0975 (0, 9, 7, F=5).

CVV (значение проверки подлинности карты) определяется по тому же алгоритму, что и PVV, только шифруемая строка (аналог TSP) формируется из следующих данных: 10 цифр PAN (за исключением крайней правой цифры) плюс срок действия карты (в формате ММГГ) плюс служебные коды (для приведенного выше примера, шифруемая строка – 789012344 1215 20110). Из-за того, что СVV/CVC слабо защищен от клонирования, в настоящее время он практически не используется и вместо него на картах ставятся нули.

LRC (продольный контроль избыточности) предназначен для контроля целостности всей дорожки. Количество единиц в битовом представлении всей дорожки, включая биты символа LRC за исключением четного паритетного бита символа LCR, должно быть четным. Четный паритетный бит символа LCR предназначен для контроля целостности только символа LCR.

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

Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.

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

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

Пещера нулевого знания

Хорошо поясняют доказательство с нулевым знанием Жан-Жак Кискатер и Луи Гиллу с помощью истории о пещере Али-Бабы (см. рисунок). Чтобы пройти сквозь пещеру, необходимо открыть дверь между C и D. Дверь открывается только тогда, когда кто-нибудь произносит волшебные слова. Пусть Пегги знает волшебные слова и хочет доказать это Виктору, не раскрывая самих слов.

Вот как происходит доказательство с нулевым знанием в данном случае:
1. Виктор находится в точке А.
2. Пегги проходит весь путь по пещере до двери либо по проходу C, либо по проходу D. Виктор не видит в какую сторону пошла Пегги. После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.
3. Виктор кричит Пегги, чтобы она вышла из пещеры либо из левого прохода, либо из правого прохода.
4. Пегги, при необходимости используя волшебные слова, чтобы отпереть дверь, выходит из пещеры из того прохода, из которого просил ее выйти Виктор.
5. Пегги и Виктор повторяют этапы 1-4 некоторое количество раз.

В случае когда Пегги не знает секрета, то она не сможет обмануть Виктора, если этапы доказательства (аккредитации) повторяются несколько раз подряд. Так как она может выйти только из того прохода, в который она зашла, в каждом раунде протокола вероятность угадать, с какой стороны Виктор попросит ее выйти, составляет 50 %. Соответственно, ее вероятность обмануть Виктора также равна 50 %. Однако, вероятность обмануть его в двух раундах составит уже 25 %, а в n раундах у нее есть только один шанс из 2^n. Виктор может уверенно предположить, что если все n (n=10-20) раундов доказательства Пегги правильны, то она действительно знает тайные слова, открывающие дверь между точками С и D.

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

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

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

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

Предварительно, перед самим доказательством доверенный центр T выбирает и публикует модуль достаточно большого числа n = p*q, разложить на множители которое трудно. При этом p, q – простые числа и держатся в секрете. Каждый пользователь A выбирает секретное s из интервала (1, n−1) взаимно простое с n. Затем вычисляется открытый ключ v = s^2 (mod n).

Полученное v регистрируется центром доверия в качестве открытого ключа пользователя A, а значение s является секретом A. Именно знание этого секрета s необходимо доказать A стороне В без его разглашение за t раундов. Каждая аккредитация состоит из следующих этапов:
1. А выбирает случайное r из интервала (1, n−1) и отсылает x = r^2 (mod n) стороне B.
2. B случайно выбирает бит e (0 или 1) и отсылает его A.
3. А вычисляет y = r*s^e (mod n) и отправляет его обратно к B.
4. Сторона B проверяет равенство y^2 ≡ x*v^e (mod n). Если оно верно, то происходит переход к следующему раунду протокола, иначе доказательство не принимается.

Выбор е из множества предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B, выбирает случайное r и отсылает x = r^2 / v, тогда если е=0, то А удачно возвращает B y = r, в случае же е=1, А не сможет правильно ответить, т.к. не знает s, а извлечь квадратный корень из v по модулю n достаточно сложно.

Вероятность того, что пользователь А не знает секрета s, но убеждает в обратном проверяющего B будет оцениваться вероятностью равной p = =2^(–t), где t – число аккредитаций. Для достижения высокой достоверности его выбирают достаточно большим (t = 20 − 40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.

Для того чтобы этот протокол корректно выполнялся, сторона А никогда не должна повторно использовать значение x. Если бы А поступил таким образом, а B во время другого цикла отправил бы А на шаге 2 другой случайный бит r, то B бы имел оба ответа А. После этого B может вычислить значение s, и ему будет известен секретный ключ Алисы.

Криптографические протоколы

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

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

Учебное пособие по протоколам многосторонних защищенных вычислений. Материалы этого учебного пособия помогут освоить третий раздел курса

Репозиторий протоколов безопасности, содержит как описание самих протоколов, так и известные атаки на них.

1) Jupiter Notebooks для языка Python. Для самостоятельного приобретения навыков применения блочных шифров. Проверка свойства гомоморфности для симметричных и асимметричных шифров.

2) Примерное содержание практических занятий.

3) Пример реализации алгоритма кодирования изображений для визуальной криптографии (автор - Robert Donovan, LessonStudio, 2014)

Вопросы для контрольных опросов

Раздел 1. Протоколы обмена ключами (5 баллов)

1. Понятие протокола. Назначение протоколов. Участники. Протоколы с посредником. Протоколы с арбитром.

2. Классификация протоколов.

3. Криптографические примитивы, используемые в протоколах.

4. Обмен ключами средствами симметричной криптографии.

5. Обмен ключами средствами криптографии с открытым ключом.

6. Свойства безопасности протоколов.

7. Основные атаки на протоколы.

8. Алгоритм Диффи-Хэлмана.

9. Трехпроходный протокол Шамира.

10. Реализация протокола EKE с помощью RSA .

11. Реализация протокола EKE с помощью Эль-Гамаля.

12. Реализация протокола EKE с помощью Диффи-Хэллмана.

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

16. Генерация ключа в зашумленной среде.

17. Кодовое зашумление. Алгоритмы кодирования и декодирования.

18. Протоколы предварительной передачи ключевого материала.

Раздел 2. Протоколы идентификации/аутентификации (5 баллов)

1. Отличия слабой и сильной аутентификации.

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

3. Атака по словарю и привязка.

4. Аутентификация средствами криптографии с открытым ключом.

5. Протоколы SKID .

7. Протокол Wide - Mouth Frog .

8. Протокол Yahalom .

9. Протокол Нидхема-Шредера.

10. Протокол Отвея-Рииса.

11. Протокол Kerberos .

12. Протокол Ньюмана-Стабблбайна.

13. Протокол DASS .

14. Протокол Деннинга-Сакко.

15. Протокол Ву-Лама.

16. Схемы идентификации Фейге-Фиата-Шамира.

17. Упрощенная схема идентификации Фейге-Фиата-Шамира.

18. Схема идентификации Охта-Окамото.

19. Схема Гиллу-Кискате.

20. Схема Шнорра.

21. Схема вручения обязательства. Свойства связности и скрытности

22. Схема вручения нечеткого обязательства Джуелса-Воттенберга. Биометрическая аутентификация.

Раздел 3. Протоколы многосторонних вычислений (5 баллов)

1. Пороговые, совершенные, идеальные схемы разделения секрета

2. Разделение секрета без помощи Трента.

3. Разделение секрета без раскрытия долей.

4. Проверяемые схемы разделения секрета.

5. Визуальная криптография.

6. Схемы разделения секрета на основе помехоустойчивых кодов (минимальные коды).

7. Тайное голосование.

8. Протокол установления соответствия.

9. Схема протокола вычисления арифметических выражений

10. Схема забывчивой передачи.

11. Протоколы вычисления на основе помехоустойчивых кодов.

2. Критерии оценки

Студент случайно выбирает 2 вопроса по теме, в рамках которой проводится устный контрольный опрос. Правильный ответ оценивается в 2 балла. Правильный ответ на дополнительный вопрос по теме выбранных вопросов оценивается в один балл.

Методические материалы для подготовки к опросам

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

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

Темы докладов для индивидуальных заданий

Раздел 1. Протоколы обмена ключами (5 баллов)

1. Атаки на протоколы обмена ключами.

2. Парадокс дней рождений.

3. Конструкции криптографических хэш-функций.

4. Атаки на хэш-функции.

5. Схема NMAC/HMAC.

6. Обоснование стойкости HMAC.

7. Схема получения ключа HKDF (extract-and-expand ).

8. Выработка ключей в протоколах блокчейн.

Раздел 2. Протоколы идентификации/аутентификации (5 баллов)

1. Атаки на протоколы аутентификации.

2. Атаки на протокол Нидхема-Шредера.

3. Атаки на протокол Отвея-Рииса.

4. Аутентификация участников и данных в протоколах блокчейн.

Раздел 3. Протоколы многосторонних вычислений (5 баллов)

1. Протоколы поиска данных в зашифрованных данных, SSE ( Searchable Symmetric Encryption ).

2. Поиск в зашифрованных данных по ключевым словам, PEKS ( Public Key Encryption with Keyword Search ).

2. Критерии оценки

Доклад оценивается по пятибалльной шкале:

5 баллов – студент приводит примеры, отвечает на вопросы по теме

4 балла – студент отвечает на вопросы по теме, но затрудняется привести пример

3 балла – студент затрудняется привести примеры, не уверенно отвечает на вопросы

2 балла – студент затрудняется привести примеры, не может ответить на дополнительные вопросы

1 балл – студент не разобрался в теме вопроса, студент затрудняется привести примеры, не уверенно отвечает на вопросы

0 – отсутствие доклада.

Ресурсы по темам докладов

Текст содержит подробное описание схем NMAC/HMAC и содержится обоснование стойкости этих схем

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

Лабораторные работы

Лабораторная работа №1 (раздел 1, 10 баллов)

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

Перечень хэш-функций: Blake2b, Blake2s, DSTU7564, GOST3411, GOST3411_2012, GOST3411_2012_256, GOST3411_2012_512, Keccak, MD2, MD4, MD5, RipeMD128, RipeMD160, RipeMD256, RipeMD320, Sha1, Sha224, Sha256, Sha384, SHA3, Sha512, Sha512t, Shake, Skein, SM3, Tiger, Whirlpool.

Перечень симметричных криптографических алгоритмов: AES, Blowfish, 3DES, GOST28147, IDEA, ISAAK, RC4, RC6, Salsa20, DSTU7624, ChaCha

Перечень асимметричных криптографических алгоритмов: RSA, Эль-Гамаль, Мак-Элис.

Лабораторная работа №2 (раздел 2, 10 баллов)

Реализация протокола Штерна. Матрица H размера (не менее 100 строк и 200 столбцов) каждым студентом выбирается самостоятельно (случайно), односторонняя функция выбирается из числа хэш-функций из первой лабораторной работы, секрет должен формироваться на основе Фамилии, Имени и Отчества студента по следующему правилу: s = h (Фамилия||Имя||Отчество), где h – криптографическая хэш-функция из первой лабораторной работы.

Лабораторная работа №3 (раздел 3, 10 баллов)

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

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

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

Содержание

Описание протоколa

A доказывает B знание s в течение t раундов. Раунд называют также аккредитацией. Каждая аккредитация состоит из 3х этапов.

Предварительные действия

Доверенный центр Т выбирает и публикует модуль n = p * q , где p, q -простые и держатся в секрете.
Каждый претендент A выбирает sвзаимно-простое с n, где . Затем вычисляется v = s 2 (mod n) . V регистрируется T в качестве открытого ключаA

Основные действия

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

А выбирает случайное r , такое, что и отсылает x = r 2 (mod n) стороне B (доказательство)
B случайно выбирает бит e (e=0 или е=1) и отсылает его A (вызов)
А вычисляет у и отправляет его обратно к B. Если e=0, то y = r , иначе y = r * s(mod n) (ответ)
Если y=0, то B отвергает доказательство или, другими словами, А не удалось доказать знание s. В противном случае, сторона B проверяет, действительно ли y 2 = x * ve (mod n) и, если это так, то происходит переход к следующему раунду протокола.

Выбор е из множества <0,1>предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B. В этом случае А, может отреагировать только на конкретное значение e. Например, если А знает, что получит е=0, то А следует действовать строго по иниструкции и В примет ответ. В случаи если А знает, что получит е=1, то А выбирает случайное r и отсылает x = r 2 / v на сторону В, в результате получаем нам нужное y = r . Проблема заключается в том, что А изначально не знает какое e он получит и поэтому не может со 100% вероятностью выслать на сторону В нужные для обмана r и х ( x = r 2 при e=0 и x = r 2 / v при e=1). Поэтому вероятность обмана в одном раунде составляет 50%. Чтобы снизить вероятность жульничества (она равна 1 / 2 t ) ) t выбирают достаточно большим (t=20, t=40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.

Пример

Пусть доверенный центр выбрал простые p=683 и q=811, тогда n=683*811=553913. А выбирает s=43215.

Откуда v = 43215 2 (mod 553913) = 1867536225(mod 553913) = 295502

A выбирает r=38177 и считает x = 38177 2 (mod 553913) = 1457483329(mod 553913) = 138226
Если B отправил e=0, то A возвращает y=38177. Иначе, A возвращает y = 38177 * 43215(mod 553913) = 1649819055(mod 553913) = 266141
Проверка B:

Если e было равно 0, то y 2 = 38177 2 (mod 553913) = 1457483329 = 138266 Подтверждено. Иначе, y 2 = 266141 2 (mod 553913) = 70831031881(mod 553913) = 514832 и x * v = 138226 * 295502(mod 553913) = 40846059452(mod 553913) = 514832 Подтверждено.

Преддипломная практика Схема аутентификации Фейге-Фиата-Шамира Выполнил: Студент 6 курса факультета КНиИТМалышев Александр ЮрьевичНаучный руководитель:Старший. - презентация

Презентация на тему: " Преддипломная практика Схема аутентификации Фейге-Фиата-Шамира Выполнил: Студент 6 курса факультета КНиИТМалышев Александр ЮрьевичНаучный руководитель:Старший." — Транскрипт:

1 Преддипломная практика Схема аутентификации Фейге-Фиата-Шамира Выполнил: Студент 6 курса факультета КНиИТМалышев Александр ЮрьевичНаучный руководитель:Старший преподаватель В. Е. Новиков

2 Определение. Натуральное число р называется простым, если р > 1 и р не имеет положительных делителей, отличных от 1 и р. Определение. Целые числа а и b называются сравнимыми по модулю m, если разность а – b делится на m, т.е. если m | a – b. У отношения сравнимости выполняются свойства: Рефлексивностьa а (mod m). Симметричностьa b (mod m), то b a (mod m). Транзитивностьa b (mod m), b c (mod m), то a c (mod m). 2

3 3 Определение. Односторонняя (однонаправленная) функция – это функция f осуществляющая отображение X->Y, где X и Y – произвольные множества, и удовлетворяющая следующим условиям: Для каждого x из области определения функции f(x) легко вычислить y = f(x). Задача нахождения прообраза x = f -1 (y) для произвольного y, принадлежащего области значений функции f(x), является вычислительно сложной задачей.

4 Задача аутентификации 4 Свойства для обрабатываемого массива данных: Подлинность – он пришел к потребителю именно таким, каким был создан источником и не претерпел на своем жизненном пути несанкционированных изменений Авторство – он был создан именно тем источником, каким предполагает потребитель

5 Клиентская сторона выбирает некоторое случайное число r, r

6 Стандарт симметричного шифрования ГОСТ Раунд алгоритма ГОСТ [2].

7 Стандарт вычисления хеш-функции ГОСТ Р Общая схема хэширования по ГОСТ Р [4]

8 Программа Share File 8 Окно регистрации нового пользователя Окно приветствия

9 Программа Share File 9 Главное окно программы

10 Программа Share File 10 Главное окно программы, в котором выделена папка

11 Программа Share File 11 Окно создания папкиВыдача прав пользователю

12 Программа Share File 12 Окно демонстрирующее файлы в папке

13 Программа Share File 13 Окно демонстрирующее файлы в папке

14 Программа Share File 14 Главное окно программы сервера

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

Протокол Фейга — Фиата — Шамира

Протокол Фейга — Фиата — Шамира — протокол идентификации с нулевым разглашением, обобщение более раннего протокола Фиата-Шамира. В отличие от предшествующих ему моделей с нулевым разглашением, протокол позволяет одному участнику (доказывающему A) доказать другому участнику (проверяющему B), что он обладает секретной информацией, не раскрывая ни единого бита этой информации [1] . Протокол не требует длительных вычислительных операций для имплементации (менее 5% числа вычислительных операций, требуемых RSA) и поэтому хорошо подходит для устройств с маломощными процессорами (например, с восьмиразрядными микропроцессорами) [2] .

Безопасность протокола основывается на сложности вычисления квадратного корня по модулю достаточно большого числа n, факторизация которого неизвестна [2] [3] .

Благодаря своей простоте, безопасности и скорости реализации, схема, разработанная Уриэлем Фейге (англ. Uriel Feige ), Амосом Фиатом (англ. Amos Fiat ) и Ади Шамиром (англ. Adi Shamir ), идеально подходит для таких устройств как смарт-карты, персональные компьютеры, документы идентификации личности [1] . 9 июля 1986 года авторы подали заявку на получение патента США. Ведомство по патентам и товарным знакам США в течение полугода должно было определиться с решением о вынесении приказа об устранении режима секретности.

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

К этому моменту Фейге, Фиат и Шамир уже успели выступить с многочисленными докладами в университетах Израиля, Европы и США и подали заявку на конференцию Ассоциации вычислительной техники, которая должна была состояться в Нью-Йорке в мае 1987 года.

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

После этого многие организации, такие как Лаборатории Белла и The New York Times, быстро подключились к решению возникшей проблемы. Наибольший вклад был внесен Агентством Национальной Безопасности (АНБ), которому изначально было неизвестно об изданном приказе. После того, как АНБ о нём сообщили, в течение двух суток приказ был аннулирован [4] [5] .

Шамир выступил на конференции Ассоциации вычислительной техники 26 мая [6] . А АНБ, как и ожидалось, осталось "без комментариев".

Схемы идентификации

Схема цифровой подписи и проверки подлинности разработана Амосом Фиатом ( Amos Fiat) и Ади Шамиром (Adi Shamir), Уриелем Фейге (Uriel Feige). Фиат и Шамир модифицировали алгоритм, превратив его в доказательство подлинности с нулевым знанием .

Упрощенная схема идентификации

Перед выдачей любых закрытых ключей арбитр выбирает случайный модуль , n, который является произведением двух больших простых чисел. В реальной жизни длина n должна быть не меньше 512 битов и лучше как можно ближе к 1024 битам. n может общим для группы контролеров. Для генерации открытого и закрытого ключей П доверенный арбитр выбирает число v, являющееся квадратичным остатком mod n.

Т.е. выбирается v так, чтобы уравнение x 2 ≡ v (mod n) имело решение, и существовало v -1 mod n.. Это v и будет открытым ключом П. Затем вычисляется наименьшее s, для которого

s ≡ sqrt (v -1 ) (mod n). Это будет закрытый ключ П.

Используется следующий протокол идентификации.

(1) П выбирает случайное r, меньшее n.

Затем он вычисляет x =-r 2 mod n и посылает x В.

(2) В посылает П случайный бит b.

(3) Если b = 0, то П посылает В r.

Если b = 1, то П посылает В y = r*s mod n.

(4)Если b = 0, В проверяет, что x = -r 2 mod n, убеждаясь, что П знает значение sqrt(x).

Если b = 1, В проверяет, что x = y 2 *v mod n, убеждаясь, что П знает значение sqrt(v -1 ).

Это один этап протокола, называемый аккредитацией .

П и В повторяют этот протокол t раз, пока В не убедится, что П знает s. Это протокол "разрезать и выбрать".

Если П не знает s, он может подобрать r так, что сможет обмануть В, если он пошлет 0, или он может подобрать r так, что он сможет обмануть В, если он пошлет ему 1 . Он не может сделать одновременно и то, и другое

Вероятность обмана В один раз, равна 50 процентам. Вероятность обмана t раз, равна 1/2 t .

В может попробовать вскрыть протокол, выдавая себя за П. Он может начать выполнение протокола с другим пользователем. Чтобы этот протокол работал, П никогда не должна использовать r повторно. В противном случае, если В на шаге (2) пошлет П другой случайный бит, то он получит оба ответа П . Тогда даже по одному из них он сможет вычислить s, и для П все закончится.

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

ключей П сначала выбирает k различных чисел: v 1, v 2, . . . v k, где каждое v i является квадратичным остатком mod n, т.е. v i выбираются так, чтобы x 2 ≡ v i (mod n) имело ре- шение, и существовало v i -1 mod n. Строка, v 1, v 2, . . . v k, служит открытым ключом. Затем вычисляются наименьшие s i, для которых s i ≡ sqrt (v i -1 ) (mod n). Строка s 1, s 2, . . . s k, служит закрытым ключом.

Выполняется следующий протокол:

(1) П выбирает случайное r, меньшее n. Затем вычисляется x = -r 2 mod n и посылает x В.

(2) В посылает П строку из k случайных битов: b 1 , b 2 , . . . b k .

(3) П вычисляет y = r *(s 1 b1 *s 2 b2 * …*s k bk )mod n. (Он перемножает вместе значения s i , соответствующие b i=1. Если первым битом В будет 1, то s 1 войдет в произведение, а если первым битом будет

0, то нет, и т.д.) и посылает В.

(4) В проверяет, что x = y 2 *(v 1 b1 *v 2 b2 *v k bk ) mod n. (Он перемножает вместе значения v i , основываясь на случайной двоичной строке. Если его первым битом является 1, то v 1 войдет в произведение, а если первым битом будет 0, то нет, и т.д.) П и В повторяют этот протокол t раз, пока В не убедится, что П знает s 1 , s 2 , . . . s k . Вероятность, что П удастся обмануть В t раз, равна 1/2 kt

. Авторы рекомендуют использовать вероят-ность мошенничества 1/2 20 и предлагают значения k = 5 и t = 4. Если у вас склонность к мании преследования, увеличьте эти значения.

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

имя, адрес, номер социального страхования, размер головного убора и другая личная информация .

Используем однонаправленную хэш-функцию H(x) для вычисле- ния H(I, j), где j - небольшое число, добавленное к I. Найдем набор j, для которых H(I,j) - это квадратичный остаток по модулю n.

Эти значения H(I, j) становятся v 1 , v 2 , . . . v k (j не обязаны быть квадратичными остатками).

Открытым ключом П служит I и перечень j. П посылает I и перечень j В перед шагом (1) протокола (или В загружает эти значения с какой-то открытой доски объявлений), и В генерирует v 1 , v 2 , . . . v k из H(I,j).

Теперь, после того, как В успешно завершит протокол с П, он будет убежден, что Т, которому известно разложение модуля на множители, сертифицировал связь между I и П, выдав П квадратные корни из v i , полученные из I.

Фейге, Фиат и Шамир добавили, что для неидеальных хэш- функций можно посоветовать рандомизировать I, добавляя к нему длинную случайную строку R. Эта строка выбирается арбитром и открывается В вместе с I. В типичных реализациях k должно быть от 1 до 18. Большие значения k могут уменьшить время и трудности связи, уменьшая количество этапов. Длина n должна быть не меньше 512 битов. Если каждый пользователь выберет свое собственное n и опубликует его в файле открытых ключей, то можно обойтись и без арбитра. Однако такой RSA-подобный вариант делает схему заметно менее удобной. Превращение этой схемы идентификации в схему подписи - это вопрос превращения В в хэш-функциию. Главным преимуществом схемы цифровой подписи Fiat-Shamir по сравнению с RSA является ее скорость. Улучшенная схема подписи Fiat-Shamir - выбор v 1 , v 2 , . . . v k так, чтобы они были первыми k простыми числами. То есть v1= 1, v2= 3, v 3= 5, и т.д. Это открытый ключ. Закрытым ключом, s 1 , s 2 , . . . s k , служат случайные квадратные корни, определяемые как

si = sqrt (vi -1 ) (mod n). В этой версии у каждого участника должен

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

Схема идентификации Ohta-Okamoto - является вариантом схемы идентификации Feige-Fiat-Shamir, его безопасность основана на трудности разложения на множители. Схема идентификации Guillou-Quisquater.

Несколько подписей. Что если несколько человек захотят подписать один и тот же документ? Проще всего, чтобы они подписали его порознь, но рассматриваемая схема подписи делает это лучше. Пусть А и Б подписывают документ, а К проверяет подписи, но в процесс подписания может быть вовлечено произвольное количество людей . Как и раньше, А и Б обладают уникальными значениями J и B: (JA,BA) и (JB,BB). Значения n и v являются общими для всей системы.

(1)А выбирает случайное целое r А , находящееся в диапазоне от 1 до n-1, вычисляет T А = r А v mod n и посылает T А Б.

(2) Б выбирает случайное целое r В , находящееся в диапазоне от 1 до n-1 и вычисляет T В = r В v mod n и посылает T В А.

(3) А и Б, каждый вычисляет T = (T А *T В ) mod n.

(5) А вычисляет D A = r A B A d mod n и посылает D A Б.

(6) Б вычисляет D B = r B B B d mod n и посылает D B А.

(7) А и Б, каждый вычисляет D = D A D B mod n. Подпись состоит из

(8) К вычисляет J = J A J B mod n.

(9) К вычисляет T’ = D v J d mod n. Затем она вычисляет d' = H(M,T'). Если d ≡ d', то множественная подпись действительна..

a q ≡ 1 (mod p). Все эти числа могут быть свободно опубликованы и использоваться группой пользователей . Для генерации конкретной пары ключей выбирается случайное число, меньшее q.

Оно служит закрытым ключом, s. Затем вычисляется открытый ключ v = a -s mod p.

Протокол проверки подлинности

(1)П выбирает случайное число r, меньшее q, и вычисляет

x = a r mod p . Эти вычисления являются предварительными и могут быть выполнены задолго до появления В .

(2) П посылает x В.

(3) В посылает П случайное число e, из диапазона от 0 до 2 t-1 . (Что такое t - позже.)

(4)П вычисляет y = (r + se) mod q и посылает y В.

(5)В проверяет, что x = a y v e mod p.

Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2 t . Шнорр советует использовать p около 512 битов, q - около 140 битов и t - 72.

Читайте также: