Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

• Название: Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография
• Автор: Жуан Гомес
• Издательство: ООО «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0682-6; 978-5-9774-0639-0 (т. 2)

Если бы историю человечества можно было представить в виде шпионского романа, то главными героями этого произведения, несомненно, стали бы криптографы и криптоаналитики. Первые — специалисты, виртуозно владеющие искусством кодирования сообщений. Вторые — гении взлома и дешифровки, на компьютерном сленге именуемые хакерами. История соперничества криптографов и криптоаналитиков стара как мир.

Эволюционируя вместе с развитием высоких технологий, ремесло шифрования достигло в XXI веке самой дальней границы современной науки — квантовой механики. И хотя объектом кодирования обычно является текст, инструментом работы кодировщиков была и остается математика.

Эта книга — попытка рассказать читателю историю шифрования через призму развития математической мысли.

---

В конце процесса отправитель и получатель договариваются о простой проверке.

Выполнив три предварительных шага, описанных выше, и имея достаточное количество сохраненных битов, отправитель и получатель связываются друг с другом любым удобным способом и вместе проверяют группу битов (скажем, 100), выбранных из общего числа случайным образом. Если все 100 битов совпали, отправитель и получатель могут быть полностью уверены, что ни один шпион не перехватил их передачу, и выбирают некоторую последовательность в качестве одноразового шифра. В противном случае им придется повторить процесс.

32 сантиметра абсолютной секретности

Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту теорию попытались применить на практике, она была встречена очень скептически.

В 1989 г., после более чем года напряженной работы, Беннет построил систему, состоящую из двух компьютеров, расположенных на расстоянии 32 сантиметра друг от друга, один из которых выступал в роли отправителя, а другой — получателя.

После нескольких часов проб и поправок эксперимент был признан успешным. Отправитель и получатель выполнили все этапы процесса, включая проверку шифра. Возможность квантовой криптографии была доказана.

Исторический эксперимент Беннета имел один очевидный недостаток: секрет посылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же эффективна. Однако в последующие годы другие исследовательские группы увеличили это расстояние. В 1995 г. ученые из Университета Женевы использовали оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-Аламосской национальной лаборатории в США повторила этот процесс на расстоянии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот метод уже может быть использован в местах, где строжайшая тайна имеет первостепенное значение, например, в правительственных зданиях и офисах компаний.

Если не брать во внимание соображения, связанные с техническими ограничениями для отправки сообщений, возможность того, что передача будет подслушана, совершенно исключена даже на квантовом уровне. Этот квантовый шифр представляет собой окончательную победу тайны над ее разглашением, криптографов над криптоаналитиками. Все, о чем нам осталось теперь позаботиться — вопрос, во всяком случае, немаловажный — как применять этот мощный инструмент и кто в результате получит наибольшую выгоду.

Приложение

Различные классические шифры и спрятанные сокровища

В этом приложении мы расскажем о различных классических криптографических шифрах, упоминаемых в предыдущих главах, но не описанных там достаточно подробно. Все они представляют различные криптографические методы и интересны даже в качестве развлечения. В завершении мы приведем процесс расшифровки из рассказа американского писателя Эдгара Аллана По, в котором блестяще проиллюстрировано применение частотного криптоанализа.

Шифр Полибия

Этот шифр, один из древнейших, о котором у нас имеется подробная информация, основан на выборе пяти букв алфавита, служащих заголовками строк и столбцов таблицы размером 5 x 5, которая затем заполняется буквами алфавита. Шифр заменяет каждую букву алфавита парой букв, являющихся заголовками соответствующих столбца и строки. Первоначально использовался греческий алфавит из 24 букв, поэтому английские буквы I и J, как правило, комбинируются (см. таблицу, приведенную ниже, где для простоты в качестве заголовков используются буквы А — Е).

Таблица заполняется по правилу, о котором договорились отправитель и получатель.

Рассмотрим, например, следующую таблицу:

Заметим, что шифроалфавит состоит из 25 букв (5 х 5). В качестве заголовков можно использовать и цифры (например, 1, 2, 3, 4 и 5). В этом случае таблица имеет вид:

Рассмотрим шифр Полибия на примере этих двух таблиц. Мы будем шифровать сообщение BLANKS («пробелы»). По первой таблице мы получим:

В заменяется парой АВ.

L заменяется парой СА.

А заменяется парой АА.

N заменяется парой СС.

К заменяется парой BE.

S заменяется парой DC.

