Лестер Гілл

Хоча популярність Гіллу приніс його знаменитий шифр, його ранні публікації [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 }$ з'являлася на трьох ручках c лівого боку. Іншими словами, «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.

• Дэвид Кан. Взломщики кодов. 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. . — Т. 38, № 4. — ISSN 1558-1586. — DOI:10.1080/01611194.2014.915260.
• Chris Christensen, David Joyner, Jenna Torres. . — Т. 36, № 2. — ISSN 1558-1586. — DOI:10.1080/01611194.2011.632805.
• . — ISSN 0362-4331.
• Хилл, Л. С. .