Математический гений в криптографии: от сцитала до RSA

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

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

Этот пост — адаптация лекции Евгения Бережного, доктора физико-математических наук и профессора математического факультета ярославского Демидовского университета, которая прошла в Точке кипения ЯрГУ.

Давайте на примерах рассмотрим общие принципы криптографии, существовавшие до эпохи вычислительных машин.

Шифрование в древности: несколько примеров

Натан Ротшильд когда-то сказал легендарную фразу, что тот, кто владеет информацией — владеет миром. 

И хотя с тех пор никто нам внятно так и не объяснил, зачем нужно этим миром владеть, информация в цене только растет.

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

Первые попытки закрыть информацию были, по теперешним меркам, наивно-примитивны: часть информации просто писали на другом языке. 

Например, вместо греческого языка текст писали на латинском. Это делали для той части греков, которые не знали латынь.

Современная криптография работает по похожему принципу — изобретается некий «язык», который недоступен основной массе.

Сцитала — первый механический шифр

Одна из первых криптографических систем и первых попыток изобрести свой секретный язык — шифросистема сцитала (другое название — скитала). 

Главная деталь такой системы — стержень или конус определенного диаметра. На него наматывали длинную полоску бумаги, на витках которой записывали текст. Затем бумагу снимали и отправляли, скажем, в другой город, где получатель имел цилиндр или конус аналогичной формы. Намотав такую бумагу на такой стержень, человек мог прочитать послание.

 Чтобы такая система работала, необходимо, чтобы и на передаче, и на приёме для восстановления информации использовали один и тот же цилиндр. Это был один из самых первых известных нам механических шифров. И, если говорить современным языком, он был не очень криптостойким.

Шифр Цезаря

Следующие шифросистемы были более хитрыми. Например, стоит упомянуть так называемый «шифр Цезаря». Суть шифра состояла в подмене значений. Предположим, у нас есть алфавит, неважно какой — латинский, русский, цифровой. И есть цифры — от единицы до пяти. Каждой цифре соответствует другая цифра, например, единице — тройка, двойке — пятерка, тройке — четверка, четверке — двойка, пятерке — единица. Таким образом, если необходимо было передать сообщение в виде последовательности цифр 1, 2, 3, 4, 5, информацию кодируют как 3, 5, 4, 2, 1. Для восстановления исходной информации на приеме используют табличку с теми же соответствиями символов.

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

Поворотная решетка: надежный механический шифр

Совершенствуя навыки тайнописи, человек создавал все более экзотические шифры. Один из них — поворотная решетка. Как и в случае со сциталой, это механический шифр. Для него необходим специальный инструмент: некий квадратный трафарет с вырезанными отверстиями-окошечками. В этих отверстиях писали текст сообщения. Далее решетку поворачивали на 90 градусов относительно центра, и отверстия попадали на чистые поля бумаги, где можно было продолжать текст. Потом решётку поворачивали еще два раза. Когда текст сообщения заканчивался, оставшиеся пустые места заполняли случайными буквами. 

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

Обычно под криптостойкостью понимают количество идентичных шифров, похожих на данный. Если вернуться к шифру Цезаря и нашему примеру с цифрами от единицы до пяти, то всего количество перестановок будет 5!. Поэтому криптостойкость нашего примера шифрования будет 1/5!. Это, конечно, не очень большое число, но если у нас 32 элемента в алфавите, то вероятность того, что мы угадаем шифр, уже будет 1/32!.

Если число элементов поворотной решетки вдоль одной стороны будет 4n, то криптостойкость метода составит 4²ⁿ.

По мере развития криптографии появлялось все больше и больше «секретов», в то время как главный принцип — замещения — оставался неизменным.

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

Переход в эпоху вычислительной техники и создание несимметричного шифра

