Материал предоставлен http://it.rfet.ru

Элементы теории чисел

Многие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел. Читатели, знакомые с теорией чисел, могут непосредственно перейти к следующему разделу.

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

Пример. Числа 11, 23 — простые; числа 27, 33 — составные (27 делится на 3 и на 9, 33 делится на 3 и на 11).

Теорема. (основная теорема арифметики)

Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом.

Пример. %%27 = 3\times3\times3%%, %%33 = 3\times11%%.

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

Пример. Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 — нет (у них есть общий делитель 3).

Определение (функция Эйлера). Пусть дано целое число %%N > 1%%. Значение функции Эйлера %%\phi(N)%% равно количеству чисел в ряду %%1,2,3,... ,N — 1%%, взаимно простых с %%N%%.

Пример. %%\phi(10)=?%%

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

1 %%\not{2}%% 3 %%\not{4}%% %%\not{5}%% %%\not{6}%% 7 %%\not{8}%% 9

%%\phi(10)=4%%

%%\phi(12)=?%%

p(12) = 4

1 %%\not{2}%% %%\not{3}%% %%\not{4}%% 5 %%\not{6}%% 7 %%\not{8}%% %%\not{9}%% %%\not{10}%% 11

%%\phi(12)=4%%

Утверждение. Если %%p%% — простое число, то %%\phi(p) = p - 1%%. Доказательство.В ряду %%1,2,3,... ,p — 1%% все числа взаимно просты с р, так как %%р%% — простое число и по определению не делится ни на какое другое число.

Утверждение. Пусть %%p%% и %%q%% — два различных простых числа %%(р \not = q)%%. Тогда %%\phi (pq) = (p — 1) (q — 1)%%.

Теорема (Ферма). Пусть %%p%% простое число и %%0<a<p%%. Тогда %%a^{p-1}mod\,p=1%%

Теорема (Эйлер). Пусть %%a%% и %%b%% — взаимно простые числа. Тогда %%a^{\phi\, (b)}\, mod\, b=1%%. Теорема Ферма является частным случаем теоремы Эйлера, когда %%b%% — простое число.

Пример. %%\phi(12) = 4%%, %%5^4 mod \,12 = (5^2)^2 mod \,12 = (1^2)^2 mod \,12 = 1%%.

Нам понадобится еще одна теорема, близкая к теореме Эйлера.

Теорема. Если %%р%% и %%q%% — простые числа, %%р \not= q%% и %%k%% — произвольное целое число, то $$a^{k \phi(pq)+1} mod \, (pq) = a \; \; \; (1)$$

Пример. Возьмем %%р = 5%%, %%q = 7%%. Тогда %%pq = 35%%, а функция Эйлера — %%\phi(35) = 4 \cdot 6 = 24%%.

Рассмотрим случай к = 2, т.е. будем возводить числа в степень %%2 \cdot 24 + 1 = 49%%. Получим $$9^{49} mod\,35 = 9$$ $$23^{49} mod\,35 = 23$$

Это не удивительно, так как каждое из чисел 9 и 23 взаимно просто с модулем 35, и по теореме Эйлера

$$9^{24} mod\,35 = 1%%, %%23^{24} mod \,35 = 1$$

Однако приведенная теорема остается верной и для следующих чисел: %%10^{49} mod 35 = 10%%, %%28^{49} mod\,35 = 28%%, в то время как теорема Эйлера для них не применима (каждое из чисел 10 и 28 не взаимно просто с модулем 35 и %%10^{24} mod\,35 = 15%%, %%28^{24} mod\,35=21%%).

Определение. Пусть %%a%% и %%b%% — два целых положительных числа. Наибольший общий делитель чисел %%a%% и %%b%% есть наибольшее число %%с%%, которое делит и %%a%% и %%b%%: $$c = gcd(a, b).$$

Обозначение gcd для наибольшего общего делителя происходит от английских слов greatest common divisor и принято в современной литературе.)

Пример. %% gcd(10,15) = 5%%; %%gcd(8, 28) = 4%%.

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

Алгоритм Евклида

ВХОД: Положительные целые числа %%a%%,%%b%%, %%a > b%%.

ВЫХОД: Наибольший общий делитель %%gcd(a, b)%%.

WHILE %%b \not = 0%% DO

