16 Введение Глава 1

сшализом? Великие, умы (хотя и не специалисты) прошедших веков ре1Сходятся во мнениях. В 1769 году в своем Философском словаре (Dictionnaire philosophique) Вольтер писал: «Сеих qui se vantent de lire les lettres chiffrees sant de plus grands charlatans que ceux qui se vanteraieat dentendre une langue quils nont point apprise* [353] (что на русском соответствует примерно следующему: «... не зная законов языка ирокезского, можешь ли ты делать такое суждение по сему предмету, которое было бы неосновательно и глупо?»). Противоположное мнение высказал Эдгар По в своем знаменитом рассказе Золотой жук (1843): «.. .едва ли разуму человека дано загадать такую загадку, которую разум его собрата, направленный должным образом, не смог бы раскрыть.» [287].

В настоящее время совершенно очевидно, что Вольтер был неправ, поскольку большинство известных из истории криптосистем были полностью раскрыты, причем иногда с очень интригующими последствиями [228]. С другой стороны, существуют криптографические системы, относительно которых было доказано, что независимо от «изобретательности» криптоаналити-ков или мощности используемых при криптоанализе вычислительных средств они останутся нераскрываемыми (таким является, например, одноразовый шифр, который рассматривается в § 3.2). Однако по прежнему открытым остается тот же самый вопрос для широко применяемых сейчас на практике криптосистем с открытым ключом (они являются предметом темы, которая обсуждается в главе 4). В настоящее время существует убеждение в том, что засвидетельствованное в самые последние годы этого столетия увеличение мощностей вычислительных средств создает в высшей степени благоприятные условия для криптографов и в свою очередь наносит ущерб крипто-аналитикам. Сложившееся положение можно считать иронией судьбы, потому что Колосс (Colossus), хронологически будучи самой первой электронно-вычислительной машиной, разрабатывался специально для криптоанализа шифров фашистской Германии [202, 302]. (Брайан Рэндел, как уже сообщалось, однажды

Козьма Прутков, Сочинения, Художественная литература, М, 1974, стр. 128.

Цитата здесь приводится в переводе А. Старцева по русскому изданию [287, стр. 184].

Введение 17

сказал по этому поводу: «По моим подсчетам, ENIAC был не первым компьютером, а оди)анадцатым.» [372].) Таким образом, можно сказать, что криптоанализ, который, по меткому выражению Рональда Л. Ривеста, является «повивальной бабкой всей информатики» [306], по всей видимости, уже породил орудие для своей собственной погибели!

До недавнего времени предполагаемая надежность криптографической системы оценивалась количеством усилий, потраченных квалифицированными криптоаналитиками при неудачных попытках ее раскрытия. История доказала явную неправомерность такого подхода к оценке стойкости, поскольку сообщения, зашифрованные с помощью криптосистем, которые их пользователи считали нераскрываемыми, впоследствии, как правило, расшифровывались. Раскрытие Энигмы (Enigma) союзниками во время (или даже до) Второй мировой войны - простейший пример подобной ситуации [187, 303]. Читателю, интересующемуся историческим значением криптологии, мы рекомендуем прочитать замечательный обзор Кана [228], а также другие популярные книги, такие как [367, 99, 187, 230, 140, 362].

В нынешнем столетии математики занимались нахождением объективных критериев надежности криптографических систем, трансформировав таким образом это древнее искусство в точную науку. Свою теорию информации, которая была опубликована в [323], Клод Шеннон создал в результате работы над другой более ранней (и первоначально засекреченной) статьей в области криптографии [324]. Для самых различных криптографических систем он смог получить верхнюю оценку на длину шифртекста, которую необходимо учитывать для того, чтобы при криптоанализе достичь любого требуемого уровня достоверности его раскрытия. В связи с этим, например, Иб Мельхиор, если бы только он был знаком с теорией Шеннона, мог бы вообще не ездить в Эльсинор, когда решил, что якобы расшифровал секрет11ую эпитафию на надгробном камне Шекспира, которая, как ему казалось, раскрывала тайну существования первого издания «Га-мдета» [228, стр.750].

Б прошедшем десятилетии специалисты по компьютерным

* На русском языке имеется книга: СОБОЛЕВА Т. А., Тайнопись в истории России. (История криптографической слуокбы в России XVIII - начала XX в.), М., «Международные отношения», 1994.

18 Введение Глаеа 1

наукам работали над обоснованием надежности криптографии исходя из более современной теории вычислительной сложности, а не из шенноновской теории информации [157, 265], результаты и выводы которой использовались ранее. Коренное различие между ними заключается в том, что при использовании теории Шеннона криптограф уповает на то, что криптоаналитик не будет располагать достаточной информацией для того, чтобы дешифровать криптограмму, в то время как, основываясь на теории вычислительной сложности, криптограф расчитывает только на то, что у криптоаналитика не хватит времени, чтобы это сделать.

Цель настоящей книги состоит в том, чтобы дать краткий обзор недавних криптографических достижений и методов, а также их многочисленных настояпщх, а возможно и будущих, применений. От читателя не предполагается никакой специальной подготовки. Несмотря на то, что освещение некоторых тем по необходимости будет кратким, в книге приводится обширный (но, конечно, далеко не исчерпывающий) список литературы. В дополнение к историческим книгам, упомянутым ранее, доступны, кроме того, книги более технического характера, такие как [181, 242, 268, 142, 136, 244, 344, 293, 341] и, наконец, некоторые популярные статьи [227, 175, 185, 214, 332, 70], а также специальные обзорные статьи [159, 326, 249, 10, 246, 93, 208, 306] и сборник [333].

* Заслуживают особого внимания также фундаментальная недавно изданная книга Менезеса, Ооршота и Ванстоуна [263] и более практическая, вышедшая вторым изданием, книга Брюса Шнайера [312];