Промышленные криптосистемы появились позже, когда возникла необходимость скрывать большие объемы данных и ограничивать доступ к информации государственной важности. Во вторую мировую войну наибольшую известность обрела немецкая шифровальная машина «Энигма», историю которой все знают по фильмам «U-571», «Игра в имитацию» и других. В легендарной немецкой шифровальной машине тоже использовали  шифр, основанный на шифре Цезаря, многократно усложненный.

Подробнее об алгоритме работе «Энигмы» можно узнать из этого ролика (eng.)

С появлением электроники криптографические системы заметно изменились. Метод закрытия информации стал иным: передаваемое сообщение в виде последовательного набора цифр 1, 2, 3, 4, 5 складывали с так называемой псевдослучайной последовательностью, генерируемой вычислительными машинами. На приеме для получения исходного сообщения эту избыточную информацию вычитали с помощью тех же вычислительных машин. 

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

RSA — имея зашифрованное сообщение и шифровальный ключ, расшифровать практически нереально

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

Даже в опубликованной в 1988 году советской брошюре по криптографии было написано, что эта тема себя исчерпала и не может содержать ничего нового.

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

Для взлома этой системы на то время понадобилось бы примерно 10 тысяч лет.

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

Предположим, у нас есть произвольное целое число n. И давайте возьмем m=5. Произвольное число n можно поделить на пять, в результате чего получится частное плюс остаток. Остаток может принимать значение 0, 1, 2, 3, 4. Оказывается, эти остатки могут вести себя как обычные числа. Запишем две таблицы — таблицу сложения для остатков и таблицу умножения для остатков. 

Имея на руках такие таблицы, можно опять получить новую арифметику. Объекты с такой новой арифметикой обозначаются как Z(m). Остаток от деления числа a на m записывается следующим образом: a mod m = b. Мы записали таблицы для числа пять — Z(5). Аналогичным образом можно записать такие таблицы для любого натурального числа Z(m).

Пример

Предположим, мы имеем исходное сообщение, которое необходимо закрыть — x. Нам необходимо придумать некоторое число m — основание для создания Z(m), а также придумать число a. Эти два числа находятся в открытом доступе, известны всем. Кроме того известно, что m=m₀ × m₁, где m₁ и m₀ — простые числа (которые делятся только на себя и единицу).

Далее согласно алгоритму шифрования создаем уравнение: x^amod m = b, где b (остаток от деления x^a на m) — наше зашифрованное сообщение. Таким образом, a,b,m — известны, и необходимо вычислить x. Для решения этой задачи нужно найти разложение m = m₀ × m₁. Как только m₁и m₀ будут найдены, расшифровать сообщение можно будет достаточно быстро через специальную систему уравнений.

Изобретатели нового шифра зашифровали фразу, где в качестве a было взято число 1007, m₀ и m₁ содержали примерно по 65 знаков в десятичной системе. Математики озвучили публичные а, зашифрованную фразу и m, предлагая всем желающим расшифровать секретную фразу. Также был опубликован алгоритм, как взломать эту систему. Вся криптостойкость определялась разложением m = m₀ × m₁. 

История длилась 17 лет, пока с появлением интернета у пользователей не появилась возможность задействовать сеть компьютеров с распределенными вычислениями. За 220 дней около 1600 компьютеров смогли восстановить исходную информацию, разложив m на два простых числа. Это событие показало, что криптография как наука жива. 

Также это доказало непостижимую эффективность математики при решении реальных задач. Сама же система получила название RSA — по именам своих создателей.

Практическое применение криптографии

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

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

На передаче используют простые алгоритмы, чтобы закрыть информацию (в нашем случае — возвести x в степень a), а на приеме происходит быстрое восстановление (если вам заранее известно разложение m на m₀ и m₁). Получается несимметричная система шифрования, которая удобна и надежна. 

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

Новые принципы криптографии привели к созданию цифровой подписи — механизму, который подтверждает аутентификацию пользователя.

Им можно подписывать документы и заверять свою личность — например, в финансовых документах. 

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

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

Математика позволяет решать самые разные и сложные задачи обеспечения информационной безопасности. И по мере развития вычислительных систем алгоритмы будут только усложняться.