ЛР3. ЛР3_МО4_МСЗИ_2021-22. Лабораторная работа 3 алгоритм rsa цель работы

• Название: Лабораторная работа 3 алгоритм rsa цель работы
• Дата: 23.12.2021
• Размер: 1.47 Mb.
• Имя файла: ЛР3_МО4_МСЗИ_2021-22.doc
• Тип: Лабораторная работа; #315293

2020-21 уч. год Методы и средства защиты информации МО 4курс

ЛАБОРАТОРНАЯ РАБОТА № 3
АЛГОРИТМ RSA

1. 
   Цель работы
   

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

1. 
   Краткие теоретические сведения
   

Это первый полноценный алгоритм с открытым ключом, который можно использовать для шифрования и цифровых подписей. Из всех предложенных алгоритмов с открытыми ключами RSA проще всего понять и реализовать. Он также является самым популярным. Названный в честь трех изобретателей - Рона Ривеста, А ли Шамира и Леонарда Эдлмана - этот алгоритм многие годы противостоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму.

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

Для генерации двух ключей используются два больших случайных простых числа, р и q. Для максимальной безопасности выбирайте р и q равной длины. Рассчитывается произведение: п = pq.

Затем случайным образом выбирается ключ шифрования е, такой что е и (p-l)(q-l) являются взаимно простыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифрования d, такого что

ed= 1 (mod(p— 1 )(q — 1)). (8)

Другими словами,

d = e^-1mc>d((p - l)(q - 1)) (9)

Заметим, что d и n также взаимно простые числа. Числа е и п - это открытый ключ, а число d - закрытый. Два простых числа р и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты.

Для шифрования сообщения m оно сначала разбивается на цифровые блоки, меньшие п (для двоичных данных выбирается самая большая степень числа 2, меньшая п). То есть, если р и q - 100 разрядные простые числа, то п будет содержать около 200 разрядов, и каждый блок сообщения m_i должен быть около 200 разрядов в длину. Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше п. Зашифрованное сообщение с будет состоять из блоков c_i- той же самой длины. Формула шифрования выглядит так:
_{ }

Для расшифровки сообщения возьмите каждый зашифрованный блок с_i, и вычислите:



Так как



все (mod п), то формула восстанавливает сообщение.

Таблица 4

Открытый ключ

n - произведение двух простых чисел р и q, которые должны храниться в секрете

е - число, взаимно простое с (р-1)(q-1)

Закрытый ключ

Шифрование

Дешифрование

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

Если р=47 и q=71, то n=pq=3337.

Ключ е не должен иметь общих множителей: (p-l)(q- 1)=46*70=3220.

Выберем (случайно) е равным 79. В этом случае d = 79^-1 mod 3220= 1019.

При вычислении этого числа использован расширенный алгоритм Эвклида. Опубликуем п и е, сохранив в секрете d. Отбросим р и q. Для шифрования сообщения: т=6882326879666683 сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков т_i: т₁=688, т₂=232, т₃=687, m₄ =966, m₅=668, т₆=003.

Первый блок шифруется как

688⁷⁹ mod 3337 = 1570 = c₁.Выполняя те же операции для последующих блоков, создает шифротекст сообщения: с=1570 2756 2091 2276 2423 158.

Для дешифрования нужно выполнить такое же возведение в степень, используя ключ дешифрования 1019: 1570¹⁰¹⁹ mod 3337 = 688 = т₁ . Аналогично восстанавливается оставшаяся часть сообщения.

2.1 Аппаратная реализация RSA

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

RSA никогда не достигнет скорости симметричных алгоритмов. Но шифрование RSA выполняется намного быстрее, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (2¹⁶ +1). Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений. Не существует никаких проблем безопасности, связанных с использованием в качестве е любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами), даже если одно и то же значение е используется целой группой пользователей.

Операции с закрытыми ключами можно ускорить при помощи китайской теоремы об остатках, если вы сохранили значения р и q, а также дополнительные значения: d mod(p-1), d mod (q-1) и q^-1 mod p.

Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам.

2.2 Безопасность RSA

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить и на множители, чтобы восстановить т по с и е. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел.

Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения п на множители.

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

Самым очевидным средством вскрытия является разложение на п множители. Любой противник сможет получить открытый ключ г и модуль п. Чтобы найти ключ дешифрования d, противник должен разложить п на множители. Но настоящие технологии разложения на множители не позволяют сделать это быстро и для больших чисел.

Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить п на множители.

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел р и q вероятностны, что произойдет, если р и q окажется составным? Однако можно свести вероятность такого события до нужного минимума. И даже если это произойдет, скорее всего, такое событие будет сразу же обнаружено - шифрование и дешифрование не будут работать. Существует ряд чисел, называемых числами Кармайкла, которые не могут обнаружить определенные вероятностные алгоритма поиска простых чисел. Они небезопасны, но чрезвычайно редки.

