top of page
                                    Лабораторная работа №5
                           Тема: Изучение криптосистемы RSA
Цель Работы: закрепление теоретических знаний и практическое освоение алгоритмов ассиметричного шифрования.

Теоретические сведения

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

Пусть Защита данных с помощью криптографического преобразования является эффективным решением проблемы их безопасности. Зашифрованные данные доступны лишь тем, кто знает, как их расшифровать, то есть тем, кто обладает соответствующим ключом шифрования.

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

Функционирование криптосистемы на основе метода RSA предполагает формирование открытого и секретного ключей. С этой целью необходимо выполнить следующие математические операции:

  • выбираем два больших простых числа р и q, понимая под простыми числами такие числа, которые делятся на само себя и число 1;

  • определяем n = p × q;

  • вычисляем число k = (p – 1) (q – 1);

  • выбираем большое случайное число d, взаимно простое с числом k

(взаимно простое число – это число, которое не имеет ни одного общего делителя, кроме числа 1);

  • определяем число е, для которого истинным является соотношение

(e × d) mod k = l;

  • принимаем в качестве открытого ключа пару чисел {е, n};

  • формирование секретного ключа в виде пары чисел {d, n}.

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

  • разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде чисел M(i)=0,1,…, n –1;

  • зашифровать текст в виде последовательности чисел M(i) по формуле:  C(i) = (M(i)e) mod n;

  • расшифрование шифротекста производится с помощью секретного ключа {d, n} при выполнении следующих вычислений:         M(i) = (C(i)d) mod n.

В результате получаем последовательность чисел M(i), представляющих исходные данные. На практике при использовании метода RSA длина р и q составляет 100 и более десятичных знаков, что обеспечивает высокую криптостойкость шифротекста.

Подготовка текста к шифрованию

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

Пример 2. Для простоты предположим, что текст сообщения содержит слова, записанные только заглавными буквами. Первый шаг состоит в замене каждой буквы сообщения числом. Пусть наша таблица замен имеет вид:

                                                Пробел между словами будем заменять числом 99.

Например, пусть открытый текст – это девиз «ПОЗНАЙ СЕБЯ». Тогда его цифровое представление имеет вид: 2524172310199927151141.

Пусть в нашем примере p = 149, q = 157, тогда N = 23393. Поэтому цифро-вое представление открытого текста нужно разбить на блоки , меньшие, чем 23393. Одно из таких разбиений выглядит следующим образом:

                                                            2524 – 1723 – 10199 – 9271 – 511 – 41.

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

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

Обратим внимание на то, что в этом примере каждую букву кодируем двузначным числом. Это сделано для предотвращения неоднозначности. Если бы мы пронумеровали буквы не по порядку, начиная с 1, т. е. А соответствует 1, Б соответствует 2 и т. д., то было бы непонятно, что обозначает блок 12: пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для кодирования можно использовать любые однозначные соответствия между буквами и числами, например ASCII-кодировку, что чаще всего это и делается.

Продолжим пример: выбираем p = 149, q = 157, вычисляем ϕ(N ) = 23 088 . Теперь нужно выбрать число e, взаимно простое с ϕ(N). Наименьшее простое, не делящее ϕ(N ) , равно 5. Положим e = 5. Зашифруем первый блок сообщения: 

вычисляем 25245 mod 23393 = 22752; далее 17235 mod 23393 = 6198. 101995 mod 23393 = 14204,

92715 mod 23393 = 23191,

5115 mod 23393 = 10723,

415 mod 23393 = 14065.

Теперь шифрованный текст имеет вид

22752619814204231911072314065

 

В нашем примере N = 23393, e = 5. Применив алгоритм Эвклида к числам ϕ(N ) = 23088 и e = 5, найдем d = e−1 mod 23088 =13853. Значит для расшифровки блоков шифртекста мы должны возвести этот блок в степень 13583 по модулю 23393. В примере первый блок шифртекста – число 22752, тогда полу-чим 2275213853 mod 23393 = 2524.

Разбиение числа на блоки можно произвести различными способами. При этом промежуточные результаты зависят от способа разбиения, однако конечный результат – не зависит.