%%r \leftarrow\,a\, mod\, b, a \, \leftarrow\, b, b \, \leftarrow \,r.%%

RETURN a.

Пример. Покажем, как с помощью алгоритма Евклида вычисляется %%gcd(28, 8)%%:

a: 28 84
b: 8 40
r: 4 0

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

Для многих криптографических систем, рассматриваемых в следующих разделах и главах, актуален так называемый обобщенный алгоритм Евклида, с которым связана следующая теорема.

Теорема. Пусть %%a%% и %%b%% — два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа %%х%% и %%у%%, такие, что $$ax + by = gcd(a, b) \;\;\; (2)$$

Обобщенный алгоритм Евклида служит для отыскания %%gcd(a, b)%% и %%х%%, %%у%%, удовлетворяющих (2). Введем три строки

%%U = (u_1, u_2, u_3),%%

%%V = (v_1, v_2, v_3)%% и

%%Т = (t_1, t_2, t_3)%%

Тогда алгоритм записывается следующим образом.

Обобщенный алгоритм Евклида

ВХОД: Положительные целые числа %%a%%, %%b%%, %%a > b%%.

ВЫХОД: %%gcd(a, b)%%, %%x%%, %%y%%, удовлетворяющие (2).

  1. %%U \leftarrow (а, 1,0), V \leftarrow (b,0,1)%%.
  2. WHILE %%v_1 \not= 0%% DO
  3. %%q \leftarrow v_1\, div\,v_2;%%
  4. %%T \leftarrow (u_1 mod\, v_1,u_2-qv_2,u3-qv_3);%%
  5. %%u \leftarrow V,V \leftarrow T. %%
  6. %%RETURN U = (gcd(a, b), x, y).%%

Результат содержится в строке %%U%%. Операция div в алгоритме — это целочисленное деление %%a \,div\, b = [a/b]%%.

Пример. Пусть %%a=28%%, %%b=19%%. Найдем числа %%x%% и %%y%%, удовлетворяющие (2).

U 28 10
V U 190 1
Т V U 9 1 -1 q = 1
  Т V U 1 -2 3 q = 2
   Т V 0 19 -28 q = 9

Поясним представленную схему. Вначале в строку U записываются числа (28,1,0), а в строку V — числа (19,0,1) (это первые две строки на схеме). Вычисляется строка Т (третья строка в схеме). После этого в качестве строки U берется вторая строка в схеме, а в качестве V — третья, и опять вычисляется строка Т (четвертая строка в схеме). Этот процесс продолжается до тех пор, пока первый элемент строки V не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ.

В нашем случае %%gcd(28,19) = 1%%, %%x = -2%%, %%y = 3%%. Выполним проверку: %%28 \cdot (—2) + 19 \cdot 3 = 1%%.

Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел %%c%%, %%m%% требуется находить такое число %%d < m%%, что $$cd \,mod \,m=1~~~(3)$$

Отметим, что такое d существует тогда и только тогда, когда числа с и m взаимно простые.

Определение. Число %%d%%, удовлетворяющее (3), называется инверсией %%c%% по модулю %%m%% и часто обозначается %%c^{-1} mod\, m%%.

Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (3) в виде %%сс^{-1} mod\, m = 1%%. Умножение на %%c^{-1}%% соответствует делению на %%c%% при вычислениях по модулю %%m%%. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю %%m%%:

$$c^{-e} = (c^e)^{-1} = (c^{-1})^e (mod\, m)$$

Пример. %%3\cdot4 mod 11 = 1%%, поэтому число 4 — это инверсия числа 3 по модулю 11. Можно записать %%3^{-1} mod 11 = 4%%. Число %%5^2\,mod 11%% может быть найдено двумя способами:

%%5^{-2} mod\, 11 = (5^2 mod\, 11)^{-1} mod \,11 = 3_1 mod\, 11 = 4, %%

%%5^{-2} mod\, 11 = (5^{-1} mod\, 11)^2 mod\, 11 = 92 mod\, 11 = 4. %%

При вычислениях по второму способу мы использовали равенство %%5^{-1} mod 11 = 9%%. Действительно, %%5 \cdot 9 \,mod\, 11 = 45,\ mod\,11 = 1%%.

Российский стандарт шифрования данных ГОСТ 28147-89Первая система с открытым ключом — система Диффи-Хеллмана