Многие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел. Читатели, знакомые с теорией чисел, могут непосредственно перейти к следующему разделу.
Как мы уже указывали ранее, целое положительное число р называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.
Пример. Числа 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)=?%%
р(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%% — два целых положительных числа. Наибольший общий делитель чисел %%а%% и %%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 = О%% DO
%%r \leftarrow\,a\, mod\, b, a \, \leftarrow\, b, b \, \leftarrow \,r.%%
RETURN a.
Пример. Покажем, как с помощью алгоритма Евклида вычисляется %%gcd(28, 8)%%:
| a: | 28 | 8 | 4 |
| b: | 8 | 4 | 0 |
| r: | 4 | 0 |
Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока Ь не станет равным нулю. Тогда в значении переменной а содержится ответ (4).
Для многих криптографических систем, рассматриваемых в следующих разделах и главах, актуален так называемый обобщенный алгоритм Евклида, с которым связана следующая теорема.
Теорема. Пусть %%a%% и %%b%% — два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа %%х%% и %%у%%, такие, что $$ах + 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).
Результат содержится в строке U. Операция div в алгоритме — это целочисленное деление a div b = [а/b].
Пример. Пусть %%а=28%%, %%b=19%%. Найдем числа %%х%% и %%у%%, удовлетворяющие (2).
| U | 28 | 1 | 0 | |||||||
| V | U | 19 | 0 | 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%%, %%х = -2%%, %%у = 3%%. Выполним проверку: %%28 \cdot (—2) + 19 \cdot 3 = 1%%.
Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел с, m требуется находить такое число d < m, что $$cd \,mod \,m=1~~~(3)$$
Отметим, что такое d существует тогда и только тогда, когда числа с и m взаимно простые.
Определение. Число %%d%%, удовлетворяющее (3), называется инверсией %%с%% по модулю %%m%% и часто обозначается %%с^{-1} mod\, m%%.
Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (3) в виде %%сс^{-1} mod\, m = 1%%. Умножение на %%с^{-1}%% соответствует делению на с при вычислениях по модулю %%m%%. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю %%m%%: $$с^{-е} = (с^e)^{-1} = (с^{-1})^e (mod\, m)$$
Пример. %%3\cdot4 mod 11 = 1%%, поэтому число 4 — это инверсия числа 3 по модулю 11. Можно записать %%З^{-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 | Первая система с открытым ключом — система Диффи-Хеллмана |