Инварианты Огюста Керкхоффа

Великими в истории любой науки могут быть названы лишь несколько книг. Некоторые из них содержат технические инновации, радикально изменяющие содержание науки. Двумя книгами такого типа до XIX века стали работы Альберти [1] и Касиски [2]. Эти книги обращены внутрь.
Другие великие книги обращены наружу. Они подтягивают науку к требованиям времени и, таким образом, вновь делают ее полезной человеку. <...> В течение трехсот лет единственной великой книгой такого типа в криптологии был труд Порта [3]. <...> Второй такой книгой стала в 1883 году. "La cryptographie militaire" (автором которой является Огюст Керкхофф. - М.О.). <...>
"La cryptographie militaire"... является, возможно, самой великой книгой по криптологии.
Дэвид Кан. "Кодоломы" [4]

   Огюст Керкхофф - "культурный герой" в истории криптологии, из тех, на кого любят ссылаться в подстрочных примечаниях, но редко читают.

   Густавус Симмонс (Gustavus J. Simmons), известный военный криптограф, участник проекта обеспечения безопасности систем ядерного вооружения, просто не считает нужным упомянуть о Керкхоффе в своей пространной статье "Криптология" в "Британнике". Дэвид Кан (David Kahn), самый авторитетный историк криптографии, восторженно (см. эпиграф) отзывающийся о вкладе Керкхоффа, ограничивается несколько вольным пересказом его работы, после чего, кажется, забывает о нем (и его принципах) до конца своего тысячестраничного исследования.

   Единственная книга Керкхоффа о криптографии - "Военная криптография" ("La cryptographie militaire") - давно стала библиографической редкостью [5] и до сих пор не переиздавалась, не говоря уже о научном комментированном издании.

   Дело не в "исторической справедливости". Дело в том, что просвещенного профессионализма быть не может без знания (и понимания) истории своей области. Криптология и криптография переживают сейчас определенную смену парадигмы, начавшуюся с того, что основными потребителями криптографии стали гражданские организации и частные лица. Смена контекста применения не только изменяет требования к системе знаний, но и сдвигает фокусы и приоритеты практической инженерии.

   Эта смена парадигмы - не первая в истории криптологии. Важнейшим периодом в развитии дисциплины стала вторая половина прошлого века, когда появление и широкое распространение телеграфной связи образовало новое поле применения криптографических приемов и технологий. Именно к этому периоду относится возникновение "полевых шифров", специфика которых наиболее ярко отмечена в творчестве Керкхоффа.

Огюст Керкхофф