Зашифрованное сообщение имеет вид ABCAAACCBEDC. Если мы используем таблицу с цифрами, то получим: «123111332543».

Шифр Гронсфельда

Этот шифр, изобретенный голландцем Мостом Максимилианом Бронкхорстом, графом Гронсфельд, использовался в Европе в XVII в. Это полиалфавитный шифр, аналогичный квадрату Виженера, но менее сложный (и менее надежный). Чтобы зашифровать сообщение, рассмотрим следующую таблицу.

Далее, для каждой буквы в нашем сообщении мы выбираем случайным образом число от 0 до 9. Для сообщения MATHEMATICAL («математический») мы выбираем случайным образом 12 чисел, например: 1, 2, 3, 4, 3, 6, 7, 8, 9, 0, 1, 2. Этот набор чисел и будет ключом шифра. Теперь вместо каждой буквы сообщения мы поставим букву из строки с соответствующим номером (см. таблицу на предыдущей странице).

Буква М будет заменена буквой Р (взятой из строки номер 1 в столбце М), и так далее. Мы получим сообщение PFASRDTQKEDQ. Буква А исходного сообщения будет зашифрована как F, Т, и D. Как и для всех полиалфавитных шифров, эта система шифрования устойчива к методу перебора всех возможных вариантов и к частотному анализу. Количество ключей в шифре Гронсфельда для алфавита из 26 букв составляет 26! х 10 = 4,03 х 10 26.

Шифр Плейфера

Создатели этого шифра лорд Лайон Плейфер и сэр Чарльз Уитстон (также изобретатель электромагнитного телеграфа) были друзьями и соседями и разделяли любовь к криптографии. Их метод напоминает знаменитый шифр Полибия и тоже использует таблицу из пяти строк и пяти столбцов. В качестве первого шага каждая буква сообщения заменяется на пару букв в соответствии с ключом из пяти различных букв. В нашем примере эти пять букв будут JAMES. В случае алфавита с 26 символами мы получаем следующую таблицу:

Далее текст сообщения разбивается на пары букв или биграммы. Две буквы каждой биграммы должны быть разными. Чтобы избежать возможных совпадений, мы используем букву X. Мы также используем эту букву, чтобы завершить биграмму в случае, если последняя буква не имеет пары.

Например, сообщение TRILL будет разбито на биграммы следующим образом:

TR IL LX.

А слово TOY — так:

ТО YX.

Разбив текст на биграммы, мы можем начать шифрование, обращая внимание на следующие условия:

а) две буквы биграммы расположены в одной и той же строке;

б) две буквы биграммы расположены в одном и том же столбце;

в) ни одно из вышеперечисленных.

В случае (а) буквы биграммы заменяются буквами, расположенными справа от каждой из них («следующими» в таблице в естественном порядке). Таким образом, пара JE будет зашифрована как AS:

В случае (б) буквы биграммы заменяются буквами, которые находятся следом ниже по таблице. Например, биграмма ЕТ будет зашифрована, как FY, a TY — как YE:

В случае (с), чтобы зашифровать первую букву биграммы, мы смотрим на ее строку, пока не дойдем до столбца, содержащего вторую букву. Результат расположен на пересечении этой строки и этого столбца. Чтобы зашифровать вторую букву, мы смотрим на ее строку, пока не дойдем до столбца, содержащего первую букву.

Результат опять расположен на пересечении этой строки и этого столбца.

Например, в биграмме СО буква С будет заменена буквой G, а буква О — буквой I или К.

Чтобы зашифровать сообщение TEA («чай») с помощью ключевого слова JAMES, мы сделаем следующее.

• Разобьем слово на биграммы: ТЕ АХ.

• Букву Т заменим буквой Y.

• Букву Е — F.

• Букву А — М.

• Букву X — W.

Мы получим зашифрованное сообщение YFMW.

Криптограмма «Золотого жука»

Уильям Легран, главный герой рассказа Эдгара Аллана По «Золотой жук» (1843), определяет, где зарыт клад с сокровищами, расшифровав криптограмму, написанную на куске пергамента. Легран использовал статистический метод, основанный на частоте, с которой буквы алфавита встречаются в английских текстах. Зашифрованное послание выглядело следующим образом:

Легран начал с предположения, что оригинальный текст был написан на английском языке. В английских текстах наиболее часто встречается буква «е». Далее, в порядке уменьшения частоты, идут остальные буквы: а, о, i, d, h, n, r, s, t, u, y, c, f, g, 1, m, w, b, k, p, q, x, z.