Канал связи продолжает ухудшается: теперь он всецело находиться во власти "плохого мальчика"(см. Приложениеч.IV). Правда, он обещал точно передавать наши сообщения, но у нас нет оснований полностью ему доверять. Следовательно, нам необходимо каким-то образом помечать или удостоверять подлинность наших сообщений, чтобы "плохой мальчик" не мог незаметно подменить подлинное сообщение ложным. Эту задачу проще сформулировать на языке казино, где играют в азартные игры.
Управляющий казино ("плохой мальчик") обманывает владельца казино ("хорошего мальчика"), сообщая тому заниженные сведения о дневной выручке и присваивая себе разницу. Чтобы предотвратить хищение, владелец намеревается установить внутри каждого автомата секретный ключ К и устройство, на вход которого поступает сообщение Х о дневной выручке и ключ К, а на выход метка, удостоверяющая подлинность сведений
Устройство печатает Х и Z на бумажной ленте. "Плохому мальчику" вменяется в обязанность пересылать ленту владельцу казино. Получив ленту, владелец считывает с нее Х, вычисляет Z по известным Х и К и тем самым проверяет, соответствует ли значение Z напечатанным на ленте. Если вычисленное значение совпадает с присланным, то владелец казино считает Х истинным.
С другой стороны, "плохой мальчик" знает Х, Z и Ф ( т.е. уму известно, как работает устройство), но не знает К и хочет подменить Х и Z другой парой Х и Z. Если ему удастся совершить подлог так, что
На рис. 8 показано, как примерно может рассуждать "плохой мальчик". Представлены всевозможные сообщения Х1, Х2, Х3, ... и метки Z1, Z2, Z3, ..., соответствующие различным ключам. Предположим, что "плохой мальчик" видит, что сообщение Х1 сопровождается меткой Z2. Взглянув на схему, он установит, что речь может идти только об одном из ключей 2, 3, 4, 5 или 6. Желая заменить Х1 сообщением Х2, "плохой мальчик" должен решить, какую метку (Z4, Z5 или Z6) ему выбрать. Шанс не быть пойманным у него наибольший, если он выберет метку Z5. Эта метка "согласуется" с ключом 2, 5, 6, т.е. "плохой мальчик" имеет на успех 3 шанса из 5. Если бы он выбрал метку Z4 или Z6, то его шансы на успех составляли бы только 1 из 5.
Как показывает это рассуждение, при проектировании системы, удостоверяющей подлинность сообщений, необходимо стремиться к тому, чтобы каждой паре сообщение -- метка соответствовало большее число
Сообщение ключ (Сообщение, метка)
┌────────────────1────────────────────* (Х1, Z1)
│
│┌───────────────2─────────────────────┐
X1*├───────────────3─────────────────────* (X1, Z2)
│├───────────────4─────────────────────│
│├───────────────5─────────────────────│
│└───────────────6─────────────────────┘
├────────────────7─────────────────────┐
├────────────────8─────────────────────* (X1, Z3)
└────────────────9─────────────────────┘
┌────────────────1────────────────────┐
├────────────────4────────────────────* (X2, Z4)
│────────────────7────────────────────┘
│
│ ┌──────────────2────────────────────┐
│ │ │
X2*─│──────────────5────────────────────* (X2, Z5)
│ │ │
│ └──────────────6────────────────────┘
│────────────────3────────────────────┐
│ │
│────────────────8────────────────────* (X2, Z6)
│ │
└────────────────9────────────────────┘
Рис.8. Соответствие между сообщениями, ключами и метками ключей. Даже в этом случае трудно понизить шансы "плохого мальчика" на успешный подлог.
Теорема 2. Пусть существуют М различных сообщений и N возможных ключей. Если сообщение и ключ выбраны случайным образом, то при оптимальной стратегии "плохой мальчик" может гарантировать себе вероятность успешного подлога не меньше, чем 1/√ N .