Хилл, Лестер

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Лестер Хилл
Lester Sanders Hill
Лестер Сандерс Хилл, 16 мая 1956 года Hill’s grandson.Лестер Сандерс Хилл, 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 году. После получения диплома магистра Хилл преподавал астрономию и математику в университете штата Монтана (19141915), затем в Принстонском университете (19151916)[1].

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

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

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

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

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

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

«Message Protector» (Lester-Weisner)
«Message Protector» — внутреннее устройство

Message Protector

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

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

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

[math]\displaystyle{ 56~99~01~12~72~64 }[/math]

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

[math]\displaystyle{ \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} }[/math]

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

Шифр Хилла

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

[math]\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} }[/math]

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

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

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

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

Публикации

  • Хилл, Л. С. Новый способ проверки правильности телеграфных сообщений : [англ.] = 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.
  • Хилл, Л. С. Об агрегатных функциях : [англ.] = Concerning Certain Aggregate Functions // American Journal of Mathematics. — 1927. — July. — ISSN 0002-9327.

Примечания

  1. 1,0 1,1 1,2 Хилл, Л.С — Candidate for Promotion, 1956.
  2. Chris Christensen — Lester Hill Revisited, 2014, p. 294.
  3. Диссертация в оригинале имела название «Aggregate-functions and an Application in Analysis Situs», однако неизвестно кто выступил в качестве научного руководителя Лестера
  4. Хилл, Л. С. — Concerning Certain Aggregate Functions, 1927.
  5. Джулия умерла 14 января 2013 года в возрасте 89 лет в Меквоне (англ. Mequon, Wisconsin), Висконсин
  6. Chris Christensen — Lester Hill Revisited, 2014, p. 307.
  7. Нью-Йорк Таймс, 1961.
  8. 8,0 8,1 Хилл, Л. С. — A Novel Checking Method for Telegraphic Sequences, 1926.
  9. Хилл, Л. С. — The Role of Prime Numbers in the Checking of Telegraphic Communications, апрель, 1927.
  10. Хилл, Л. С. — The Role of Prime Numbers in the Checking of Telegraphic Communications, июль, 1927.
  11. Chris Christensen — Lester Hill's Error-Detecting Codes, 2012, p. 96.
  12. Дэвид Кан — «Взломщики кодов», 1996, с. 404.
  13. Патент США № 1 845 947 от 16 февраля 1932. Message protector. Описание патента на сайте Ведомства по патентам и товарным знакам США.
  14. Chris Christensen — Lester Hill Revisited, 2014, p. 304.
  15. Chris Christensen — Lester Hill's Error-Detecting Codes, 2012, p. 97.
  16. Chris Christensen — Lester Hill Revisited, 2014, p. 305.
  17. Хилл, Л. С. — Cryptography in an Algebraic Alphabet, 1929.
  18. Chris Christensen — Lester Hill Revisited, 2014, p. 296.
  19. Дэвид Кан — «Взломщики кодов», 1996, с. 404-410.
  20. Абраам Синков — Elementary Cryptanalysis: A Mathematical Approach, 1998.
  21. Этот факт был отмечен в книге «Elementary Cryptanalysis: A Mathematical Approach»[20] Абраама Синкова
  22. Хилл, Л. С. — Concerning Certain Linear Transformation Apparatus in Cryptography, 1931.
  23. Chris Christensen — Lester Hill Revisited, 2014, p. 300-301.
  24. Дэвид Кан — «Взломщики кодов», 1996, с. 408, 410.

Литература

Книги

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

Статьи