Главная | Обратная связь

Криптосистема шифрования данных RSA

Предложена в 1978 году авторами Rivest, Shamir и Aldeman и основана на трудности разложения больших целых чисел на простые сомножители.

Последовательность действий пользователя:

1. Получатель выбирает 2 больших простых целых числа p и q, на основе которых вычисляет N=pq; M=(p-1)(q-1).

2. Получатель выбирает целое случайное число d, которое является взаимопростым со значением М, и вычисляет значение е из условия ed=1(mod M).

3. d и N публикуются как открытый ключ, е и М являются закрытым ключом.

4. Если S –сообщение и его длина: 1<Len(S)<N, то зашифровать этот текст можно как S’=S^d(mod N), то есть шифруется открытым ключом.

Получатель расшифровывает с помощью закрытого ключа: S=S’^e(mod N).

Шифрование с использованием алгоритма RSA

Задача, положенная в основу метода состоит в том, чтобы найти такую функцию y=f(x), чтобы получение обратной функции x=f^-1(y) , было бы в общем случае очень сложной задачей (NP-полной задачей), однако, если знать некую секретную информацию, то сделать это существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом. Например, получить произведение двух чисел n=p*q просто, а разложить n на множители, если p и q достаточно большие простые числа, сложно.

1. Первым шагом в использовании алгоритма RSA является генерация ключей. Для этого нужно:

2. Выбрать два очень больших простых числа p и q.

3. Вычислить произведение n= p*q.

4. Выбрать большое случайное число d, не имеющее общих сомножителей с числом (p-1)*(q-1).

5. Определить число e, чтобы выполнялось (e*d) mod ((p-1)*(q-1))=1.

Тогда открытым ключом будут числа e и n, а секретным ключом - числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

· Разбить шифруемый текст на блоки, где i-й блок может быть представлен в виде числа m(i)=0,1,2..., n-1. Их должно быть не более n-1.

· Зашифровать текст, рассматриваемый как последовательность чисел m(i) по формуле c(i)=(m(i)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо вычислить: m(i) = (c(i)^d) mod n. В результате будет получено множество чисел m(i), которые представляют собой часть исходного текста.

Например, зашифруем и расшифруем сообщение AБВ, которое представим, как последовательность чисел 123 (в диапазоне 0-32)

· Выбираем p=5 и q=11 (числа на самом деле должны быть большими).

· Находим n=5*11=55

· Определяем (p-1)*(q-1) = 40. Тогда d будет равно, например 7.

· Выберем e, исходя из (e*7) mod 40=1. Например, e=3.

Теперь зашифруем сообщение, используя открытый ключ {3,55}

· C₁ = (1³)mod 55 = 1

· C₂ = (2³)mod 55 = 8

· C₃ = (3³)mod 55 = 27

Теперь расшифруем эти данные, используя закрытый ключ {7,55}.

· M₁ = (1⁷)mod 55 = 1

· M₂ = (8⁷)mod 55 = 2097152mod 55 = 2

· M₃ = (27⁷)mod 55 = 10460353203 mod 55 = 3

Таким образом, все, данные расшифрованы.

Итак, мы выяснили, что современная криптография включает в себя следующие крупные разделы:

· Симметричные криптосистемы.

· Криптосистемы с открытым ключом.

· Системы электронной подписи.

· Управление ключами,

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

Вопросы для самопроверки

1. Цель и задачи криптографии.

2. Шифры одиночной перестановки и перестановки по ключевому слову. Шифр Гронфельда.

3. Шифры двойной перестановки. Шифрование с помощью магического квадрата.

4. Шифр многоалфавитной замены и алгоритм его реализации.

5. Алгоритм шифрации двойным квадратом. Шифр Enigma.

6. Алгоритм шифрования DES.

7. Алгоритм шифрования ГОСТ 28147-89.

8. Алгоритм шифрования RSA.

9. Алгоритм шифрования Эль Гамаля.

10. Задачи и алгоритмы электронной подписи.

11. Задачи распределения ключей.