2.1. Криптосистема без передачи ключей.

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

Сущность алгоритма Евклида состоит в отыскании нод(a,b) и заключается в следующем. Пусть и положительные целые числа и . Тогда для указанных значений будут справедливы соотношения:

(2.1)

Алгоритм заканчивается при получении некоторого остатка Наибольшим общим делителем тогда будет последний не равный нулю остаток .

Алгоритм Евклида можно представить также в виде следующих арифметических действий:

В теории существует математическая связь данного алгоритма и представления частного от деления двух чисел в виде полиномиальных дробей:

(2.3)

Из данных равенств следует:

(2.4)

Пример: пусть тогда в соответствии с алгоритмом Евклида значения q будут равны , а таблица 2.1 примет вид:

Тогда:

(2.5)

Дальнейшее математическое обоснование криптосистемы без передачи ключей базируется на решении сравнений первой степени с одним неизвестным.

Для определения понятия «сравнение» будем рассматривать некоторые целые числа, представляющие собой остатки от деления на другое, заданное на-

туральное число , которое назовем модулем.

Сравнимость чисел и по модулю записывается в виде:

(2.6)

и читается: « сравнимо с по модулю ».

Сравнения обладают рядом свойств, характерных для обыкновенных равенств:

а) если два числа сравнимы с третьим, то все три числа сравнимы между собой по заданному модулю;

б) сравнения можно почленно складывать:

(2.7)

тогда:

(2.8)

в) слагаемое, стоящее в какой либо части сравнения, можно переносить в другую часть, переменив знак на противоположный:

(2.9)

Например:

г) к каждой части сравнения можно прибавить любое число, кратное модулю:

; (2.10)

д) сравнения можно почленно перемножать:

(2.11)

е) следствие из (2.11):

(2.12)

ж) если выражения для многочленов А и В сравнимы по модулю , то есть:

(2.13)

то сравнимы и сами многочлены А и В по модулю :

(2.14)

Данное свойство является обобщением предыдущих свойств сложения и умножения;

з) обе части сравнения и модуль можно умножить на одно и тоже число:

(2.15)

Рассмотрим, теперь, две теоремы, являющиеся базой для криптографического метода с закрытой системой ключей.

Теорема Эйлера: пусть числа и взаимно простые, то есть , тогда будет справедливо равенство:

(2.16)

где - это функция Эйлера, которая показывает число чисел взаимно простых с .

Например: , так как в ряду 0,1,2,3,4,5 только два числа 1 и 5 не имеют сомножителей принадлежащих числу 6. Соответственно:

(2.17)

Теорема Ферма: если -простое число, а число не делится на , то есть , то имеет место сравнение вида:

(2.18)

где . Например:

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

Пусть требуется решить сравнение первой степени с одним неизвестным:

. (2.19)