Китайская теорема об остатках и ее применение в криптографии

Федеральное агентство по образованию

Ставропольский государственный университет

Кафедра высшей алгебры и геометрии

РЕФЕРАТ НА ТЕМУ:

«Китайская теорема об остатках и ее применение в криптографии»

Выполнила: студентка ФМФ

Спец. математика, гр. А

Баймурзаева Г.С.

Проверила: Бондарь

Ставрополь, 2010

Содержание

1. Введение………………………………………...………………………              3

2. Китайская теорема об остатках……………….……………………….              4

              2. 1. Умножение  в классах вычетов…………………………..…..              4

              2. 2 Метод Гельфонда………………………………….…………...8

              2. 3 Метод базы разложения………….…………………………..              10

3.Заключение…………...………………………………………………...              14

4. Список литературы……………………………………………………              16

Введение

              Китайская теорема об остатках в ее арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин»(кит. 孙子算经, пиньинь sūnzǐ suànjīng), предположительно датируемом третьим веком н.э.

              Китайская теорема об остатках часто используется в криптографии и вычислительной технике. Примеры ее использования:

      Быстрое умножение больших чисел;

      Нахождение индекса элемента конечной циклической группы алгоритмом  Гельфонда за счет преставлении ее в виде прямого произведения групп в соответствии с основной теоремой  об абелевых группах;

      Вычисление дискретного логарифма в группе методом базы разложения.

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

2. Китайской теоремы об остатках.

              Пусть - коммутативное кольцо и - идеалы кольца такие, что для всех . Тогда для набора элементов , где , существует элемент такой, что для всех .

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

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

2.1.  Умножение в классах вычетов

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

,

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

1.      Перейти к представлению сомножителей в классах вычетов по модулям .

2.      Вычислить произведения сомножителей по модулям.

3.      восстановить произведение по китайской теореме об остатках.

Пусть максимальный размер входа алгоритма равен . Тогда произведение будет иметь длину не более . Найдем взаимно простых (но необязательно простых)  чисел таких, что их произведение

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

.

Таблица чисел фиксирована, поэтому можно заранее вычислить вспомогательные величины

На практике удобно выбирать число так, чтобы оно было степенью двойки. Нахождение вычетов по модулям можно ускорить следующим образом: сначала вычислить произведения после этого – произведения затем и т.д. и, наконец, найти с помощью «деления пополам» вычеты по соответствующим модулям. Пусть известен вычет по модулю . Тогда представление     по модулям и будет иметь вид:

.

Находим вычеты по модулям :

Для перехода от представления в классах вычетов к обычному надо воспользоваться китайской теоремой об остатках:

              ,              (1)

где .

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

,

Где

Данное разбиение дает возможность применить тот же метод, что и при нахождении остатков по модулю .

Найдем произведение подряд идущих двух, четырех, восьми и т.д. модулей: . Обозначим через произведение подряд идущих модулей, начиная с . Найдем целые числа

.

Для ускорения вычисления можно воспользоваться рекуррентной формулой:

.

Тогда .

Пример. Умножение в классах вычетов.

Найдем произведение чисел . Пусть . Вычисляем :

Находим векторы . Тогда . Отсюда

Поэтому . Вычисление   можно проводить по модулю .

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

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

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

2.2. Метод Гельфонда.

Метод А. О. Гельфонда[1] базируется на основной теореме об абелевых группах, утверждающей, что конечная абелева группа раскладывается в прямое произведение циклических групп, порядки которых являются степенями простых чисел.

Алгоритм. Логарифмирование на эллиптической кривой методом Гельфонда.

Вход. Кривая над конечным полем ; образующая точка и точка ; разложение порядка группы: .

Выход. Логарифм такой, что .

Метод.

1.      Для выполнить следующие действия.

1.1. Положить .

1.2. Положить .

1.3. Вычислить .

1.4. Для выполнить следующие действия.

1.4.1.    Положить .

1.4.2.    Вычислить логарифм любым алгоритмом (например, алгоритмом Полларда).

1.5. Положить .

2.      Восстановить логарифм из по китайской теореме об остатках.

3.      Результат: .

Для обеспечения стойкости к методу Гельфонда  число точек на кривой должно быть простым или иметь большой простой делитель .

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

Пример. Логарифмирование на эллиптической кривой методом Гельфонда.

Пусть . Нужно найти логарифм такой, что .

Для . Тогда и .

Для . На шаге 1.4 и для , и для . Тогда .

Для . Тогда и .

Восстанавливаем логарифм по китайской теореме об остатках: .

2.3. Метод базы разложения.

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

