Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[32]

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

При разработке математики таких схем, обеспечение безопасности которых оказалось зверски сложным, был выполнен большой объем работы - главным образом в Японии . Многие предложенные решения содержат выбор Трентом случайного числа для каждого пользователя - по моему, это угрожает самой идее таких систем . Ряд алгоритмов, рассматриваемых в главах 19 и 20, могут быть личностными . Подробности алгоритмов и криптосистем можно найти в [191, 1422, 891, 1022, 1515, 1202, 1196, 908, 692, 674, 1131, 1023, 1516, 1536, 1544, 63, 1210, 314, 313, 1545, 1539, 1543, 933, 1517, 748, 1228]. Алгоритм, который не использует случайных чисел, описан в [1035]. Система, обсуждаемая в [1546, 1547, 1507], ненадежна против вскрытия с использованием выбранного открытого ключа, то же самое можно сказать и о системе, предложенной как NIKS-TAS [1542, 1540, 1541, 993, 375, 1538]. По правде говоря, среди предложенного нет ничего одновременно практичного и безопа с-ного.

5.5 Рассеянная передача

Криптограф Боб безнадежно пытается разложить на множители 500-битовое число n. Он знает, что оно является произведением пяти 100-битовых чисел, и ничего больше . (Вот проблема. Если он не восстановит ключ, ему придется работать сверхурочно, и он не попадет на еженедельную игру с Алисой в мысленный покер .) Что же делать? И вот появляется Алиса:

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

Боб заинтересован, но только за 50 долларов. Алиса не хочет сбрасывать цену и предлагает продать Бобу половину битов за половину стоимости. "Это заметно сократит тебе работу", -.

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

Они в патовой ситуации. Алиса не может убедить Боба в том, что она знает сомножитель n, не раскрыв его, а Боб не хочет покупать 50 битов, которые вполне могут оказаться бесполезными .

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

В следующем протоколе Алиса посылает Бобу одно из двух сообщений. Боб получает сообщение, но какое -Алиса не знает.

(1)Алиса генерирует две пары открытый ключ/закрытый ключ, всего четыре ключа . Она посылает оба открытых ключа Бобу.

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

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

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

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

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

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

В этот момент, конечно же Боб сможет узнать и второе сообщение .


Протокол надежно защищен от взлома со стороны Алисы, потому что у нее нет возможности узнать, какой из двух ключей DES является настоящим. Оба из них она использует для шифрования своих сообщений, но Боб может успешно расшифровать только одно из них - до этапа (6) . Протокол защищен и от взлома со стороны Боба, потому что до этапа (6) он не сможет получить закрытый ключ Алисы, чтобы определить ключ DES, которым зашифровано другое сообщение . На вид этот протокол может показаться просто усложненным способом бросать "честную" монету по модему, но он интенсивно используется во многих сложных протоколах .

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

В литературе можно найти и другие протоколы рассеянной передачи . Некоторые из них неинтерактивны, т.е. Алиса публикует свои два сообщения, а Боб может прочесть только одно из них . Он может сделать это, когда захочет, ему не нужно для этого связываться с Алисой [105].

В действительности на практике никто не использует протокол рассеянной передачи , но это понятие является важным блоком при построении других протоколов . Хотя существует много типов рассеянной передачи - у меня есть два секрета, а вы получаете один, у меня есть n секретов, а вы получаете один, у меня есть один секрет, который вы получаете с вероятностью 1/2 и так далее - все они эквивалентны [245, 391, 395].

5.6 Рассеянные подписи

Честно говоря, я не могу придумать, чего их можно использовать, но существует два типа рассеянных по д-писей [346]:

1.У Алисы есть n различных сообщений. Боб может выбрать одно из них, чтобы Алиса его подписала, и у Алисы не будет способа узнать, что же она подписала.

2.У Алисы есть единственное сообщение . Боб может выбрать один из n ключей, которым Алиса подпишет сообщение, и Алиса не сможет узнать, какой ключ она использовала .

Идея изящна, я уверен, что где-нибудь она найдет применение .

5.7 Одновременная подпись контракта

Подпись контракта с помощью посредника

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

(1)Алиса подписывает копию контракта и посылает ее Тренту .

(2)Боб подписывает копию контракта и посылает ее Тренту .

