Сергей Дориченко - 25 этюдов о шифрах

Еще одна большая проблема — дискретное логарифмирование в конечных полях. Пусть, например, нам даны элементы a и b из конечного поля F , причем известно, что a = b x при некотором натуральном x . Задача дискретного логарифмирования состоит в том, чтобы определить это x . Можно, разумеется, просто перебирать последовательно все натуральные числа, проверяя, выполнено ли указанное равенство, но это будет экспоненциальный алгоритм. Пока наилучший из разработанных математиками алгоритмов дискретного логарифмирования является субэкспоненциальным.

В настоящее время эти описанные трудные математические проблемы имеют многочисленные криптографические приложения (см. этюды 3.5, 3.6, 3.7).

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

Однако уже в начале 1977 г. американские специалисты по компьютерным наукам Р. Ривест, А. Шамир и Л. Адлеман придумали одну такую функцию. Система на основе этой функции оказалась очень практичной и получила широкое распространение под названием «система RSA» по первым английским буквам фамилий авторов.

Опишем систему RSA. При этом мы будем использовать без подробных пояснений обозначения и результаты этюдов 3.2 и 3.3. Пусть n = p q , где 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}.

Функцию F K : X → Y определим равенством: F K ( x ) = x e (mod n ).

Свойство а) односторонней функции с секретом выполнено для F K очевидным образом. Проверим свойство в). Для этого просто укажем, как при известном K инвертировать функцию F K : решением уравнения F K ( x ) = y будет x = y d (mod n ). Подробное доказательство этого факта оставляем читателю, приведем лишь необходимые выкладки без комментариев:

d ∙ e = φ ( n )∙ m + 1

( x e ) d (mod n ) = x φ ( n )∙ m +1(mod n ) = ( x φ ( n )) m ∙ x (mod n ) = (1) m ∙ x (mod n ) = x .

Свойство б) для функции F K строго не доказано. Пока общепризнано, что для инвертирования F K необходимо разложить n на множители, а, как указывалось в этюде 3.4, задача факторизации целых чисел относится к трудным математическим задачам.

Таким образом, описанную функцию F K можно считать кандидатом на звание односторонней функции с секретом. Система RSA строится с помощью этой функции так, как рассказано в этюде 3.2.

В газете «Известия» за 29 апреля 1994 г. под заголовком «Сверхсекретный шифр разгадан за 17 лет» появилось следующее сообщение: «Когда в 1977 году математики Рональд Ривест, Ади Шамир и Леонард Адлеман зашифровали фразу из нескольких слов, используя комбинацию из 129 цифр, они утверждали, что на разгадку понадобятся триллионы лет. Однако ключ к самому сложному в мире шифру «РСА-129» (RSA) был найден за 17 лет... Разгадка шифра за такой относительно короткий срок имеет огромное значение для государственных организаций и предпринимателей, которые пользуются аналогичными длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных...» Пока это сообщение не подтверждено научными публикациями, ясно лишь, что речь идет о том, что удалось разложить на множители то 129-значное число, которое было использовано в 1977 году. Но уже давно в реальных системах RSA используются более длинные числа.

Подумайте сами :

1. Разберите примеры работы системы RSA, приведённые на стр. 241–243 книги М. Гарднера «От мозаик Пенроуза к надёжным шрифтам».

Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллмэн в той же работе предложили еще одну новую идею — открытое распределение ключей . Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов A и B по открытым каналам связи, чтобы решить следующие задачи:

1) вначале у A и B нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у A и B появляется, т.е. вырабатывается;

2) противник, который перехватывает все передачи информации и знает, что хотят получить A и B , тем не менее не может восстановить выработанный общий ключ A и B .

Диффи и Хеллмэн предложили решать эти задачи с помощью функции F ( x ) = α x (mod p ), где p — большое простое число, x — произвольное натуральное число, α — некоторый примитивный элемент поля GF ( p ).

Примитивным называется такой элемент a из GF ( p ), что каждый элемент поля, за исключением нуля, может быть представлен в виде степени a . Можно доказать, хотя это и не просто, что примитивный элемент всегда существует.

Общепризнано, что инвертирование функции α x (mod p ), т.е. дискретное логарифмирование, является трудной математической задачей (см. этюд 3.4).

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

Числа p и α считаются общедоступными.

Абоненты A и B независимо друг от друга случайно выбирают по одному натуральному числу — скажем x ( A ) и x ( B ). Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

y ( A )= α x ( A )(mod p ), y ( B )= α x ( B )(mod p ).

Потом они обмениваются этими элементами по каналу связи. Теперь абонент A , получив y ( B ) и зная свой секретный элемент x ( A ), вычисляет новый элемент

y ( B ) x ( A )(mod p )=( α x ( B )) x ( A )(mod p ).

Аналогично поступает абонент B :

y ( A ) x ( B )(mod p )=( α x ( A )) x ( B )(mod p ).

Из свойств поля следует, что тем самым у A и B появился общий элемент поля, равный α x ( A ) x ( B ). Этот элемент и объявляется общим ключом A и B .