Просмотр кода страницы Хилл, Лестер

{{ФИО}}
{{Учёный
 |Имя                  = Лестер Хилл
 |Оригинал имени       = {{lang-en|Lester Sanders Hill}}
 |Изображение          = Хилл Сандерс Лестер.jpg
 |Ширина               = 
 |Описание изображения = Лестер Сандерс Хилл, 16 мая 1956 года
Hill’s grandson.
 |Дата рождения        = 18.01.1890
 |Место рождения       = {{место рождения|Нью-Йорк}}, [[Соединённые Штаты Америки|США]]
 |Дата смерти          = 09.01.1961
 |Место смерти         = {{место смерти|Нью-Йорк}}, [[Соединённые Штаты Америки|США]]
 |Гражданство          = {{флагификация|США}}
 |Научная сфера        = [[теория информации]], [[криптография]]
 |Место работы         = 
 |Учёная степень       = {{PhD|математике}}
 |Учёное звание        = 
 |Альма-матер          = [[Хантерский колледж]]
 |Научный руководитель = 
 |Знаменитые ученики   = 
 |Известен как         = автор [[Шифр Хилла|шифра Хилла]], автор трудов по [[Обнаружение_и_исправление_ошибок | обнаружению ошибок]] в телеграфном коде
 |Награды и премии     = 
 |Роспись              = 
 |Ширина росписи       = 
 |Сайт                 = 
 |Викитека             = 
 |Викисклад            = <!--  БЕЗ префикса Category:-->
}}
'''Ле́стер Са́ндерс Хилл''' ({{lang-en|Lester Sanders Hill}}; {{дата рождения|18|1|1890}}, Нью-Йорк, [[США]] — {{дата смерти|9|1|1961}}, там же) — [[Американцы США|американский]] [[математик]], учёный в области [[Криптография|криптографии]]. Предложил собственный метод [[Обнаружение и исправление ошибок|обнаружения ошибок]] в телеграфном коде. Внес большой вклад в развитие [[Криптография|криптографии]] и [[Кодирование информации|теории кодирования]]. Известен как создатель [[шифр Хилла|шифра]], построенного на [[синтез]]е [[Сравнение по модулю|модульной арифметики]] и [[Линейная алгебра|линейной алгебры]] для символьного [[Кодирование информации|кодирования]].

== Биография ==
Лестер Хилл родился 18 января [[1890 год]]а в [[Нью-Йорк]]е. [[Бакалавр искусств|Степень бакалавра]] [[математика|математических наук]] получил в [[1911 год]]у в {{не переведено 2|Колумбийский колледж|Колумбийском колледже|en|Columbia_College,_Columbia_University |Columbia College}}. Окончил [[магистр]]атуру [[Колумбийский университет|Колумбийского университета]] в [[1913 год]]у. После получения диплома магистра Хилл преподавал [[Астрономия|астрономию]] и математику в [[Университет штата Монтана|университете штата Монтана]] ([[1914 год|1914]]—[[1915 год|1915]]), затем в [[Принстонский университет|Принстонском университете]] ([[1915 год|1915]]—[[1916 год|1916]]){{sfn|Хилл, Л.С — ''Candidate for Promotion''|1956}}.

25 мая [[1917 год]]а в Нью-Йорке Хилл записался [[Волонтёр (военный)|добровольцем]] в [[Военно-морские силы США]] и был принят на службу {{не переведено 2|моряк второго класса|моряком второго класса|en|Seaman apprentice|seaman apprentice}} в резерв береговой охраны. На тот момент его единственным близким родственником был отец Джеймс Эдвард Хилл ({{lang-en|James Edward Hill}}), проживавший в [[Кливленд]]е{{sfn|Chris Christensen — ''Lester Hill Revisited''|2014|p=294}}. 21 июля [[1917 год]]а Лестера призвали на очную службу, где 23 июля ему было присвоено звание {{не переведено 2|Yeoman (United States Navy)|главного старшины|en|Yeoman (United States Navy)|Yeoman}}. В начале августа его повысили до звания [[Энсин|прапорщика]]. C [[1919 год]]а по [[1921 год]] Хилл служил в {{не переведено 2|United States Navy Reserve|резерве ВМС США|en|United States Navy Reserve| U.S. Naval Reserve}} в качестве представителя продаж в [[Европа|Европе]]{{sfn|Хилл, Л.С — ''Candidate for Promotion''|1956}}.

