На пути к математической криптографии

В 1824 году выходит книга Жана-Франсуа Шампольона «Précis du système hiérogl. d. anciens Egyptiens ou recherches sur les élèments de cette écriture» («Краткий очерк иероглифической системы древних египтян или исследования элементов этого письма»), содержавшая расшифровку египетских иероглифов, скрывавших свои тайны более трёх тысяч лет.

В 1863 году Фридрих Касиски (англ. Friedrich Kasiski) опубликовал метод, впоследствии названный его именем, позволявшим быстро и эффективно вскрывать практически любые шифры того времени. Метод состоял из двух частей — определение периода шифра и дешифровка текста с использованием частотного криптоанализа.

В 1883 году Огюст Керкгоффс опубликовал труд под названием «Военная криптография» (фр. La Cryptographie Militaire). В нём он описал шесть требований, которым должна удовлетворять защищённая система. Хотя к некоторым из них стоит относиться с подозрением, стоит отметить труд за саму попытку:

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

Auguste Kerckhoffs. La Cryptographie Militaire

В настоящее время второе из этих правил известно как принцип Керкгоффса.

В конце XIX — начале XX века правительства стран вновь бросили значительные силы на шифрование и криптоанализ. В 1914 году Британия открыла «Комнату 40», в 1917 году США — MI-8, ставшую предшественницей современного АНБ.

В 1918 году вышла монография американского криптографа российского происхождения Уильяма Ф. Фридмана «Индекс совпадения и его применение в криптографии» (англ. «Index of Coincidence and Its Applications in Cryptography»). Работа вышла в открытой печати, несмотря на то, что была выполнена в рамках военного заказа. Двумя годами позже Фридман ввёл в научный обиход термины криптология и криптоанализ.

В начале 1920-х годов практически одновременно в разных странах появляются патенты и электромеханические машины, использующие принципы криптографического диска (ротора) и автоматизирующие процесс шифрования. В США это был Эдвард Геберн (англ. Edward Hebern), после него — Хьюго Кох (англ. Hugo Koch) из Нидерландов и его «Энигма» (позже патент был куплен Артуром Шербиусом (англ. Arthur Scherbius)), Арвид Герхард Дамм из Швеции и его машина «B-1» — разработки последнего были продолжены Борисом Хагелиным.

В 1928—1929 годах польское «Biuro Szyfrów» организовало курсы для 20 математиков со знанием немецкого языка — будущих криптоаналитиков, трое из которых известны работой по взлому «Энигмы». До этого на работу принимали в основном лингвистов.

В 1929 году Лестер Хилл (англ. Lester S. Hill) опубликовал в журнале «The American Mathematical Monthly» статью «Cryptography in an Algebraic Alphabet». В ней он описал подход к конструированию криптографических систем, для которых математически была доказана их неуязвимость к частотным атакам, в том числе к методу Касиски. Для представления текста он перевёл его в цифровой вид, а для описания шифрования использовал полиномиальные уравнения.

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