Следовательно, он не может вычислить га в равенстве . Противник также не может воспроизвести действия законного получателя сообщения . Выберем параметры аналогично тому, как это было сделано в примере . Пусть абонент В выбрал для себя секретное число св — . Абонент А выбирает случайно число к, например к . Теперь А посылает к В зашифрованное сообщение в виде пары чисел . Мы видим, что В смог расшифровать переданное сообщение. Ясно, что по аналогичной схеме могут передавать сообщения любые два абонента в сети. Заметим, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных . Мы видели, что шифр Шамира полностью решает задачу обмена сообщениями, закрытыми для прочтения, в случае, когда абоненты могут пользоваться только открытыми линиями связи. Однако при этом сообщение пересылается три раза от одного абонента к другому, что является недостатком. Интересно то, что она базируется на другой односторонней функции, отличной от дискретного логарифма. Кроме того, здесь . Криптосистемы с открытым ключом Таблица . Секретная инф. А . Пусть Алиса хочет передать сообщение . Алиса шифрует сообщение по формуле е . мы встретимся с еще одним изобретением современной криптографии односторонней функцией с . В этой системе используются следующие два факта из теории. Задача проверки числа на простоту является сравнительно легкой. Задача разложения чисел вида . Пусть в нашей системе есть абоненты А, В , С,. Затем он вычисляет число . Боб, получивший зашифрованное сообщение, вычисляет га. абонент В получает исходящее от А сообщение. По построению протокола га. Отсюда и из теоремы . Первое свойство следует из утверждения . Для доказательства второго свойства заметим, что злоумышленник знает только открытые параметры . Для того чтобы найти с, он должен знать значение ф . Вообще говоря, он может найти Р и . Отметим, что выбор больших случайных Р и . Криптосистемы с открытым ключом . Такие односторонние функции с лазейкой находят применение и в других разделах криптографии. Отметим, что для схемы . Однако этого не требуется от второго открытого параметра . Тогда шифрование выполняется максимально быстро, всего за два умножения. Допустим, Алиса хочет передать Бобу число . Пусть Боб выбрал следующие параметры. Найдем св с помощью обобщенного алгоритма Евклида. Кодируем га по формуле . Только Боб знает св . Таким образом, Боб расшифровал сообщение Алисы. Рассмотренная система невскрываема при больших Р и . Злоумышленник не может читать сообщения, предназначенные для В, однако он может передать сообщение к Б от имени А. Избежать этого можно, используя более сложные протоколы, например, следующий. А хочет передать В сообщение га. Сначала А вычисляет число е — . Затем А вычисляет число . Как и в исходной схеме . В знает, что сообщение пришло от А, т. Она — одно из широко используемых на практике изобретений современной криптографии и будет систематически изучаться в главе . В данном параграфе мы рассмотрим два таких метода, для того чтобы дать читателю некоторое представление об этой . Мы видели, что многие рассматриваемые шифры основываются на односторонней функции у . Однако отыскание х по известным а и у , т. вычисление дискретного логарифма, — задача намного более трудная. Как было показано при рассмотрении шифра Шамира . Поэтому нам достаточно рассматривать только показатели. Время возведения в степень по алгоритмам из . Теперь перейдем к задаче отыскания х в . Сначала оценим сложность прямого перебора. Для этого можно было бы сначала вычислить а. Если нет, то проверяем а. Таким образом, время прямого перебора . В описываемом ниже методе . Чтобы сделать сравнение более наглядным, выразим время вычисления через длину числа р в . Обозначим эту длину в битах через п. При вычислениях по модулю р имеем п . Вопрос о существовании более быстрых алгоритмов для вычисления дискретных логарифмов, как и для решения других обратных задач, возникающих в криптоанализе, остается открытым. Методы взлома шифров . Это был один из первых методов, который показал, что задача вычисления дискретного логарифма может быть решена значительно быстрее, чем методом перебора. Перейдем к описанию этого метода отыскания х в . Сначала берем два целых числа га и к , такие, что ткр. Вычислим два ряда чисел у, . Кроме того, целые числа . Первая часть утверждения следует из приводимой ниже символической цепочки равенств, где все вычисления даны по модулю р, а деление соответствует умножению на обратный элемент. Для этого сведем все числа вида . Мы видим, что в таблице содержатся все числа от . Таким образом, любой показатель степени х р будет содержаться в таблице, . Выберем га , к . Дальнейшие вычисления не проводим, так как уже нашлись одинаковые числа в . Объясним происхождение названия рассмотренного метода. Мы знаем, что в криптографии р — большое простое число, значит га и к тоже большие. Оценим сложность этого метода. Время вычислений по данному методу при больших р удовлетворяет неравенству . Методы взлома шифров Доказательство. Мы можем взять . Мы знаем, что для . У нас все числа берутся из множества . Отсюда мы сразу получаем время, затраченное на вычисление рядов . Однако мы не учли все этапы алгоритма. Мы не учли время, требуемое для нахождения равных чисел в этих рядах. При больших кит это далеко не простая задача. Она решается следующим образом. всего требуется порядка у. После сортировки объединенного ряда надо просмотреть отсортированный объединенный ряд и найти два равных числа из разных рядов. Таким образом, суммируя время вычисления на всех этапах, получаем . На настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в уравнениях типа . Для удобства описания алгоритма введем следующее понятие. Число п называется р . Алгоритм исчисления порядка . Перейдем непосредственно к описанию алгоритма.