Хилл, Лестер

В Википедии есть статьи о других людях с такой фамилией, см. Хилл.

Лестер Хилл
англ. Lester Sanders Hill
Лестер Сандерс Хилл, 16 мая 1956 года Hill’s grandson.
Дата рождения	18 января 1890(1890-01-18)
Место рождения	Нью-Йорк, США
Дата смерти	9 января 1961(1961-01-09) (70 лет)
Место смерти	Нью-Йорк, США
Страна	США
Род деятельности	математик, криптограф
Научная сфера	теория информации, криптография
Место работы	Принстонский университет Йельский университет Хантерский колледж Университет Монтаны
Альма-матер	Хантерский колледж
Учёная степень	доктор философии (PhD) по математике
Известен как	автор шифра Хилла, автор трудов по обнаружению ошибок в телеграфном коде

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

Биография

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

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

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

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

Во время Второй мировой войны Хилл преподавал математику с июля 1945 по январь 1946 в университете армии США (англ. US Army universities) в городе Биарриц, во Франции.

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

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

«Message Protector» (Lester-Weisner)

«Message Protector» — внутреннее устройство

Message Protector

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

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

Оригинальный текст (англ.)

[Hill] hoped to make some money from his checking scheme... but this did not go anywhere...

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

$56~99~01~12~72~64$

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

${\begin{bmatrix}3&1&2&2&3&1\\2&3&1&3&1&2\\1&2&3&1&2&3\end{bmatrix}}{\begin{bmatrix}56\\99\\01\\12\\72\\64\end{bmatrix}}={\begin{bmatrix}68\\40\\100\end{bmatrix}}{\pmod {101}}$

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

Шифр Хилла

Основная статья: Шифр Хилла

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

${\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.

Литература

Книги

• Дэвид Кан. Взломщики кодов = The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Macmillan, 1996. — 1200 с. — ISBN 978-0684831305.

• Абраам Синков. Простой криптоанализ: математический подход = Elementary Cryptanalysis: A Mathematical Approach. — The L. W. Singer Company, 1998. — 232 с. — ISBN 978-0883856222.

Статьи

• Chris Christensen. Lester Hill Revisited (англ.) // Cryptologia. — 2014. — 30 August (vol. 38, no. 4). — P. 293—332. — ISSN 1558-1586. — doi:10.1080/01611194.2014.915260.
• Chris Christensen, David Joyner, Jenna Torres. Lester Hill's Error-Detecting Codes (англ.) // Cryptologia. — 2012. — 12 April (vol. 36, no. 2). — P. 88—103. — ISSN 1558-1586. — doi:10.1080/01611194.2011.632805.
• Lester Hill Dies; Mathematician (англ.) // New York Times. — 1961. — 10 January. — P. 47. — ISSN 0362-4331.
• Хилл, Л. С. Candidate for Promotion (англ.). — 1956. — April.