3. 
   Вскрытие с выбранным шифротекстом против RSA
   

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

3. 
   Вскрытие общего модуля RSA
   

При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль п, но каждому свои значения показателей степени е и d. Наиболее очевидная проблема в этом случае: если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт, даже без знания ключей дешифрования. Можно воспользоваться расширенным алгоритмом для вычисления, вероятностным методом для разложения п на множители и детерминированным алгоритмом вычисления какого-нибудь секретного ключа без разложения модуля на множители.

3. 
   Вскрытие малого показателя шифрования RSA
   

Шифрование и проверка подписи RSA выполняется быстрее, если для е используется небольшое значение, но это также может быть небезопасным. Если е(е+1)/2 линейно зависящих сообщений с различными открытыми ключами шифруются одним и тем же значением е, существует способ вскрыть такую систему. Если сообщений не так много, или если сообщения не связаны, то проблем нет. Если сообщения одинаковы, то достаточно е сообщений. Проще всего дополнять сообщения независимыми случайными числами.

Это также гарантирует, что

_{ } (12)

Так делается в большинстве практических реализаций RSA.

3. 
   Вскрытие малого показателя дешифрования RSA
   

Другое вскрытие, предложенное Майклом Винером, раскрывает d, где d не превышает четверти размера п, а е меньше п.

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

7. 
   Вскрытие шифрования и подписи с использованием RSA
   

Имеет смысл подписывать сообщение перед шифрованием, но на практике это мало кто делает. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания.

Хэш-функции не решают проблему. Однако она решается при использовании для каждого пользователя фиксированного показателя шифрования.

7. 
   Ограничения RSA
   

Джудит Мур на основании перечисленных вскрытий приводит следующие ограничения RSA:

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

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

3. Примеры

1 . Введем данные, которые необходимо зашифровать, и посмотрим, как данные поступают на шифратор, а потом на дешифратор (рис. 29-30).

Р ис.29. Входные данные

Рис.30. Процесс зашифровывания и расшифровывания
2 . Сгенерируем два простых числа p и q, вычислим основные параметры алгоритма, в том числе личный и открытый ключ и зашифруем сообщение с помощью открытого ключа (рис. 31-32).


Рис.31. Генерация главных чисел алгоритма p и q




Рис.32. Вычисление ключей и зашифровывание информации с помощью открытого ключа
3. Создадим документ и зашифруем его с помощью имеющегося ключа (рис. 33-35).



Рис.33. Создание документа с конфиденциальной информацией



Рис.34. Выбор ключа



Рис.35. Зашифрованная информация

4. Проведем анализ зашифрованного сообщения с помощью различных видов атак (рис.36-40).



Рис.36. Атака со знанием р (ввод открытого ключа и р)



Рис.37. Атака на стереотипные сообщения



Рис.38. Атака на секретные ключи небольших размеров



Рис.39. Анализируем параметры



Рис.40. Наглядность проведение атак и перехвата сообщений

5. Расшифруем зашифрованный документ с помощью имеющегося ключа (рис. 41-42).



Рис.41. Выбор ключа



Рис.42. Результат расшифровывания

4. Содержание работы

В ходе выполнения работы студенты должны выполнить следующие задания:

1. 
   Познакомиться с основными параметрами алгоритма и их вычислением, зашифровать с помощью данных параметров информацию в текстовом и числовом виде и расшифровать (Indiv.Procedures -RSA Cryptosystem - RSA Demonstration).
   

3. 
   Создать документ (File - New) с произвольной информацией и зашифровать его с помощью имеющегося ключа (Encrypt/Decrypt - Asymmetric (modem) - RSA Encryption), посмотреть, как выглядит зашифрованная информация в шестнадцатеричной системе счисления и в виде текста. Сохранить документ в зашифрованном виде, удалив при этом исходный.
   
4. 
   Провести анализ зашифрованного документа различными методами, посмотреть параметры анализа алгоритма, попробовать изменить параметры вводимые при анализе, сравнить результаты (Analysis - Asymmetric Encryption).
   
5. 
   Расшифровать сохраненный документ с помощью имеющегося ключа, попробовать ввести правильный и неправильный pin ((Encrypt/Decrypt - Asymmetric (modern) - RSA Decryption)). Сделать выводы о проделанной работе.
   

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

1. 
   На чем основана безопасность RSА?
   
2. 
   Назовите основные параметры алгоритма, как вычисляются ключи?
   
3. 
   Как происходит шифрование и дешифрование в данном алгоритме? На основе каких формул?
   
4. 
   Опишите основные методы вскрытия RSA?
   
5. 
   Какие необходимо принять меры, чтобы избежать раскрытия алгоритма?