После службы в [[Военно-морские силы США|Военно-морских силах США]] во время [[Первая мировая война|Первой мировой войны]] Хилл работал [[доцент]]ом в [[Университет Мэна|университете Мэна]] с [[1921 год|1921]] по [[1922 год|1922]] и инструктором в [[Йельский университет|Йельском университете]] ([[1922 год|1922]]—[[1927 год|1927]]), где он защитил докторскую [[Диссертация|диссертацию]]{{#tag:ref|Диссертация в оригинале имела название «''Aggregate-functions and an Application in Analysis Situs''», однако неизвестно кто выступил в качестве научного руководителя Лестера}}, и стал [[Доктор философии|доктором математических наук]] в [[1926 год]]у. Идеи диссертации были развиты автором в статье «''Concerning Certain Aggregate Functions''»{{sfn|Хилл, Л. С. — ''Concerning Certain Aggregate Functions''|1927}}, опубликованной в [[American Journal of Mathematics|Американском журнале математики]] в [[1927 год]]у. Примерно в это же время он женится на Мэйбл Хит ({{lang-en|Mabel Hitt}}) родом из города [[Калпепер (Виргиния)|Калпепер]], [[штат Виргиния]], которая преподавала в высшей школе [[Пуэрто-Рико]]. Их единственная дочь Джулия родилась в [[1923 год]]у в [[Нью-Хейвен]]е, [[Коннектикут]]{{#tag:ref|Джулия умерла 14 января [[2013 год]]а в возрасте 89 лет в {{не переведено 2|Mequon, Wisconsin|Меквоне|en|Mequon, Wisconsin|Mequon, Wisconsin}}, [[Висконсин]]}}.

Основную часть своей научной и преподавательской деятельности Хилл посвятил работе на математическом факультете в [[Хантерский колледж|Хантерском колледже]], куда был принят на должность [[Преподаватель|преподавателя]] математики в [[1927 год]]у. В [[1929 год]]у Хилл получил звание [[доцент]]а, а в [[1956 год]]у стал [[профессор]]ом и оставался им вплоть до своего ухода в [[1960 год]]у, причиной которому послужило слабое здоровье{{sfn|Chris Christensen — ''Lester Hill Revisited''|2014|p=307}}.

Во время [[Вторая мировая война|Второй мировой войны]] Хилл преподавал математику с июля [[1945 год|1945]] по январь [[1946 год|1946]] в {{не переведено 2|G.I. American Universities|университете армии США|en|G.I. American Universities|US Army universities}} в городе [[Биарриц]], во [[Франция|Франции]]{{sfn|Хилл, Л.С — ''Candidate for Promotion''|1956}}.

Хилл Лестер умер 9 января [[1961 год|1961]] после продолжительной болезни в {{не переведено 2|Lawrence Hospital|госпитале Лоуренса|en|Lawrence Hospital|Lawrence Hospital}}{{sfn|Нью-Йорк Таймс|1961}}.

== Научная деятельность ==
[[Файл:Message Protector.png|thumb|«''Message Protector''» (''Lester-Weisner'')]]
[[Файл:Message Protector (Lester-Weisner) - 2.png|thumb|«''Message Protector''» — внутреннее устройство]]

=== Message Protector ===
Хотя известность Хиллу принёс его знаменитый шифр, его ранние публикации{{sfn|Хилл, Л. С. — ''A Novel Checking Method for Telegraphic Sequences''|1926}}{{sfn|Хилл, Л. С. — ''The Role of Prime Numbers in the Checking of Telegraphic Communications'', апрель|1927}}{{sfn|Хилл, Л. С. — ''The Role of Prime Numbers in the Checking of Telegraphic Communications'', июль|1927}} в области [[теория кодирования|теории кодирования]] описывают предложенный им алгоритм обнаружения ошибок в телеграфных кодах с использованием [[модульная арифметика|модульной арифметики]] и [[Линейная алгебра|линейных преобразований]]. В [[1926 год]]у в статье «''A Novel Checking Method for Telegraphic Sequences''»{{sfn|Хилл, Л. С. — ''A Novel Checking Method for Telegraphic Sequences''|1926}} Хилл предложил метод [[Обнаружение и исправление ошибок|помехоустойчивого кодирования]] [[Линейный код|линейных блочных кодов]], на два десятилетия раньше, чем это сделал [[Хэмминг, Ричард Уэсли|Ричард Хэмминг]]{{sfn|Chris Christensen — Lester Hill's Error-Detecting Codes|2012|p=96}}. Метод не стал общеиспользуемым, о чём [[Кан, Дэвид|Дэвид Кан]] написал в своей книге «[[Взломщики кодов]]»{{sfn|Дэвид Кан — «Взломщики кодов»|1996|с=404}}:
{{начало цитаты}}
[Хилл] хотел выручить денег с предложенной им схемы проверки, однако метод не нашёл практического применения…
{{oq|en|[Hill] hoped to make some money from his checking
scheme... ''but this did not go anywhere''...}}
{{конец цитаты}}
Однако во время работы в [[Хантерский колледж|Хантерском колледже]] Хилл совместно со своим коллегой {{не переведено 2|Луи, Вайснер|Луи Вайснером|en|Louis Weisner|Louis Weisner}}, выдвинул заявку на патент устройства «''Message Protector''»{{#tag:ref|{{патент США|номер=1845947|заглавие=Message protector|дата=1932-02-16}}}}, работа которого основана на методе Хилла по обнаружению ошибок. В заявлении патента Хилл и Вайснер предложили использовать «''Message Protector''» для проверки [[чек]]ов во время платёжных переводов. Проверка [[чек]]а начиналась сбором чековых данных, которые [[Кодирование информации|кодировались]] в строку двузначных номеров от 00 до 99. В их примере данные чека представляли собой следующую строку:
: <math>56~99~01~12~72~64</math>
Эти шесть входных параметров выставлялись на ручках с передней стороны устройства. Строка проверки <math>68~40~100</math> появлялась на трех ручках c левой стороны.
Другими словами, «''Message Protector''» реализовывал следующее линейное преобразование в виде перемножения [[Матрица (математика)|матриц]]{{sfn|Chris Christensen — Lester Hill Revisited|2014|p=304}}:
: <math>\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>

Хотя считается, что это устройство было прямой реализацией [[шифр Хилла|шифра Хилла]]{{sfn|Chris Christensen — Lester Hill's Error-Detecting Codes|2012|p=97}}, в заявлении на [[патент]] оно было описано как устройство обнаружения ошибок. Однако в 1931 году Хилл предложил модернизировать «''Message Protector''» таким образом, чтобы его можно было использовать в качестве [[Шифратор (криптография)|шифратора]]. Для этого [[Матрица (математика)|матрица]] [[Шифрование|шифрования]] должна была быть [[квадратная матрица|квадратной]] и [[обратимая матрица|обратимой]]. Функционал этой матрицы воспроизводился внутренней конструкцией аппарата, в которую сложно было вносить изменения. Кроме того, если бы матрица шифрования не была [[Инволютивная матрица|инволютивной]], то потребовалось бы два устройства типа «''Message Protector''»: один для шифрования, другой для [[дешифровка|дешифровки]]{{sfn|Chris Christensen — Lester Hill Revisited|2014|p=305}}.

=== Шифр Хилла ===
{{main|Шифр Хилла}}
[[Шифр Хилла]] считается наиболее значимой работой Хилла в области [[Криптография|криптографии]]. Впервые шифр был опубликован в ''[[American Mathematical Monthly]]'' в [[1929 год]]у в статье «''Cryptography in an Algebraic Alphabet''»{{sfn|Хилл, Л. С. — ''Cryptography in an Algebraic Alphabet''|1929}}.
[[Шифр Хилла]] принципиально схож с [[Криптосистема с открытым ключом|шифрованием на открытом ключе]], так как использует два ключа для [[шифрование|шифрования]] и [[дешифрование|дешифровки]] — аналоги открытого и закрытого ключей в [[Криптосистема с открытым ключом|криптосистемах с открытым ключом]]. Отличие же заключается в том, что [[криптоанализ|криптоаналитик]], будучи специалистом в области [[линейная алгебра|линейной алгебры]] и [[модульная арифметика|модульной арифметики]], может легко вычислить закрытый ключ, зная ключ шифрования{{sfn|Chris Christensen — ''Lester Hill Revisited''|2014|p=296}}.
Следующей собенностью этого шифра было то, что при его разработке Хилл использовал нелинейные перестановки алфавитных символов{{sfn|Дэвид Кан — «Взломщики кодов»|1996|с=404—410}}, которые обеспечивали шифр бо́льшей [[криптостойкость]]ю{{#tag:ref|Этот факт был отмечен в книге «''Elementary Cryptanalysis: A Mathematical Approach''»{{sfn|Абраам Синков — ''Elementary Cryptanalysis: A Mathematical Approach''|1998}} Абраама Синкова}}:
: <math>
\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''»{{sfn|Хилл, Л. С. — Concerning Certain Linear Transformation Apparatus in Cryptography|1931}}, бо́льшая часть которой была посвящена алгебраическому аппарату, наиболее известному сейчас как [[коммутативное кольцо]].

Считается, что предшественником [[шифр Хилла|шифра Хилла]] является шифр, предложенный Джеком Левином ({{lang-en|Jack Levine}}). Оба шифра использовали один и тот же математический аппарат с одной лишь разницей в том, что [[шифр Хилла]] полиграфичен: сообщение разбивается на блоки и каждый блок [[шифрование|шифруется]] раздельно, в то время как в шифре Левина два сообщения объединялись в одно, и только затем [[шифрование|шифровались]]{{sfn|Chris Christensen — ''Lester Hill Revisited''|2014|p=300—301}}.

Безусловно, [[шифр Хилла]] был мощным толчком в развитии [[криптография|криптографии]], как прикладной науки, о чем написано во «[[Взломщики кодов|Взломщиках кодов]]» [[Дэвид Кан|Дэвида Кана]]{{sfn|Дэвид Кан — «Взломщики кодов»|1996|с=408, 410}}:
{{начало цитаты}}
… хотя система шифрования, предложенная Хиллом, не имела практического использования, она оказала огромное влияние на криптографию. Когда он [Хилл] опубликовал свои статьи в 1929 и 1931 годах, криптография, как и другие прикладные науки, начала искать решения своих проблем в широком применении математики… Хилл ускорил эту тенденцию.
{{oq|en|... 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
 | месяц                 = 10
 | день                  = 1
 | номер                 = 
 | том                   = 
 | volume                = 
 | выпуск                = 
 | issue                 = 
 | страницы              = 456—460
 | pages                 = 456—460
 | язык                  = en
 | issn                  = 
 | ref                   = Хилл, Л. С. — ''A Novel Checking Method for Telegraphic Sequences''
}}

* {{публикация|статья
 | автор                 = Хилл, Л. С.
 | заглавие              = Роль простых чисел в проверке телеграфных коммуникаций
 | ссылка                = 
 | оригинал              = The Role of Prime Numbers in the Checking of Telegraphic Communications
 | вид                   = 
 | издание               = Telegraph and Telephone Age
 | тип                   = 
 | год                   = 1927
 | месяц                 = 04
 | день                  = 1
 | номер                 = 
 | том                   = 
 | volume                = 
 | выпуск                = 
 | issue                 = 
 | страницы              = 151—154
 | pages                 = 151—154
 | язык                  = en
 | issn                  = 
 | ref                   = Хилл, Л. С. — ''The Role of Prime Numbers in the Checking of Telegraphic Communications'', апрель
}}
* {{публикация|статья
 | автор                 = Хилл, Л. С.
 | заглавие              = Роль простых чисел в проверке телеграфных коммуникаций
 | ссылка                = 
 | оригинал              = The Role of Prime Numbers in the Checking of Telegraphic Communications
 | вид                   = 
 | издание               = Telegraph and Telephone Age
 | тип                   = 
 | год                   = 1927
 | месяц                 = 07
 | день                  = 16
 | номер                 = 
 | том                   = 
 | volume                = 
 | выпуск                = 
 | issue                 = 
 | страницы              = 323—324
 | pages                 = 323—324
 | язык                  = en
 | issn                  = 
 | ref                   = Хилл, Л. С. — ''The Role of Prime Numbers in the Checking of Telegraphic Communications'', июль
}}

* {{публикация|статья
 | автор                 = Хилл, Л. С.
 | заглавие              = Криптография в алгебраическом алфавите
 | ссылка                = http://www.marksmath.com/old-papers/hill-1.pdf
 | оригинал              = Cryptography in an Algebraic Alphabet
 | вид                   = 
 | издание               = The American Mathematical Monthly
 | тип                   = 
 | год                   = 1929
 | месяц                 = 06
 | день                  = 
 | номер                 = 6
 | том                   = 36
 | volume                = 36
 | выпуск                = 
 | issue                 = 
 | страницы              = 306—312
 | pages                 = 306—312
 | язык                  = en
 | issn                  = 0002-9890
 | ref                   = Хилл, Л. С. — ''Cryptography in an Algebraic Alphabet''
}}

* {{публикация|статья
 | автор                 = Хилл, Л. С.
 | заглавие              = Об аппарате линейных преобразований в криптографии
 | ссылка                = http://www.marksmath.com/old-papers/hill-2.pdf
 | оригинал              = Concerning Certain Linear Transformation Apparatus in Cryptography
 | вид                   = 
 | издание               = The American Mathematical Monthly
 | тип                   = 
 | год                   = 1931
 | месяц                 = 03
 | день                  = 
 | номер                 = 3
 | том                   = 38
 | volume                = 38
 | выпуск                = 
 | issue                 = 
 | страницы              = 135—154
 | pages                 = 135—154
 | язык                  = en
 | issn                  = 0002-9890
 | ref                   = Хилл, Л. С. — Concerning Certain Linear Transformation Apparatus in Cryptography
}}

* {{публикация|статья
 | автор                 = Хилл, Л. С.
 | заглавие              = Об агрегатных функциях
 | ссылка                = 
 | оригинал              = Concerning Certain Aggregate Functions
 | вид                   = 
 | издание               = American Journal of Mathematics
 | тип                   = 
 | год                   = 1927
 | месяц                 = 07
 | день                  = 
 | номер                 = 
 | том                   = 
 | volume                = 
 | выпуск                = 
 | issue                 = 
 | страницы              = 419–432
 | pages                 = 419–432
 | язык                  = en
 | issn                  = 0002-9327
 | ref                   = Хилл, Л. С. — ''Concerning Certain Aggregate Functions''
}}

== Примечания ==
{{примечания|2}}

== Литература ==

=== Книги ===
* {{книга
 |автор                = [[Кан,_Дэвид | Дэвид Кан]]
 |заглавие             = [[Взломщики кодов]]
 |оригинал             = The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet 
 |издательство         = [[Macmillan_Publishers | Macmillan]]
 |год                  = 1996
 |страниц              = 1200
 |isbn                 = 978-0684831305
 |ref                  = Дэвид Кан — «Взломщики кодов»
}}

* {{книга
 |автор                = [[Abraham_Sinkov|Абраам Синков]]
 |заглавие             = Простой криптоанализ: математический подход
 |оригинал             = Elementary Cryptanalysis: A Mathematical Approach 
 |издательство         = The L. W. Singer Company
 |год                  = 1998
 |страниц              = 232
 |isbn                 = 978-0883856222
 |ref                  = Абраам Синков — ''Elementary Cryptanalysis: A Mathematical Approach''
}}

=== Статьи ===
* {{статья
 |автор         = Chris Christensen
 |заглавие      = Lester Hill Revisited
 |ссылка        = http://dx.doi.org/10.1080/01611194.2014.915260
 |язык          = en
 |издание       = Cryptologia
 |тип           = 
 |год           = 2014
 |месяц         = 08
 |число         = 30
 |том           = 38
 |номер         = 4
 |страницы      = 293—332
 |doi           = 10.1080/01611194.2014.915260
 |issn          = 1558-1586
 |ref           = Chris Christensen — ''Lester Hill Revisited''
}}
* {{статья
 |автор         = Chris Christensen, David Joyner, Jenna Torres
 |заглавие      = Lester Hill's Error-Detecting Codes
 |ссылка        = http://dx.doi.org/10.1080/01611194.2011.632805
 |язык          = en
 |издание       = Cryptologia
 |тип           = 
 |год           = 2012
 |месяц         = 04
 |число         = 12
 |том           = 36
 |номер         = 2
 |страницы      = 88—103
 |doi           = 10.1080/01611194.2011.632805
 |issn          = 1558-1586
 |ref           = Chris Christensen — ''Lester Hill's Error-Detecting Codes''
}}
* {{статья
 |автор         = 
 |заглавие      = Lester Hill Dies; Mathematician
 |ссылка        = 
 |язык          = en
 |издание       = New York Times
 |тип           = 
 |год           = 1961
 |месяц         = 01
 |число         = 10
 |том           = 
 |номер         = 
 |страницы      = 47
 |doi           = 
 |issn          = 0362-4331
 |ref           = Нью-Йорк Таймс
}}
* {{статья
 |автор         = Хилл, Л. С.
 |заглавие      = Candidate for Promotion
 |ссылка        = 
 |язык          = en
 |тип           = 
 |год           = 1956
 |месяц         = 04
 |число         = 
 |том           = 
 |архив         = New York: Hunter College Archives
 |номер         = 
 |страницы      =
 |doi           = 
 |issn          = 
 |ref           = Хилл, Л.С — ''Candidate for Promotion''
}}
{{Внешние ссылки}}

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