Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Рассмотрим ситуацию, при которой криптоаналитик перехватил шифртекст «xtj ja» и знает (или предполагает), что он был зашифрован с использованием шифра простой замены. Этот шифртекст говорит ему о том, что открытый текст сообщения состоит из пяти букв, третья и четвертая из которых являются одной и той же, а все остальные отличными от нее и разными. Он не может считать, что открытый текст — это слово «hello», потому что это также могло бы быть, например, и слово «teddy». Тем не менее апостериорные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. Криптоаналитик,, кроме этого, совершенно уверен (в предположении, что он прав относительно характера криптосистемы) в том, что этот открытый текст не может быть ни словом «peace», ни словом «гатЪо», и, таким образом, апостериорная вероятность обоих этих открытых текстов сокраща-
Теория информации 29
ется до нуля даже вне зависимости от их априорной вероятности.
Шеннон называет криптографическую систему совершенно секретной, если, каким бы ни был зашифровываемый с ее помощью открытый текст, знания, которые могут быть получены из соответствующего ему шифртекста, не раскрывают никакой информации об исходном тексте, за исключением, возможно, его длины. Другими словами, в подобных системах апостериорные вероятности открытых текстов даже после просмотра шифрованных текстов остаются точно такими же, какими были их априорные. вероятности. Совершенно секретные системы действительно существуют [352], и может показаться странным, почему .они не являются панацеей для всех криптографических потребностей. Имеются три основных причины, объясняющих такое положение дел.
• Как и любые криптосистемы с секретным ключом, совершенно секретные системы предполагают, что проблема распределения ключей уже решена.
• Трудность проблемы распределения ключей еще больше усугубляется в связи с тем, что согласно теореме Шеннона соблюдение совершенной секретности возможно только тогда, когда ключевое пространство является, по крайней мере, таким же большим, как и пространство открытых текстов сообщений (что в свою очередь позволяет утверждать, что секретный ключ должен иметь по крайней мере такую же длину, как и само сообщение), и только если один и тот же ключ не используется при шифровании более одного раза.
• Третий недостаток совершенно секретных криптосистем состоит в том, что они (как описано в § 5.1) могут играть лишь незначительную роль для целей аутентификации.
Несмотря на это, совершенно секретные криптографические системы используются на практике в самых ответственных приложениях, наподобие «красного телефона» между Москвой и Вашингтоном.
Совершенная секретность может быть достигнута следующим образом. Пусть т — это открытый текст некоторого сообщения,
30 Системы с секретным ключом
Глава 3
например, «hello». Одноразовым шифром к сообщения m называется полученная совершенно случайным образом строка,симт волов, в точности такой же длины, как и т, например «iwpbu». Шифрование сообщения т с использованием ключа к очень похоже на то, которое применялось в нашем первом обобщении криптосистемы с использованием шифра Юлия Цезаря, и было описано в главе 2, за исключением того, что число позиций букв в алфавите, на которое в этом случае нужно сдвинуться, чтобы вместо очередного символа открытого текста получить соответствующий символ шифртекста, не является постоянной величиной. В нашем примере буква «h» открытого текста т должна быть заменена на букву «q», являющуюся девятым после «h» символом английского алфавита, потому что соответствующий символ ключа к — буква «i» — девятый символ этого алфавита. Аналогично, буква «е», циклически сдвигаясь на 23 позиции (в соответствии с положением символа «и» ключа в алфавите), становится буквой «Ь». Если продолжать далее таким же образом, то в результате мы получим шифртекст «qbbnj». Обратите внимание, что третий и четвертый символы открытого текста являются идентичными, что не так, если посмотреть на соответствующие символы шифртекста, в то время как, напротив, второй и третий символы в шифртексте одинаковы. .
Открытый текст «hello» может быть легко восстановлен из шифртекста «qbbnj» при условии, что ключ «iwpbu», который используется для шифрования, известен. Однако без этой информации при помощи соответствующего ключа произвольный шифртекст может быть дешифрован в любые пять символов открытого текста. Например, «qbbnj» можно дешифровать в «реасе», используя ключ «awake». Здесь решающим для понимания является то, что если ключ действительно выбирается наугад, как это и должно быть, то оба ключа, «iwpbu» и «awake», будут абсолютно равновероятными, даже несмотря на то, что один из них случайно оказался осмысленным словом английского языка. Это иллюстрирует важность требования, согласно которому ключ должен выбираться случайным образом. Фактически, если известно, что и ключ, и открытый текст должны быть словами английского языка, то для того чтобы эффективно восстановить и тот и другой из имеющегося шифрованного текста, обычно бывает достаточно его отрезка, длиной в несколько