Схема алгоритма шифрования данных RSA

  1. Выбирают два случайных простых числа (p и q) и вычисляют модуль:       n = pq

  2. Вычисляется функция Эйлера: φ(n)=(p-1)(q-1);

  3. Случайным образом выбирается секретный ключ е, при этом должно выполняться условие взаимной простоты чисел е и φ(n).

  4. Вычисляют ключ дешифрования по формуле: ed =ed = 1 mod φ(n)                                                                          заметим, что d и n также должны быть взаимно простыми числами.

  5. Для шифрования необходимо разбить сообщение на блоки одинаковой длинны. Число двоичных разрядов в блоке должно соответствовать числу разрядов модуля n.

  6. Шифрование блока сообщения осуществляется по формуле: Ci=Mie mod n

  7. Дешифрование каждого блока ci осуществляется по формуле: Mi= Cid mod n

Выбор d в качестве открытого ключа, а e в качестве секретного совершенно условный. Оба ключа совершенно равноправны. В качестве открытого ключа можно взять е, а в качестве закрытого – d.

Пример шифрования:

  1. Выбираем р = 7, q = 13, модуль n = pq = 7·13 = 91;

  2. Вычисляем функцию Эйлера φ(n) = (p-1)(q-1) = (7-1)(13-1) = 72;

  3. С учетом условий НОД(e, φ(n)) = 1 и 1 < e ≤ φ(n), выбираем секретный ключ e = 5;

  4. Исходя из условия ed = 1 mod φ(n), вычисляем парный секретный ключ 5·d = 1 mod 72, используя расширенный алгоритм Евклида, находим  открытый ключ d = 29;

  5. Берем открытое сообшение m = 225367 и разбиваем его на блоки одинаковой длинны m1 = 22, m2 = 53, m3 = 67.

  6. Шифруем:                                                                                                     

 С1 = 225 mod 91 = 29,                                                                                   

C2 = 535 mod 91 = 79,                                                                                  

 C3 = 675 mod 91 = 58;

  1. Расшифровываем:                                                                                       

M1 = 2929 mod 91 = 22,                                                                                

M2 = 7929 mod 91 = 53,                                                                                

M3 = 5829 mod 91 = 67;

Задания:

  1. Используя заданные в соответствии с вариантом значения p, q и закрытого ключа Kс вычислить открытый ключ Ko при помощи расширенного алгоритма Евклида и выполнить шифрование по алгоритму RSA открытым ключом (Ko) своей фамилии. Для представления букв в числовой форме использовать следующее соответствие: ‘A’ – 2, ‘Б’ – 3, ‘В’ – 4, ..., ‘Ё’ – 8, ..., ‘Я’ –

  2. Выполнить проверку правильности расшифрования полученных зашифрованных данных при помощи закрытого ключа Kс.

Варианты заданий

  1. p=5, q=7, Kс=11.

  2. p=17, q=5, Kс=7.

  3. p=11, q=5, Kс=13.

  4. p=7, q=11, Kс=19.

  5. p=7, q=17, Kс=5.

  6. p=3, q=17, Kс=23.

  7. p=13, q=3, Kс=11.

  8. p=5, q=13, Kс=19.

  9. p=7, q=13, Kс=17.

  10. p=3, q=19, Kс=7.

  11. p=5, q=7, Kс=23.

  12. p=17, q=5, Kс=19.

  13. p=11, q=5, Kс=17.

  14. p=7, q=11, Kс=13.

  15. p=7, q=17, Kс=11.

16. p=3, q=17, Kс=13.

17. p=13, q=3, Kс=17.

18. p=5, q=13, Kс=11.

19. p=7, q=13, Kс=19.

20. p=3, q=19, Kс=13.

21. p=5, q=7, Kс=19.

22. p=17, q=5, Kс=23.

23. p=11, q=5, Kс=19.

24. p=7, q=11, Kс=17.

25. p=7, q=17, Kс=23.

26. p=3, q=17, Kс=11.

27. p=13, q=3, Kс=19.

28. p=5, q=13, Kс=17.

29. p=7, q=13, Kс=23.

30. p=3, q=19, Kс=11

Контрольные вопросы:

  1. На какой базе обычно создаются криптографические системы с открытыми ключами?

  2. Перечислить число параметров в криптографической системе RSA.

  3. Перечислить секретные параметры системы RSA.

  4. Перечислить открытые параметры системы RSA.

  5. На каком математическом результате базируется система RSA.

  6.  Какими свойствами должны удовлетворять параметры p и q системы RSA.

  7. Какими свойствами должны удовлетворять параметры e и  d системы RSA.

bottom of page