08.04.09.Печать_edit
.pdf
из последнего равенства следует d | b. Мы пришли к противоречию, следовательно, наше допущение неверно, что доказывает утверждение.
Утверждение 17
Если НОД(a, m) = 1, то сравнение ax b (mod m) имеет единственное решение.
Доказательство
Если НОД(a, m) = 1, то в приведенной системе наименьших неотрица-
тельных вычетов по модулю m существует единственный элемент a 1, такой что a 1a = 1. Для этого элемента имеем НОД(a 1, m) = 1. Умножая обе части
сравнения ax b (mod m) на a 1, получим a 1ax a 1b (mod m) x a 1b (mod m).
Утверждение 18
Числа класса a по модулю m образуют следующие k классов по модулю km: a, a m, a 2m, ..., a (k 1)m.
Утверждение 19
Если НОД(a, m) = d и d | b, то сравнение ax b (mod m) имеет d решений. Все эти решения принадлежат одному классу по модулю m/d.
Доказательство
Из утверждения 15 следует, что при НОД(a, m) = d и d | b сравнение ax b (mod m) эквивалентно сравнению вида a1x b1 (mod m1), где m1 = m/d,
НОД(a1, m1) = 1.
Согласно утверждению 17, последнее сравнение имеет одно решение, представляющее собой один класс по модулю m/d, т. е. этому сравнению
удовлетворяют числа вида x (mod m/d), где может быть найдено, на-
пример, по формуле x a1 1b1 a1 (m/d) 1b1 (mod m/d). Числа этого класса по модулю m/d образуют d классов по модулю m (см. утверждение 18), и
решения сравнения ax b (mod m) могут быть записаны в виде x (mod m),
x + m/d (mod m), …, x + (d 1)m/d (mod m).
31
Утверждение 20
Если НОД(a, m) = 1 и x пробегает значения, образующие приведенную систему вычетов, то ax также принимает значения, образующие приведенную систему вычетов по модулю m.
Теорема 13
1. При p /| a сравнение x n a (mod p) по простому модулю p > 2 либо совсем не имеет решений, либо число решений равно наибольшему общему делителю n и p 1.
2. Сравнение (1) не имеет решений, если для = НОД(n, p 1) |/ ind a, и имеет решений, если | ind a.
Доказательство
Пусть НОД(n, p 1) = . По простому модулю p существуют первообразные корни (см. утверждение 8). Пусть g есть некоторый первообразный
корень. Индексируя сравнение |
|
|
x n a (mod p) |
(1) |
|
по основанию g, получаем сравнение |
|
|
n ind x ind a (mod p 1), |
(2) |
|
которое эквивалентно исходному. Если обозначить ind x = z, ind a = b, то для неизвестной z получим сравнение 1-й степени:
nz b (mod p 1).(3)
При |/ ind a, т. е. |/ b, сравнение (3) не имеет решений (см. утверждение 16), но тогда не существует и значений x, удовлетворяющих сравнениям
(2) и (1). При | ind a, т. е. | b, согласно утверждению 19, сравнение (3) имеет решений. Значения ind x, удовлетворяющие сравнению (2), принадлежатклассам по модулю p 1, а следовательно, и для x существует классов по модулю p, удовлетворяющих сравнению (1).
Замечание.
При p | a сравнение (1) может быть записано в виде x n 0 (mod p), и в этом случае оно имеет одно решение x 0 (mod p).
32
Пусть g и h — произвольные первообразные корни по модулю p. Тогда
имеем |
h gindgh hindhg indgh hindhg indgh (mod p) |
|
|||||||
indh g ∙ indg h 1(mod p 1) |
indh g (indg h) 1 (mod p 1), |
т. е. индексы |
|||||||
первообразных корней являются взаимно простыми с p 1. |
Действи- |
||||||||
тельно, пусть НОД(indg a, p 1) = > 1. Тогда |
|
|
|||||||
|
|
p 1 |
p 1 |
|
indga |
|
|
||
|
|
|
gindga |
|
|
g p 1 |
|
|
|
|
|
|
|
1z 1(mod p) , |
|
||||
|
a |
|
|
|
|||||
где z — целое число, т. е. показатель, к которому относится число a, меньше чем p 1. Поскольку НОД(indh g, p 1) = 1 и indh a indh g ∙ indg a, то из |/ indg a (или из | indg a) следует |/ indh a (или | indh a).
Заметим, что ind 1 = p 1, т. е. ind 1 0 (mod p 1). Следовательно,
| ind 1 и сравнение xn 1 (mod p) имеет решений.
Определение
1.Число a называется вычетом n-й степени по простому модулю p, если p |/ a и сравнение x n a (mod p) имеет решения.
2.Число a называется невычетом n-й степени по простому модулю p, если сравнение x n a (mod p) не имеет решений.
Теорема 14
По простому модулю p > 2 число классов вычетов n-й степени равно
(p 1)/ , где = НОД(n, p 1).
Доказательство
Всего по модулю p имеется p 1 классов, взаимно простых с модулем (класс 0, состоящий из чисел, делящихся на p, согласно указанному выше определению, не относится к вычетам n-й степени). Индексы этих классов образуют полную систему вычетов по модулю p 1, т. е. каждому такому классу (если взять ind 1 = p 1) можно сопоставить индекс, равный одному из чисел: 1, 2, …, p 1.
33
Пусть НОД(n, p 1) = . Среди чисел 1, 2, …, p 1 имеется |
p 1 |
чисел, |
|||||||
|
|||||||||
|
|
|
|
|
|
|
|
||
делящихся на , которыми являются числа , 2 , …, |
p 1 |
|
1 , (p 1). Эти |
||||||
|
|||||||||
|
|
|
|
|
|
|
|||
числа являются индексами |
p 1 |
различных чисел |
из |
множества |
|||||
|
|
||||||||
|
|||||||||
|
|
|
|
|
|
|
|||
{1, 2, …, p 1}. Если a равно любому из этих чисел, то, согласно теореме 13,
сравнение x n a (mod p) имеет решения, т. е. существует |
p 1 |
классов выче- |
||
|
|
|||
|
|
|||
тов n-й степени по простому модулю p. |
|
|
|
|
Теорема 15
Если = НОД(n, p 1), то вычеты n-й степени по простому модулю p > 2 совпадают с вычетами степени по этому модулю.
Доказательство
Если НОД(n, p 1) = , то будем иметь также НОД( , p 1) = . При p |/ a
сравнения x n a (mod p) и x a (mod p), согласно теореме 13, имеют реше-
ния при одних и тех же числах a, таких что | ind a.
В силу теоремы 15 можно рассматривать вычеты и невычеты n-й степени только для таких n, которые являются делителями числа p 1, т. е. рас-
сматривать сравнения вида x n a (mod p), где n | p 1. Действительно, срав-
нение xn a (mod p) можно записать в виде:
(x ) n/ a (mod p), (4)
где НОД((n/ ), p 1) = 1, т. е. сравнение (4) имеет единственное решение от-
носительно неизвестной z = x . Пусть x b (mod p). Последнее сравнение имеет вид сравнения x n a (mod p), где n | p 1. Для случая n | p 1 теоремы 13 и 14 имеют следующую формулировку.
Теорема 13*
34
При p |/ a и n | p 1 сравнение x n a (mod p) по простому модулю p > 2 либо совсем не имеет решений, либо имеет n решений. По такому модулю a является вычетом n-й степени тогда и только тогда, когда n | ind a.
Теорема 14*
По простому модулю p > 2 и n | p 1 число классов вычетов n-й степени равно (p 1)/n.
Теорема 16
При n | p 1 a является вычетом n-й степени по простому модулю p > 2 тогда и только тогда, когда a (p 1)/n 1 (mod p).
Доказательство
Индексируя сравнение a (p 1)/n 1 (mod p), получаем, что это сравнение
имеет место тогда и только тогда, когда p 1ind a 0(mod p 1) , т. е. когда n
p 1ind a Q ( p 1) или ind a = nQ (Q — целое число), т. е. сравнение n
a(p 1)/n 1 (mod p) имеет место тогда и только тогда, когда n | ind a.
Теорема 17
При p |/ a и n | p 1 все решения сравнения x n a (mod p) по простому модулю p > 2 можно получить, умножая одно решение этого сравнения на различные решения сравнения x n 1 (mod p).
Другими словами, все корни n-й степени из a по модулю p можно по-
лучить, умножая один из этих корней на различные корни n-й степени из 1.
Доказательство
Поскольку ind 1 = 0 и n | 0, сравнение x n 1 (mod p) имеет n решений.
Обозначим эти решения через t1, …, tn, где ti tj (mod p) и p |/ ti. Пусть x0
удовлетворяет сравнению (1), тогда (x0ti)n = x0ntin a 1 a (mod p) при i = 1,
35
2, …, n, т. е. классы x0t1, ..., x0tn представляют собой решения сравнения x n a (mod p).
Поскольку p |/ a, то p |/ x0 и НОД(x0, p) = 1, следовательно, числа x0t1, …, x0tn являются (утверждение 20) частью приведенной системы вычетов по модулю p и x0t1, …, x0tn представляют собой n различных решений сравнения
(1). Степень этого сравнения равна n, следовательно, x0t1, …, x0tn охватывают все решения.
Важным частным случаем степенных сравнений являются сравнения второй степени. Из доказанных выше теорем вытекают следующие следствия, относящиеся к случаю n = 2.
Следствие 3
Необходимым и достаточным условием того, чтобы число a было квадратичным вычетом по простому модулю p > 2 (p |/ a), является выполнимость сравнения
p 1
a 2 1 (mod p) .
мость сравнения a 2 1(mod p) .
36
Доказательство
В силу малой теоремы Ферма имеем a p 1 1 0 (mod p) . Поскольку
|
|
p 1 |
|
p 1 |
|
|
|
||
2 | p 1, то можем записать |
|
|
|
|
|
|
|
|
|
(a 2 1)(a 2 |
1) 0 (mod p) . Последнее срав- |
||||||||
|
|
|
|
|
|
|
|
p 1 |
|
|
|
|
|
|
|
||||
нение выполняется, когда |
имеет |
место |
либо a 2 1 0 (mod p) , либо |
||||||
p 1
a 2 1 0 (mod p) . Первое из последних двух сравнений выполняется, когда a является квадратичным вычетом. Если a является квадратичным невы-
p 1
четом, то имеем a 2
1 0 (mod p) .
ГЛАВА 2. Алгоритмы двухключевой криптографии
2.1. Генерация простых чисел
Для генерации больших простых чисел могут быть использованы следующие два подхода:
формируются случайные числа заданного размера и проверяется, являются ли они простыми, с помощью вероятностных тестов;
по определенной процедуре генерируются простые числа, проверка которых осуществляется с помощью детерминистических тестов на простоту.
Впервом случае тесты строятся на основе определенных теорем из теории чисел, сформулированных и доказанных для простых чисел. Если число не удовлетворяет тесту, то оно не является простым и отбрасывается. Для проверки берется следующее случайное число требуемого размера. Если число проходит тест, то некоторый переменный параметр, используемый для тестирования, изменяется и тест повторяется снова. Число, прошедшее большое число опытов определенного типа, принимается в качестве простого, поскольку вероятность, что составное число может пройти все тесты, пренебрежимо мала. Для того чтобы исключить некоторые возможные классы составных чисел, которые могут проходить тесты конкретного типа, используют несколько различных тестов, по каждому из которых выполняется большое число опытов. Достоинством генерации вероятностных простых чисел является сравнительная простота процедуры. Недостатком первого под-
37
хода является то, что после генерации большого вероятностного простого числа p может оказаться достаточно сложным определение разложения числа p 1, которое необходимо знать, например, в случае ЭЦП на основе сложности задачи дискретного логарифмирования с сокращенной длиной подписи. Разложение числа p 1 представляет интерес также и для отсеивания некоторых классов слабых простых чисел. Следующие два вероятностных теста могут быть применены совместно. Пусть мы хотим проверить, является ли число p простым.
Тест Ферма заключается в проверке соотношения b p 1 = 1 (mod p) для большого числа различных значений b. Число различных использованных при тестировании значений b, для которых выполняется указанное соотношение, определяет число выполненных опытов по тесту Ферма. Однако известен класс составных чисел, которые проходят тест Ферма (числа Кар-
майкла; например 1105 = 5 13 17 и 41 041 = 7 11 13 41).
Тест Соловея–Штрассена заключается в проверке равенств |
b |
1, |
||
|
|
|
||
|
||||
|
|
p |
|
|
b
где — символ Лежандра для значений b, являющихся квадратичными
p
вычетами по модулю p, и для значений b, являющихся квадратич-
ными невычетами по модулю p (квадратичным вычетом называется число, являющееся квадратом некоторого числа x по модулю p; т. е. для квадратич-
ного вычета существует квадратный корень: b = x 2 mod p).
Второй тест хорошо отсеивает числа Кармайкла. Вероятность того, что составное число пройдет один опыт по тесту Соловея–Штрассена, не превышает значения 0.5. Это позволяет получить оценку числа опытов, которые следует выполнить в соответствии с данным тестом, чтобы получить необходимо низкую вероятность принятия составного числа в качестве простого. Первый тест используется в качестве предварительной отбраковки чисел. Второму тесту подвергают только числа, прошедшие первый. (Второй тест
p 1
на самом деле поглощает первый, поскольку проверка условия b 2
mod p 1
38
для значений b, являющихся квадратичными вычетами, фактически означает проверку по тесту Ферма.)
2.2. Детерминистическая генерация больших простых чисел
Способ на основе подбора разложения функции Эйлера
Формируется набор k простых чисел {q1, q2, …, qk} сравнительно малой длины (например, имеющих 8 10 десятичных знаков). Причем числа q1, q2, …, qk проверяются детерминистическим тестом на простоту, в качестве которого можно взять проверку на делимость на все натуральные числа от
2 до 
qi (метод пробного деления; g обозначает наименьшее целое чис-
ло, не меньшее, чем число g). Из указанного набора случайным образом выбираются h простых чисел m1, m2, …, mh, вычисляется число p1, имеющее следующую структуру:
i h
p1 1 2 mi .
i 1
Затем выбирается некоторое число b и проверяется, выполняются ли для данного p1 следующие два условия:
p1 |
1 |
|
p1 1 |
|
|
|
||
|
|
|
|
|
|
|||
= 1 (mod p) и b mi |
1 mod p для всех m |
{m , m , …, m }. |
||||||
b |
|
|||||||
|
|
|
|
|
i |
1 2 |
h |
|
Если после нескольких попыток найдется некоторое b, которое удовлетворяет указанным выше двум соотношениям, то p является простым числом. Если такое число не найдено, то выбирается другой случайный набор простых чи-
сел m1, m2, …, mh из набора q1, q2, …, qk. Сформированное таким образом число p1 имеет длину примерно в h раз больше средней длины чисел q1, q2,…, qk (например, от 8h до 10h десятичных знаков). Можно аналогич-
ным образом сформировать следующий набор простых чисел {p1, p2, …, pk} и, используя их в качестве исходных, повторить рассматриваемую процедуру, формируя еще более длинные простые числа. Достоинством данного способа является то, что мы заведомо знаем разложение p 1; кроме того, мы можем формировать это разложение таким образом, чтобы в нем содержались простые числа требуемой длины. Основным недостатком такого спосо-
39
ба является то, что формируется только некоторый подкласс простых чисел заданной большой длины. Однако мощность этого подкласса может быть задана такой, что этим обстоятельством атакующий не сможет воспользоваться для раскрытия той или иной двухключевой криптосистемы, в которой будет использоваться данная процедура детерминистической генерации простых чисел.
Данный детерминистический тест основан на следующей теореме.
Теорема о простоте числа.
Пусть p — целое нечетное число, превышающее 1. Если существует b p – 1, такое что выполняются следующие условия:
1) b p –1 = 1 mod p и
p 1
2) b mi 1 mod p для каждого простого делителя mi числа p – 1, то число p является простым.
Доказательство
Допустим, что p не является простым. Тогда функция Эйлера от p имеет значение меньшее чем p – 1, т. е. (p) < p – 1. Рассмотрим два случая: а)
НОД (b, p) = 1 и б) НОД (b, p) 1. В случае а) порядок числа b должен делить
(p) < p – 1, но по условию теоремы порядок b равен p – 1. В случае б) не существует целых степеней n, для которых выполняется условие b n = 1 mod p. В обоих случаях приходим к противоречию, которое доказыва-
ет утверждение теоремы. (Пояснение к случаю б): если НОД (b, p) = 1, то
| b n mod p для любого n, поскольку для остатка r от деления b n на p имеем НОД (bn, r) = ).
Способ по стандарту ГОСТ Р 34.10–94
Для генерации больших простых чисел в ГОСТ Р 34.10–94 используется детерминистический тест, основанный на следующей теореме.
Теорема о простоте числа.
40