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



              

Алгоритм RSA


Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = me(mod n).

При этом n = pq, где p и q — случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < ?(n), с условием: НОД(e, j(n)) = 1, где j(n) — наименьшее общее кратное чисел p–1 и q–1.

Далее, решая в целых числах x, y уравнение xe + y?(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение med

= m(n), поэтому знание d позволяет расшифровывать криптограммы.

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

1.     Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.

2.     Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.

Рассмотрим построение криптосистемы RSA на простом примере.

1.     Выберем p = 3 и q = 11.

2.     Определим n = 3 • 11 = 33.

3.     Найдем j(n) = (p – 1)(q – 1) = 20.

4.     Выберем e, взаимно простое с 20, например, e = 7.

5.     Выберем число d, удовлетворяющее 7d = 1(mоd 20).

Легко увидеть, что d = 3(mоd 20).

Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С = 3, ..., Z = 26. Поскольку size(n) = 6,

то наша криптосистема в состоянии зашифровывать буквы латинского алфавита, рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предложим прочим участникам системы секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес. Пусть таким сообщением будет CAB, которое в выбранном нами кодировке принимает вид (3, 1, 2). Отправитель должен зашифровать каждый блок и отправить зашифрованное сообщение в наш адрес:




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