Хилл, Лестер: биография

Эти шесть входных параметров выставлялись на ручках с передней стороны устройства. Строка проверки 68   40   100 {\displaystyle 68~40~100} появлялась на трех ручках c левой стороны. Другими словами, «Message Protector» реализовывал следующее линейное преобразование в виде перемножения матриц:

Хотя считается, что это устройство было прямой реализацией шифра Хилла, в заявлении на патент оно было описано как устройство обнаружения ошибок. Однако в 1931 году Хилл предложил модернизировать «Message Protector» таким образом, чтобы его можно было использовать в качестве шифратора. Для этого матрица шифрования должна была быть квадратной и обратимой. Функционал этой матрицы воспроизводился внутренней конструкцией аппарата, в которую сложно было вносить изменения. Кроме того, если бы матрица шифрования не была инволютивной, то потребовалось бы два устройства типа «Message Protector»: один для шифрования, другой для дешифровки.

<3>Шифр Хилла

Шифр Хилла считается наиболее значимой работой Хилла в области криптографии. Впервые шифр был опубликован в American Mathematical Monthly в 1929 году в статье «Cryptography in an Algebraic Alphabet». Шифр Хилла принципиально схож с шифрованием на открытом ключе, так как использует два ключа для шифрования и дешифровки — аналоги открытого и закрытого ключей в криптосистемах с открытым ключом. Отличие же заключается в том, что криптоаналитик, будучи специалистом в области линейной алгебры и модульной арифметики, может легко вычислить закрытый ключ, зная ключ шифрования. Следующей собенностью этого шифра было то, что при его разработке Хилл использовал нелинейные перестановки алфавитных символов, которые обеспечивали шифр бльшей криптостойкостью:

a b c d e f g h i j 5 23 2 20 10 15 8 4 18 25 {\displaystyle {\begin{matrix}a&b&c&d&e&f&g&h&i&j\\5&23&2&20&10&15&8&4&18&25\end{matrix}}}

После выступления в августе 1929 года перед Американским математическим обществом в Боулдере, Хилл опубликовал свою следующую работу «Concerning Certain Linear Transformation Apparatus of Cryptography», бльшая часть которой была посвящена алгебраическому аппарату, наиболее известному сейчас как коммутативное кольцо.

Считается, что предшественником шифра Хилла является шифр, предложенный Джеком Левином (англ. Jack Levine). Оба шифра использовали один и тот же математический аппарат с одной лишь разницей в том, что шифр Хилла полиграфичен: сообщение разбивается на блоки и каждый блок шифруется раздельно, в то время как в шифре Левина два сообщения объединялись в одно, и только затем шифровались.

Безусловно, шифр Хилла был мощным толчком в развитии криптографии, как прикладной науки, о чем написано во «Взломщиках кодов» Дэвида Кана:

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

Оригинальный текст (англ.)   ... although Hill’s cipher system itself saw almost no practical use, it had a great impact upon cryptology. When [Hill] published his articles in 1929 and 1931, cryptology, like other applied sciences, was beginning to drift toward a wide-spread application of mathematics to its problems. ...Hill accelerated this trend.

Публикации

• Хилл, Л. С. Новый способ проверки правильности телеграфных сообщений : [англ.] = A Novel Checking Method for Telegraphic Sequences // Telegraph and Telephone Age. — 1926. — 1 October.

• Хилл, Л. С. Роль простых чисел в проверке телеграфных коммуникаций : [англ.] = The Role of Prime Numbers in the Checking of Telegraphic Communications // Telegraph and Telephone Age. — 1927. — 1 April.
• Хилл, Л. С. Роль простых чисел в проверке телеграфных коммуникаций : [англ.] = The Role of Prime Numbers in the Checking of Telegraphic Communications // Telegraph and Telephone Age. — 1927. — 16 July.

• Хилл, Л. С. Криптография в алгебраическом алфавите : [англ.] = Cryptography in an Algebraic Alphabet // The American Mathematical Monthly. — 1929., № 6 (June). — ISSN 0002-9890.

• Хилл, Л. С. Об аппарате линейных преобразований в криптографии : [англ.] = Concerning Certain Linear Transformation Apparatus in Cryptography // The American Mathematical Monthly. — 1931., № 3 (March). — ISSN 0002-9890.

• Хилл, Л. С. Об агрегатных функциях : [англ.] = Concerning Certain Aggregate Functions // American Journal of Mathematics. — 1927. — July. — ISSN 0002-9327.