(3)Трент посылает сообщение и Алисе, и Бобу, сообщающее, что другой партнер подписал контракт .

(4)Алиса подписывает две копии контракта и посылает их Бобу .

(5)Боб подписывает обе копии контракта, сохраняет одну для себя, и посылает другую Алисе .

(6)Алиса и Боб сообщают Тренту, что у каждого из них есть подписанная обоими партнерами копия контра к-та.

(7)Трент уничтожает свои две копии контракта, с единственной подписью под каждым .

Этот протокол работает, потому что Трент защищает любую из сторон от мошенничества другой . Если Боб попытается отказаться от подписи под контрактом на этапе (5), Алиса может обратиться к Тренту за копией контракта, уже подписанного Бобом . Если Алиса попытается отказаться от подписи под контрактом на этапе (4), Боб может сделать то же самое . Когда Трент сообщает, что он получил оба контракта на этапе (3), Алиса и Боб узнают, что другой партнер уже подписал контракт . Если Трент не получит оба контракта на этапах (1) и (2), он уничтожает имеющуюся у него копию, и ни одна из сторон не связана более обязательствами контракта .

Одновременная подпись контракта без посредника (лицом к лицу)

Если Алиса и Боб встречаются лицом к лицу, они могут подписать контракт следующим образом [1244]:

(1)Алиса пишет первую букву своего имени и передает контракт Бобу.

(2)Боб пишет первую букву своего имени и передает контракт Алисе.


(3)Алиса пишет вторую букву своего имени и передает контракт Бобу.

(4)Боб пишет вторую букву своего имени и передает контракт Алисе.

(5)Это продолжается до тех пор, пока Алиса и Боб не напишут свои имена полностью.

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

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

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

Одновременная подпись контракта без посредника (без личной встречи)

В этом протоколе используется такая же неопределенность [138]. Алиса и Боб по очереди движутся детскими шажками к подписанию протокола.

В этом протоколе Алиса и Боб обмениваются рядом подписанных сообщений вида : "Я согласен, что с вероятностьюp я связан условиями контракта."

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

(1)Алиса и Боб согласовывают дату окончания подписания контракта .

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

(3)Алиса посылает Бобу подписанное сообщение с вероятностью p = а.

(4)Боб посылает Алисе подписанное сообщение с p = а + b.

(5)Пусть p - это вероятность из сообщения, полученного Алисой от Боба на предыдущем этапе . Алиса посылает Бобу подписанное сообщение с p = p + а или 1, смотря что меньше.

(6)Пусть p - это вероятность из сообщения, полученного Бобом от Алисы на предыдущем этапе . Боб посылает Алисе подписанное сообщение с p = p + b или 1, смотря что меньше.

(7)Алиса и Боб продолжают выполнять этапы (5) и (6) до тех пор, пока они оба не получат сообщения с p = l или пока не наступит согласованная на этапе (1) дата .

По мере выполнения протокола и Алиса, и Боб соглашаются, что они оказываются связанными контрактом со все большей и большей вероятностью . Например, Алиса может определить свое а как 2 процента, а Боб свое b - как 1 процент. (Лучше бы они выбрали большие приращения, а то мы застрянем на этом месте.) В первом сообщении Алиса сообщает, что она связана контрактом с вероятностью 2 процента . Боб может ответить, что он связан контрактом с вероятностью 3 процента. Следующее сообщение Алисы может утверждать, что она связ а-на контрактом с вероятностью 5 процента и так далее, пока вероятности обоих не достигнут 100 процентов .

Если и Алиса, и Боб завершили протокол к оговоренной дате, то все прекрасно. В противном случае, любая из сторон может предъявить контракт судье вместе с подписанным последним сообщением другой стороны. Прежде, чем просмотреть контракт, судья случайным образом выбирает число между 0 и 1. Если это число меньше вероятности, подписанной второй стороной, то обе стороны связаны контрактом. Если это число больше вероятности, подписанной второй стороной, то обе стороны не связаны контрактом. (Затем судья сохраняет использованное число на случай решения другого вопроса, касающегося того же контракта .) Именно это и означает "быть связанным контрактом с вероятностью p".

Это базовый протокол, но могут использоваться и дополнительные усложнения . Судья может принимать ре-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203]