Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Gilles Brassard Брюссель, апрель 1988
2 Летом 1994 года в ответ на вопрос, «набрался ли он храбрости», а если да, то когда можно ожидать выход в свет этого учебника, Жиль ответил мне, что уже оставил свою затею, так как «за него» такой учебник написал Дуглас Стинсон [341] (это и все дальнейшие подстрочные примечания в книге принадлежат переводчику).
Глава 1
Введение
«Тот, кто записывает свои секреты таким способом, который не позволяет скрывать их от посторонних — сумасшедший.» [12]
— Роджер Бэкон, около 1250 г.
На протяжении тысячелетий криптография была искусством засекречивания важной государственной информации при передаче ее по незащищенным каналам связи, а криптоанализ был двойственным криптографии искусством раскрытия такой информации. Поэтому криптология, объединяющая в себе криптографию и криптоанализ, исторически ранее находилась почти исключительно в руках военных и дипломатических ведомств. Однако в нынешний период осуществления во всем мире компьютерной революции, когда огромное количество персональной, финансовой, коммерческой и технологической информации хранится в компьютерных банках данных и пересылается по информационным компьютерным сетям, чрезвычайно важным является то обстоятельство, что в обществе появляется острейшая потребность в гражданской криптографии. Отражением этого факта служат слова Дэвида Кана: «Криптография, в 1945 году тесно связанная с сохранением национальных секретов, стала теперь общедоступной» [229]. (См. также [239, 240, 241, 280].)
Кто же, в конце концов, может рассчитывать на победу в этом многовековом ноединке между криптографией и крипто-
16 Введение
Глава 1
анализом? Великие, умы (хотя и не специалисты) прошедших веков расходятся во мнениях. В 1769 году в своем Философском словаре (Dictionnaire philosophique) Вольтер писал: «Сеих qui se vantent de lire les lettres chiffrees sant de plus grands charlatans que ceux qui se vanteraieat d’entendre une langue qu’ils n’ont point apprise» [353] (что на русском соответствует примерно следующему: «... не зная законов языка ирокезского, можешь ли ты делать такое суждение по сему предмету, которое было бы неосновательно и глупо?»1). Противоположное мнение высказал Эдгар По в своем знаменитом рассказе Золотой жук (1843): «.. .едва ли разуму человека дано загадать такую загадку, которую разум его собрата, направленный должным образом, не смог бы раскрыть.» [287]2.
В настоящее время совершенно очевидно, что Вольтер был неправ, поскольку большинство известных из истории криптосистем были полностью раскрыты, причем иногда с очень интригующими последствиями [228]. С другой стороны, существуют криптографические системы, относительно которых было доказано, что независимо от «изобретательности» криптоаналитиков или мощности используемых при криптоанализе вычислительных средств они останутся нераскрываемыми (таким является, например, одноразовый шифр, который рассматривается в § 3.2). Однако по прежнему открытым остается тот же самый вопрос для широко применяемых сейчас на практике криптосистем с открытым ключом (они являются предметом темы, которая обсуждается в главе 4). В настоящее время существует убеждение в том, что засвидетельствованное в самые последние годы этого столетия увеличение мощностей вычислительных средств создает в высшей степени благоприятные условия для криптографов и в свою очередь наносит ущерб криптоаналитикам. Сложившееся положение можно считать иронией судьбы, потому что Колосс (Colossus), хронологически будучи самой первой электронно-вычислительной машиной, разрабатывался специально для криптоанализа шифров фашистской Германии [202, 302]. (Брайан Рэндел, как уже сообщалось, однажды
1 Козьма ПРУТКОВ, Сочинения, Художественная литература, М, 1974, стр.128.
2 Цитата здесь приводится в переводе А. С тар дева по русскому изданию [287, стр. 184].
Введение 17
сказал по этому поводу: «По моим подсчётам, ENIAC был не первым компьютером, а одиннадцатым.» [372].) Таким образом, можно сказать, что криптоанализ, который, по меткому выражению Рональда Л. Ривеста, является «повивальной бабкой всей информатики» [306], по всей видимости, уже породил орудие для своей собственной погибели!
До недавнего времени предполагаемая надежность криптографической системы оценивалась количеством усилий, потраченных квалифицированными криптоаналитиками при неудачных попытках ее раскрытия. История доказала явную неправомерность такого подхода к оценке стойкости, поскольку сообщения, зашифрованные с помощью криптосистем, которые их пользователи считали нераскрываемыми, впоследствии, как правило, расшифровывались. Раскрытие Энигмы (Enigma) союзниками во время (или даже до) Второй мировой войны — простейший пример подобной ситуации [187, 303]. Читателю, интересующемуся историческим значением криптологии, мы рекомендуем прочитать замечательный обзор Кана [228]3, а также другие популярные книги, такие как [367, 99, 187, 230, 140, 362].
