Идея ассиметричных алгоритмов основана на применении однонаправленных функций. Однонаправленную функцию можно определить f:X->Y где x и y некоторое произвольное множество. Функция является однонаправленной если для всех значений X принадлежащих X можно вычислить функцию где y принадлежит Y. Для большинства y=Y достаточно сложно получить x=X такое что f(x)=y. То есть эта функция отображает свои аргументы в некотором диапазоне таким образом что каждое значение функции имеет уникальное обратное значение при этом значение функции вычислить легко а найти по значению функции значение аргумента практически не возможно. Таким образом основным критерием отнесения функции к однонаправленным является отсутствие эффективных алгоритмов обратного преобразования Y в X.
В качестве примера рассмотрим целочисленное умножение.
При этом прямой задачей будет являться вычисление произведения двух больших чисел. П и Ку. Обратной задачей является разложение на множители большого целого числа. То есть определение из значение Н множителей П и Ку. Эта задача является практически не разрешимой при достаточно больших значениях Н. по современным оценкам теории чисел при значении Н 2664 для разложения на множители такого числа требуется примерно 1023 операции, что для современных вычислительных систем пока еще не реализуемо.
Следующим примером однонаправленной функции является модульная экспонента с фиксированным основанием и модулем.
Допустим что А и Н некоторые целые числа что А больше или равно 1 но меньше Н. Требуется определить множество такое …
Модульная экспонента
В настоящее время при построении криптосистем с открытым ключом используются однонаправленные функции с потайным ходом. Такая функция предполагает что она легко вычисляется в одном направлении и практически не вычислима при отсутствии дополнительной информации. При наличии такой информации время вычисления обратного значения является функцией длины этого значения.
Выбрать большое число Кс оно должно быть взаимно простым с результатом умножения. Определить такое число Ко для которого выполняется следующее соотношение КоКс(modFi(N))=1 . Затем чтобы зашифровать данное с помощью открытого ключа Ко необходимо разбить шифруемый текс на блоки каждый из которых может быть представлен в виде числа M(i=1..N-1), Mi – блок открытого текста. Текст будет выглядеть как последовательность зашифрованных чисел Mi.
Пример! Шифруем 651
П=3 ку=11
Н=3*11
Функция элера = 20
Кс = 3
Ко = в качестве такого числа может быть взято любое число для которого справедливо соотношение Ко * 3 мод 20 = 1
Ко=7
М1=6 М2=5 М3=1
С1=279936 мод 33=30
С2=14
С3=1
30 14 1
тким образом криптостойкость алгоритма РСА основывается на предположении исключительной трудоемкости определения секретного ключа по открытому. Так как для этого необходимо решить задачу существования делителей целого числа. В качестве кого чаще всего выбирают 3 17.
При аппаратной реализации аппарат РСА имеет в 100 раз медленнее чем Des.