Лестер Гілл

Лестер Гілл
англ. Lester S. Hill
Народився	18 січня 1891(1891-01-18) Нью-Йорк, Нью-Йорк, США
Помер	1961 Нью-Йорк, Нью-Йорк, США
Країна	США
Діяльність	математик, криптограф
Alma mater	Колумбійський університет Єльський університет Гантерський коледж
Галузь	теорія інформації і криптографія
Заклад	Принстонський університет Єльський університет Гантерський коледж Університет Монтани^d
Науковий ступінь	доктор філософії

Лестер Сандерс Гілл (англ. Lester S. Hill; 18 січня 1890, Нью-Йорк, США — 9 січня 1961, там само) — американський математик, учений в області криптографії. Запропонував власний метод виявлення помилок у телеграфному коді. Зробив великий внесок у розвиток криптографії та теорії кодування. Відомий як творець шифру, побудованого на синтезі модульної арифметики і лінійної алгебри для символічного кодування.

Біографія

Гілл Лестер народився 18 січня 1890 року в Нью-Йорку. Ступінь бакалавра математичних наук отримав в 1911 році в Колумбійському коледжі (англ. Columbia_College,_Columbia_University). Закінчив магістратуру Колумбійського університету в 1913 році. Після отримання диплома магістра Гілл викладав астрономію й математику в університеті штату Монтана (1914—1915), потім в Прінстонському університеті (1915—1916)^[1].

25 травня 1917 року в Нью-Йорку Гілл записався добровольцем у Військово-морські сили США і був прийнятий на службу моряком другого класу в резерв берегової охорони. На той момент його єдиним близьким родичем був батько Джеймс Едвард Гілл (англ. James Edward Hill), проживав у Клівленді^[2]. 21 липня 1917 року Лестера закликали на очну службу, де 23 липня йому було присвоєно звання головного старшини. На початку серпня його підвищили до звання прапорщика. C 1919 по 1921 рік Гілл служив в резерві ВМС США, як представник продажів у Європі^[1].

Після служби у Військово-морських силах США під час Першої світової війни Гілл працював доцентом в університеті Мену з 1921 по 1922 і інструктором в Єльському університеті (1922—1927), де він захистив докторську дисертацію^[3], і став доктором математичних наук в 1926 році. Ідеї дисертації були розвинуті автором у статті «Concerning Certain Aggregate Functions»^[4], опублікованій в Американському журналі математики в 1927 році. Приблизно в цей же час він одружується на Мейбл Хіт (англ. Mabel Hitt) родом з міста Калпепер, штат Вірджинія, яка викладала у вищій школі Пуерто-Рико. Їх єдина дочка Джулія народилася у 1923 році в Нью-Хейвені, штат Коннектикут (Джулія померла 14 січня 2013 року у віці 89 років у Вісконсіні).

Основну частину своєї наукової та викладацької діяльності Гілл присвятив роботі на математичному факультеті в Хантерському коледжі, куди був прийнятий на посаду викладача математики у 1927 році. У 1929 році Гілл отримав звання доцента, а в 1956 році став професором і залишався ним аж до свого відходу в 1960 році, причиною якого стало слабке здоров'я^[5].

Під час Другої світової війни Гілл викладав математику з липня 1945 по січень 1946 в університеті армії США, в місті Біарріц, у Франції^[1].

Гілл Лестер помер 9 січня 1961 після тривалої хвороби в госпіталі Лоуренса.

Наукова діяльність

«Message Protector» (Lester-Weisner)

«Message Protector» — внутрішній устрій

Message Protector

Хоча популярність Гіллу приніс його знаменитий шифр, його ранні публікації^[6][7][8] в області теорії кодування описують запропонований ним алгоритм виявлення помилок в телеграфних кодах з використанням модульної арифметики і лінійних перетворень. У 1926 році в статті «A Novel Checking Method for Telegraphic Sequences»^[9] Гілл запропонував метод завадостійкого кодування лінійних блокових кодів, на два десятиліття раніше, ніж це зробив Річард Геммінг^[10]. Метод не став загальновживаним, про що Девід Кан написав у своїй книзі «Зломщики кодів»^[11]

[Гілл] хотів виручити грошей із запропонованої ним схеми перевірки, однак метод не знайшов практичного застосування …

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

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

Проте під час роботи в Хантерському коледжі Гілл спільно зі своїм колегою Луї Вайснером, висунув заявку на патент пристрою «Message Protector»^[12], робота якого заснована на методі Гілла за виявлення помилок. У заяві патенту Гілл і Вайснер запропонували використовувати «Message Protector» для перевірки чеків під час платіжних переказів. Перевірка чека починалася збором чекових даних, які кодувалися в рядок двозначних номерів від 00 до 99. На їх прикладі дані чека представляли собою наступний рядок:

${\displaystyle 56~99~01~12~72~64}$

Ці шість вхідних параметрів виставлялися на ручках з передньої сторони пристрою. Рядок перевірки ${\displaystyle 68~40~100}$ з'являвся на трьох ручках з лівого боку. Іншими словами, «Message Protector» реалізовував наступне лінійне перетворення у вигляді перемноження матриць^[13]:

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