Различные варианты метода базы разложения были предложены Адельманом, Мерклем и Поллардом.

Кольцо является кольцом целых элементов поля , при этом группа и, следовательно, полугруппа имеют бесконечное множество образующих, совпадающее с множеством простых чисел. Перенумеруем простые числа 2, 3, 5, 7, …, начиная с 1. Вероятность того, что случайное число делится на е простое число , равна . Обозначим множество, состоящее из числа и первых простых чисел , через .

Алгоритм 3. Логарифмирование в подгруппе группы методом базы разложения.

Вход. Характеристика поля , образующая подгруппы  простого порядка , экспонента .

Выход. Показатель , для которого .

Метод.

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

2.      Случайным выбором показателей найти множество из гладких чисел и разложить их на множители путем вычисления наибольшего общего делителя с произведениями элементов базы разложения (при этом гладким может быть не , , в этом случае в разложении участвует элемент – 1 базы разложения):

              (здесь в каждом уравнении почти все показатели будут нулевыми).

3.      Подбором найти показатель такой, что число является гладким, и найти разложение этого числа:

.

4.      Используя показатели , , записать систему линейных сравнений:

.

5.      Методом гауссова исключения выразить как линейную комбинацию от . Найти логарифм по формуле .

6.      Результат: .

Данный алгоритм является вероятностным и требует объема памяти , где . Выбор на шагах 2 и 3 тех значений и ,для которых экспонента является гладкой, можно рассматривать как «просеивание» экспонент через «решето». Поэтому данный метод относится к методам решета.

Решение большой системы линейных уравнений над полем можно ускорить, если воспользоваться технологиями разреженных матриц. Кроме того, на шаге 2 можно искать числа вида для целых до получения системы линейно независимых сравнений, тогда шаг 3 не нужен.

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

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

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

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

Заключение

Китайская теорема об остатках (КТО) также часто используется, чтобы оптимизировать операции в RSA. При ее использовании сначала вычисляются y mod p и y mod q, где y - сообщение. Эти первоначальные шаги могут быть уязвимыми для временных атак. Простейшая из них состоит в том, что нужно выбрать значения y, которые являются близкими к p или q, и, используя измерения времени, выяснить, является ли предполагаемое значение меньше, чем фактическое значение p (или q). Если y - меньше, чем p, то вычисление y mod p не нужно, в то время как если y больше, чем p, то для вычисления y mod p необходимо вычитание p по крайней мере один раз. Также, если сообщение чуть-чуть больше, чем p, y mod p будет иметь первые нулевые биты, что может сократить время, требуемое для первого шага умножения. Особенности временных характеристик зависят от реализации. Модульная функция сокращения RSAREF с 512-битным модулем на компьютере Pentium с y, выбранным случайно между 0 и 2p, занимает в среднем 42.1 мкс, если y < p, и 73.9 мкс, если y > p. Время измерения для многих y может использоваться для последовательной аппроксимации p.

              В некоторых случаях возможно улучшить атаку на RSA с КТО, если использовать известный (не выбранный) шифрованный текст, сокращая число требуемых сообщений и делая возможными атаки на цифровые подписи RSA. Сокращение модульных операций выполняется вычитанием нескольких модулей сразу, и вариации времени, которые можно использовать, возникают за счет разного количества шагов "сравнения-вычитания". Например, цикл деления RSAREF выполняет целочисленное деление старших двух цифр y на старшую цифру p, умножает p на частное, сдвигает влево на соответствующее число цифр, а затем вычитает результат из y. Если результат больше, чем p (сдвинутый влево), то выполняется дополнительное вычитание. Решение, делать ли дополнительное вычитание в первом цикле алгоритма деления, обычно зависит только от y (который известен) и старших двух цифр p. Временной анализ может быть использован для определения старших цифр p. Например, полный перебор по всем возможным значениям для старших двух цифр p (или более эффективные методы) может установить значение, для которого наблюдаемое время коррелирует наиболее близко с ожидаемым количеством действий вычитания. Как и в случае атаки для метода Диффи-Хеллмана, как только одна цифра p будет найдена, измерения времени могут многократно использоваться, чтобы найти последующие цифры.

              Еще не известно, может ли быть приспособлен временной анализ, чтобы непосредственно нападать на возведение в степень по модулю p и q, выполняемых с помощью КТО.

4. Список литературы

1. Ростовцев А. Г., Маховенко Е. Б. Теоретическая криптография. Санкт-Петербург: Изд-во АНО НПО «Профессионал», 2004 г.

2. http://ru.wikipedia.org/wiki/

16