Методы и средства защиты информации


             

Алгоритм RSA


Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :

  • Выбираются два простых (!) числа p и q
  • Вычисляется их произведение n(=p*q)
  • Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).
  • Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y ? метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.
  • Два числа (e,n) ? публикуются как открытый ключ.
  • Число d хранится в строжайшем секрете ? это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

    Как же производится собственно шифрование с помощью этих чисел :

    1. Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.
    2. Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку.операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci

      прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.

    А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d.

    Содержание  Назад  Вперед