Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
26 Системы с секретным ключом
Глава 3
состоящих из восьми символов. В этом случае может случиться так, что в действительности сообщение m окажется слишком длинным, чтобы его можно было расшифровать непосредственно. Если это и в самом деле так, то m нужно разбить на части, а процедуру шифрования Ек применять несколько раз. В дальнейшем мы еще обсудим эту ситуацию в разделе § 5.
Первое требование, которому должна удовлетворять криптосистема с секретным ключом, заключается в том, что криптоаналитик должен быть неспособен воспроизвести открытый текст m (или, что еще хуже, к) из перехваченного шифртекста с=Ек(т). Однако отметим при этом, что криптографическая система, которая невосприимчива даже к такой угрозе, может оказаться слабой при других обстоятельствах. В криптографии с секретным ключом различают три уровня криптографических атак.
• Атака на основе ..только шифртекста: криптоаналитику заданы с\ = Ек(т\), с2 = Ек(т2), ..., с\ = Ek(mi), являющиеся шифртекстами г различных неизвестных открытых текстов сообщений, зашифрованных на одном и том же неизвестном ключе. Он должен определить ключ к или убедиться в своей неспособности это сделать, исходя из такого количества различных открытых текстов mi, т2, ..., ш,-, какое для этого потребуется.
• Атака на основе известного открытого текста: криптоаналитику заданы шифртексты с\, с^, ..., сг такие же, как определены выше, а также соответствующие им открытые тексты mi, тп2, ..., т,-. Он должен либо определить ключ к, либо, убедившись в своей неспособности это сделать, вычислить т,•+! из некоторого нового шифртекста с,+1 = Ек (77}, 1), зашифрованного с использованием того же самого ключа.
• Атака на основе выбранного открытого текста: криптоаналитику предоставляется выбрать несколько сообщений 77ii j ”12, ..., т,- открытого текста и вместе с тем ему передаются соответствующие им шифртексты ci = Ek(mi), С2 = ?>(тп2), ci = Ek{rrii). Криптоаналитик должен либо найти к, либо, убедившись в своей способности это сделать, вычислить tto,-+i из некоторого нового шифртекста
Теория информации 27
Ci+i = Ек(т{+1), зашифрованного с исйользованием того же самого ключа. (Ситуации, в которых может быть проведена подобная мощная атака на основе выбранного открытого текста, существуют в реальной жизни — например, в системах идентификации типа «друг-или-враг» [228].)
Различие в степени действенности этих трех уровней атак лучше всего объяснить при помощи нашего предыдущего примера шифра простой замены. Когда мы говорили, что он является «легким» для криптоанализа, то имели в виду — «легким при атаке на основе только шифртекста». Хотя это и в самом деле так, для подобного криптоанализа все-таки требуется выполнить некоторую работу. Если же проводить атаку на основе известного открытого текста, то раскрытие становится совершенно тривиальным, как только в доступных открытых текстах сообщений встретятся, по крайней- мере по одному разу, все символы алфавита (естественно, при этом достаточно даже всех, кроме одного). А при атаке на основе выбранного открытого текста даже не нужно ничего ждать; ключ (то есть секретная перестановка алфавита) получается тотчас же после того, как становится доступным значение f*(ABCD.. .XYZ).
§ 2. Теория информации
Что же мы подразумеваем под словами: «криптоаналитик должен быть неспособен воспроизвести открытый текст т»? Заслуживает некоторого пояснения, какой смысл вкладывается здесь в слова «неспособен» и «Воспроизвести». При этом с самого начала отметим, что в данном параграфе под криптографической атакой обычно подразумевается атака на основе только щифр-текста.
С точки зрения классической теории информации Клода Шеннона, слово «неспособность» означает «математическую невозможность вне зависимости от доступных ресурсов». Например, предположим, что вы бросаете жребий, но перед тем как самому взглянуть на то, что выпало, «орел» или «решка», просите своего друга случайным образом решить, оставить то, что получилось, или перебросить. Очевидно, что из знания конечного результата такого эксперимента, невозможно определить, каков был первичный исход подбрасывания монеты. (При" этом
28 Системы с секретным ключом
Глава 3
необходимо отметить, что в главе 4, когда мы будем обсуждать криптосистемы с открытым ключом, слово «неспособен» будет иметь совершенно другой смысл.)
Точное смысловое значение слова «воспроизвести» гораздо труднее объяснить без определения важнейших положений теории информации. Относительно формального математического изложения последней мы рекомендуем обратиться к [323, 324, 184]. Окончательная цель криптоаналитика заключается, конечно же, в том, чтобы точно и определенно вычислить ключ к криптосистемы или, хотя бы, какое-то конкретное сообщение m открытого текста. Однако он может быть удовлетворен, узнав даже некоторую вероятностную информацию об т. Уже само предположение о том, что открытый текст некоторого сообщения написан по-английски, предоставляет криптоаналитику определенную априорную информацию об этом сообщении даже до того, как он увидит его шифртекст. Так, например, он заранее знает, что слово «hello» является более вероятным началом сообщения, чем скажем набор букв «xykph». Поэтому текущая цель криптоанализа заключается в том, чтобы посредством изменения вероятностей увеличить количество этой априорной информации, относящейся к каждому возможному сообщению открытого текста, таким образом, чтобы правильный открытый текст сделать более вероятным, хотя, быть может, и не обязательно точным.