width=152

   Огюст Керкхофф (Jean-Guillaume-Hubert-Victor-Franзois-Alexandre-Auguste Kerckhoffs von Nieuwenhof) родился в 1835 году в Нуте, в зажиточной и одной из самых знатных семей Фламандского герцогства Лимбург. Окончил церковную школу под Ахеном, полтора года изучал английский в Британии, затем завершил образование в Университете Льежа, получив две магистерские степени: по естественным наукам и словесности.
   Преподавал современные языки в школах Голландии, затем заведовал кафедрой в Мелю (1863-73 гг.). С 1873 года Керкхофф - французский подданный. В 1873-76 гг. готовит и защищает докторскую диссертацию в Германии, одновременно служа тьютором юного графа де Сано Мамеде (впоследствии секретаря португальского короля).
   В 1876-81 гг. работает учителем в семье де Сано Мамеде. В 1881-91 гг. - профессор немецкого языка в Высшей коммерческой школе и в Эколь Араго.
   Среди трудов Керкхоффа - фламандская грамматика, английская грамматика, справочник немецких пословиц, лингвистические, историко-филологические работы. Керкхофф активно участвовал в общественной жизни: он основал Общество содействия просвещению в Мелю, был членом Французского общества археологии, возглавлял Международную академию воляпюка и Французскую ассоциацию пропаганды воляпюка, был командиром католического Ордена Христа.
   Огюст Керкхофф умер в 1903 году в Швейцарии, его прах покоится на Монпарнасском кладбище в Париже.

   Криптография и рождение Киберпространства
   Середина XIX века. В более или менее либеральных демократиях и просвещенных монархиях постепенно укореняются принципы гражданских прав и свобод. Эпоха правительственных "черных палат", перлюстрирующих всю международную и значительную часть внутренней переписки в европейских странах, закончилась, казалось бы, навсегда.

   "Мир и процветание" (со всеми оговорками, вроде франко-прусской войны) постнаполеоновской эры, однако, больно ударили по криптологии как науке и профессии. Ведь "черные кабинеты" - "СОРМ" XVII-XVIII вв. - были единственным местом профессиональной практики криптоаналитиков, и само их наличие держало в форме криптографов.

   Но на протяжении XIX столетия изменения в двух областях человеческой деятельности - связи и военном искусстве - создали предпосылки для возрождения интереса к криптологии.

   Три года назад один из основателей Фонда электронных рубежей (Electronic Frontier Foundation) Джон Барлоу (John Perri Barlow) в ответ на наш вопрос о том, что он считает своим самым выдающимся достижением, довольно неожиданно ответил, что больше всего гордится тем, что ввел в начале девяностых в широкое употребление слово "киберпространство", придуманное фантастом Уильямом Гибсоном (William Gibson). Барлоу имел в виду, в основном, телефонные сети, поверх которых энтузиасты плели тогда сети компьютерные.

   Если Барлоу прав, то первой ниточкой из образующих сегодня Киберпространство мириадов связей, была, конечно же, не телефонная, а телеграфная линия, по которой Самуэль фон ЗЈммерринг (Samuel Thomas von Sцmmerring) осуществил в 1809 году в Мюнхене первый в истории сеанс цифровой (дискретной) телекоммуникации. Тридцатью годами позже его тезка Морзе (Samuel Morse) довел телеграф до ума, и спрос на новомодное изобретение не заставил себя ждать.

   Телеграф сделал мир связи, обслуживаемый прежде почтовыми курьерами, очень маленьким. И очень опасным: для того чтобы сунуть нос в чужие дела, уже не нужно было перехватывать и отпаривать конверты, рискуя оставить следы; достаточно стало присоединиться к кабелю в любой точке. Таким образом, массовая электрическая связь не могла обеспечить конфиденциальность, что всерьез заботило широко пользовавшихся ею коммерсантов, а для дипломатов и военных "прозрачность" телеграфа была серьезным препятствием к его использованию.

   А военным очень хотелось. Происшедшие изменения в стратегии и тактике боевых действий исключали непосредственное руководство армиями - военачальнику теперь приходилось командовать из штаба в тылу, опираясь на сведения, доставляемые курьерами, и таким же образом отдавая приказы своим частям.

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

   Гуманитарий примеряет мундир
   Свести воедино стратегические и технологические инновации своего времени и понять, как они изменяют задачу криптографа, смог Керкхофф.

   Не вполне понятно, что заставило уже известного к тому времени лингвиста и интерлингвиста (см. биографию во врезке), гуманиста, космополита и сторонника развития международной торговли и мирного сосуществования наций6, почти в пятидесятилетнем возрасте обратиться к теме секретных военных коммуникаций. Можно было бы предположить в качестве причины франко-прусскую войну 1870-71 гг., однако известно, что еще десятью годами ранее он претендовал на кафедру немецкого языка в Высшей военной школе в Париже и не прошел конкурс лишь по недоразумению.

   Тем обиднее, наверное, было читать искушенным в своем ремесле генералам и военным ученым в опубликованной в январском выпуске 1863 года "Журнала военных наук" первую главу работы Керкхоффа, называющуюся "Криптография на военной службе" ("La cryptographie dans l'armйe"):

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

   Далее на протяжении шестидесяти с лишним страниц Керкхофф дает сводку основных криптографических и криптоаналитических приемов, известных к тому времени, добавляя к последним два разработанных им самим: прием суперимпозиции шифровок, позволяющий "ломать" полиалфавитные криптосистемы с многократно используемым ключом, и прием определения скрытой симметрии позиций, оба из которых остаются важными средствами в арсенале современного криптоанализа. Характерно, что приемы криптоанализа Керкхофф демонстрирует на примерах реально используемых в его время шифров.

   Керкхофф также популяризовал использование "криптографических линеек" ("шифра Сен-Кюра") и показал их (и известных с эпохи Возрождения "шифровальных дисков") теоретическую эквивалентность табличной форме шифра Виженера.

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

   Словарик

   Ключ - число, используемое в криптографическом алгоритме для шифрования/расшифровки или наложения/проверки цифровой подписи. В криптографии с открытым ключом каждый коммуникант генерирует себе пару ключей: открытый (который передается другим коммуникантам или публикуется) и закрытый (который остается персональным секретом коммуниканта). В криптографии с секретным ключом два или более коммуниканта пользуются одним и тем же ключом.
   Криптоанализ - искусство нахождения и эксплуатации нестойких элементов в криптосистемах.
   Криптография - инженерная дисциплина, занятая разработкой и реализацией стойких протоколов коммуникации. Основной сферой применения современной криптографии является обеспечение защиты целостности, аутентичности и конфиденциальности электронных сообщений, например, в системах электронной почты, цифровой телефонии и т. д.
   Криптография с открытым ключом (асимметричная криптография) - криптографические технологии, позволяющие использовать для шифрования и расшифровки (или для наложения и проверки электронной подписи) два различных, но связанных между собой ключа. Криптография с открытым ключом решает "проблему распределения ключей", поскольку закрытый (private) ключ, который используется для наложения подписи и расшифровки, владельцу не нужно никому передавать, а открытый (public) ключ, используемый для шифрования и проверки подписи, не нужно держать в секрете.
   Криптография с секретным ключом (симметричная криптография) - традиционные криптографические технологии, в которых для шифрования и расшифровки используется один и тот же ключ, его копиями должны обладать оба коммуниканта. В современных криптосистемах используется обычно вместе с криптографией с открытым ключом.
   Криптология - раздел прикладной математики, изучающий стойкость протоколов коммуникации.
   Криптосистема - набор алгоритмов и протоколов, стойких к попыткам несанкционированного вмешательства с целью нарушения конфиденциальности или целостности сообщений.
   Шифр Вернама ("одноразовый шифр", "шифр длинной ленты") - криптосистема с секретным ключом, представляющим собой случайный массив, равный по длине шифруемому тексту. Разработан американским инженером Гилбертом Вернамом (Gilbert S. Vernam) в 1917 году. Шифр Вернама является теоретико-информационно стойким и не может быть "взломан" даже при неограниченной вычислительной мощности, которой располагает оппонент.
   Шифрование - преобразование информации с целью защитить ее конфиденциальность. Обратная шифрованию операция, выполняемая в рамках криптопротокола, называется расшифровкой. Попытки выполнить обратную операцию оппонентом за рамками криптопротокола называется дешифровкой.

   Принципы & desiderata
   Керкхофф, анализируя плачевное состояние теории и практики криптографии, выделяет два принципа организации криптоинженерии и шесть требований (desiderata) к криптографическим системам.

   Первый принцип можно назвать принципом массового применения шифрования. "Следует различать, - пишет Керкхофф, - систему шифрования, предназначенную для обмена время от времени письмами между несколькими изолированными лицами, и криптографический метод, защищающий постоянную корреспонденцию между несколькими военачальниками в течение неограниченного времени".

   Массово применяемые в военном деле шифры Керкхофф назвал "полевыми шифрами".

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

   На основании этих принципов Керкхофф и сформулировал систему требований к "полевым шифрам" (см. врезку).

   Актуален ли Керкхофф?
   Публикация Керкхоффа была "чистым экспериментом": насколько нам известно, Керкхофф не привлекался к практическому военному криптоанализу или разработке криптосистем; нет данных и о том, что он когда-либо преподавал криптологию. В истории этой науки он останется просвещенным дилетантом и автором одной работы. Работы, с которой начинается систематическая французская (и, возможно, англосаксонская) традиция академической криптологии. Работы, принципы которой проигнорировали немцы со столь фатальным исходом в эпоху мировых войн.

   Актуален ли "военный" Керкхофф сегодня, когда основные криптографические приложения - гражданские, и спустя четверть века после того, как криптография с открытым ключом решила "проблему распределения ключей"?

   Мы полагаем, что "полевые шифры" Керкхоффа, которые он выделил в первом своем принципе и по отношению к которым вводил свои требования, - лишь частный пример того, что можно назвать "абонентской криптографией" - открытыми криптографическими технологиями, реализованными в устройствах (и, разумеется, в программном обеспечении), находящихся под контролем пользователя и эксплуатируемых им в своих интересах. Подавляющее большинство гражданских криптографических приложений относится к "абонентской криптографии".

   Мы возьмем на себя смелость попытки (возможно, несколько наивной) нового "перевода" или интерпретации требований Керкхоффа применительно к эпохе развитого Киберпространства.

   1. Практическая стойкость
   Сегодня в результате систематического применения к криптологическим проблемам традиционных (таких как теория чисел, статистика) и относительно новых (теория сложности, теория алгоритмов) разделов математики, мы можем говорить о мере стойкости.

   Поскольку строгих доказательств стойкости для практически используемых криптоалгоритмов пока не построено, такую меру (эффективную длину ключа, или размер пространства перебора) следует интерпретировать скорее как коллективную экспертную оценку стойкости алгоритма, даваемую криптологическим сообществом (см. второй принцип Керкхоффа). Исключением является непрактичный (в массовых системах) "шифр Вернама", стойкость которого доказана теоретико-информационным путем.

   Таким образом, требование практической стойкости распадается на два.

   1.1. В отношении криптоалгоритма (криптосистемы) должна существовать коллегиальная и основанная на продолжительном опыте криптоанализа уверенность в том, что его стойкость не ниже заявленной.

   1.2. Заявленная стойкость должна обеспечивать вычислительную невозможность (infeasibility) практического криптоанализа. Опыт показывает, что оценки достаточной заявленной стойкости на основании прогнозов роста вычислительной мощности, которой обладает человечество, неизменно оказываются чрезмерно оптимистичными; более надежны физические границы (количество доступного вещества и энергии), что и подняло планку считающихся ныне "безопасными" длин ключей до сотен бит для симметричных алгоритмов и тысяч бит - для асимметричных.

   2. Открытость
   Требование "пассивной" открытости ("доступ к ней противника не должен влечь неприятных последствий") в свете первого принципа Керкхоффа постепенно было радикализовано и превратилось в требование "активной" открытости. Его можно сформулировать следующим образом.

   2.1. Криптосистема (включающая спецификации алгоритмов и форматов) должна быть полностью открыта для поощрения академического криптанализа и получения эмпирических свидетельств ее стойкости.

   2.2. Требование 2.1 справедливо для всех используемых сегодня криптографических алгоритмов (как симметричных - с секретным ключом, так и асимметричных - с открытым ключом; как обеспечивающих конфиденциальность - шифры, так и обеспечивающих целостность - цифровые подписи и коды аутентификации), за исключением теоретико-информационно стойкого шифрования ("шифра Вернама"). Оно будет сохраняться в силе до получения теоретически строгих доказательств стойкости используемых алгоритмов.

   3. "Компактность" персонального ключа
   3.1. Современные криптографические технологии, и прежде всего криптография с открытым ключом, наибольшее значение имеют именно для третьего из desiderata Керкхоффа, то есть требования "компактности" ключа. Благодаря криптографии с открытым ключом проблема распространения ключей снята. Секретные ключи используются сегодня в основном в "гибридных" схемах в форме одноразовых сеансовых ключей, которые сами передаются только в зашифрованном виде.

   3.2. Однако "компактность" нужна не только для передачи ключа, но и для его запоминания. Идеальной следовало бы считать ситуацию, когда закрытый ключ хранится только в памяти его владельца. Однако, к сожалению, практическая стойкость закрытых ключей превалирующих сегодня систем (RSA и ElGamal) начинается от длин порядка 2 кбит. 2 килобита - это 128 шестнадцатеричных цифр; возможно, чтобы запомнить число такой длины, и не нужно обладать феноменальной памятью, но требуемые для этого способности явно выше среднего.

   3.3. На практике "персональным ключом последней инстанции" становится либо мнемонический пароль (с риском выбора пользователем пароля на многие порядки менее стойкого, нежели ключ), либо мобильный компонент ("таблетка", "ключик" и т. п.), в который зашит ключ (с риском утраты и компрометации ключа вследствие утери этого компонента), либо биометрическая процедура (с целым набором специфических рисков), либо комбинация перечисленного.

   3.4. "Компактность" персонального ключа в смысле его непосредственной доступности пользователю видится нам на сегодняшний день скорее исследовательской и инженерной проблемой, нежели областью готовых решений.

   4. Совместимость со стандартными системами коммуникаций
   Требование совместимости со стандартными системами цифровых телекоммуникаций (во времена Керкхоффа это означало телеграф) кажется очевидным. Сегодня "стандартные системы" должно, видимо, означать преобладающую "слоеную" модель сетей, в OSI/ISO-варианте или в версии стандартов Internet. Конкретная криптосистема, если ее разработчики надеются увидеть ее воплощенной и применяющейся на практике, должна специфицировать слой или слои (меж)сетевого взаимодействия, в которых она оперирует.

   5-6. Автоматизация и прозрачность
   Пятое требование сводится сегодня, на наш взгляд, к требованию максимальной автоматизации исполнения криптопроцедур. Криптографическое оборудование и обеспечение должны быть "прозрачны" для конечного пользователя. Наилучшим образом требования автоматизации и прозрачности удовлетворяются решениями, интегрирующими криптофункциональность в пользовательское коммуникационное оборудование/обеспечение.

   Таким образом, с течением времени desiderata, выдвинутые Керкхоффом, не потеряли своей актуальности. Мы не видим ни малейшей возможности отбросить ни одно из них.
   Более того, некоторые из них (например, первое и второе, а также третье, пятое и шестое) оказываются связанными и взаимозависимыми. Иными словами, система desiderata сегодня выглядит "системнее", чем раньше.

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

