Математические основы защиты информации. Ишмухаметов Ш.Т - 19 стр.

Глава 1. Системы шифрования с открытым ключом                                  20

образует группу по умножению, имеющую p − 1 элемент. Будем обозначать
это множество через Zp∗ . По теореме Лагранжа порядок любого элемента
a ∈ Zp∗ является делителем порядка p − 1, откуда ap−1 ≡ 1 ( mod p).
       Из теоремы Ферма сразу следует, что если для некоторого a < p
выполнено условие ap−1 ̸≡ 1 ( mod p), тогда число p является составным.
Однако обращение малой теоремы Ферма не верно – существуют составные
числа p, для которых выполняется условие Ферма для каждого a, не
сравнимого с p. Такие числа называются числами Кармайкла .


2.3. Функция Эйлера φ(n)
       Знаменитый математик Леонард Эйлер (1707–1783), проживший
в   России   большую      часть     своей    жизни   и      написавший   огромное
количество математических трудов в разных областях математики,
ввел в обиход функцию φ (Euler’ totient function), определенную на
целых положительных числах, значением которой на аргументе n является
количество положительных чисел, меньших n и взаимно-простых с n.
       Очевидно, что для всех n > 1 φ(n) < n, и для простого числа p
значение φ(n) равно p − 1. Также выполнены и другие формулы, полезные
для вычисления функции φ(n):

             φ(p) = p − 1 для всех простых p,
             φ(pk ) = pk − pk−1 для простых p и натуральных k ,              (2.2)
             φ(n1 · n2 ) = φ(n1 ) · φ(n2 )

2.4. Алгоритм RSA.
В этом параграфе рассмотрим алгоритм RSA. Его работы состоит из трех
частей:
       I. Генерация ключей.

    1. Выбираем два произвольных простых числа p и q .

    2. Вычисляем их произведение n = p · q и функцию Эйлера

                                 φ(n) = (p − 1) · (q − 1)