Алгоритмы, используемые при реализации асимметричных криптосхем

From CryptoWiki
Jump to: navigation, search

Contents

Постановка задачи

Эффективная генерация параметров открытых ключей является необходимым условием для криптосистем с открытым ключом. Например, для использования протокола Диффи-Хеллмана (Diffie-Hellman) и его вариаций необходимо выработать простое число p для задания конечного поля Gus1.gif. Другим примером является выработка простых чисел p и q для получения модуля n=pq в RSA. В этом случае простые числа должны быть больших размеров и случайными в том смысле, что вероятность выбора любого конкретного простого числа должна быть достаточно малой для того, чтобы не дать злоумышленнику возможность использовать эту вероятность для оптимизации стратегии поиска [KL07]. Иногда к простым числам могут предъявляться дополнительные требования для того, чтобы они были устойчивы к каким-либо специализированным атакам. Третий пример – выработка неприводимого многочлена f(x) степени m над конечным полем Gus1.gif для построения конечного поля Gus2.gif. В этом случае также необходима выработка элемента высокого порядка в Gus3.gif.

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


Вернуться к оглавлению

Подходы к генерации больших простых чисел

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

1. Генерация случайного числа n необходимого размера, называемого кандидат.

2. Проверка числа n на простоту.

3. Если n – составное, вернуться на первый шаг.

Небольшой модификацией является выбор кандидатов из некоторой последовательности, начинающейся с n. Такой последовательностью является, например, n, n+2, n+4, n+6, … Использование специальных последовательностей позволяет увеличить вероятность того, что кандидат будет простым числом, а также находить простые числа, удовлетворяющие специальным требованиям.

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

Последним различием между различными техниками генерации больших простых чисел является использование «случайности». Обычно кандидаты генерируются как функции от случайных входных данных. Техника для определения простоты числа может использовать или не использовать случайные числа. В некоторых случаях необходимо, чтобы простое число имело дополнительные свойства. К примеру, чтобы сделать извлечение дискретного логарифма Gus5.gif стойким к алгоритму Полига-Хеллмана требуется, чтобы p-1 имело большой простой делитель. Поэтому техники для генерации параметров открытых ключей, таких как простые числа специальной формы, должны это учитывать [GB08].

Вероятностные тесты на простоту

Вероятностные тесты на простоту имеют под собой следующую базу. Для каждого положительного целого числа n определяется множество Gus6.gif, такое, что выполняются следующие свойства.

1) Для любого a из Gus7.gif можно проверить за полиномиальное время принадлежность a W(n).

2) Если n простое, то W(n) – пустое множество.

3) Если n составное, тогда мощность множества Gus8.gif.

Вероятностный тест на простоту использует свойства множества W(n) следующим образом. Предположим, что n – целое число, простоту которого необходимо проверить. Целое число a из Gus7.gif выбирается случайно и проверяется, входит ли a в W(n). Если это так, тогда говорят, что n не прошел тест на простоту для основания a; в этом случае утверждается, что n – составное. Если же a не принадлежит W(n), тогда говорят, что n прошло тест на простоту для основания a; в этом случае нельзя сделать никакого вывода о простоте числа n, оно может быть как простым, так и составным.

Каждый раз, когда тест выдает результатом то, что n – составное, в этом нет сомнений. С другой стороны, успешные независимые прогоны теста, в результате которых утверждается, что n – вероятно простое позволяют увеличить уверенность в том, что искомое число действительно простое до необходимого уровня – результирующая вероятность ошибки уменьшается с каждым независимым прогоном. Если тест прогоняется t раз независимо над одним и тем же числом n, вероятность того, что во все прогоны результатом будет то, что n – вероятно простое (то есть вероятность ошибки) составляет, по крайней мере, Gus9.gif.

Далее будут рассмотрены два вероятностных теста на простоту: Соловея-Штрассена (Solovay-Strassen) и Миллера-Рабина (Miller-Rabin). По историческим причинам также представлен тест Ферма (Fermat), однако его нельзя назвать вероятностным тестом на простоту, поскольку он не различает простые числа и особые составные числа, именуемые числами Кармайкла (Carmichael numbers).


