Здавалка
Главная | Обратная связь

Односторонние функции и функции-ловушки



Центральным понятием в теории асимметричных криптогра­фических систем является понятие односторонней функции.

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

Под функцией мы будем понимать семейство отображений {fn}, где fn: Sn ® Sm, m = m(n). Для простоты предположим, что n пробегает натуральный ряд, а отображения fn определены всюду. Функция f называется честной, если $ полином q(x), такой что " n q(m(n)) і n.

Формально понятие односторонней функции описывается следующим образом:

Определение 3.1. Четная функция f называется односторонней, если

1. Существует полиномиальный алгоритм, который для всякого x вычисляет f(x);

2. Для любой полиномиальной вероятностной машины Тьюринга A выполнено следующее. Пусть строка x выбрана случайным образом из множества Sn. Тогда для любого полинома p и всех достаточно больших n

P{f(A(f(x))) = f(x)} < 1/p(n).

Второе условие качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга A может по данному y найти x из уравнения f(x) = y лишь с пренебрежимо малой вероятностью.

Заметим, что требование честности опустить нельзя. Поскольку длина входного слова f(x) машины A равна m, ей может не хватить полиномиального от m времени просто на выписывание строки x.

Существование односторонних функций является необходимым условием стойкости многих криптосистем. Вернемся к примеру, приведенному в п. 3.1. Рассмотрим функцию f, такую, что f(r) = k1. Она вычислима с помощью алгоритма G за полиномиальное время. Покажем, что если f – не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм A, обращающий f с вероятностью по крайней мере 1/p(n) для некоторого полинома p. Злоумышленник может подать на вход алгоритма значение ключа k1 и получить с указанной вероятностью некоторое значение r' из прообраза. Далее злоумышленник подает r' на вход алгоритма G и получает пару ключей (k1, k2'). Хотя k2' не обязательно совпадает с k2, по определению криптосистемы для любого открытого текста m. Поскольку k2' найден с вероятностью по крайней мере 1/p(n), схема нестойкая.

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

В качестве задач, приводящих к односторонним функциям, можно привести следующие.

1. Разложение числа на простые сомножители.

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

2. Дискретное логарифмирование в конечном простом поле.

Допустим, задано большое простое число p и пусть g – примитивный элемент поля GF(p). Тогда для любого a вычислить ga(mod p) просто, а вычислить a по заданным k = ga(mod p) и p оказывается затруднительным.

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

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

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

 

Алгоритм RSA

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :

Выбираются два простых (!) числа p и q

Вычисляется их произведение n(=p*q)

Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

Два числа (e,n) – публикуются как открытый ключ.

Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел :

Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку.операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Теперь умножим обе ее части на x : (x(-y)(p-1)(q-1)+1)mod n = 1*x = x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m : ((ci)d)mod n = ((mi)e*d)mod n = mi.

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







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.