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

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

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

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

С учетом p ≡ 2 mod 3:

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

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

Использование следов в GF(p2) Элементами, сопряженными с в являются: сам и , а их сумма — след .

Кроме того:

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

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

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

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

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

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

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

Алгоритм быстрого вычисления Tr(gn) по Tr(g) Определение: Для каждого определим:

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

Свойства и :

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

Утверждение: Пусть даны . Вычисление требует двух операций произведения в поле . Вычисление требует четырёх операций произведения в поле . Вычисление требует четырёх операций произведения в поле . Вычисление требует четырёх операций произведения в поле .

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

Алгоритм для вычисления Sn(c) при заданных n и c При алгоритм применяется для и , затем используется свойство 2 для получения конечного результатаю При , . При , . При , воспользуемся выражениями для и , чтобы найти и, соответственно, . При , чтобы вычислить , введем

и если не нечетно и если четно. Положим и найдем , используя Утверждение, и . Пусть, в дальнейшем,

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

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

Алгоритм А Найдём такое, что число  — простое число длиной в бит. Найдем такое, что число  — простое длиной бит, а также .

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

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

Алгоритм Б Выберем простое число длиной в бит, такое, что . Найдем корни и . Найдем такое, что , - простое -битовое число и при этом для

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

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

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

Базовый алгоритм для поиска : Выберем случайное . Если  — приводим, вернемся на первый шаг. Воспользуемся алгоритмом для поиска . Найдем . Если имеет порядок не равный , вернемся на первый шаг. Пусть . Данный алгоритм вычисляет элемент поля эквивалентный для некоторых порядка .

Примеры

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

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

Примечания

Категория:Криптография с открытым ключом Категория:Шифры