Тест Ферма (Fermat test)

Теорема Ферма утверждает, что если n – простое число и a – любое целое число, Gus10.gif, тогда Gus11.gif. Потому если n – целое число, чья простота под вопросом, нахождение такого a в этом интервале, что это равенство не выполняется, докажет, что n – составное.

И наоборот, если найти целое число a, такое что Gus11.gif, утверждается, что n – простое, в том смысле, что оно удовлетворяет теореме Ферма для основания a. Отсюда вытекает следующее определение. Составное n такое, что Gus11.gif называется псевдопростым по основанию a. Примером такого числа является число 341 (11 х 31) – оно псевдопростое по основанию 2, поскольку Gus12.gif.

Тест Ферма

Вход: целое число Gus13.gif и параметр безопасности Gus14.gif.

Выход: Ответ на вопрос является n простым или составным (n – составное или n –простое).

1. В цикле i от 1 до t выполнить:
    1.1 Выбрать случайное a: Gus15.gif.
    1.2 Вычислить Gus16.gif.
    1.3 Если Gus17.gif, тогда вернуть («n – составное»).
2. Вернуть («n – простое»).


Если алгоритм утверждает, что n – составное, то оно однозначно составное. С другой стороны, если алгоритм утверждает, что n – простое, нет никаких гарантий того, что n – действительно простое. Однако, поскольку для заданного основания a псевдопростых чисел не так много, тест Ферма выдает правильный результат на большинстве входных значений, но не на всех [G04].

Если nчисло Кармайкла, тогда только свидетели Ферма для n представляют собой такие a: Gus10.gif, для которых НОД(a,n) > 1. Таким образом, с большой вероятностью тест Ферма выдаст результат, что n – простое, даже если число итераций t велико. Этот недостаток теста Ферма был устранен в тестах Соловея-Штрассена (Solovay-Strassen) и Миллера-Рабина (Miller-Rabin), которые полагаются на критерии более сильные, чем теорема Ферма.

Тест Соловея — Штрассена (Solovay-Strassen test)

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем (Robert Martin Solovay) совместно с Фолькером Штрассеном (Volker Strassen). Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.

В 17 веке Ферма (Fermat) доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту: Если n - простое, и a не делится на n, то Gus11.gif . Эта проверка для заданного n не требует больших вычислений, однако утверждение обратное этому, неверно. Кроме того, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел, взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много. В связи с обнаруженным недостатком теста Ферма актуальность приобрела задача увеличения достоверности вероятностных тестов. Первый тест, отсеивающий числа Кармайкла как составные, предложил Леманн (Lehmann). Этот недостаток отсутствует также в тестах Соловея-Штрассена и Миллера-Рабина за счет более сильного критерия отсева, чем малая теорема Ферма. Р. Соловей (R. Solovay) совместно с Ф. Штрассеном (V. Strassen) в 1977 году доказали, что аналога чисел Кармайкла, которые являются составными и одновременно эйлеровыми псевдопростыми, нет. На основе этого и был предложен тест Соловея-Штрассена на простоту, он был опубликован в 1977 году.

Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Якоби (Jacobi symbol):

Если n — нечетное составное число, то количество целых чисел a, взаимно простых с n и меньших n, удовлетворяющих сравнению Gus18.gif , не превосходит Gus19.gif .

Составные числа n, удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби (Euler–Jacobi pseudoprime) по основанию a.

Алгоритм Соловея — Штрассена параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число a < n. Если НОД(a,n) > 1, то выносится решение, что n составное. Иначе проверяется справедливость сравнения Gus18.gif . Если оно не выполняется, то выносится решение, что n - составное. Если это сравнение выполняется, то a является свидетелем простоты числа n. Далее выбирается другое случайное a, и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью Gus20.gif .

