Введение в криптографию
[an error occurred while processing this directive]

Введение


Рассмотрим следующую, в наше время вполне реальную ситуацию. Два совладельца драгоценности хотят положить ее на хранение в сейф. Сейф современный, с цифровым замком на 16 цифр. Так как совладельцы не доверяют друг другу, то они хотят закрыть сейф таким образом, чтобы они могли открыть его вместе, но никак не порознь. Для этого они приглашают третье лицо, называемое дилером, которому они оба доверяют (например, потому что оно не получит больше доступ к сейфу). Дилер случайно выбирает 16 цифр в качестве ``ключа'', чтобы закрыть сейф, и затем сообщает первому совладельцу втайне от второго первые 8 цифр ``ключа'', а второму совладельцу втайне от первого - последние 8 цифр ``ключа''. Такой способ представляется с точки здравого смысла оптимальным, ведь каждый из совладельцев получил ``полключа'' и что может быть лучше?! Недостатком данного примера является то, что любой из совладельцев, оставшись наедине с сейфом, может за пару минут найти недостающие ``полключа'' с помощью несложного устройства, перебирающего ключи со скоростью 1МГц. Кажется, что единственный выход - в увеличении размера ``ключа'', скажем, вдвое. Но есть другой, математический выход, опровергающий (в данном случае - к счастью) соображения здравого смысла. А именно, дилер независимо выбирает две случайные последовательности по 16 цифр в каждой, сообщает каждому из совладельцев втайне от другого ``его'' последовательность, а в качестве ``ключа'', чтобы закрыть сейф, использует последовательность, полученную сложением по модулю 10 соответствующих цифр двух выбранных последовательностей. Довольно очевидно (и ниже мы это докажем), что для каждого из совладельцев все возможных ``ключей'' одинаково вероятны и остается только перебирать их, что потребует в среднем более полутора лет для устройства, перебирающего ключи со скоростью 100МГц.

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]