§3. Теория сравнений
Будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m – модуль. Если 2 целых числа a и b имеют одинаковый остаток от деления на m, то говорят, что они называются равноостаточными или сравнимыми по модулю m, и пишут a ≡ b (mod m), что равносильно a = b+mt, где t Z, или m\(a–b) (очевидно)
3.1. Свойства сравнений:
a ≡ b (mod m), b ≡ c (mod m), a ≡ c (mod m)
a ≡ b (mod m) b ≡ a (mod m)
a1 ≡ b1 (mod m), a2 ≡ b2 (mod m), … , ak ≡ bk (mod m) =>
a1+…+ak ≡ b1+…bk(mod m)
a+b ≡ c (mod m) a ≡ c–b (mod m)
a ≡ b (mod m) a+mt ≡ b+mk(mod m) (t, k Z)
a ≡ b (mod m), c ≡ d (mod m) ac ≡ bd (mod m)
a ≡ b (mod m) ak ≡ bk(mod m)
a ≡ b (mod m) ak ≡ bk(mod m)
Если a ≡ b (mod m), (a, b) = c, (c, m) = 1 (mod m)
a ≡ b (mod m) ak ≡ bk (mod mk)
a ≡ b (mod m), a = a1d, b = b1d, m = m1d a1 ≡ b1(mod m1)
a ≡ b (mod m1), a ≡ b(mod m2), …, a ≡ b(mod mk)
a ≡ b (mod НОК(m1,…,mk))
a ≡ b (mod m), d\m a ≡ b(mod d)
d\a, d\m, a ≡ b(mod m) d\b
a ≡ b (mod m) (a, m) = (b, m)
Доказательство данных свойств не представляет сложности и может быть проведено читателем самостоятельно. Найти доказательства этих свойств можно в [5].
3.2. Полная система вычетов.
Совокупность чисел, сравнимых с a по модулю m называется классом чисел по модулю m (или классом эквивалентности). Все числа одного класса имеют вид mt + r при фиксированном r.
При заданном m, r может принимать значения от 0 до m—1, т.е. всего существует m классов чисел по модулю m, и любое целое число попадет в один из классов по модулю m. Таким образом,
Z = [0]m [1]m … [m—1]m, где [r]m={x Z: x≡r(mod m)}
Любое число класса [r]m называется вычетом по модулю m по отношению ко всем числам того же класса. Число, равное остатку r, называется наименьшим неотрицательным вычетом.
Вычет, наименьший по абсолютной величине, называется абсолютно наименьшим вычетом.
Пример
Возьмем модуль m=5. И пусть a=8. Разделим a на m с остатком:
8=5·1+3.
Остаток r=3. Значит 8 [3]5, и наименьший неотрицательный вычет числа 8 по модулю 5 есть 3.
Абсолютно наименьший вычет можно отыскать, вычислив r—m=3—5=—2, и сравнив абсолютные величины |—2| и |3|. |—2|<|3|, значит —2 – абсолютно наименьший вычет числа 8 по модулю 5.
Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Если все эти числа будут являться наименьшими неотрицательными вычетами по модулю m, то такая система вычетов называется полной системой наименьших неотрицательных вычетов, и обозначается Zm.
{0; 1;…; m—1} = Zm – полная система наименьших неотрицательных вычетов.
{– ;…; 0;…; } (если m–нечетное число) ;
{ — ,…,—1, 0, 1,…, } или {— ,…, —1, 0, 1,…, } (если m четное число) – полная система абсолютно наименьших вычетов.
Пример
Если m=11, то полная система наименьших неотрицательных вычетов есть {0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, а полная система абсолютно наименьших вычетов – {–5; –4; –3; –2; –1; 0; 1; 2; 3; 4; 5}.
Утверждение 1
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Доказательство:
Действительно, в силу несравнимости эти числа принадлежат к разным классам, а т.к. их m штук, то в каждый существующий класс попадает ровно одно число.
j
Утверждение 2
Если (a, m) = 1, и x пробегает полную систему вычетов по модулю m, то ax+b, где b – любое число из Z, тоже пробегает полную систему вычетов по модулю m.
Доказательство:
Чисел ax+b будет ровно m штук. Остается доказать, что любые 2 числа ax1+b и ax2+b несравнимы по модулю m, если x1 x2(mod m)
Доказательство от противного. Предположим, что ax1+b ≡ ax2+b (mod m) в силу 4-го св-ва сравнений, ax1 ≡ ax2 (mod m) в силу св-ва сравнений №9 и того, что (a, m) = 1, имеем x1 ≡ x2(mod m). Получили противоречие с тем, что x1 x2(mod m). Следовательно, предположение неверно, а значит верно обратное. То есть ax1+b и ax2+b несравнимы по модулю m, если x1 x2(mod m), что и требовалось доказать.
j
3.3. Приведенная система вычетов
Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же НОД. Особенно важны классы, для которых он равен 1.
Взяв от каждого из таких классов по одному числу, получим приведенную систему вычетов по модулю m. Обычно ее выделяют из системы наименьших неотрицательных вычетов по модулю m.
Приведенная система наименьших неотрицательных вычетов по модулю m обозначается Um.
Количество чисел в приведенной системе вычетов по модулю m, очевидно, равно φ(m).
Пример:
Приведенная система вычетов по модулю 15 есть {1; 2; 4; 7; 8; 11; 13; 14}. Заметим, что φ(15)=(5–1)(3–1)= 8 и действительно, в приведенной системе вычетов по модулю 15 ровно 8 элементов.
Утверждение 1
Любые φ(m) чисел, попарно несравнимых по модулю m и взаимно простых с m, образуют приведенную систему вычетов.
(Доказательство очевидно как в утверждении 1 пункт 2)
Утверждение 2
Если (a, m) = 1, x пробегает приведенную систему вычетов по модулю m, то ax тоже пробегает приведенную систему вычетов по модулю m . (Доказательство очевидно как в утверждении 2 пункт 2).
3.4. Обратный элемент.
Говорят, что элемент b называется обратным к a по модулю m, если ab≡1(mod m), и пишут b ≡ a–1 (mod m).
Вообще, классическая теория чисел не нуждается в таком понятии как обратный элемент, в чем можно убедиться, ознакомившись, например, с [5]. Однако криптология использует системы вычетов как в теоретико-числовом, так и в алгебраическом аспекте, а потому, для удобства изложения алгебраических основ криптологии, мы вводим понятие обратного элемента.
Возникает вопрос – для всех ли элементов по данному модулю m существует обратный (по умножению), и если для каких-то элементов обратный существует, как его найти?
Для ответа на этот вопрос воспользуемся расширенным алгоритмом Евклида. Рассмотрим сначала взаимно простые число a и модуль m. Тогда, очевидно, (a,m)=1. Расширенный алгоритм Евклида позволяет получить числа x и y, такие, что ax+my=(a,m), или, что то же самое, ax+my=1. Из последнего выражения получаем сравнение ax+my≡1(mod m). Поскольку my≡0(mod m), то ax≡1(mod m), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю m.
Пример.
a=5, m=7. Требуется найти a-1mod m.
Воспользуемся расширенным алгоритмом Евклида.
7=51+2
5=22+1
2=12
Обратный ход:
1=5–22=5–(7–51)2=53–72.
x=3, y=–2.
5-1≡3(mod 7)
Проверка: 53=15. 15≡1(mod 7).
Действительно, 3 является обратным элементом к 5 по модулю 7.
Итак, конструктивным образом убедились в том, что для чисел, взаимно простых с модулем, существует обратный по этому модулю. А существуют ли обратные элементы для чисел, не являющихся с модулем взаимно простыми?
Пусть (a,m)=d≠1. Тогда a и m представимы в виде a=da1, m=dm1. Допустим, что для a существует обратный элемент по модулю m, то есть b: ab≡1(modm). Тогда ab= mk +1. Или, что то же самое, da1b= dm1k +1. Но тогда по теореме 2 из §1 п.1, в силу того, что и левая часть данного уравнения, и первое слагаемое в правой части делятся на d, то d\1, а это не так, поскольку d≠1. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.
Итак, мы только что доказали
Теорему обратимости
a-1 (mod m) (a, m) = 1.
■
Суммируя все рассуждения этого пункта, можем сказать, что обратимыми являются только взаимно простые с модулем числа, и найти обратные для них можно с помощью расширенного алгоритма Евклида.
3.5. Алгебраические структуры на целых числах.
Покажем некоторые интересные свойства приведенной системы вычетов. Но сначала напомним определения группы, кольца и поля.
Примечание: операция называется заданной на множестве, если результат применения этой операции к любым элементам множества также принадлежит этому множеству.
Группой называют множество G с заданной на нем бинарной операцией •, если:
а) Операция • ассоциативна, то есть a,b,c G выполняется (a•b)•c=a•(b•c);
б) a•e=e•a=a (Если групповая операция называется сложением, то e называют нулевым элементом, если операция – умножение, то e называют единичным элементом.);
в) (Если групповая операция называется сложением, то xґ называют противоположным к x элементом, если операция – умножение, то обратным элементом.);
Если операция группы коммутативна (то есть ), то группа называется коммутативной, или абелевой.
Утверждение 1
< Zm , +(mod m)> — абелева группа.
Доказательство
Докажем, что Zm вместе с операцией сложения по модулю m образуют абелеву группу. Действительно, операция сложения не выводит за пределы множества целых чисел, а Zm покрывает своими вычетами всё Z, поэтому можно сказать, что операция +(mod m) задана на Zm. Ассоциативность операции +(mod m) следует из ассоциативности сложения, в качестве нулевого элемента выступает «0», а в качестве противоположного к a выступает m—a. Коммутативность групповой операции следует из коммутативности сложения.
j
Более того, как нетрудно показать, любая полная система вычетов вместе с операцией сложения по модулю m образует абелеву группу.
Утверждение 2
m, · (mod m)> — абелева группа.
Доказательство
Докажем, что умножение по модулю m задано на приведенной системе вычетов по модулю m. Действительно, Um покрывает своими вычетами всё Z кроме тех чисел, которые имеют с m общие нетривиальные делители. Результат умножения двух чисел, каждое из которых взаимно просто с m, также будет взаимно просто с m. Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же наибольший общий делитель. Это значит, что операция умножения по модулю m не выводит за пределы Um, а значит задана на Um.
Ассоциативность и коммутативность операции · (mod m) следует из ассоциативности и коммутативности умножения, единичным элементом является «1». Каждый элемент множества Um имеет обратный согласно теореме обратимости в силу того, что все элементы Um взаимно просты с m.
m
Из курса алгебры мы знаем, что группа, содержащая конечное число элементов, называется конечной группой.
Кольцом называют непустое множество K вместе с заданными на нем бинарными операциями + и , если:
а) — абелева группа;
б) Операция ассоциативна;
в) Операция дистрибутивна относительно + (то есть a(b+c)=(ab)+(ac), (a+b)c=(ac)+(bc));
Кольцо называют коммутативным, если операция коммутативна.
Кольцо называют кольцом с единицей, если xe=ex=x.
Полем называют коммутативное кольцо с единицей , в котором каждый ненулевой элемент обратим по операции .
Утверждение
p,+(mod p), (mod p)> — поле, если p – простое число.
Доказательство:
Согласно утверждению 1, p,+(mod p)> - абелева группа, причем в качестве нулевого элемента выступает 0 Zp. Поскольку Zp покрывает своими вычетами всё множество целых чисел, а операция умножения не выводит целые числа за пределы Z, то и операция умножения по модулю p не выводит за пределы Zp. То есть операция (mod p) задана на Zp.
Ассоциативность и коммутативность операции (mod p) следует из аналогичных свойств операции умножения, дистрибутивность умножения по модулю p относительно сложения по модулю p следует из дистрибутивности умножения относительно сложения.
В качестве единицы по операции (mod p) выступает 1 Zp.
Итак, p,+(mod p), (mod p)> — коммутативное кольцо с единицей. А поскольку в силу простоты p все элементы, кроме нулевого, взаимно просты с модулем p, то, по теореме обратимости, обратим по операции (mod p).
Следовательно, по определению поля, p,+(mod p),(mod p)> — поле.
Из курса алгебры мы знаем, что поле, содержащее конечное число элементов, называется конечным полем. Конечные поля называются полями Галуа по имени их первооткрывателя, Эвариста Галуа.
Число элементов в поле называется его мощностью. Все поля одинаковой мощности изоморфны друг другу. Таким образом, любое поле, мощность которого есть простое число, изоморфно p,+(mod p),(mod p)> для подходящего p.
Поле p,+(mod p),(mod p)> иначе обозначается GF(p), то есть поле Галуа мощности p.
Кроме полей GF(p) существуют поля составной мощности. Различают GF(2α), GF(pα) (где p – простое число, не равное 2 ). В настоящей главе мы будем рассматривать поля GF(p), получим для таких полей некоторые результаты, а затем, во второй главе, обобщим их и на другие конечные поля.
3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
В этом пункте будут доказаны важнейшие теоремы теории чисел и показаны их приложения к задачам криптографии.
Теорема Эйлера.
При m > 1, (a, m) = 1 aφ(m) ≡ 1 (mod m).
Доказательство:
Если x пробегает приведенную систему вычетов x = r1, r2,…,rc (c = φ(m)), составленную из наименьших неотрицательных вычетов, то в силу того, что (a,m)=1, наименьшие неотрицательные вычеты чисел ax = ρ1, ρ2,…, ρc будут пробегать ту же систему, но, возможно, в другом порядке (это следует из утверждения 2 пункт 3). Тогда, очевидно,
r1·…·rc = ρ1·… ·ρc *
Кроме того, справедливы сравнения
ar1 ≡ ρ1(mod m), ar2 ≡ ρ2(mod m), … , arc ≡ ρc(mod m).
Перемножая данные сравнения почленно, получим
ac ·r1 ·r2 ·…·rc ≡ ρ 1·…· ρ c(mod m)
Откуда в силу (*) получаем
ac ≡ 1 (mod m)
А поскольку количество чисел в приведенной системе вычетов по модулю m есть φ(m), то есть c = φ(m), то
aφ(m) ≡ 1 (mod m).
Теорема Ферма (малая)
р – простое, p не делит a ap–1 ≡ 1 (mod m)
Доказательство: по теореме Эйлера при m=p.
Важное следствие:
ap ≡ a (mod p) a, в том числе и для случая p\a.
Теорема Эйлера применяется для понижения степени в модулярных вычислениях.
Пример:
10100 mod 11 = 10911+1 = 109+1 mod 11 = (–1)10 mod 11 = 1.
Следствие:
Если a: 0 < a < p, для которого ap–1 1 (mod p) p – составное.
Отсюда –
Тест Ферма на простоту
Вход: число n – для проверки на простоту, t – параметр надежности.
Повторяем t раз:
а) Случайно выбираем a [2, n-2]
б) Если an–1 1 (mod n) «n – составное». Выход.
«n – простое с вероятностью 1– εt »
Этот тест может принять составное число за простое, но не наоборот.
Вероятность ошибки есть εt, где ε
В случае составного числа n, имеющего только большие делители, ε , то есть существуют числа, для которых вероятность ошибки при проверке их на простоту тестом Ферма близка к 1.
Для теста Ферма существуют так называемые числа Кармайкла – такие составные числа, что a: (a,n) = 1 an–1 ≡ 1(mod n). То есть числа Кармайкла – это такие составные числа, которые всегда принимаются тестом Ферма за простые, несмотря на то, как велико число t – параметр надежности теста.
Теорема Кармайкла
n – число Кармайкла 1) n свободно от квадратов (т.е. n = p1p2…pk);
2) (pi – 1)\(n – 1), i = 1,…,k ;
3) k .
Наименьшее известное число Кармайкла n=561 = 311·17
3.7. Применение теоремы Эйлера в RSA:
Если известно разложение числа на простые сомножители a = p1 p2 … pn , то легко вычислить функцию Эйлера φ(a).
Отсюда вывод: сложность вычисления функции Эйлера не выше сложности задачи факторизации .
Покажем, что в случае n=pq (p,q – простые числа, p q) задачи нахождения функции Эйлера и факторизации эквивалентны. (то есть в случае, когда n – модуль RSA).
Учтем, что φ(n) = (p – 1)(q – 1). Тогда имеем систему
.
Зная n и φ(n), находим p и q из системы, приведенной выше, следующим образом:
Первое уравнение системы является квадратным уравнением относительно q,
q = , где Dq = [n– φ(n)+1]2 – 4n.
Подставляя полученное q во второе уравнение системы, находим p.
Видим, что при нахождении чисел p, q по известным n, φ(n) применяются только «дешевые» в смысле времени операции – сложение, деление на 2. Только при вычислении дискриминанта приходится применять возведение в степень, а при вычислении q – извлечение квадратного корня. Однако эти операции производятся однократно, поэтому временные затраты не столь существенны.
Итак, для модуля RSA задачи нахождения функции Эйлера и факторизации равносложны.
Формулировка теоремы Эйлера для RSA:
n = pq; p≠q; p, q – простые числа a выполняется akφ(n)+1≡ a (mod n).
(на самом деле n может быть просто свободно от квадратов, то есть произведением произвольного количества различных простых чисел)
Доказательство:
Возможны два случая:
(a, n) = 1 по теореме Эйлера aφ(n) ≡ 1 (mod n)
akφ(n)+1 = 1k a ≡ a (mod n).
(a, n) ≠ 1, n не делит a в силу основного свойства простых чисел, либо p\ a, либо q \ a.
Не нарушая общности, предположим, что p\a, q не делит a.
Тогда по теореме Ферма, akφ(n)+1≡a(mod p),
qq–1≡1 (mod q) akφ(n)+1≡1k(p–1)·a ≡ a (mod q).
Итак, akφ(n)+1 ≡ a (mod p), akφ(n)+1≡ a (mod q). Отсюда по св-ву сравнений №12, akφ(n)+1≡ a(mod НОК(p,q)). В силу простоты p и q, НОК(p,q)=pq=n, значит
akφ(n)+1≡ a (mod n).
n\a a≡0(mod n) akφ(n)+1≡0≡a(mod n).
Примечание:
Если вместо φ(n) в теореме Эйлера для RSA взять НОК(p–1, q–1), теорема все равно будет верна.
Применение теоремы Эйлера в RSA:
Напомним, что криптосистема RSA является системой с открытым ключом. В качестве параметров системы выбираются различные большие простые числа p и q, вычисляется n=pq, φ(n)=(p–1)(q–1), выбирается число e: 2<e<n, (e, φ(n))=1 и вычисляется d=e-1(mod φ(n)). В качестве открытого ключа берется пара (n, e), в качестве закрытого, хранимого в секрете, четверка (p, q, φ(n), d).
Для того, чтобы зашифровать открытый текст x, абонент, пользуясь открытым ключом, вычисляет зашифрованный текст y по следующей формуле:
y = xe mod n.
Для того, чтобы осуществить расшифрование, владелец секретного ключа вычисляет
x = yd mod n.
В результате такого расшифрования действительно получится открытый текст, поскольку yd mod n=xed mod n=xed mod φ(n)mod n =x1 mod n=x.
Без знания простых сомножителей p и q сложно вычислить значение функции Эйлера φ(n), а значит, и степень d, в которую следует возводить зашифрованный текст, чтобы получить открытый.
Более того, знание простых сомножителей p и q может значительно облегчить процедуру возведения шифрованного текста y в степень d. Действительно, пользуясь теоремой Эйлера для RSA, можем понизить степень d. Разделим d на φ(n) с остатком:
d=kφ(n)+r
x=yd mod n= ykφ(n)+r mod n= yr mod n.
Еще более можно понизить степень, используя НОК(p–1,q–1)= вместо φ(n).
Пример:
n=1923=, φ(n)=1822=396, d=439.
НОК(18,22)=1822/2=198.
d mod φ(n)=43. d mod НОК(p–1,q–1)=43.
Число d=439 в двоичном представлении есть 110110111. Поэтому возведение в степень d c применением дихтономического алгоритма (см. гл.2) требует 8 возведений в квадрат и 6 умножений чисел.
Число 43 в двоичном представлении есть 101011. Возведение в степень 43 требует 5 возведений в квадрат и 3 умножения чисел. Кроме того, для вычисления φ(n) требуется 1 операция умножения.
Таким образом, для данного примера экономия времени составляет 2 сложные операции.
В случае больших простых делителей числа n экономия оказывается более существенной.
|
