Русская Википедия:Хилл, Лестер
Шаблон:Однофамильцы Шаблон:Учёный Лéстер Сáндерс Хилл (Шаблон:Lang-en; Шаблон:Дата рождения, Нью-Йорк, США — Шаблон:Дата смерти, там же) — американский математик, учёный в области криптографии. Предложил собственный метод обнаружения ошибок в телеграфном коде. Внес большой вклад в развитие криптографии и теории кодирования. Известен как создатель шифра, построенного на синтезе модульной арифметики и линейной алгебры для символьного кодирования.
Биография
Лестер Хилл родился 18 января 1890 года в Нью-Йорке. Степень бакалавра математических наук получил в 1911 году в Шаблон:Не переведено 2. Окончил магистратуру Колумбийского университета в 1913 году. После получения диплома магистра Хилл преподавал астрономию и математику в университете штата Монтана (1914—1915), затем в Принстонском университете (1915—1916)Шаблон:Sfn.
25 мая 1917 года в Нью-Йорке Хилл записался добровольцем в Военно-морские силы США и был принят на службу Шаблон:Не переведено 2 в резерв береговой охраны. На тот момент его единственным близким родственником был отец Джеймс Эдвард Хилл (Шаблон:Lang-en), проживавший в КливлендеШаблон:Sfn. 21 июля 1917 года Лестера призвали на очную службу, где 23 июля ему было присвоено звание Шаблон:Не переведено 2. В начале августа его повысили до звания прапорщика. C 1919 года по 1921 год Хилл служил в Шаблон:Не переведено 2 в качестве представителя продаж в ЕвропеШаблон:Sfn.
После службы в Военно-морских силах США во время Первой мировой войны Хилл работал доцентом в университете Мэна с 1921 по 1922 и инструктором в Йельском университете (1922—1927), где он защитил докторскую диссертацию[1], и стал доктором математических наук в 1926 году. Идеи диссертации были развиты автором в статье «Concerning Certain Aggregate Functions»Шаблон:Sfn, опубликованной в Американском журнале математики в 1927 году. Примерно в это же время он женится на Мэйбл Хит (Шаблон:Lang-en) родом из города Калпепер, штат Виргиния, которая преподавала в высшей школе Пуэрто-Рико. Их единственная дочь Джулия родилась в 1923 году в Нью-Хейвене, Коннектикут[2].
Основную часть своей научной и преподавательской деятельности Хилл посвятил работе на математическом факультете в Хантерском колледже, куда был принят на должность преподавателя математики в 1927 году. В 1929 году Хилл получил звание доцента, а в 1956 году стал профессором и оставался им вплоть до своего ухода в 1960 году, причиной которому послужило слабое здоровьеШаблон:Sfn.
Во время Второй мировой войны Хилл преподавал математику с июля 1945 по январь 1946 в Шаблон:Не переведено 2 в городе Биарриц, во ФранцииШаблон:Sfn.
Хилл Лестер умер 9 января 1961 после продолжительной болезни в Шаблон:Не переведено 2Шаблон:Sfn.
Научная деятельность
Message Protector
Хотя известность Хиллу принёс его знаменитый шифр, его ранние публикацииШаблон:SfnШаблон:SfnШаблон:Sfn в области теории кодирования описывают предложенный им алгоритм обнаружения ошибок в телеграфных кодах с использованием модульной арифметики и линейных преобразований. В 1926 году в статье «A Novel Checking Method for Telegraphic Sequences»Шаблон:Sfn Хилл предложил метод помехоустойчивого кодирования линейных блочных кодов, на два десятилетия раньше, чем это сделал Ричард ХэммингШаблон:Sfn. Метод не стал общеиспользуемым, о чём Дэвид Кан написал в своей книге «Взломщики кодов»Шаблон:Sfn: Шаблон:Начало цитаты [Хилл] хотел выручить денег с предложенной им схемы проверки, однако метод не нашёл практического применения… Шаблон:Oq Шаблон:Конец цитаты Однако во время работы в Хантерском колледже Хилл совместно со своим коллегой Шаблон:Не переведено 2, выдвинул заявку на патент устройства «Message Protector»[3], работа которого основана на методе Хилла по обнаружению ошибок. В заявлении патента Хилл и Вайснер предложили использовать «Message Protector» для проверки чеков во время платёжных переводов. Проверка чека начиналась сбором чековых данных, которые кодировались в строку двузначных номеров от 00 до 99. В их примере данные чека представляли собой следующую строку:
- <math>56~99~01~12~72~64</math>
Эти шесть входных параметров выставлялись на ручках с передней стороны устройства. Строка проверки <math>68~40~100</math> появлялась на трех ручках c левой стороны. Другими словами, «Message Protector» реализовывал следующее линейное преобразование в виде перемножения матрицШаблон:Sfn:
- <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, в заявлении на патент оно было описано как устройство обнаружения ошибок. Однако в 1931 году Хилл предложил модернизировать «Message Protector» таким образом, чтобы его можно было использовать в качестве шифратора. Для этого матрица шифрования должна была быть квадратной и обратимой. Функционал этой матрицы воспроизводился внутренней конструкцией аппарата, в которую сложно было вносить изменения. Кроме того, если бы матрица шифрования не была инволютивной, то потребовалось бы два устройства типа «Message Protector»: один для шифрования, другой для дешифровкиШаблон:Sfn.
Шифр Хилла
Шаблон:Main Шифр Хилла считается наиболее значимой работой Хилла в области криптографии. Впервые шифр был опубликован в American Mathematical Monthly в 1929 году в статье «Cryptography in an Algebraic Alphabet»Шаблон:Sfn. Шифр Хилла принципиально схож с шифрованием на открытом ключе, так как использует два ключа для шифрования и дешифровки — аналоги открытого и закрытого ключей в криптосистемах с открытым ключом. Отличие же заключается в том, что криптоаналитик, будучи специалистом в области линейной алгебры и модульной арифметики, может легко вычислить закрытый ключ, зная ключ шифрованияШаблон:Sfn. Следующей собенностью этого шифра было то, что при его разработке Хилл использовал нелинейные перестановки алфавитных символовШаблон:Sfn, которые обеспечивали шифр бóльшей криптостойкостью[4]:
- <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, бóльшая часть которой была посвящена алгебраическому аппарату, наиболее известному сейчас как коммутативное кольцо.
Считается, что предшественником шифра Хилла является шифр, предложенный Джеком Левином (Шаблон:Lang-en). Оба шифра использовали один и тот же математический аппарат с одной лишь разницей в том, что шифр Хилла полиграфичен: сообщение разбивается на блоки и каждый блок шифруется раздельно, в то время как в шифре Левина два сообщения объединялись в одно, и только затем шифровалисьШаблон:Sfn.
Безусловно, шифр Хилла был мощным толчком в развитии криптографии, как прикладной науки, о чем написано во «Взломщиках кодов» Дэвида КанаШаблон:Sfn: Шаблон:Начало цитаты … хотя система шифрования, предложенная Хиллом, не имела практического использования, она оказала огромное влияние на криптографию. Когда он [Хилл] опубликовал свои статьи в 1929 и 1931 годах, криптография, как и другие прикладные науки, начала искать решения своих проблем в широком применении математики… Хилл ускорил эту тенденцию. Шаблон:Oq Шаблон:Конец цитаты
Публикации
Примечания
Литература
Книги
Статьи
- ↑ Диссертация в оригинале имела название «Aggregate-functions and an Application in Analysis Situs», однако неизвестно кто выступил в качестве научного руководителя Лестера
- ↑ Джулия умерла 14 января 2013 года в возрасте 89 лет в Шаблон:Не переведено 2, Висконсин
- ↑ Шаблон:Патент США
- ↑ Этот факт был отмечен в книге «Elementary Cryptanalysis: A Mathematical Approach»Шаблон:Sfn Абраама Синкова
Шаблон:Выбор языка Шаблон:Добротная статья
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- Преподаватели Хантерского колледжа
- Преподаватели Йельского университета
- Преподаватели Университета Монтаны
- Преподаватели Университета Мэна
- Теория кодирования
- Теория информации
- Обнаружение и устранение ошибок
- Криптографы США
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии