Бросание "честной"монеты с помощью целых чисел Блюма - раздел Компьютеры, Схемы идентификации В Протоколе Бросания Монеты Можно Использовать Челые Числа Блюма .
(...
В протоколе бросания монеты можно использовать челые числа Блюма .
(1) Алиса генерирует целое число Блюма п, случайное х, взаимно простое с п, х0 = х2 mod пмх= х02 mod п. Она посылает Бобу и и хь
(2) Боб угадывает, четным или нечетным является х0.
(3) Алиса посылает х Бобу.
(4) Боб проверяет, что и является целым числом Блюма (Алиса нужно передать Бобу множители и и доказательства того, что они являются простыми, или выполнить некоторый протокол с нулевым знанием, убе ведающий Боба, что п - это целое число Блюма), и что х0 = х2 mod п и х, = х02 mod п. Если все проверки выполняются, и Боб угадал правильно, он выигрывает бросок.
Это важно, чтобы п было числом Блюма. Иначе Алиса сможет найти такое х'0, что х'02 mod п = х02 mod n=xu где х'0также является квадратичным остатком. Если бы х0 был четным, а х'0 - нечетным (или наоборот), Алиса могла бы мошенничать.
23.8 Однонаправленные сумматоры
Существует простая функция однонаправленного сумматоры [116] (см. раздел 4.12.):
А(х„ у) = х,У mod n
Числа п (являющееся произведением двух простых чисел) и х0 должны быть заранее согласованы. Тогда суммированием уъу2и у3 будет
((x/q modnY2 тойп)Уз modn
Это вычисление не зависит от порядка уъу2иу3.
23.9 Раскрытие секретов "все или ничего"
Этот протокол позволяет нескольким сторонам (для работы протокола нужно не меньше двух участников) покупать различные секреты у одного продавца (см. раздел 4.13) [1374, 1175]. Начнем с определения. Возьмем две строки битов, х и у. Фиксированным битовым индексом (fixed bit index, FBI)x и у называется последовательность номеров совпадающих битов этих строк.
Например:
х= 110101001011
у= 101010000110
FBI(je,j;) = {1, 4, 5, 11}
(Мы читаем биты справа налево, считая нулевым крайний правый бит .)
Теперь вот как выглядит протокол. Алиса будет продавцом. Боб и Кэрол - покупателями. У Алисы есть к п-битовых секретов: Sh S2, . . . Sk. Боб хочет купить секрет Sb, Кэрол - секрет Sc.
(1) Алиса генерирует пару "открытый ключ/закрытый ключ"и сообщает Бобу (но не Кэрол) открытый ключ. Она генерирует другую пару "открытый ключ/закрытый ключ"и сообщает Кэрол (но не Бобу) открытый ключ.
(2) Боб генерирует к и-битовых случайных чисел, Въ В2, . . . Вк, и сообщает их Кэрол. Кэрол генерирует к 71-битовых случайных чисел, Ch С2, . . . Ск, и сообщает их Бобу.
(3) Боб шифрует Сь (напомним, он хочет купить секрет Sb) открытым ключом, полученным от Алисы. Он вычисляет FBI для Съ и только что зашифрованного результата. Он посылает этот FBI Кэрол.
Кэрол шифрует Вс (напомним, она хочет купить секрет Sc) открытым ключом, полученным от Алисы. Она вычисляет FBI для Вс и только что зашифрованного результата. Она посылает этот FBI Бобу.
(4) Боб берет каждое из й-битовых чисел Ви В2, . . . Вки заменяет каждый бит, номера которого нет в FBI,
полученном от Кэрол, его дополнением. Он посылает этот новый список й-битовых чисел В, В'2, . . . В'к
Алисе.
Кэрол берет каждое из и-битовых чисел Сь С2, . . . Ск и заменяет каждый бит, номера которого нет в FBI, полученном от Боба, его дополнением. Она посылает этот новый список й-битовых чисел С, С2, . . . С Алисе.
(5) Алиса расшифровывает все С, закрытым ключом Боба, получая к й-битовых чисел С', С"2, . . . С"к. Она
вычисляет S, © С", для i = 1, . . . к, и посылает результаты Бобу.
Алиса расшифровывает все В', закрытым ключом Кэрол, получая к й-битовых чисел В"и В"2, . . . В"к. Она вычисляет St © В", для i = 1, . . . к, и посылает результаты Кэрол.
(6) Боб вычисляет Sb, выполняя XOR Съ и й-го числа, полученного от Алисы.
Кэрол вычисляет Sc, выполняя XOR Вс и с-го числа, полученного от Алисы..
Все так сложно. Поясним эти долгие действия на примере .
У Алисы есть для продажи восемь 12-битовых секретов : & = 1990, S2 = 471, S3 = 3860, S4 = 1487, S5 = 2235, S6 = 3751, S1 = 2546 и S8 = 4043. Боб хочет купить S7, а Кэрол - S2.
(1) Алиса использует алгоритм RSA. В диалоге с Бобом она использует следующую пару ключей : и = 7387, е = 5145 и d = 777, а в диалоге с Кэрол - л = 2747, е = 1421 и а? = 2261. Она сообщает Бобу и Кэрол их открытые ключи.
(2) Боб генерирует восемь 12-битовых чисел, Вг= 743, В2= 1988, S3= 4001, Вл= 2942, £5= 3421, £6= 2210, £7=2306 и S8= 222, и сообщает их Кэрол. Кэрол генерирует восемь 12-битовых чисел, d= 1708, С2 = 711, С3= 1969, С4 = 3112, С5 = 4014, С6 = 2308, С7 = 2212 и С8 = 222, и сообщает их Бобу.
(3) Боб хочет купить S7, поэтому он открытым ключом, выданным Алисой, шифрует С7. 22125145 mod 7387 = 5928
Теперь:
2212 = 0100010100100
5928 = 1011100101000
Следовательно, FBI этих двух чисел равен {0, 1, 4, 5, 6}. Он посылает его Кэрол.
Кэрол хочет купить S2, поэтому она открытым ключом, выданным Алисой, шифрует В2 и вычисляет FBI В2 и результата шифрования. Она посылает Бобу {0, 1, 2, 6, 9, 10}.
(4) Боб берет ВъВ2, . . .В%и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 2, 6, 9, 10} его
дополнением. Например:
В2= 111111000100 = 1988
В'2 = 011001111100 = 1660
Он посылает В, В'2, . . . В Алисе.
Кэрол берет Сь С2, . . . С8 и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 4, 5, 6} его дополнением. Например:
С7 = 0100010100100 = 2212
С"7 = 1011100101000 = 5928
Она посылает С, С2, . . . С Алисе.
(5) Алиса расшифровывает все С, закрытым ключом Боба и выполняет XOR результатов с S,. Например, для
i = 7:
5928777 mod 7387 = 2212; 2546 © 2212 = 342
Она посылает результат Бобу.
Алиса расшифровывает все В', закрытым ключом Кэрол и выполняет XOR результатов с S,. Например,
для i = 2:
16602261 (mod 2747) = 1988; 471 © 1988 = 1555 Она посылает результат Кэрол.
(6) Боб вычисляет S7, выполняя XOR С7 и седьмого числа, полученного им от Алисы:
2212 © 342=2546
Кэрол вычисляет S2, выполняя XOR В2 и второго числа, полученного ей от Алисы.
1988 ©1555 = 471
Протокол работает для любого количества покупателей . Если Боб, Кэрол и Дэйв хотят купить секреты, Алиса выдает каждому покупателю два открытых ключа, по одному на каждого другого покупателя . Каждый покупатель получает набор чисел от каждого другого покупателя . Затем они выполняют протокол с Алисой для каждого из своих наборов номеров и выполняют XOR всех полученных от Алисы результатов, получая свои секр е-ты. Более подробно это описано в [1374, 1175].
К сожалению, пара нечестных участников могут смошенничать. Алиса и Кэрол, действуя на пару, могут легко понять, какой секрет получил Боб: если они знают FBI Cb и алгоритм шифрования Боба, они могут подыскать такое Ъ, что у Сь будет правильный FBI. А Боб и Кэрол, действуя вместе, могут легко заполучить все секреты Алисы.
Если вы считаете, что участники честны, можно использовать протокол попроще [389].
(1) Алиса шифрует все секреты RSA и посылает их Бобу: С, = 5*,е mod n
(2) Боб выбирает свой секрет Сь, генерирует случайное число г и посылает Алисе. С = Cbre mod n
(3) Алиса посылает БобуЛ P' =&mod n
(4) Боб вычисляет Р'
Sb-PYl mod n
Если участники могут жульничать, Боб может доказать с нулевым знанием, что он знает некоторое г, такое что С = Cbre mod п, и хранить в Ъ секрете, пока Алиса не передаст ему на этапе (3) Р' [246).
23.10 Честные и отказоустойчивые криптосистемы
Все темы данного раздела:
FEIGE-FIAT-SHAMIR
Схема цифровой подписи и проверки подлинности, разработанная Амосом Фиатом (Amos Fiat) и Ади Ша-миром (Adi Shamir), рассматривается в [566, 567]. Уриель Фейге (Uriel Feige), Фиат и Шамир модифициро
Улучшения
В протокол можно встроить идентификационные данные. Пусть / - это двоичная строка, представляющая идентификатор Пегги: имя, адрес, номер социального страхования, размер головного убора, любимый сор
GUILLOU-QUISQUATER
Feige-Fiat-Shamir был первым практическим протоколом идентификации. Он минимизировал вычисления, увеличивая число итераций и аккредитаций на итерацию. Для ряда реализаций, например, для интеллектуа
Несколько подписей
Что если несколько человек захотят подписать один и тот же документ ? Проще всего, чтобы они подписали его порознь, но рассматриваемая схема подписи делает это лучше . Пусть Алиса и Боб подписывают
Протокол проверки подлинности
(1) Пегги выбирает случайное число г, меньшее q, и вычисляет х = d mod/;. Эти вычисления являются предварительными и могут быть выполнены задолго до появления Виктора .
Протокол цифровой подписи
Алгоритм Schnorr также можно использовать и в качестве протокола цифровой подписи сообщения М. Пара ключей используется та же самая, но добавляется однонаправленная хэш-функция ЩМ).
Патенты
Schnorr запатентован в Соединенных Штатах [1398] и многих других странах. В 1993 году РКР приобрело обще мировые права на этот патент (см. раздел 25.5). Срок действия патента США истекает 19 феврал
DIFFIE-HELLMAN
Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году [496]. Его безопасность опирается на трудность вычисления дискретных логарифмов в конечном поле (в сравнении с
Расширенный Diffie-Hellman
Diffie-Hellman также работает в коммутативных кольцах [1253]. 3. Шмули (Z. Shmuley) и Кевин МакКерли (Kevin McCurley) изучили вариант алгоритма, в котором модуль является составным числом [1441, 10
Обмен ключом без обмена ключом
Если у вас сообщество пользователей, каждый может опубликовать открытый ключ , Х= gx mod и, в общей базе данных. Если Алиса захочет установить связь с Бобом, ей понадобится только
Патенты
Алгоритм обмена ключами Diffie-Hellman запатентован в Соединенных Штатах [718] и Канаде [719]. Группа, называющаяся Public Key Partners (PKP, Партнеры по открытым ключам), получила вместе с другим
Базовый протокол ЕКЕ
Алиса и Боб (два пользователя, клиент и сервер, или кто угодно) имеют общий пароль Р. Используя следующий протокол, они могут проверить подлинность друг друга и генерировать общий сеансовый
Реализация ЕКЕ с помощью ElGamal
Реализация ЕКЕ на базе алгоритма ElGamal проста, можно даже упростить основной протокол. Используя обозначения из раздела 19.6, g ир служат частями открытого ключа, общими для всех пользоват
Реализация ЕКЕ с помощью Diffte-Hellman
При использовании протокола Diffie-Hellman К генерируется автоматически. Окончательный протокол еще проще. Значения g и п определяются для всех пользователей сети.
(1)
Усиление ЕКЕ
Белловин (Bellovin) и Мерритт (Merritt) предложили улучшение запросно-ответной части алгоритма, которое позволяет избежать возможного вскрытия при обнаружении криптоаналитиком ста рого значения
Расширенный ЕКЕ
Протокол ЕКЕ страдает одним серьезным недостатком: он требует, чтобы обе стороны знали Р. В большинстве систем авторизации доступа хранятся значения однонаправленной хэш-функции паролей пол
Применения ЕКЕ
Белловин и Мерритт предлагают использовать этот протокол для безопасной телефонной связи [109]:
Предположим, что развернута сеть шифрующих телефонных аппаратов . Если кто-нибудь хочет восп
Распределение ключей для конференции
Этот протокол позволяет группе из п пользователей договориться о секретном ключе, используя только н е-секретные каналы. Группа использует два общих больших простых числа р и q,
Tateboyashi-Matsuzaki-Newman
Этот протокол распределения ключей подходит для использования в сетях [1521]. Алиса хочет с помощью Трента, KDC, генерировать ключ для сеанса связи с Бобом. Всем участникам известен открытый ключ Т
Asmuth-Bloom
В этой схеме используются простые числа [65]. Для (от, и)-пороговой схемы выбирается большое простое числом, большее М. Затем выбираются числа, меньшие р - dh d2, .
Karnin-Greene-Hellman
В этой схеме используется матричное умножение [818]. Выбирается и+1 от-мерных векторов, V0, Vu . . . Vn, так, что ранг любой матрицы размером от*от, образова
Более сложные пороговые схемы
В предыдущих примерах показаны только простейшие пороговые схемы : секрет делится на п теней так, чтобы, объединив любые от из них, можно было раскрыть секрет. На базе этих алгоритмов можно
Ong-Schnorr-Shamir
Этот подсознательный канал (см. раздел 4.2), разработанный Густавусом Симмонсом (Gustavus Simmons) [1458, 1459, 1460], использует схему идентификации Ong-Schnorr-Shamir (см. раздел 20.5). Как и в о
Уничтожение подсознательного канала eDSA
Подсознательный канал опирается на то, что Алиса может выбирать к для передачи подсознательной информации. Чтобы сделать подсознательный канал невозможным, Алисе не должно
Другие схемы
Подсознательный канал можно организовать для любой схемы подписи [1458, 1460, 1406]. Описание протокола встраивания подсознательного канала в схемы Fiat-Shamir и Feige-Fiat-Shamir вместе с возможн
Доказательство с нулевым знанием для дискретного логарифма
Пегги хочет доказать Виктору, что ей известно х, являющееся решением Ax = B (jaod p)
тпер - простое число, а х - произвольное число, взаимно простое
Доказательство с нулевым знанием для возможности вскрыть RSA
Алиса знает закрытый ключ Кэрол. Может быть она взломала RSA, а может она взломала дверь квартиры Кэрол и выкрала ключ. Алиса хочет убедить Боба, что ей известен ключ Кэрол. Однако она не хочет ни
Доказательство с нулевым знанием того, что п является числом Блюма
Пока неизвестно никаких действительно практичных доказательств того, что п =pq, где р и q - простые числа, конгруэнтные 3 по модулю 4. Однако если п имеет форму
MITRENET
Одной из самых ранних реализаций криптографии с открытыми ключами была экспериментальная система MEMO (MITRE Encrypted Mail Office, Шифрованное почтовое отделение). MITRE - это была команда умных п
STU-III
STU обозначает "Secure Telephone Unit" (Безопасный телефонный модуль), разработанный в NSA безопасный телефон. По размерам и форме этот модуль почти такой же, как и обычный телефон, и мо
KERBEROS
Kerberos представляет собой разработанный для сетей TCP/IP протокол проверки подлинности с доверенной третьей стороной. Служба Kerberos, работающая в сети, действует как доверенный посредник, обесп
Модель Kerberos
Базовый протокол Kerberos был схематично описан в разделе 3.3. В модели Kerberos существуют расположенные в сети объекты - клиенты и серверы. Клиентами могут быть пользователи, но могут и независи
Как работает Kerberos
Вэтом разделе рассматривается Kerberos версии 5. Ниже я обрисую различия между версиями 4 и 5 . Протокол Kerberos прост (см. 23rd). Клиент запрашивает у Kerberos мандат на обращен
Сообщения Kerberos версии 5
В Kerberos версии 5 используется пять сообщений (см. 23-й):
1. Клиент-Kerberos: c,tgs
2. Kerberos-клиент: {Kc>tgs}Kc, {Tc>tgs
Получение первоначального мандата
У клиента есть часть информации, доказывающей его личность - его пароль . Понятно, что не хочется заставлять клиента передавать пароль по сети. Протокол Kerberos минимизирует вероятность компромет
Получение серверных мандатов
Клиенту требуется получить отдельный мандат для каждой нужной ему услуги . TGS выделяет мандаты для отдельных серверов.
Когда клиенту нужен мандат, которого у него пока нет, он посылает за
Kerberos версии 4
В предыдущих разделах рассматривался Kerberos версии 5. Версия 4 немного отличается сообщениями и конструкцией мандатов и удостоверений. В Kerberos версии 4 используются следующие пять сообщений:
Безопасность Kerberos
Стив Белловин (Steve Bellovin) и Майкл Мерритт (Michael Merritt) проанализировали некоторые потенциальные уязвимые места Kerberos [108]. Хотя эта работа была написана про протоколы версии 4, многи
KRYPTOKNIGHT
KryptoKnight (КриптоРыцарь) является системой проверки подлинности и распределения ключей, разраб о-танной в IBM. Это протокол с секретным ключом, использующий либо DES в режиме СВС (см. раздел 9.3
Сертификаты
Наиболее важной частью Х.509 используемая им структура сертификатов открытых ключей. Имена всех пользователей различны. Доверенный Орган сертификации (Certification Authority, CA) присваивает каждо
Протоколы проверки подлинности
Алисе нужно связаться с Бобом. Сначала она извлекает из базы данных последовательность сертификацииот Алисы до Боба и открытый ключ Боба. В этот момент Алиса может инициировать од
Документы РЕМ
РЕМ определяется в следующих четырех документах:
— RFC 1421: Часть I, Процедуры шифрования и проверки подлинности сообщений . В этом документе определяются процедуры шифрования и проверки
Сертификаты
РЕМ совместим со схемой проверки подлинности, описанной в [304], см. также [826]. РЕМ представляет собой надмножество Х.509, определяя процедуры и соглашения для инфраструктуры управления ключами,
Сообщения РЕМ
Сердцем РЕМ является формат сообщений. На 20-й показано зашифрованное сообщение при симметричном управлении ключами. На 19-й показано подписанное и зашифрованное сообщение при управлении ключами на
CLIPPER
Микросхема Clipper (известная также как MYK-78T) - это разработанная в NSA, устойчивая к взлому микросхема, предназначенная для шифрования переговоров голосом. Это одна из двух схем, реализующих п
Коммерческая программа сертификации компьютерной безопасности
Коммерческая программа сертификации компьютерной безопасности (Commercial COMSEC Endorsement Program (CCEP)), кодовое имя Overtake, - это предложение, сделанное NSA в 1984 году и призванное облегчи
ISO/IEC 9979
В середине 80-х ISO стандартизировать DES, который уже использовался в качестве FIPS и стандарта ANSI. После некоторой политической возни ISO решило не стандартизировать криптографические алгоритмы
ISCMEC 9979
Регистрационный номерНазвание
1 B-CRYPT
2 IDEA
3 LUC
25.10 Профессиональные и промышленные группы, а также группы защитников гражданских свобод
ПослесловиеМэттаБлейза
Одним из самых опасных моментов криптологии (и, следовательно, данной книги ), является то, что вам почти удается измерить ее. Знание длины ключей, способов разложения на множители и криптоаналити
Новости и инфо для студентов