Тест Соловея-Штрассена

Вход: n > 2, тестируемое нечётное натуральное число;

k - параметр, определяющий точность теста.

Выход: составное, означает, что n точно составное;

вероятно простое , означает, что n вероятно является простым.

1.В цикле i от 1 до k выполнить:
    1.1. Выбрать a  - случайное целое от 2 до n-1 , включительно;
    1.2. Если НОД(a, n) > 1, тогда вернуть (составное);
    1.3.Если Gus21.gif , тогда вернуть (составное).
2.Вернуть (простое с вероятностью Gus20.gif ).

Тест Миллера-Рабина (Miller-Rabin test)

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

Алгоритм был разработан Гари Миллером (Gary Miller) в 1976 году и модифицирован Майклом Рабином (Michael Rabin) в 1980 году.

Пусть n — нечётное число большее 1. Число n-1 однозначно представляется в виде Gus23.gif , где t нечётно. Целое число a, 1 < a < n, называется свидетелем простоты числа n , если выполняется одно из условий:

Gus24.gif

или

• существует целое число k , Gus25.gif , такое, что Gus26.gif.

Теорема Рабина утверждает, что составное нечётное число n имеет не более Gus27.gif различных свидетелей простоты, где Gus28.gifфункция Эйлера (Euler's phi function).

Тест Миллера-Рабина

Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины Gus22.gif, где n — проверяемое число.

Для данного n находятся такие целое число s и целое нечётное число t, что Gus23.gif . Выбирается случайное число a, 1 < a < n. Если a не является свидетелем простоты числа n, то выдается ответ «m — составное», и алгоритм завершается. Иначе, выбирается новое случайное число a, и процедура проверки повторяется. После нахождения r свидетелей простоты выдается ответ «n — вероятно простое», и алгоритм завершается.

Вход: n > 2, нечётное натуральное число, которое необходимо проверить на простоту;

r — количество раундов.

Выход: составное, означает, что n является составным числом;

вероятно простое, означает, что n с высокой вероятностью является простым числом.

1. Представить n − 1 в виде Gus23.gif, где t нечётно, можно сделать последовательным делением n - 1 на 2.
2. В цикле по i от 1 до r выполнить:
    2.1. Выбрать случайное целое число a в отрезке [2, m − 2].
    2.2. Gus29.gif, вычисляется с помощью алгоритма возведения в степень по модулю.
    2.3. Если x = 1 или x = m − 1, то перейти на следующую итерацию цикла 2.
    2.4. В цикле по j от 1 до s − 1 выполнить:
         2.4.1. Gus30.gif.
         2.4.2. Если x = 1, то вернуть (составное).
         2.4.3. Если x = m − 1, то перейти на следующую итерацию цикла 2.
    2.5. Вернуть (составное).
3. Вернуть (вероятно простое).

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа n, то вероятность того, что n составное, не превосходит Gus31.gif.

Детерминированные тесты на простоту

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

Проверка чисел Мерсенна (Mersenne primes)

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

Числа Мерсенна — числа вида Gus32.gif, где s — натуральное число. Названы в честь французского математика Марена Мерсенна (Marin Mersenne).

Пусть Gus33.gif. Число Мерсенна Gus32.gif является простым тогда и только тогда, когда выполнено два условия:

1. s – простое;

2.Последовательность чисел, определенная следующим образом: Gus34.gif, удовлетворяет условию Gus35.gif.

Этот факт приводит нас к детерминированному алгоритму проверки простоты числа Мерсенна за полиномиальное время.

Тест Люка-Лемера (Lucas–Lehmer primality test)

Вход: Число Мерсенна Gus32.gif, Gus33.gif.

Выход: простое или составное.

1. Проверить наличие делителей у s в промежутке от 2 до Gus36.gif;
2. Если найден хоть один, то вернуть (составное);
3. Установить u = 4;
4. В цикле по k от 1 до s-2 выполнить Gus37.gif;
5.Если u = 0 вернуть (простое), в противном случае вернуть (составное).

На сентябрь 2013 года самым большим известным простым числом является число Мерсенна Gus38.gif, найденное 25 января 2013 года Кертисом Купером (Curtis Cooper) в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа n содержит 17 425 170 цифр.

Всего известно 48 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 42-х. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

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

Генерация простых чисел

В этом подразделе будут рассмотрены алгоритмы генерации простых чисел для криптографических целей.

Случайный поиск вероятно простых чисел

Как уже отмечалось выше, простейшим способом является случайный выбор числа необходимого размера и проверка его вероятностным тестом на простоту, например, тестом Миллера-Рабина. Однако, если кандидат n делится на малое простое число, проверка делимости на небольшие простые числа позволит отбросить не прошедшего кандидата n быстрее, чем по алгоритму Миллера-Рабина. Поскольку вероятность того, что случайное целое число имеет небольшой простой делитель, достаточно высока, до применения теста Миллера-Рабина стоит проверить n на простые делители до некоторой границы B. Это можно сделать последовательным делением n на все простые числа, меньше B или вычислением НОД n и произведения нескольких простых чисел, меньших B [MOV01].

Случайный поиск простого числа с использованием теста Миллера-Рабина.

Вход: целое число k, параметр безопасности t.

Выход: случайное вероятно простое целое число длиной k бит.

1. Сгенерировать случайное число n длиной k бит;
2. Использовать деление n на простые числа, меньше B для проверки существования простого делителя;
3. Если хотя бы один найден – вернуться на шаг 1;
4. Проверить простоту n тестом Миллера-Рабина;
5. Если n – вероятно простое, то вернуть (n), в противном случае вернуться на шаг 1.

Генерация сильно простых чисел

Криптосистема RSA использует модуль вида n=pq, где p и q – различные простые числа. Простые числа p и q должны быть существенного размера, чтобы факторизация их произведения была вычислительно сложной. На практике, простые числа должны быть предопределенной длины для того, чтобы соответствовать спецификациям систем [M03]. Создание криптосистемы RSA привело к появлению некоторых дополнительных ограничений на выбор p и q, которые необходимы для уверенности, что итоговая система RSA защищена от атак криптоаналитика, и было введено понятие сильно простых чисел. Тем не менее, доказано, что сильно простые числа обеспечивают защиту не многим больше, чем просто случайно выбранные простые числа.

Простое число p называется сильно простым, если существуют целые числа r,s,t, удовлетвоярющие следующим условиям:

1. p+1 имеет большой простой делитель s;

2. p-1 имеет большой простой делитель r;

3. r-1 имеет большой простой делитель t.

В этом определении величина делителей зависит от вида атаки, от которой необходимо защититься.

Алгоритм Гордона (Gordon’s algorithm) для генерации сильно простого числа

Выход: Сильно простое число p.

1. Сгенерировать два больших простых числа s и t одной длины;
2. Выбрать число Gus39.gif. Найти первое простое число в последовательности 2it+1, где i= Gus39.gif, i=i+1. Обозначить это число r=2it+1;
3. Вычислить Gus40.gif;
4. Выбрать целое число Gus42.gif. Найти первое простое число в последовательности Gus41.gif, где j = Gus42.gif, j=j+1. Обозначить это число p=Gus41.gif;
5. Вернуть (p).

Доказательство:

Для того, чтобы убедиться, что простое число p, сгенерированное по алгоритму Гордона, действительно является сильно простым, заметим во-первых, что Gus43.gif; это следует из теоремы Ферма. Следовательно, Gus44.gif. Наконец,

Gus45.gif, и отсюда p – 1 имеет простой делитель r;

Gus46.gif, и отсюда p + 1 имеет простой делитель s;

Gus47.gif, и отсюда r - 1 имеет простой делитель t.

Если на этапах 1, 2 и 4 используется тест Миллера-Рабина, время выполнения алгоритма Гордона в среднем всего на 19% больше по сравнению с алгоритмом случайного поиска простого числа.

Метод NIST для генерации простых чисел для DSA

Некоторые схемы с открытым ключом требуют, чтобы простые числа удовлетворяли специфичным условиям. К примеру, DSA требует два простых числа p, q, удовлетворяющих следующим трем условиям:

1. q – 160-битное простое число;

2. pL-битное простое число, где L=512+64l для некоторого l от 0 до 8;

3. q должно делить p-1.

В этом подразделе представлен алгоритм для генерации таких простых p и q. Под H понимается хэш-функция SHA-1, переводящая строки длины < Gus48.gif в 160-битные хэш-коды. Где это необходимо, целое число x: Gus49.gif, чье двоичное представление: Gus50.gif представляется в виде g-битной последовательности Gus51.gif и наоборот.

Метод NIST для генерации простых чисел для DSA.

Вход: целое число l в интервале от 0 до 8.

Выход: 160-битное простое число q, L-битное простое число p, где L=512+64l и q|(p-1)

1. Вычислить L = 512+64l. Найти n, b: L-1 = 160n+b, где b в интервале от 0 до 159;
2. В цикле выполнить следующее:
    2.1. Выбрать случайное число s (не обязательно хранить его в секрете) длины g больше или равной 160;
    2.2. Вычислить Gus52.gif;
    2.3. Сформировать q, установив самый старший и самый младший биты U в 1;
    2.4. Проверить q на простоту тестом Миллера-Рабина с параметром t  > 17;
    2.5. Если q – составное, то вернуться на шаг 2;
3. Установить i=0, j=2;
4. В цикле пока i < 4096 выполнить:
    4.1. В цикле для k от 0 до n выполнить: Установить Gus53.gif;
    4.2. Для целого числа Gus55.gif, определить Gus54.gif;
    4.3. Вычислить Gus56.gif и установить p = X – (c-1);
    4.4. Если Gus57.gif тогда выполнить:
         4.4.1. Проверить p на простоту тестом Миллер-Рабина для параметра t > 4;
         4.4.2. Если p – вероятно простое, вернуть (q,p);
    4.5. Установить i=i+1, j=j+n+1;
5. Вернуться на шаг 2.

Конструктивные техники для простых чисел

Алгоритм Морера (Maurer’s algorithm) генерирует случайные однозначно простые числа, которые почти равномерно распределены над множеством всех простых чисел необходимого размера. Ожидаемое время генерации немногим больше, чем генерация вероятно простого числа алгоритмом случайного поиска простого числа с параметром t=1 [S05].

Пусть n > 2 – целое число и предположим, что n=1+2Rq, где q – простое и q > R.

1. Если существует целое число a: Gus11.gif и Gus58.gif, то n – простое.

2. Если n – простое, вероятность, что случайно выбранное число a удовлетворяет условиям Gus11.gif и Gus58.gif, равна Gus59.gif.

Алгоритм Морера рекурсивно генерирует простое число q и затем выбирает целые числа R < q, пока не будет доказано по первому пункту вышеописанной теоремы, что n=1+2Rq – простое по некоторому основанию a.

Алгоритм Морера

Вход: положительное целое число k.

Выход: простое число n длины k бит.

1. Если k < 21 тогда в цикле выполнить:
    1.1. Выбрать случайное целое число n длины k бит;
    1.2. Последовательно поделить n на все простые числа от 2 до Gus4.gif;
    1.3. Если нашелся хоть один делитель, вернуться на шаг 1, в противном случае вернуть (n);
2. Установить c = 0.1, m = 20;
3. Установить Gus60.gif;
4. Если k > 2m тогда в цикле выполнить: выбрать случайное число s в интервале [0,1], установить Gus61.gif до тех пор пока (k - rk) > m. В противном случае установить r = 0.5;
5. Вычислить q, как результат алгоритма Морера с параметром (Gus62.gif);
6. Установить Gus63.gif;
7. Установить success=0;
8. Пока success=0 выполнить в цикле:
    8.1. Выбрать случайное целое число R в интервале [I+1, 2I] и установить n = 2Rq + 1;
    8.2. Использовать деление n на простые числа < B для нахождения простых делителей:
    8.3. Если простые делители не найдены выполнить:
         8.3.1. Выбрать случайное целое a в интервале [2, n-2];
         8.3.2. Вычислить Gus64.gif;
         8.3.3. Если b = 1 выполнить:
              8.3.1.1. Вычислить Gus65.gif;
              8.3.1.2.	Если d=1 установить success = 1;
9.Вернуть (n).

Неприводимые многочлены

Многочлен Gus66.gif степени m > 0 называется неприводимым над Gus67.gif, если его нельзя записать, как произведение двух многочленов в Gus68.gif со степенями меньшими m. Такой многочлен f(x) можно использовать для представления элементов конечного поля Gus69.gif, поскольку Gus70.gif – множество всех многочленов в Gus68.gif степени меньшей m, где сложение и умножение многочленов происходит по модулю f(x). В этом подразделе представлены техники для построения неприводимых многочленов над Gus67.gif, где p – простое. Конечные поля Gus71.gif представляют особый интерес для криптографических приложений, поскольку вычисления в этих полях могут эффективно производится, как в программном, так и аппаратном обеспечении. По этой причине, особое внимание уделяется особому случаю неприводимых многочленов над Gus72.gif.

Если Gus66.gifнеприводимый многочлен над Gus67.gif и a – ненулевой элемент в Gus67.gif, то af(x) тоже неприводим над Gus67.gif [Ф10]. Следовательно имеет смысл рассматривать только нормированные многочлены, то есть многочлены, старший коэффициент которых равен единице. Важно заметить, что если многочлен неприводим, то его свободный член не может быть нулевым. В частности, если Gus73.gif, то свободный член должен быть равен единице.

Пусть p – простое, а k – положительное целое число.

1. Произведение всех нормированных неприводимых многочленов в Gus68.gif степени делителей k равно Gus74.gif.

2. Пусть f(x) - полином степени m в Gus68.gif. Тогда f(x) неприводим над Gus67.gif тогда и только тогда, когда Gus75.gif.

Проверка многочлена на неприводимость

Вход: Простое число p и нормированный многочлен f(x) степени m в Gus68.gif.

Выход: Ответ на вопрос, приводим ли многочлен f(x) над Gus67.gif.

1. Установить u(x)=x;
2. В цикле по i от 1 до Gus76.gif выполнить:
    2.1. Вычислить Gus77.gif;
    2.2. Вычислить d(x) = НОД (f(x), u(x)-x);
    2.3. Если Gus78.gif вернуть (приводимый);
3. Вернуть (неприводимый).

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

Генерация случайного нормированного неприводимого многочлена над Gus67.gif

Вход: простое число p и положительное целое число m.

Выход: нормированный неприводимый многочлен f(x) степени m в Gus68.gif.

1. В цикле выполнить (пока f(x) – приводим):
    1.1. Случайно выбрать целые числа Gus79.gif в интервале от 0 до p-1, при условии, что Gus80.gif. Пусть многочлен Gus81.gif;
    1.2. Использовать алгоритм проверки многочлена на неприводимость для проверки f(x) на неприводимость над Gus67.gif;
2. Вернуть (f(x)).

Этот алгоритм выполняется за Gus82.gif операций в Gus67.gif.

Примитивные многочлены

Примитивные многочлены используются в создании ЛРП максимального периода.

Пусть Gus66.gifнеприводимый многочлен степени m. Если известно разложение числа Gus83.gif на множители, тогда существует алгоритм проверки многочлена на примитивность. В противном случае, эффективных алгоритмов неизвестно.

Пусть p – простое число и Gus84.gif – различные простые сомножители Gus83.gif. Тогда неприводимый многочлен примитивен тогда и только тогда, когда для всех i от 1 до t Gus85.gif.

Проверка неприводимого многочлена на примитивность

Вход: Простое число p, положительное целое число m, Gus84.gif – различные простые сомножители Gus83.gif и нормированный неприводимый многочлен f(x) степени m в Gus68.gif.

Выход: Ответ на вопрос, является ли f(x) примитивным.

1. В цикле для i от 1 до t выполнить:
    1.1. Вычислить Gus86.gif;
    1.2. Если l(x) = 1 вернуть (не примитивный);
2. Вернуть (примитивный).

Существует точно Gus87.gif нормированных примитивных многочленов степени m в Gus68.gif, где Gus88.gifфункция Эйлера. Поскольку число нормированных неприводимых многочленов степени m в Gus68.gif примерно Gus89.gif, следовательно вероятность того, что случайный нормированный неприводимый многочлен степени m в Gus68.gif окажется примитивным примерно Gus90.gif.

Генераторы и элементы высоких порядков

Если G – мультипликативная конечная группа, порядком элемента Gus91.gif называется минимальное положительное число t: Gus92.gif. Если в G n элементов и если a – элемент порядка n, тогда G называется циклической группой, а a – генератором или примитивным элементом G. Особый интерес для криптографических приложений представляют мультипликативная группа Gus5.gif целых чисел по модулю простого числа p и мультипликативная группа Gus93.gif конечного поля Gus71.gif характеристики 2; эти группы – циклические. Также интерес представляет группа Gus94.gif, где n – произведение двух различных простых чисел.

Определение порядка элемента группы

Вход: мультипликативная конечная группа G порядка n, элемент Gus91.gif и разложение n на простые множители: Gus95.gif.

Выход: Порядок t элемента a.

1. Установить t=n;
2. В цикле по i от 1 до k выполнить:
    2.1. Установить Gus96.gif;
    2.2. Вычислить Gus97.gif;
    2.3. Пока Gus98.gif вычислить Gus99.gif и установить Gus100.gif;
3. Вернуть (t).

Предположим теперь, что G – циклическая группа порядка n. Тогда для любого делителя d числа n число элементов порядка d в G в точности Gus101.gif, где Gus88.gif – функция Эйлера. В частности, G имеет ровно Gus28.gif генераторов и отсюда вероятность того что случайный элемент из G является генератором равна Gus102.gif. Отсюда проистекает следующий алгоритм.

Нахождение генератора циклической группы

Вход: Циклическая группа G порядка n и разложение на множители числа n: Gus95.gif.

Выход: генератор Gus103.gif группы G.

1. Выбрать случайный элемент Gus103.gif в G;
2. В цикле по i от 1 до k выполнить:
    2.1. Вычислить Gus104.gif;
    2.2. Если b=1, то вернуться на шаг 1;
3. Вернуть (Gus103.gif)

Если n=pq, где p,q – различные простые числа, тогда Gus94.gif – нециклическая группа порядка Gus105.gif. Максимальный порядок элемента в Gus94.gifНОК (p-1, q-1).

Выбор элемента максимального порядка в Gus94.gif, где n=pq.

Вход: два различных простых числа p,q и разложение на множители p-1, q-1.

Выход: Элемент Gus103.gif максимального порядка НОК(p-1,q-1) в Gus94.gif, где n=pq.

1. Используя предыдущий алгоритм, приняв за G=Gus94.gif и n=p-1 найти a - генератор Gus5.gif;
2. Используя предыдущий алгоритм, приняв за G=Gus94.gif и n=q-1 найти b - генератор Gus5.gif;
3. Используя алгоритм Гаусса, найти число Gus103.gif в интервале от 1 до n-1, удовлетворяющее условиям: Gus106.gif;
4. Вернуть (Gus103.gif).

Глоссарий

Библиографический указатель

Перейти к списку литературы по разделу "Алгоритмы, используемые при реализации асимметричных криптосхем".

Вернуться к оглавлению

Гусев П.Д. Ловянников А.С., 2013