Подпись контракта с помощью посредника - раздел Программирование, Протоколы, алгоритмы и исходные тексты на языке С Алиса И Боб Хотят Заключить Контракт. Они Достигли Согласия На Словах, Но Ник...
Алиса и Боб хотят заключить контракт. Они достигли согласия на словах, но никто не хочет ставить свою подпись, пока не поставлена подпись другого. При личной встрече это не вызывает затруднений - оба подпис ы-вают вместе. На расстоянии они могут обратиться к посреднику.
(1) Алиса подписывает копию контракта и посылает ее Тренту.
(2) Боб подписывает копию контракта и посылает ее Тренту.
(3) Трент посылает сообщение и Алисе, и Бобу, сообщающее, что другой партнер подписал контракт .
(4) Алиса подписывает две копии контракта и посылает их Бобу.
(5) Боб подписывает обе копии контракта, сохраняет одну для себя, и посылает другую Алисе .
(6) Алиса и Боб сообщают Тренту, что у каждого из них есть подписанная обоими партнерами копия контра к-та.
(7) Трент уничтожает свои две копии контракта, с единственной подписью под каждым .
Этот протокол работает, потому что Трент защищает любую из сторон от мошенничества другой . Если Боб попытается отказаться от подписи под контрактом на этапе (5), Алиса может обратиться к Тренту за копией контракта, уже подписанного Бобом. Если Алиса попытается отказаться от подписи под контрактом на этапе (4), Боб может сделать то же самое. Когда Трент сообщает, что он получил оба контракта на этапе (3), Алиса и Боб узнают, что другой партнер уже подписал контракт. Если Трент не получит оба контракта на этапах (1) и (2), он уничтожает имеющуюся у него копию, и ни одна из сторон не связана более обязательствами контракта .
Одновременная подпись контракта без посредника (лицом к лицу)
Если Алиса и Боб встречаются лицом к лицу, они могут подписать контракт следующим образом [1244]:
(1) Алиса пишет первую букву своего имени и передает контракт Бобу.
(2) Боб пишет первую букву своего имени и передает контракт Алисе.
(3) Алиса пишет вторую букву своего имени и передает контракт Бобу.
(4) Боб пишет вторую букву своего имени и передает контракт Алисе.
(5) Это продолжается до тех пор, пока Алиса и Боб не напишут свои имена полностью.
Если пренебречь очевидной проблемой протокола (имя Алисы длиннее имени Боба), то он работает дост а-точно хорошо. Написав только одну букву из подписи, Алиса знает, что никакой судья не станет заставлять ее выполнять условия контракта. Но написанная буква - это акт доброй воли, и Боб отвечает аналогичным дейс т-вием.
Когда каждая из сторон напишет несколько букв подписи, судья вероятно сможет убедиться, что обе стороны подписали контракт. Хотя, если вглядеться, ситуация весьма туманна. Конечно же, то, что контракт не вступает в силу после написания первых букв, так же очевидно как и то, что контракт становится действующим после того, как стороны напишут свои имена. В каком месте протокола стороны оказываются связанными контрактом? Написав половину своих имен? Две трети? Три четверти?
Так как ни Алиса, ни Боб не знают точно, с какого момента начинает действовать контракт, то у каждого из них на протяжении всего протокола есть опасение, что для него или для нее контракт уже вступил в силу . Не существует этапа протокола, на котором Боб смог бы сказать : "Вы написали четыре буквы подписи, а я только три. Вы связаны контрактом, а я нет." У Боба нет причин прекращать выполнение протокола. Более того, чем дольше стороны выполняют протокол, тем больше вероятность того, что судья решит, что контракт вступил в силу. И снова, нет причины прерывать протокол. В конце концов, они оба хотели подписать контракт, они просто не хотели подписывать его раньше другого партнера.
Одновременная подпись контракта без посредника(без личной встречи)
В этом протоколе используется такая же неопределенность [138]. Алиса и Боб по очереди движутся детскими шажками к подписанию протокола.
В этом протоколе Алиса и Боб обмениваются рядом подписанных сообщений вида : "Я согласен, что с вероятностью/^ связан условиями контракта."
Получатель сообщения может предъявить его судье и, с вероятностью р, судья признает контракт подписанным.
(1) Алиса и Боб согласовывают дату окончания подписания контракта .
(2) Алиса и Боб договариваются о различии вероятностей, которым они собираются пользоваться. Например, Алиса может решить, что ее вероятность быть связанной условиями контракта не должна превышать в е-роятность Боба больше, чем на 2 процента. Обозначим различие Алисы как а, различие Боба - как Ъ.
(3) Алиса посылает Бобу подписанное сообщение с вероятностью р = а.
(4) Боб посылает Алисе подписанное сообщение ср=а + Ь.
(5) Пусть/; - это вероятность из сообщения, полученного Алисой от Боба на предыдущем этапе . Алиса посылает Бобу подписанное сообщение ср' =р + ашт1, смотря что меньше.
(6) Пусть/; - это вероятность из сообщения, полученного Бобом от Алисы на предыдущем этапе . Боб посылает Алисе подписанное сообщение ср' =р + Ьшт1, смотря что меньше.
(7) Алиса и Боб продолжают выполнять этапы (5) и (6) до тех пор, пока они оба не получат сообщения с р = 1 или пока не наступит согласованная на этапе (1) дата.
По мере выполнения протокола и Алиса, и Боб соглашаются, что они оказываются связанными контрактом со все большей и большей вероятностью. Например, Алиса может определить свое а как 2 процента, а Боб свое Ъ - как 1 процент. (Лучше бы они выбрали большие приращения, а то мы застрянем на этом месте.) В первом сообщении Алиса сообщает, что она связана контрактом с вероятностью 2 процента . Боб может ответить, что он связан контрактом с вероятностью 3 процента. Следующее сообщение Алисы может утверждать, что она связ а-на контрактом с вероятностью 5 процента и так далее, пока вероятности обоих не достигнут 100 процентов .
Если и Алиса, и Боб завершили протокол к оговоренной дате, то все прекрасно. В противном случае, любая из сторон может предъявить контракт судье вместе с подписанным последним сообщением другой стороны. Прежде, чем просмотреть контракт, судья случайным образом выбирает число между 0 и 1. Если это число меньше вероятности, подписанной второй стороной, то обе стороны связаны контрактом. Если это число больше вероятности, подписанной второй стороной, то обе стороны не связаны контрактом. (Затем судья сохраняет использованное число на случай решения другого вопроса, касающегося того же контракта .) Именно это и означает "быть связанным контрактом с вероятностью р".
Это базовый протокол, но могут использоваться и дополнительные усложнения . Судья может принимать ре-
шение в отсутствие одной из сторон. Решение судьи связывает контрактом либо обе стороны, либо ни одну из них. Не существует ситуации, когда одна из сторон связана контрактом, а другая - нет . Более того, протокол завершится, как только одна из сторон захочет иметь хоть немного большую, чем другая, вероятность быть ев я-занной контрактом.
Одновременная подпись контракта без посредника (с помощью криптографии)
Этот криптографический протокол использует тот же принцип детских шажков [529]. Для определенности используется DES, хотя вместо него может быть любой симметричный алгоритм .
(1) И Алиса, и Боб случайным образом выбирают 2п ключей DES, сгруппированных попарно. В парах нет ничего особенного, это просто способ группировки для данного протокола .
(2) И Алиса, и Боб создают п пар сообщений, Ц и R„ например, "Это левая половина моей г-ой подписи" и "Это правая половина моей г'-ой подписи". Идентификатор, i, меняется от 1 до и. В каждое сообщение, вероятно, также будет входить цифровая подпись контракта и метка времени . Контракт считается подписанным, если другая сторона может предъявить обе половины, Ц и Rh одной пары подписей.
(3) И Алиса, и Боб шифруют свои пары сообщений парами ключей DES, левое сообщение - левым ключом в паре , а правое - правым.
(4) Алиса и Боб посылают друг другу свои пачки из 2п шифрованных сообщений, поясняя, какие сообщения какими половинами каких пар являются.
(5) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи для каждой пары. То есть, Алиса посылает Бобу независимо для каждой из п пар ключей либо ключ, использованный для шифрования левого сообщения, либо ключ, использованный для шифрования правого сообщения . Боб делает то же самое. Они могут посылать свои половинки по очереди, или сначала один может послать все 100, а потом другой - это не имеет значения. Теперь и у Алисы, и у Боба есть по одному ключу из каждой пары, но никто не знает, какие из половинок получил партнер .
(6) Алиса и Боб, используя полученные ключи, расшифровывают те половинки сообщений, которые они м о-гут расшифровать. Они убеждаются, что расшифрованные сообщения правильны .
(7) Алиса и Боб посылают друг другу первые биты всех 2п ключей DES.
(8) Алиса и Боб повторяют этап (7) для вторых битов всех 2п ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы.
(9) Алиса и Боб расшифровывают оставшиеся половинки сообщений, и контракт подписан.
(10) Алиса и Боб обмениваются закрытыми ключами, использованными для протокола рассеянной передачи
на этапе (5), и каждый из них убеждается в отсутствии мошенничества .
Почему Алисе и Бобу нужно выполнить всю эту нудную последовательность действий? Предположим, что Алиса хочет смошенничать, и посмотрим, что получится. На этапах (4) и (5) Алиса могла бы разрушить протокол, послав Бобу ничего не значащие строки. Боб обнаружил бы это на этапе (6) при попытке расшифровать полученные половинки. Боб с полной безопасностью может остановиться до того, как Алиса сможет расшифр о-вать любую из пар сообщений Боба.
Если бы Алиса была очень хитрой, она могла бы разрушить только половину протокола . Она могла бы послать одну половинку из каждой пары правильно, а вместо второй отправить бессмысленные строки . Вероятность Боба получить правильную половинку составит только 50 процентов , поэтому в половине случаев мошенничество Алисы удастся, но только для одной пары. Если бы использовались только две пары, этот способ мошенничества удастся в 25 процентах случаев. Вот почему п должно быть велико. Алисе необходимо точно угадать результат п протоколов рассеянной передачи, ее вероятность добиться этого составляет 1 шанс из 2 п. Если п = 10, у Алисы 1 шанс из 1024 обмануть Боба.
Алиса также может отправить Бобу случайные биты на этапе (8). Возможно, Боб не узнает, что она послала ему случайные биты, пока не получит весь ключ и не попытается расшифровать половинки сообщения . Но снова вероятность на стороне Боба. Он уже получил половину ключей, и Алиса не знает какую. Если п достаточно велико, Алиса наверняка пришлет ему бессмысленный бит для ключа, который у него уже есть, и он немедле н-но узнает, что она пытается его обмануть.
Возможно, Алиса будет выполнять этап (8) до тех пор, пока она не получит достаточно битов ключей для вскрытия грубым взломом, и затем прекратит передачу битов . Длина ключа DES - 56 битов. Если она получила 40 из 56 битов, ей останется перебрать 216, или 65536, ключей для дешифровки сообщения, а эта задача, опр е-деленно, по силам современным компьютерам. Но Боб получит ровно столько же битов ее ключей (или, в худшем случае, на один бит меньше), следовательно, он сможет сделать то же самое. У Алисы нет другого выбора, кроме как продолжать следовать протоколу.
Идея в том, что Алисе придется играть честно, потому что вероятность обмануть Боба слишком мала . В конце протокола у обеих сторон есть п подписанных пар сообщений, любое из которых достаточно для правильной подписи.
У Алисы есть только один способ смошенничать - она может послать Бобу одинаковые сообщения на этапе (5). Боб не сможет обнаружить этого до окончания протокола, но он сможет использовать стенограмму проток о-ла, чтобы убедить судью в двуличности Алисы.
Протоколы этого типа имеют два слабых места [138]. Во первых, проблема возникает, если вычислительная мощь одной стороны гораздо больше, чем у другой. Если, например, Алиса может выполнить вскрытие грубым взломом быстрее Боба, то она рано прекратит передачу битов на этапе (8) и раскроет ключи Боба самостоятельно. Бобу, которому для таких же действий просто не хватит времени, не повезет .
Во вторых, проблема возникает, если одна из сторон прекращает протокол раньше времени . Если Алиса оборвет выполнение протокола, оба столкнутся с одинаковыми вычислительными проблемами, но у не хватит ресурсов завершить вычисления к нужному сроку. Проблема появляется, к примеру, если контракт определяет, что Алиса должна сделать что-то через неделю, а она прерывает протокол в тот момент, когда Бобу для вычи с-ления ее подписи потребуется целый год расчетов. Реальная сложность при этом заключается в близкой дате предмета контракта, к которой процесс не будет завершен одной или обеими подписывающими сторонами .
Эти проблемы существуют также для протоколов разделов 5.8 и 5.9.
5.8 Электронная почта с подтверждением
Такой же протокол одновременной рассеянной передачи, использованный для подписания контракта, с н е-болыпими изменениями используется для электронной почты с подтверждением [529]. Пусть Алиса хочет послать сообщение Бобу, но не хочет, чтобы он прочитал его, не расписавшись в получении . В реальной жизни это обеспечивается неприветливыми почтовыми служащими, но то же самое может быть сделано при помощи криптографии. Эту проблему первым рассмотрел Уитфилд Диффи в [490].
На первый взгляд, эту проблему мог бы решить протокол одновременного подписания контракта. Алиса просто копирует свое сообщение ключом DES. Ее половина протокола выглядит примерно так: "Это левая половина ключа DES: 32f5", а половина протокола Боба - так: "Это левая половина моей квитанции." Все остальное не меняется.
Чтобы понять, почему это не работает, вспомните, что протокол опирается на то, что рассеянная передача на этапе (5) предохраняет от мошенничества обе стороны. Оба партнера знают, что они послали другой стороне правильную половину, но никто не знает какую. Они не мошенничают на этапе (8), потому что вероятность выйти сухим из воды чрезвычайно мала. Если Алиса посылает Бобу не сообщение, а половину ключа DES, то Боб не может проверить правильность ключа DES на этапе (6). Алиса же может проверить правильность квитанции Боба, поэтому Бобу придется быть честным. Алиса легко может отправить Бобу неправильный ключ а когда он обнаружит это, его квитанция уже будет у Алисы. Вот невезуха, Боб.
Решение этой проблемы потребует некоторой коррекции протокола :
(1) Алиса шифрует свое сообщение случайным ключом DES и посылает его Бобу.
(2) Алиса создает п пар ключей DES. Первый ключ каждой пары генерируется случайным образом, а второй представляет собой XOR первого ключа и ключа шифрования сообщения.
(3) Алиса шифрует сообщение-заглушку каждым из своих 2п ключей.
(4) Алиса посылает Бобу всю пачку шифрованных сообщений, проверяя, что он знает, какие сообщения какими половинами каких пар являются.
(5) Боб создает п пар случайных ключей DES.
(6) Боб создает пару сообщений, образующих правильную квитанцию. Хорошим вариантами могут служить "Это левая половина моей квитанции" и "Это левая половина моей квитанции" с добавлением какой-нибудь строки случайных битов. Он создает п пар квитанций, нумеруя каждую. Как и в предыдущем пр о-токоле квитанция считается правильной, если Алиса может предъявить обе половины квитанции (с одним и тем же номером) и все ее ключи шифрования.
(7) Боб шифрует каждую свою пару сообщений парами ключей DES, г-ую пару сообщений - г-ой парой ключей, левое сообщение - левым ключом в паре , а правое - правым . в паре.
(8) Боб посылает Алисе свою пачку шифрованных сообщений , проверяя, что она знает, какие сообщения какими половинами каких пар являются.
(9) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи . То есть,
Алиса посылает Бобу независимо для каждой из п пар ключей либо ключ, использованный для шифрования левого сообщения, либо ключ, использованный для шифрования правого сообщения . Боб делает то же самое. Они могут посылать свои половинки по очереди, или сначала один может послать все п, а потом другой - это не имеет значения. Теперь и у Алисы, и у Боба есть по одному ключу из каждой пары , но никто не знает, какие из половинок получил партнер .
(10) Алиса и Боб расшифровывают те половинки сообщений, которые могут и убеждаются, что расшифрованные сообщения правильны.
(И) Алиса и Боб посылают друг другу первые биты всех 2п ключей DES. (Если они беспокоятся, что Ева сможет прочитать эти почтовые сообщения, то они должны шифровать свой обмен битами).
(12) Алиса и Боб повторяют этап (И) для вторых битов всех 2п ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы.
(13) Алиса и Боб расшифровывают оставшиеся половинки сообщений. Алиса получает правильную квитанцию от Боба, а Боб может выполнить "исключающее или" для любой пары ключей и пролучить ключ, к о-торым зашифровано оригинальное сообщение.
(14) Алиса и Боб обмениваются закрытыми ключами, использованными для протокола рассеянной передачи, и каждый из них убеждается в отсутствии мошенничества.
Этапы (5)-(8) для Боба и (9)-(12) для обеих сторон не меняются по сравнению с протоколом подписания ко н-тракта. Отличие - в сообщениях-заглушках Алисы. Они предоставляют Бобу возможность проверить правильность ее рассеянной передачи на этапе (10), что заставляет ее оставаться честной на этапах (П)-(13). И, как и для протокола одновременного подписания контракта, для выполнения протокола требуются обе половины одного из сообщений Алисы.
5.9 Одновременный обмен секретами
Алиса знает секрет А, а Боб - секрет В. Алиса собирается сообщить Бобу А, если он расскажет ей В. Боб хочет сообщить Алисе В, если она расскажет ему А. Следующий протокол, подслушанный на школьном дворе, работать не будет:
(1) Алиса: "Я скажу, если ты скажешь мне первым."
(2) Боб: "Я скажу, если ты скажешь мне первой."
(3) Алиса: "Нет, ты первый."
(4) Боб: "Ну, хорошо." Боб шепчет Алисе.
(5) Алиса: "Ха, а я тебе не скажу."
(6) Боб: "Это не честно."
Честным это может сделать криптография. Предыдущие два протокола являются реализациями более общ е-го протокола, который и позволит Алисе и Бобу одновременно обменяться секретами [529]. Чтобы не повторять полностью весь протокол, я набросаю необходимые изменения протокола почты с подтверждением .
Алиса выполняет этапы (1)-(4), используя в качестве сообщения А. Боб выполняет эти же действия, используя в качестве своего сообщения В. Алиса и Боб выполняют рассеянную передачу на этапе (9), расшифровывают на этапе (10) те половинки, которые могут, и выполняют необходимые итерации на этапах (11) и (12). Чтобы защититься от Евы, они должны шифровать свои сообщения . Наконец, и Алиса, и Боб расшифровывают оставшиеся половины пар сообщения и выполняют XOR для любой пары ключей, чтобы получить ключи, которыми зашифрованы оригинальные сообщения.
Этот протокол позволяет Алисе и Бобу одновременно обмениваться секретами, но не гарантирует качества переданных секретов. Алиса может пообещать Бобу план лабиринта Минотавра и прислать ему схему Босто н-ского метро. Боб получит только тот секрет, который Алиса пришлет ему. Другие протоколы описаны в [1286, 195, 991, 1524, 705, 753, 259, 358, 415].
Все темы данного раздела:
Об авторе
БРЮС ШНАЙЕР - президент Counterpane Systems, Оак Парк, Иллинойс, фирма-консультант, специализирующаяся в криптографии и компьютерной безопасности. Брюс также написал E-Mail Security, John W
DKi(EK/M))=M
Безопасность этих алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован. Продукты, использующие этот алгоритм, могут
Симметричные алгоритмы
Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом . Симметричные алгоритмы,иногда называемые условными алгоритмами, представляют собой
DK(C)=M
Симметричные алгоритмы делятся на две категории . Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмамиили потоковыми
Криптоанализ
Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от зл о-умышленников (также называемых взломщиками, соперниками, врагами, перехватчиками). Предполагает
Безопасность алгоритмов
Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных,
Исторические термины
Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фраз
Перестановочные шифры
В перестановочном шифременяется не открытый текст, а порядок символов. В простом столбцовом перестановочном шифреоткрытый текст пишется горизонтально на разграфле
Роторные машины
В 1920-х годах для автоматизации процесса шифрования были изобретены различные механические устро й-ства. Большинство использовало понятие ротора,механического колеса, используемог
Элементы протоколов
2.1 Введение в протоколы
Смысл криптографии - в решении проблем. (По сути, в этом состоит и смысл использования компьютеров, о чем многие пытаются забыть.) Криптография решает проблемы сек
Самодостаточные протоколы
Самодостаточный протоколявляется лучшим типом протокола. Он полностью обеспечивает честность сторон (см. 1-й(в)). Для выполнения протокола не нужен ни посредник, не решающий споры
Попытки вскрытия протоколов
Криптографические попытки взлома могут быть направлены против криптографических алгоритмов, и с-пользуемых в протоколах, против криптографических методов, используемых для реализации алгоритмов и п
Коды проверки подлинности сообщения
Код проверки подлинности сообщения(message authentication code, MAC), известный также как код про-
верки подлинности данных (data authentication code, DAG), представл
Смешанные криптосистемы
Первые алгоритмы с открытым ключом стали известны в то же время, когда проходило DES обсуждение как предполагаемого стандарта. Это привело к известной партизанщине в криптографическом сообществе .
Подпись документа с помощью симметричных криптосистем и посредника
Алиса хочет подписать цифровое сообщение и отправить его Бобу. Она может это сделать с помощью Тре н-та и симметричной криптосистемы.
Трент - это обладающий властью посредник, которому дов
Подпись документа с помощью криптографии с открытыми ключами
Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В н е-которых алгоритмах - примером является RSA (см. раздел 19.3) - для шифрования может быть использова
Подпись документа и метки времени
На самом деле, при определенных условиях Боб сможет смошенничать . Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Алиса подписала контракт (одной копией по
Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций
На практике алгоритмы с открытыми ключами часто недостаточно эффективны для подписи больших док у-ментов. Для экономии времени протоколы цифровой подписи нередко используют вместе с однонаправленны
Алгоритмы и терминология
Существует множество алгоритмов цифровой подписи. Все они представляют собой алгоритмы с открытыми ключами с закрытой частью для подписи документов и с открытой - для проверки подписи . Иногда проц
Несколько подписей
Как Алисе и Бобу одновременно подписать один и тот же документ? В отсутствие однонаправленных хэш-функций существует две возможности. Алиса и Боб могут подписать различные копии одного и того же до
Невозможность отказаться от цифровой подписи
Алиса может смошенничать с цифровыми подписями, и с этим ничего нельзя поделать. Она может подп и-сать документ и затем утверждать, что она этого не делала. Сначала она, как обычно, подписывает пис
Использование цифровых подписей
Одним из самых ранних предложенных применений цифровых подписей было упрощение проверки собл ю-дения договоров о ядерных испытаниях [1454, 1467]. Соединенные Штаты и Советский Союз (кто-нибудь пом
Обнаружение вскрытия, основанного на возвращении сообщения
Только что описанное вскрытие работает потому, что операция шифрования совпадает с операцией проверки подписи, а операция дешифрирования - с операцией подписи. Операции шифрования и цифровой подпис
Вскрытия криптографии с открытыми ключами
Во всех подобных протоколах криптографии с открытыми ключами я не рассказал , как Алиса получает открытый ключ Боба. Подробно этот вопрос описан в разделе 3.1, но о нем стоит упомянуть и здесь.
Генерация случайных и псевдослучайных последовательностей
Почему даже в книге по криптографии снова эти докучливые рассуждения о генерации случайных чисел? Генератор случайных чисел встроен в каждый компилятор, обычный вызов функции. Почему бы не использ
Псевдослучайные последовательности
Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностейЧто это такое? Многие пытались дать его формальное определение, но я уклонюсь от этого. Псевд
Криптографически безопасные псевдослучайные последовательности
Криптографические приложения предъявляют к генератору псевдослучайных последовательностей более высокие требования по сравнению с другими приложениями . Криптографическая случайность не ограничивае
Настоящие случайные последовательности
Теперь мы вторгаемся в область, принадлежащую философам . Существует ли такая вещь как случайность? Что такое случайная последовательность? Как узнать, что последовательность случайна? Является ли
Основные протоколы
3.1 Обмен ключами
Общепринятой криптографической техникой является шифрование каждого индивидуального обмена соо б-щениями отдельным ключом. Такой ключ называется сеансовым, так как он исп
Обмен ключами с помощью симметричной криптографии
Этот протокол предполагает, что пользователи сети, Алиса и Боб, получают секретный ключ от Центра ра с-пределения ключей (Key Distribution Center, KDC) [1260] - Трента наших протоколов. Перед начал
Обмен ключами, используя криптографию с открытыми ключами
Базовая смешанная криптосистема обсуждалась в разделе 1.5. Для согласования сеансового ключа Алиса и Боб применяют криптографию с открытыми ключами, а затем используют этот сеансовый ключ для шифро
Обмен ключами с помощью цифровых подписей
Использование цифровой подписи в протоколе обмена сеансовым ключом также позволяет избежать вскр ы-тия "человек-в-середине". Трент подписывает открытые ключи Алисы и Боба. Подписанные клю
Передача ключей и сообщений
Алисе и Бобу не обязательно выполнять протокол обмена ключами перед обменом сообщениями. В этом протоколе Алиса отправляет Бобу сообщение без предварительного протокола обмена ключами :
(1
Широковещательная рассылка ключей и сообщений
Не существует причин, запрещающих Алисе посылать шифрованное сообщение нескольким людям . В следующем примере Алиса посылает шифрованное сообщение Бобу, Кэрол и Дэйву :
(1) Алиса генериру
Удостоверение подлинности с помощью однонаправленных функций
Роджер Неедхэм (Roger Needham) и Майк Гай (Mike Guy) показали, что главному компьютеру не нужно знать сами пароли, вполне достаточно, чтобы главный компьютер мог отличать правильные пароли от непр
Удостоверение подлинности с помощью криптографии с открытыми ключами
Даже с использованием "соли" у первого протокола есть серьезные проблемы с безопасностью . Когда Алиса посылает свой пароль главному компьютеру, любой, у кого есть доступ пути передачи ее
Удостоверение подлинности сообщений
Когда Боб получает сообщение от Алисы, как ему узнать, что это сообщение подлинно? Если Алиса подписала свое сообщение, то все просто. Цифровая подпись Алисы достаточна, чтобы подтвердить кому уго
Лягушка с широким ртом
Протокол "Лягушка с широким ртом" (Wide-Mouth Frog) [283,284], возможно, является простейшим симметричным протоколом управления ключами, в котором используется заслуживающий доверия серв
Otway-Rees
Этот протокол также использует симметричную криптографию [1224].
(1) Алиса создает сообщение, состоящее из порядкового номера, ее имени, имени Боба и случайного числа. Сообщение шифруе
Широковещательная передача сообщения
Представьте, что в некоей операции занято 100 ваших тайных агентов . Вы хотите иметь возможность посылать сообщения группам агентов, но вы не знаете заранее состав групп . Можно либо шифровать соо
Совместное использование с мошенниками
Существует множество способов обмануть пороговую схему. Вот только несколько из них. Сценарий 1 : Полковники Алиса, Боб и Кэрол сидят в изолированном бункере где-то глубоко под землей. Однажды они
Совместное использование секрета без раскрытия долей
У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно. Если разделяемый секрет являетс
Схемы совместного использования секрета с мерами предохранения
Секрет делится среди 50 человек так, чтобы любые 10 могли собраться вместе и восстановить секрет . Это нетрудно. Но, можем ли мы реализовать ту же схему совместного использования секрета, добавив т
Совместное использование секрета с вычеркиванием из списка
Вы создали систему совместного использования секрета и теперь хотите застрелить одного из владельцев части секрета. Вы могли бы создать новую схему, исключив этого несчастного, но время поджимает.
Промежуточные протоколы
4.1 Службы меток времени
Во многих ситуациях людям нужно убедиться, что определенный документ уже существовал в определенный момент времени. Примером является спор об авторских правах или
Решение с посредником
В этом протоколе участвуют Трент, обладающий надежной службой меток времени, и Алиса, которая хочет задать метку времени для документа.
(1) Алиса передает копию документа Тренту.
Улучшенное решение с посредником
Большинство этих проблем легко снимаются при использовании однонаправленной хэш-функции и цифр о-вых подписей:
(1) Алиса вычисляет значение однонаправленной хэш-функции для документа.
Протокол связи
Одним из путей решения этой проблемы является установление связи между меткой времени Алисы и ме т-ками времени, ранее созданными Трентом. Весьма вероятно, что эти метки были созданы не для Алисы,
Распределенный протокол
Люди умирают, метки времени теряются. Между пометкой документа и его оспариванием может произойти многое, что помешает Алисе получить копию метки времени !„.,. Эта проблема может быть частич
Дальнейшая работа
Дальнейшие улучшения протоколов метки времени описаны в [92]. Авторы используют двоичные деревья для увеличения количества меток времени, зависящих от данной метки, уменьшая вероятность создания це
Применения подсознательного канала
Наиболее очевидным применением подсознательного канала является шпионская сеть. Если кто-то посылает и принимает сообщения, то передача сообщений по подсознательному каналу в подписанных документах
Подписи, свободные от подсознательного канала
Алиса и Боб обмениваются подписанными сообщениями, обговаривая сроки контракта. Они используют протокол цифровой подписи. Однако, эти переговоры на самом деле маскируют шпионскую деятельность Ал и-
Групповые подписи с надежным посредником
Следующий протокол использует заслуживающего посредника:
(1) Трент создает большую кучу пар открытый ключ/закрытый ключ и выдает каждому члену группы инд и-видуальный список уникальных зак
Подписи с обнаружением подделки
Пусть Ева является могучим противником. У нее есть обширные компьютерные сети и залы, набитые ко м-пьютерами Крэй, на много порядков более мощных, чем доступные Алисе . Все эти компьютеры днем и но
Вручение бита с помощью генератора псевдослучайной последовательности
Этот протокол даже проще [1137]:
(1) Боб создает строку случайных битов и посылает ее Алисе.
Rb
(2) Алиса создает стартовую последовательность для генератора псевд
Blob-объекты
Строки, которые Алиса посылает Бобу для вручения бита, иногда называют blob-объектами.Blob-объект -это последовательность битов, хотя протоколы этого и не требуют. Как сказал Жиль
Бросок монеты с помощью однонаправленных функций
Если Алиса и Боб договорятся об однонаправленной функции, протокол прост : (1) Алиса выбирает случайное число, х. Она вычисляет y—f(x), где/fx) - однонаправленная функция.
Бросок монеты с помощью криптографии с открытыми ключами
Этот протокол работает как с криптографией с открытыми ключами, так и с симметричной криптографией . Единственное условие - переключение алгоритма. То есть :
DKi(EK
Бросок монеты в колодец
Интересно отметить, что во всех этих протоколах Алиса и Боб узнают результат броска не одновременно . В каждом протоколе есть момент, когда одна из сторон (Алиса в первых двух протоколах и Боб в по
Генерация ключей с помощью броска монеты
Реальным применением этого протокола служит генерация сеансового ключа. Протоколы броска монеты п о-зволяют Алисе и Бобу создать случайный сеансовый ключ так, что никто из них не сможет повлиять на
Мысленный покер с тремя игроками
Покер интереснее, если в игре участвуют несколько человек. Базовый протокол мысленного покера легко может быть распространен на трех и более игроков . В этом случае криптографический алгоритм также
Вскрытия мысленного покера
Криптографы показали, что при использовании этими протоколами покера алгоритма с открытыми ключами RSA происходит небольшая утечка информации [453, 573]. Конкретно, если двоичное представление карт
Анонимное распределение ключей
Хотя непохоже, чтобы кто-нибудь собирался использовать этот протокол для игры в покер по модему , Чарльз Пфлегер (Charles Pfleeger) рассматривает ситуацию, в которой этот тип протокола может оказат
Политика условного вручения ключей
Помимо правительственных планов относительно условного вручения ключей распространяются и комме р-ческие системы с условным вручением ключей. Возникает очевидный вопрос: какое преимущество от услов
Развитые протоколы
5.1 Доказательства с нулевым знанием
А вот другая история:
Алиса: "Я знаю пароль компьютера Федеральной Резервной Системы, компоненты секретного соуса Макдональдс и оде р-жан
Изоморфизм графа
Объяснение этого понятия, пришедшего из теории графов [619, 622], может занять некоторое время. Граф представляет собой сеть линий соединяющих различные точки. Если два графа идентичны во всем, кро
Гамилыпоновы циклы
Вариант этого примера был впервые представлен Мануэлем Блюмом (Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз .
Параллельные доказательства с нулевым знанием
В базовом протоколе с нулевым знанием используется п обменов информацией между Пегги и Виктором. Почему бы не выполнить их параллельно:
(1) Пегги использует свою информацию и п
Неинтерактивные доказательства с нулевым знанием
Кэрол невозможно убедить, потому что она не участвует в интерактивном процессе протокол. Для убеждения Кэрол и других заинтересованных лиц нам нужен неинтерактивный протокол .
Для неинтера
Общие замечания
Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что д о-казательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для это
Проблема гроссмейстера
Вот как Алиса, даже не зная правил шахмат, может обыграть гроссмейстера. (Иногда это называется проблемой гроссмейстера.) Она посылает вызов Гарри Каспарову и Анатолию Карпову, предлагая играть в
Обман, выполненный мафией
Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за ме
Обман, выполненный террористами
Если Алиса хочет объединиться с Кэрол, то они также могут провести Дэйва. В этом протоколе Кэрол - и з-вестная террористка. Алиса помогает ей въехать в страну. Дэйв - офицер-пограничник, Алиса и Кэ
Предлагаемые решения
Оба описанных мошенничества возможны, так как заговорщики используют тайный радиоканал. Одним из способов предотвратить мошенничество является проведение процедуры идентификации в клетке Фарадея, б
Обман с несколькими личностями
Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не п
Прокат паспортов
Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". (Первым это предложил Боб, но возник ряд очевидных проблем
Доказательство членства
Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее,
Полностью слепые подписи
Боб - государственный нотариус. Алиса хочет, чтобы он подписал документ, не имея ни малейшего пре д-ставления о его содержании. Боб не отвечает за содержание документа, он только заверяет, что нота
Рассеянные подписи
Честно говоря, я не могу придумать, чего их можно использовать, но существует два типа рассеянных по д-писей [346]:
1. У Алисы есть п различных сообщений. Боб может выбрать одно из
Эзотерические протоколы
6.1 Безопасные выборы
Компьютерное голосование никогда не будет использовано для обычных выборов, пока не появится прот о-кол, который одновременно предохраняет от мошенничества и защищает
Упрощенный протокол голосования №1
(1) Каждый голосующий шифрует свой бюллетень открытым ключом Центральной избирательной комиссии (ЦИК).
(2) Каждый голосующий посылает свой бюллетень в ЦИК.
(3) ЦИК расшифровывает
Упрощенный протокол голосования №2
(1) Каждый голосующий подписывает свой бюллетень своим закрытым ключом .
(2) Каждый голосующий шифрует свой бюллетень открытым ключом ЦИК .
(3) Каждый голосующий посылает свой бюл
Голосование со слепыми подписями
Нам нужно как-то отделить бюллетень от голосующего, сохранив процедуру идентификации личности . Именно это можно сделать с помощью протокола слепой подписи .
(1) Каждый избиратель создает
Голосование с двумя Центральными комиссиями
Одним из решений является разделить ЦИК пополам . Ни у одной из них не будет достаточно власти, чтобы смошенничать по своему усмотрению.
В следующем протоколе используется Центральное упра
Голосование с одной Центральной комиссией
Чтобы избежать опасности сговора между ЦУР и ЦИК можно использовать более сложный протокол [1373]. Этот протокол идентичен предыдущему с двумя изменениями :
— ЦУР и ЦИК являются единой орг
Улучшенное голосование с одной Центральной комиссией
В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, допо
Улучшенное голосование с одной Центральной комиссией
В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, допо
Голосование без Центральной избирательной комиссии
В следующем протоколе ЦИК не используется, избиратели следят друг за другом . Этот протокол, созданный Майклом Мерриттом [452, 1076, 453], настолько громоздок, что возможность его реализации больше
Другие схемы голосования
Было предложено много сложных безопасных протоколов выборов . Их можно разделить на два типа. Суще-ствуют протоколы с перемешиванием, как "Голосование без Центральной избирательной комиссии&qu
Протокол №1
Как может группа людей вычислить свою среднюю зарплату без того, чтобы зарплата одного стала известна другому?
(1) Алиса добавляет секретное случайное число к сумме своей зарплаты, шифрует
Протокол №2
Алиса и Боб вместе в ресторане и спорят о том, кто старше. Никто, однако, не хочет сообщить другому свой возраст. Каждый из них мог бы прошептать свой возраст на ушко доверенной нейтральной стороне
Протокол №3
Алиса нравится забавляться с плюшевыми медведями. В эротических фантазиях Боба важное место зан и-мают мраморные столы. Оба весьма стесняются своих привычек, но с удовольствием нашли бы кого-нибудь
Протокол №4
Вот другая проблема для безопасных вычислений со многими участниками [1373]: совет семи регулярно
встречается, чтобы тайно проголосовать по некоторым вопросам. (Все в порядке, они упр
Безопасная оценка схемы
Вход Алисы - а, а Боба - Ъ. Они вместе хотят вычислить некоторую функцию f(a,b) так, чтобы Алиса не смогла ничего узнать о входе Боба, а Боб - о входе Алисы. Главная проблема б
Протокол №4
Если окажется, что человек, выписавший банковский чек, попытался обмануть продавца, то банк может з а-хотеть личность этого человека. Чтобы сделать это, придется вернуться от физических аналогий в
Электронные наличные и идеальное приведение
У электронных наличных есть и своя темная сторона. Иногда людям не нужно так много секретности. Смотрите, как Алиса совершает идеальное преступление [1575]:
(1) Алиса крадет ребенка.
Другие протоколы электронных наличных
Существуют и другие протоколы электронных наличных, см. [707, 1554, 734, 1633, 973]. Ряд из них использует весьма изощренную математику. Различные протоколы электронных наличных можно разделить на
Анонимные кредитные карточки
Этот протокол [988] для защиты личности клиента использует несколько различных банков. Каждый клиент имеет счет в двух различных банках. Первый банк, которому известна личность человека, может зачи
Новости и инфо для студентов