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

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

Абоненты А и В выбирают себе секретные ключи и соответственно такие, что НОД НОД

Затем абоненты А и В находят вторые секретные ключи и соответственно такие, что

Пересылаемые сообщения разбиваются на части, меньшие р – 1.

Предположим, абонент А решил отправить сообщение х абоненту В.

Для этого абонент А вычисляет и отправляет абоненту В сообщение

Абонент В вычисляет и отправляет абоненту А сообщение

Абонент А вычисляет и отправляет абоненту В сообщение

Абонент В вычисляет а это и есть переданное сообщение х.

Доказательство этого факта основано на теореме Ферма. Корректность работы такой криптосистемы аналогична работе криптосистемы с открытым ключом.