Глава 3

Системы с секретным ключом

§ 1. Определения и уровни атак

Криптосистема с открытым ключом состоит из пространства ключей /С и, для каждого к € 1С, из пространства открытых текстов сообщений Мк, пространства шифртекстов сообщений Ск и пары функций Ек-Мк и Dk.Ck- Мк таких, что Dk{Ek(m)) = m для каждого сообщения открытого текста т€Мк-При этом необходимо, чтобы, задаваясь любым ключом к, можно было легко получать эффективные алгоритмы для вычисления Ек и Dk- Криптосистема называется эндоморфной, если Ск=Мк для каждого к.

Для обеспечения секретной связи криптосистема используется следуюпдам образом. Если, например, Алиса и Боб предполагают, что в конечном счете могут установить друг с другом конфиденциальную связь, то с самого начала они должны договориться между собой о некотором совместном секретном ключе fee/С. ТоРда, если в дальнейшем Алиса захочет послать некоторое специальное сообщение т£Мк Бобу, то она, для того чтобы сформировать шифртекст c=ffe(ra), должна использовать алгоритм шифрования Ек; затем ей необходимо будет послать шифр-текст с по незащищенному каналу Бобу; получив этот шифр-текст с. Боб должен использовать алгоритм Dk, чтобы восстановить открытый текст сообщения га= Dfe(c).

Во многих практически используемых криптографических системах и Мк, я Ск - конечные множества, часто не зависящие от самого ключа к. Таково, например, множество всех строк.

состоящих из восьми символов, в этом случае может случиться так, что в действительности сообщение га окажется слишком длинным, чтобы его можно было расшифровать непосредственно. Если это и в самом деле так, то га нужно разбить на части, а процедуру шифрования Ек применять несколько раз. В дальнейшем мы еще обсудим эту ситуацию в разделе § 5.

Первое требование, которому должна удовлетворять криптосистема с секретным ключом, заключается в том, что криптоаналитик должен быть неспособен воспроизвести открытый текст га (или, что еще хуже, к) из перехваченного шифртекста с=Е(т). Однако отметим при этом, что криптографическая система, которая невосприимчива даже к такой угрозе, может оказаться слабой при других обстоятельствах. В криптографии с секретным ключом различают три уровня криптографических атак.

• Атака на основе ..только шифртекста: криптоаналитику заданы Ci = Ekipii), сг = Ek{m2), ..., ci = Ек{т,), являю-пщеся шифртекстами г различных неизвестных открытых текстов сообщений, зашифрованных на одном и том же неизвестном ключе. Он должен определить ключ к или убедиться в своей неспособности это сделать, исходя из такого количества paзJfичныx открытых текстов rai, гаг, ..., га,-, какое для этого потребуется.

• Атака на основе известного открытого текста: криптоаналитику заданы шифртексты Cj, С2, ..., Cj такие же, как определены выше, а также соответствующие им открытые тексты mi, гаг, ..., га,-. Он должен либо определить ключ к, либо, убедившись в своей неспособности это сделать, вычислить га,-+1 из некоторого нового шифртекста с,-+1 = Efc(rai+i), зашифрованного с использованием того же самого ключа.

• Атака на основе выбранного открытого текста: криптоаналитику предоставляется выбрать несколько сообщений mi, гаг, ..., га,- открытого текста и вместе с тем ему передаются соответствуюпще им шифртексты ci = Ek[mi), С2 = Ек(т2), Cl = ffc(mi). Криптоаналитик должен либо найти к, либо, убедившись в своей способности это сделать, вычислить m,+i из некоторого нового шифртекста

с,+1 = £(пг,\(.1), зашифрованного с исйользованием того же самого ключа. (Ситуации, в которых может быть проведена подобная мопдаая атака на основе выбранного открытого текста, существуют в реальной жизни - например, в системах идентификации типа «друг-или-враг» [228].)

Различие в степени действенности этих трех уровней атак лучше всего объяснить при помощи нашего предыдущего примера шифра простой замены. Когда мы говорили, что он является «легким» для криптоанализа, то имели в виду - «легким при атаке на основе только шифртекста». Хотя это и в самом деле так, для подобного криптоанализа все-таки требуется выполнить некоторую работу. Если же проводить атаку на основе известного открытого текста, то раскрытие становится совершенно тривиальным, как только в доступных открытых текстах сообщений встретятся, по крайнеймере по одному разу, все символы алфавита (естественно, при этом достаточно даже всех, кроме одного). А при атаке на основе выбранного открытого текста даже не нужно ничего ждать; ключ (то есть секретная перестановка алфавита) получается тотчас же после того, как становится доступным значение Efe(ABCD.. .XYZ).

§ 2. Теория информации

Что же мы подразумеваем под словами: «криптоаналитик должен быть неспособен воспроизвести открытый текст га»? Заслуживает некоторого пояснения, какой смысл вкладывается здесь в слова «неспособен» и «Воспроизвести». При этом с самого начала отметим, что в данном параграфе под криптографической атакой обычно подразумевается атака на основе только шифр-текста.

С точки зрения классической теории информации Клода Шеннона, слово «неспособность» означает «математическую невозможность вне зависимости от доступных ресурсов». Например, предположим, что вы бросаете жребий, но перед тем как самому взглянуть на то, что выпало, «орел» или «решка», просите своего друга случайным образом решить, оставить то, что получилось, или перебросить. Очевидно, что из знания конечного результата такого эксперимента, невозможно определить, каков был первичный исход подбрасывания монеты. (Приэтом