Хоча вважається, що цей пристрій був прямою реалізацією шифру Гілла^[14], в заяві на патент він був описаний як пристрій виявлення помилок. Однак у 1931 році Гілл запропонував модернізувати «Message Protector» таким чином, щоб його можна було використовувати як шифратор. Для цього матриця шифрування повинна була бути квадратною та оборотною. Функціонал цієї матриці відтворювався внутрішньою конструкцією апарату, в яку складно було вносити зміни. Крім того, якби матриця шифрування не була інволютивною, то знадобилося б два пристрої типу «Message Protector»: один для шифрування, інший-для дешифрування^[15].

Шифр Гілла

Шифр Гілла вважається найбільш значущою роботою Гілла в області криптографії. Вперше шифр був опублікований в American Mathematical Monthly в 1929 році в статті «Cryptography in an Алгебраїчна Alphabet»^[16]. Шифр Гілла принципово схожий з шифруванням на відкритому ключі, так як використовує два ключа для шифрування і дешифрування — аналоги відкритого та закритого ключів у криптосистемах з відкритим ключем. Відмінність же полягає в тому, що криптоаналітик, будучи фахівцем в області лінійної алгебри та модульної арифметики, може легко обчислити закритий ключ, знаючи ключ шифрування^[17]. Наступною особливістю цього шифру було те, що при його розробці Гілл використовував нелінійні перестановки алфавітних символів^[18], які забезпечували шифр більшою криптостійкістю^[20]:

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

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

Вважається, що попередником шифру Гілла є шифр, запропонований Джеком Левіним (англ. Jack Levine). Обидва шифри використовували один і той же математичний апарат з однією лише різницею в тому, що шифр гілла поліграфічний: повідомлення розбивається на блоки і кожен блок шифрується окремо, в той час як в шифрі Левіна два повідомлення об'єднувалися в одне, і тільки потім шифрувалися^[22].

Безумовно, шифр Гілла був потужним поштовхом у розвитку криптографії, як прикладної науки, про що написано в «Зломщиках кодів» Девіда Кана^[11]:

... хоча система шифрування, запропонована Гіллом, не мала практичного використання, вона справила величезний вплив на криптографію. Коли він [Гілл] опублікував свої статті в 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.

Примітки

1. Хилл, Л.С — Candidate for Promotion, 1956.
2. Chris Christensen — Lester Hill Revisited, 2014, с. 294.
3. Диссертация в оригинале имела название «Aggregate-functions and an Application in Analysis Situs», однако неизвестно кто выступил в качестве научного руководителя Лестера
4. Хилл, Л. С. — Concerning Certain Aggregate Functions, 1927.
5. Chris Christensen — Lester Hill Revisited, 2014, с. 307.
6. Хилл, Л. С. — A Novel Checking Method for Telegraphic Sequences, 1926.
7. Гілл, Л. С. — The Role of Prime Numbers in the Checking of Telegraphic Communications, квітень, 1927.
8. Гілл, Л. С. — The Role of Prime Numbers in the Checking of Telegraphic Communications, липень, 1927.
9. Гілл, Л. С. - A Novel Checking Method for Telegraphic Sequences , 1926.
10. Chris Christensen - Lester Hill's Error-Detecting Codes, 2012, с. 96.
11. Девід Кан - «Зломщики кодів», 1996.
12. US patent 
13. Chris Christensen — Lester Hill Revisited, 2014, с. 304.
14. Chris Christensen — Lester Hill's Error-Detecting Codes, 2012, с. 97.
15. Chris Christensen — Lester Hill Revisited, 2014, с. 305.
16. Хилл, Л. С. — Cryptography in an Algebraic Alphabet, 1929.
17. Chris Christensen — Lester Hill Revisited, 2014, с. 296.
18. Дэвид Кан — «Взломщики кодов», 1996, с. 404-410.
19. Абраам Синков — Elementary Cryptanalysis: A Mathematical Approach, 1998.
20. Этот факт был отмечен в книге «Elementary Cryptanalysis: A Mathematical Approach»^[19] Абраама Синкова
21. Хилл, Л. С. — Concerning Certain Linear Transformation Apparatus in Cryptography, 1931.
22. Chris Christensen — Lester Hill Revisited, 2014, с. 300-301.

Література

Книги

• David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Macmillan, 1996. — 1200 с. — ISBN 978-0684831305.
• Abraham Sinkov. Elementary Cryptanalysis: A Mathematical Approach — The L. W. Singer Company, 1998. — 232 с. — ISBN 978-0883856222.

Статті

• Chris Christensen. Lester Hill Revisited // Cryptologia. — 2014. — Vol. 38, no. 4, (08). — 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. — Vol. 36, no. 2, (04). — P. 88-103. — ISSN 1558-1586. — DOI:10.1080/01611194.2011.632805.
• Lester Hill Dies; Mathematician // New York Times. — 1961. — . — 01. — P. 47. — ISSN 0362-4331.
• Хилл, Л. С. Candidate for Promotion. — 1956. — 04.