Ле́стер Са́ндерс Хилл (; , Нью-Йорк, США — , там же) — американский , учёный в области криптографии. Предложил собственный метод обнаружения ошибок в телеграфном коде. Внес большой вклад в развитие криптографии и теории кодирования. Известен как создатель шифра, построенного на синтезе модульной арифметики и линейной алгебры для символьного кодирования.

Биография Лестер Хилл родился 18 января 1890 года в Нью-Йорке. Степень бакалавра математических наук получил в 1911 году в . Окончил магистратуру Колумбийского университета в 1913 году. После получения диплома магистра Хилл преподавал астрономию и математику в университете штата Монтана (1914—1915), затем в Принстонском университете (1915—1916).

25 мая 1917 года в Нью-Йорке Хилл записался добровольцем в Военно-морские силы США и был принят на службу в резерв береговой охраны. На тот момент его единственным близким родственником был отец Джеймс Эдвард Хилл (), проживавший в Кливленде. 21 июля 1917 года Лестера призвали на очную службу, где 23 июля ему было присвоено звание . В начале августа его повысили до звания прапорщика. C 1919 года по 1921 год Хилл служил в в качестве представителя продаж в Европе.

После службы в Военно-морских силах США во время Первой мировой войны Хилл работал доцентом в университете Мэна с 1921 по 1922 и инструктором в Йельском университете (1922—1927), где он защитил докторскую диссертацию, и стал доктором математических наук в 1926 году. Идеи диссертации были развиты автором в статье «Concerning Certain Aggregate Functions», опубликованной в Американском журнале математики в 1927 году. Примерно в это же время он женится на Мэйбл Хит () родом из города Калпепер, штат Виргиния, которая преподавала в высшей школе Пуэрто-Рико. Их единственная дочь Джулия родилась в 1923 году в Нью-Хейвене, Коннектикут.

Основную часть своей научной и преподавательской деятельности Хилл посвятил работе на математическом факультете в Хантерском колледже, куда был принят на должность преподавателя математики в 1927 году. В 1929 году Хилл получил звание доцента, а в 1956 году стал профессором и оставался им вплоть до своего ухода в 1960 году, причиной которому послужило слабое здоровье.

Во время Второй мировой войны Хилл преподавал математику с июля 1945 по январь 1946 в в городе Биарриц, во Франции.

Хилл Лестер умер 9 января 1961 после продолжительной болезни в .

Научная деятельность

Message Protector Хотя известность Хиллу принёс его знаменитый шифр, его ранние публикации в области теории кодирования описывают предложенный им алгоритм обнаружения ошибок в телеграфных кодах с использованием модульной арифметики и линейных преобразований. В 1926 году в статье «A Novel Checking Method for Telegraphic Sequences» Хилл предложил метод помехоустойчивого кодирования линейных блочных кодов, на два десятилетия раньше, чем это сделал Ричард Хэмминг. Метод не стал общеиспользуемым, о чём Дэвид Кан написал в своей книге «Взломщики кодов»:

[Хилл] хотел выручить денег с предложенной им схемы проверки, однако метод не нашёл практического применения…

Однако во время работы в Хантерском колледже Хилл совместно со своим коллегой , выдвинул заявку на патент устройства «Message Protector», работа которого основана на методе Хилла по обнаружению ошибок. В заявлении патента Хилл и Вайснер предложили использовать «Message Protector» для проверки чеков во время платёжных переводов. Проверка чека начиналась сбором чековых данных, которые кодировались в строку двузначных номеров от 00 до 99. В их примере данные чека представляли собой следующую строку:

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

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

Шифр Хилла

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

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

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

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

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

Публикации

Примечания

Литература

Книги

Статьи

Категория:Преподаватели Хантерского колледжа Категория:Преподаватели Йельского университета Категория:Преподаватели Принстонского университета Категория:Преподаватели Университета Монтаны Категория:Преподаватели Университета Мэна Категория:Теория кодирования Категория:Теория информации Категория:Обнаружение и устранение ошибок Категория:Криптографы США