RSA (Rivest, Shemir, Adleman).

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

Суть: пользователь выбирает два простых больших числа P и Q равных разрядов и перемножая их получает N=P*Q. Число N опубликовывается, P и Q держатся в тайне.

Ф(N)= (P-1)*(Q-1). Число целых чисел меньших N и взаимно простых по отношению к N.

Затем случайным образом выбирается число Е, из диапазона 2…Ф(N), взаимно простое с числом Ф(N), оно также публикуется.

ОК пользователя является пара чисел N и E. В качестве ЛК D выбирается выберается число удовлетворяющее требованию EDmodФ(N)=1. Если Е=7, то D=3.

Шифрование осуществляется по формуле:

C-шифрованный текст, S- открытый текст.

Расшифровка производится, используя ЛК получателя:

DE равно сумме некоторого число f(N) и 1.

Пример: CAB шифруем сообщение с помощью открытого ключа E,N = 7,33

ЛК 3,33 || || ||

Контроль целостности, хэш-функции, российский стандарт хэш-функции.

Наиболее простым способом КЦ данных является выявление контрольной суммы (остаток от деления суммы всех чисел входных данных на максимально возможное значение контрольных сумм).

Недостаток: хотя несовпадение, полученной контрольной суммы с вновь вычисленной является подтверждением потери целостности, Их совпадение не дает уверенности в их неизменности.

Более совершенный способ: использование циклически избыточных кодов или метод CRC. Он широко используется в сетевых адаптерах. Он основан на полиномиальном распределении, где каждый разряд некоторой порции данных соответствует коэффициенту полинома, например:

Операция умножения и деления полинома выполняется как с обычными числами.

Если полином, соответствующий входным данным, разделить на фиксированный полином, то получаем полином-частное и полином-остаток (он является контрольной суммой).

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

Поэтому на практике для контроля используется хэш-функция.

Хэш-функция делится на 2 класса: с ключом и без ключа. Значение хэш-функции с ключом может вычислить лишь тот ,кто знает ключ.

MessageAutentificationCode (MAC)

Хэш-функция с ключомH(k,x), где k-ключ, x- сообщение, называется функция со свойствами:

1) Описание функций открыто, секретным является лишь ключ.

2) Аргумент X – строка произвольной длины. Значении функции имеет фиксированную длину.

3) Значение функции легко вычисляется для любого вргумента.

4) Вычислительно невозможно восстановить по значению функции значение аргумента.

5) Должно быть трудно определить значение ключа по большому числу известных пар H(k,xi), а также невозможно вычислить хэш-функцию для иного значения аргумента.

Пример хэш-функции с ключом – имитовставка.

Хэш-функция без ключаMDC делится на 2 класса: слабые и сильные.

Слабая – хэш-функция H(x), где x – исходный текст, который удовлетворяет след.свойствам:

1) Описание функции открыто

2) Аргумент х-строка произвольной длины. Значение функции имеет фиксированную длину.

3) Значение функции легко вычисляемо для любого значения аргумента.

4) Восстановить значение аргумента по значению функции почти невозможно, т.е. функция H является односторонней.

5) Для любого фиксир. значения аргумента невозможно найти др. значение аргумента с тем же значением хэш-функции.

Сильная – первые 4 свойства те же самые, а вот 5-ое отличается:

5)невозможно найти любые 2 сообщения с одинаковым значением хэш-функции.

В России действует стандарт хэш-функции ГОСТ 34.11-94, который преобразует любую последовательность в хэш-функцию длиной 256 бит. Она зависит от сообщения и таблиц замен ГОСТ 28147-89, который используется в процессе хэширования.

Данный стандарт описывает хэш-функции с ключом. Если вы зафиксируете и опубликуете значение узлов замены, у вас получится хэш-функция без ключа.