Підходить для надійного ЗАХИСТУ ІНФОРМАЦІЇ. Найпростішім прикладом є шифр заміні, что відповідає відображенню
: х - > х + k (mоd m),
де k - Деяк фіксоване ціле.
У 1978 р. Американці Р.Рівест, А. Шамір и Л. Адлеман (RL Rivest, A. Shamir, L. Adelman) запропонувалі функцію f з Наступний властівостямі:
а) існує й достатньо швидкий алгоритм обчислення значень f (х);
б) існує й достатньо швидкий алгоритм обчислення значень оберненої Функції f -1 (х);
в) функція f (х) містіть Певного В«секретВ», знання Якого дозволяє й достатньо Швидко обчісліті Значення f -1 (х); інакше обчислення f -1 (х) перетворюється на й достатньо складаний завдання, яка вімагає стількі годині для розв язання, что по его закінченню зашифрована інформація втрачає свою Цінність.
На Основі цієї Функції булу Створена діюча система шифрування, названа за дерло літерами імен своих творців - RSA. Функція f Діє на Деяк ПОВІДОМЛЕННЯ х за таким правилом:
: х - > х е (mоd m), е, m ГЋN (3.1.1)
тоді дешіфрування ПОВІДОМЛЕННЯ а = f (х) зводіться до розв язання конгруенції
х е Вє а (mоd m). (3.1.2)
Если Показник степеня в (3.1.2) є взаємно пробачимо з j (m), тоб
НСД (е, j (m)) = 1, (3.1.3)
то (3.1.2) має єдиний розв язок. Тут j (m) - функція Ейлера, кількість натуральних чисел від 1 до (m-1), взаємно простих з m. Зазначімо деякі Властивості j (m), відомі з курсу Теорії чисел, Які будемо застосовуваті далі:
j (1) = 1, (3.1.4)
j (р) = р-1, де р - просте, (3.1.5)
j (аb) =
