Сергей Дориченко - 25 этюдов о шифрах
8) Для каждых двух элементов a, b ∈ F a∙b=b∙a.
9) Для каждых трех элементов a, b, c ∈ F a∙(b+c)=a∙b+a∙c.
Свойства 1) – 4) — это свойства операции сложения, свойства 5) – 8) — свойства операции умножения, а свойство 9) устанавливает связь между этими двумя операциями.
Оказывается, в математике существует много других множеств с парами операций на них, обладающих теми же самыми свойствами. Для таких множеств есть даже специальное название: поле.
Полем называется множество F с двумя отображениями («операциями»), каждое из которых сопоставляет любой паре элементов из F однозначно определенный третий элемент из F, и эти отображения (условно обозначаемые «+» и «∙») удовлетворяют девяти аксиомам (свойствам), приведенным выше.
Особенно важными для криптографии являются конечные поля. Сконструируем одно из таких полей.
Пусть p — простое число. Рассмотрим множество чисел {0, 1, 2, ..., p−1} с операциями сложения и умножения по модулю p (суммой двух чисел считаем остаток от деления на p обычной суммы, произведением — остаток от деления на p обычного произведения). Легко проверить, что свойства 1) – 4) выполнены: для свойств 1) и 4) это очевидно, элемент 0 в свойстве 2) — это обычный нуль, противоположный к элементу a в свойстве 3) — это элемент p — a. Так же легко проверяются свойства 5), 6), 8) и 9). Свойство 7) надо доказывать. Предлагаем вам доказать это самостоятельно, поясним только идею: для каждого a ∈ {0, 1, 2, ..., p−1} требуется найти такие x и y, что ax=1+py, т.е. ax−py=1, а такие x и y всегда можно найти с помощью алгоритма Евклида.
Конечное поле — очень интересный математический объект. Оказывается, например, что число элементов в конечном поле может быть только степенью простого числа, и наоборот, для любого простого числа p и для любого натурального числа n существует и в некотором смысле единственное поле из pn элементов. Для него введено даже специальное обозначение: GF(pn).
Поясним более подробно, в каком смысле поле из pn элементов единственно. В математике принято не различать многие объекты, изучаемые свойства которых совпадают. Например, для того, чтобы складывать и умножать, вовсе не обязательно учить отдельно таблицы сложения и умножения для яблок, и отдельно — для стульев. Достаточно уметь складывать числа. Число в данной ситуации можно представлять как количество единиц некоторого обобщенного продукта, неважно какого. В теории полей два поля F и G считаются «одинаковыми» или изоморфными, если можно построить такое взаимно-однозначное отображение s:F→G, чтобы для любых x1,x2∈F выполнялись условия s(x1+x2)=s(x1)+s(x2), s(x1x2)=s(x1)s(x2). Фактически это означает, что можно взаимно-однозначно сопоставить всем элементам одного поля элементы другого так, что таблицы умножения и сложения в этих полях будут «одинаковыми». Легко, например, доказать, что при изоморфизме нуль переходит в нуль, единица — в единицу.
Яркий пример использования полей в криптографии вы найдете в этюде 3.5, описывающем криптосистему RSA. Для ее полного понимания рекомендуем решить (или прочитать в любой книге по теории чисел, например, в книге И.М. Виноградова «Основы теории чисел» или в книге О. Оре «Приглашение в теорию чисел») приведенные ниже задачи.
Подумайте сами:
1. Функцией Эйлера (обозначение φ(n)) называется количество неотрицательных целых чисел, меньших n и взаимно простых с n. Пусть n = p1α1∙...∙pkαk, где p1, ..., pk — различные простые числа, а α1, ..., αk — натуральные. Доказать, что
2. (Малая теорема Ферма). Пусть p — простое число, a — число взаимно простое с p. Докажите, что тогда
3. (Теорема Эйлера). Пусть a и n — взаимно простые числа. Докажите, что тогда
3.4. Проблемы факторизации чисел и дискретного логарифмирования
Еще в младших классах школы все решают задачи по разложению чисел на простые множители. Делается это просто делением данного числа на последовательные простые числа. Если число большое, то этот алгоритм будет работать долго (даже на компьютере). Если же число очень большое (скажем, состоит из 200 знаков), самому современному компьютеру могут понадобиться годы работы. И, как это ни странно, до сих пор математики не придумали никакого другого алгоритма, работающего существенно быстрее. Проблема построения такого алгоритма называется проблемой факторизации чисел. С другой стороны, существуют быстрые алгоритмы, позволяющие с большой вероятностью определять, является ли данное число простым или нет (но никакого разложения числа на простые множители эти алгоритмы не находят).
Криптографические приложения проблемы факторизации чисел и, особенно, заинтересованность пользователей банковских систем цифровой подписи привели к резкому увеличению исследований, связанных с разложением чисел на множители. В последние годы благодаря применению тонких методов теории чисел и алгебраической геометрии было разработано несколько эффективных алгоритмов факторизации. Наилучший из таких алгоритмов еще не является полиномиальным, но уже и не экспоненциальный, он относится к классу так называемых субэкспоненциальных алгоритмов (говоря строго, его сложность превосходит любой полином от n, но меньше, чем 2N, где N=nε для любого ε>0).
Среди последних достижений в этой области можно упомянуть об успехе Ленстры и Монасси, разложивших в июне 1990 года 155-разрядное число на три простых. Для этого они использовали 1000 объединенных ЭВМ и шесть недель их машинного времени. Вычисления проводились с помощью алгоритма английского математика Дж. Полларда. Ленстра и Монасси считают, что в настоящее время (1991 г.) можно в течение года разложить новые классы целых чисел длиной до 155 разрядов, затратив на это $200 млн.
Еще одна большая проблема — дискретное логарифмирование в конечных полях. Пусть, например, нам даны элементы a и b из конечного поля F, причем известно, что a=bx при некотором натуральном x. Задача дискретного логарифмирования состоит в том, чтобы определить это x. Можно, разумеется, просто перебирать последовательно все натуральные числа, проверяя, выполнено ли указанное равенство, но это будет экспоненциальный алгоритм. Пока наилучший из разработанных математиками алгоритмов дискретного логарифмирования является субэкспоненциальным.
В настоящее время эти описанные трудные математические проблемы имеют многочисленные криптографические приложения (см. этюды 3.5, 3.6, 3.7).
3.5. Криптосистема RSA
В этюде 3.2 описано, как Диффи и Хеллмэн с помощью односторонней функции с секретом построили криптосистему с открытым ключом. Правда, они не предложили функций, удобных для реализации.
Однако уже в начале 1977 г. американские специалисты по компьютерным наукам Р. Ривест, А. Шамир и Л. Адлеман придумали одну такую функцию. Система на основе этой функции оказалась очень практичной и получила широкое распространение под названием «система RSA» по первым английским буквам фамилий авторов.
Опишем систему RSA. При этом мы будем использовать без подробных пояснений обозначения и результаты этюдов 3.2 и 3.3. Пусть n=pq, где p и q — большие простые числа, а e — некоторое число, взаимно простое с φ(n). Найдем число d из уравнения: d∙e=1(modφ(n)).
Числа p, q и d будем считать секретными и обозначим секрет K={p, q, d}. Числа n и e будем считать общедоступными. Множества открытых сообщений X и шифрованных сообщений Y будем считать равными: X = Y = {1, 2, ... , n−1}.