Desiderata Керкхоффа

   1 Le systиme doit кtre matйriellement, sinon mathйmatiquement, indйchiffrable;
   2 Il faut qu'il n'exige pas le secret, et qu'il puisse sans inconvйnient tomber entre les mains de l'ennemi;
   3 La clef doit pouvoir en кtre communiquйe et retenue sans le secours de notes йcrites, et кtre changйe ou modifiйe au grй des correspondants;
   4 Il faut qu'il soit applicable а la correspondance tйlйgraphique;
   5 Il faut qu'il soit portatif, et que son maniement ou son fonctionnement n'exige pas le concours de plusieurs personnes;
   6 Enfin, il est nйcessaire, vu les circonstances qui en commandent l'application, que le systиme soit d'un usage facile, ne demandant ni tension d'esprit, ni la connaissance d'une longue sйrie de rиgles а observer.

   1 Система должна быть невзламываема практически, если не математически;
   2 Она не должна требовать секретности, и доступ к ней противника не должен влечь неприятных последствий;
   3 Ключ должен быть передаваем в процессе коммуникации и запоминаем без помощи письменных знаков, а также подлежать изменению или модификации по решению коммуникантов;
   4 Она должна быть применима в телеграфной коммуникации;
   5 Она должна быть портативной, а ее обслуживание и функционирование не должно требовать усилий нескольких людей;
   6 Наконец, в том, что касается условий применения, необходима простота системы в использовании и ее нетребовательность к напряжению мысли или запоминанию длинных правил применения, которые необходимо соблюдать.

