Лестер Гілл

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

Біографія

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

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

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

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

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

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

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

«Message Protector» (Lester-Weisner)

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

Message Protector

Хоча популярність Гіллу приніс його знаменитий шифр, його ранні публікаціїШаблон:SfnШаблон:SfnШаблон:Sfn в області теорії кодування описують запропонований ним алгоритм виявлення помилок в телеграфних кодах з використанням модульної арифметики і лінійних перетворень. У 1926 році в статті «A Novel Checking Method for Telegraphic Sequences»Шаблон:Sfn Гілл запропонував метод завадостійкого кодування лінійних блокових кодів, на два десятиліття раніше, ніж це зробив Річард ГеммінгШаблон:Sfn. Метод не став загальновживаним, про що Девід Кан написав у своїй книзі «Зломщики кодів»Шаблон:Sfn Шаблон:Початок цитати [Гілл] хотів виручити грошей із запропонованої ним схеми перевірки, однак метод не знайшов практичного застосування … Шаблон:Oq Шаблон:Кінець цитати Проте під час роботи в Хантерському коледжі Гілл спільно зі своїм колегою Луї Вайснером, висунув заявку на патент пристрою «Message Protector», робота якого заснована на методі Гілла за виявлення помилок. У заяві патенту Гілл і Вайснер запропонували використовувати «Message Protector» для перевірки чеків під час платіжних переказів. Перевірка чека починалася збором чекових даних, які кодувалися в рядок двозначних номерів від 00 до 99. На їх прикладі дані чека представляли собою наступний рядок:

$569901127264$

Ці шість вхідних параметрів виставлялися на ручках з передньої сторони пристрою. Рядок перевірки $6840100$ з'являвся на трьох ручках з лівого боку. Іншими словами, «Message Protector» реалізовував наступне лінійне перетворення у вигляді перемноження матрицьШаблон:Sfn:

$\left[\begin{array}{cccccc}3& 1& 2& 2& 3& 1\\ 2& 3& 1& 3& 1& 2\\ 1& 2& 3& 1& 2& 3\end{array}\right]\left[\begin{array}{c}56\\ 99\\ 01\\ 12\\ 72\\ 64\end{array}\right]=\left[\begin{array}{c}68\\ 40\\ 100\end{array}\right](\mathrm{mod}101)$

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

Шифр Гілла

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

$\begin{array}{cccccccccc}a& b& c& d& e& f& g& h& i& j\\ 5& 23& 2& 20& 10& 15& 8& 4& 18& 25\end{array}$

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

Вважається, що попередником шифру Гілла є шифр, запропонований Джеком Левіним (Шаблон:Lang-en). Обидва шифри використовували один і той же математичний апарат з однією лише різницею в тому, що шифр гілла поліграфічний: повідомлення розбивається на блоки і кожен блок шифрується окремо, в той час як в шифрі Левіна два повідомлення об'єднувалися в одне, і тільки потім шифрувалисяШаблон:Sfn.

Безумовно, шифр Гілла був потужним поштовхом у розвитку криптографії, як прикладної науки, про що написано в «Зломщиках кодів» Девіда КанаШаблон:Sfn: Шаблон:Початок цитати ... хоча система шифрування, запропонована Гіллом, не мала практичного використання, вона справила величезний вплив на криптографію. Коли він [Гілл] опублікував свої статті в 1929 і 1931 роках, криптографія, як і інші прикладні науки, почала шукати вирішення своїх проблем в широкому застосуванні математики ... Гілл прискорив цю тенденцію. Шаблон:Oq Шаблон:Кінець цитати

Публікації

• 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.

Література

Книги

• 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.

Статті

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття