Материал из РУВИКИ — свободной энциклопедии

XTR (алгоритм)

XTR (сокращение от ECSTR — «Efficient and Compact Subgroup Trace Representation») — алгоритм шифрования с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. Преимущества этого алгоритма перед другими, использующими эту идею, в более высокой скорости и меньшем размере ключа.

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

Теоретическая основа XTR[править | править код]

Алгоритм работает в конечном поле . Рассмотрим группу порядка , и её подгруппу порядка q, где p — простое число, такое, что другое достаточно большое простое число q является делителем . Группа порядка q называется XTR-подгруппой. Эта циклическая группа является подгруппой и имеет генератор g.

Арифметические операции в [править | править код]

Пусть p — простое число, такое, что p2 mod 3, а p2 — p + 1 делится на достаточно большое простое q. Так как p21 mod 3, p порождает . Таким образом, круговой многочлен является неприводимым в . Следовательно, корни и образуют оптимальный нормальный базис над и

С учетом p2 mod 3:

Таким образом, стоимость арифметических операций следующая:

  • Вычисление xp не требует умножения
  • Вычисление x2 требует двух операций умножения в
  • Вычисление xy требует трех операций умножения в
  • Вычисление xz-yzp требует четырёх операций умножения в .:[1]

Использование следов в [править | править код]

Элементами, сопряженными с в являются: сам и , а их сумма — след .

Кроме того:

Рассмотрим генератор XTR-группы порядка , где  — простое число. Так как  — подгруппа группы порядка , то . Кроме того,

и

.

Таким образом,

Отметим также, что сопряженным к элементу является , то есть, имеет норму равную 1. Ключевой особенностью XTR является то, что минимальный многочлен в

упрощается до

Иными словами, сопряженные с элементы, как корни минимального многочлена в , полностью определяются следом . Аналогичные рассуждения верны для любой степени :

— этот многочлен определяется следом .

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

Алгоритм быстрого вычисления по [2][править | править код]

Определение: Для каждого определим:

Определение: Пусть  — корни в , а . Обозначим:

Свойства и :

  1. для
  2. для
  3. Либо все имеют порядок, являющийся делителем и , либо все  — в поле . В частности,  — неприводим тогда и только тогда, когда его корни имеют порядок, являющийся делителем и .
  4. приводим в поле тогда и только тогда, когда

Утверждение: Пусть даны .

  1. Вычисление требует двух операций произведения в поле .
  2. Вычисление требует четырёх операций произведения в поле .
  3. Вычисление требует четырёх операций произведения в поле .
  4. Вычисление требует четырёх операций произведения в поле .

Определение: Пусть .

Алгоритм для вычисления при заданных и [править | править код]

  • При алгоритм применяется для и , затем используется свойство 2 для получения конечного результатаю
  • При , .
  • При , .
  • При , воспользуемся выражениями для и , чтобы найти и, соответственно, .
  • При , чтобы вычислить , введем
и если не нечетно и если четно. Положим и найдем , используя Утверждение, и . Пусть, в дальнейшем,
где и . Для последовательно выполним следующее:
  • При , воспользуемся чтобы найти .
  • При , воспользуемся чтобы найти .
  • Заменим на .

По завершении итераций, , а . Если n — четно, воспользуемся чтобы найти .

Выбор параметров[править | править код]

Выбор поля и размера подгруппы[править | править код]

Чтобы воспользоваться преимуществами представления элементов групп в виде их следов и обеспечить достаточную защищенность данных, необходимо найти простые и , где  — характеристика поля , причем , а  — размер подгруппы и делитель . Обозначим как и размеры и в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать таким, что , то есть а может быть около 160. Первый алгоритм, который позволяет вычислить такие простые и  — Алгоритм А.

Алгоритм А

  1. Найдём такое, что число  — простое число длиной в бит.
  2. Найдем такое, что число  — простое длиной бит, а также .
Корректность Алгоритма А:
Необходимо проверить лишь то, что , так как все оставшиеся свойства очевидно выполнены из-за специфики выбора и .
Нетрудно заметить, что , значит .

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

От этого недостатка избавлен более медленный Алгоритм Б.

Алгоритм Б

  1. Выберем простое число длиной в бит, такое, что .
  2. Найдем корни и .
  3. Найдем такое, что , - простое -битовое число и при этом для
Корректность Алгоритма Б:
Как только мы выбираем , автоматически выполняется условие (Так как и ). Из этого утверждения и квадратичного закона взаимности следует, что корни и существуют.
Чтобы проверить, что снова рассмотрим для и заметим, что .Значит и -корни и, следовательно, .

Выбор подгруппы[править | править код]

В предыдущем разделе мы нашли размеры и конечного поля и мультипликативной подгруппы в . Теперь следует найти подгруппу в для некоторых таких, что . Однако, необязательно искать явный элемент , достаточно найти элемент такой, что для элемента порядка . Но при данном , генератор XTR-группы может быть найден путём нахождения корня . Чтобы найти это , рассмотрим свойство 5 . Найдя такое следует проверить, действительно ли оно порядка , однако сначала нужно выбрать c\in GF(p²), такое, что F(c,\ X) — неприводимо. Простейший подход в том, чтобы выбирать случайным образом.

Утверждение: Для случайно выбранного вероятность, что  — неприводимо, больше 1/3.

Базовый алгоритм для поиска :

  1. Выберем случайное .
  2. Если  — приводим, вернемся на первый шаг.
  3. Воспользуемся алгоритмом для поиска . Найдем .
  4. Если имеет порядок не равный , вернемся на первый шаг.
  5. Пусть .

Данный алгоритм вычисляет элемент поля эквивалентный для некоторых порядка .[1]

Примеры[править | править код]

Протокол Диффи-Хеллмана[править | править код]

Предположим, у Алисы и Боба есть открытый XTR-ключ и они хотят сгенерировать общий закрытый ключ .

  1. Алиса выбирает случайное число такое, что , вычисляет и посылает Бобу.
  2. Боб получает от Алисы, выбирает случайное такое, что , вычисляет и посылает Алисе.
  3. Алиса получает от Боба, вычисляет и получает  — закрытый ключ .
  4. Точно так же, Боб вычисляет и получает  — закрытый ключ .

Схема Эль-Гамаля[править | править код]

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

  1. Боб выбирает случайное такое, что и вычисляет .
  2. Затем Боб вычисляет.
  3. Боб определяет симметричный ключ основанный на .
  4. Боб шифрует сообщение ключом , получая зашифрованное сообщение .
  5. Пару Боб посылает Алисе.

Получив пару , Алиса расшифровывает её следующим образом:

  1. Алиса вычисляет .
  2. Алиса определяет симметричный ключ основанный на .
  3. Зная, что алгоритм шифрования сообщения — симметричный, Алиса ключом расшифровывает , получая исходное сообщение .

Таким образом, сообщение передано.

Примечания[править | править код]

  1. 1 2 Lenstra, Arjen K.; Verheul, Eric R. An overview of the XTR public key system (неопр.). Архивировано 15 апреля 2006 года.
  2. Lenstra, Arjen K.; Verheul, Eric R. The XTR public key system (неопр.).