1 (обратно к тексту) - Среди трудов великого итальянского ученого и деятеля эпохи Возрождения Леона Баттисты Альберти (Leon Battista Alberti, 1404-72 гг.) - написанный в 1466-67 гг. трактат о криптоанализе, сделавший Альберти "отцом западной криптологии".

2 (обратно к тексту) - Фридрих Касиски (Friedrich W. Kasiski, 1805-81 гг.) - прусский офицер, решивший задачу дешифровки полиалфавитных шифров, автор знаменитой книги "Тайнопись и искусство дешифровки" (Die Geheimschriften und die Dechiffrir-kunst, 1863).

3 (обратно к тексту) - Джованни Баттиста Порта (Giovanni Battista Porta, 1573-16?? гг.) - итальянский ученый позднего Возрождения, среди трудов которого De Furtivis Literarum Novi - трактат, сведший воедино достижения криптологии своего времени.

4 (обратно к тексту) - David Kahn, The Codebreakers, 2nd Ed.: N.Y., 1996, p.230.

5 (обратно к тексту) - Auguste Kerckhoffs, La cryptographie militaire // Journal des sciences militaires, vol. IX, pp. 5-38, Janvier 1883, pp. 161-191, Fйvrier 1883; Auguste Kerckhoffs, La cryptographie militaire, P.: 1983.
Хотя ее, вероятно, переводили для своих нужд военные ведомства различных стран, единственным относительно широко известным переводом остается английский подстрочник 1964 года, выполненный Уорреном Мак-Креди (Warren T. McCready) из Университета Торонто, циркулирующий, впрочем, в рукописи.
В процессе подготовки этой статьи нас уведомили об инициативе Фабиана Птиколя (Fabien A. P. Petitcolas) из вычислительного центра Кембриджского университета (Великобритания), взявшегося опубликовать работу Керкхоффа в онлайне. На настоящий момент уже доступна первая половина материала (www.cl.cam.ac.uk/users/fapp2/kerckhoffs); завершить публикацию Птиколя планирует к концу года.