28567

Система открытого шифрования RSA, атаки на RSA

Доклад

Информатика, кибернетика и программирование

В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA названный так по начальным буквам фамилий ее изобретателей Rivest Shamir и Adleman и представляющую собой криптосистему стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Чтобы использовать алгоритм RSA надо сначала сгенерировать открытый и секретный ключи выполнив следующие шаги: выберем два очень больших простых числа p и q; определим n как результат умножения p на q n = p Ч...

Русский

2013-08-20

15.87 KB

12 чел.

  1.  Система открытого шифрования RSA, атаки на RSA.

В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий ее изобретателей (Rivest, Shamir и Adleman) и представляющую собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители..

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

Под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги:

  1.  выберем два очень больших простых числа p и q;
  2.  определим n как результат умножения p на q (n = p Ч q);
  3.  выберем большое случайное число, которое назовем d (оно должно быть взаимно простым с m результатом умножения (р – 1) × (q – 1));
  4.  определим такое число e, для которого является истинным следующее соотношение: (e Ч d) mod (m) =1 или e = (1 mod (m))/d.

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

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

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

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

Криптостойкость алгоритма RSA основывается на проблеме факторизации больших простых чисел. Действительно, если злоумышленнику удастся разложить число n на простые множители p и q, то для него не составит труда вычислить (n), а затем и определить секретный ключ пользователя. Однако   нахождение секретного ключа RSA не эквивалентно проблеме факторизации. Это означает, что T(RSA)<=T(факторизации), где T(RSA) – трудоемкость определения секретного ключа RSA, а T(факторизации) – трудоемкость факторизации числа n. То есть, могут быть найдены эффективные алгоритмы определения секретного ключа алгоритма RSA, причем проблема факторизации при этом не будет разрешена.

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

Схема шифрования RSA несостоятельна при использовании абонентами общих модулей n. Допустим, что имеются 2 абонета A и В с открытыми ключами (e1,n) и (e2,n). Центр (например, общий сервер) желает послать обоим абонетам одно и то же сообщение m. Он получает me1=c1(mod n) и me2=c2(mod n) и посылает c1 и c2 абонентам А и В соответственно. Положим, что противник перехватывает эти сообщения. Затем, если (e1,e2)=1, то с помощью расширенного алгоритма Евклида можно найти такие k1 и k2, для которых e1k1+e2k2=1. И, соответственно, me1k1me2k2=m. Найдя такие k1 и k2 (это можно сделать, ведь открытые ключи противнику известны), противник вычислит собщение: (c1)k1(c2)k2 = m.


 

А также другие работы, которые могут Вас заинтересовать

16312. Определение деформации при косом изгибе 5.06 MB
  ОПРЕДЕЛЕНИЕ ПРОГИБОВ ПРИ КОСОМ ИЗГИБЕ Цель работы Ознакомление с косым изгибом консольного бруса и сравнение опытных значений прогиба с теоретическим. Содержание работы Если плоскость действия изгибающего момента возникающего в поперечном сечении бруса не сов...
16313. Определение модуля сдвига при кручении 97 KB
  ОПРЕДЕЛЕНИЕ МОДУЛЯ СДВИГА ПРИ КРУЧЕНИИ Цель работы Экспериментальная проверка закона Гука при сдвиге и определение модуля сдвига материала вала.
16314. Определение прогибов балки на двух опрах 95 KB
  ОПРЕДЕЛЕНИЕ ПРОГИБОВ БАЛКИ НА ДВУХ ОПОРАХ Цель работы Приобретение практических навыков по измерению прогибов балки. Содержание работы. Балка это стержень нагруженный силами действующими в направлении перпендикулярном его оси. В инженерной практике часто воз
16315. ИЗУЧЕНИЕ ЗАКОНОВ ГЕОМЕТРИЧЕСКОЙ ОПТИКИ 321.5 KB
  ИЗУЧЕНИЕ ЗАКОНОВ ГЕОМЕТРИЧЕСКОЙ ОПТИКИ Теоретические основы эксперимента Геометрическая лучевая оптика Согласно электромагнитной теории диапазон видимого света представляет собой электромагнитные волны определенной длины : от 40105 см до 7...
16316. ОПРЕДЕЛЕНИЕ НЕИЗВЕСТНОЙ КОНЦЕНТРАЦИИ ОКРАШЕННОГО РАСТВОРА ПРИ ПОМОЩИ КОЛОРИМЕТРА КФО 290.5 KB
  Лабораторная работа ОПРЕДЕЛЕНИЕ НЕИЗВЕСТНОЙ КОНЦЕНТРАЦИИ ОКРАШЕННОГО РАСТВОРА ПРИ ПОМОЩИ КОЛОРИМЕТРА КФО Теоретические основы эксперимента Физика взаимодействия света с веществом Взаимодействие света и среды в общих чертах можно представить следующим
16317. ИССЛЕДОВАНИЕ СОСТОЯНИЯ ПОЛЯРИЗАЦИИ ЛАЗЕРНОГО ИЗЛУЧЕНИЯ 66.5 KB
  Лабораторная работа ИССЛЕДОВАНИЕ СОСТОЯНИЯ ПОЛЯРИЗАЦИИ ЛАЗЕРНОГО ИЗЛУЧЕНИЯ Практическая часть Упражнение №1. Изучение состояния поляризации лазерного излучения Оптическая схема лаб
16318. ИЗУЧЕНИЕ ЗАКОНОВ ФОТОМЕТРИИ 194 KB
  ИЗУЧЕНИЕ ЗАКОНОВ ФОТОМЕТРИИ Теоретическая часть Разнообразные действия света обусловлены наличием определенной энергии излучения световой энергии. Непосредственное восприятие света обусловлено действием световой энергии на любой приемник способный реагиро...
16319. Дифракция Фраунгофера 231.5 KB
  Лабораторная работа № 7 Дифракция Фраунгофера Теоретические основы эксперимента Многие явления наблюдаемые в обыденной жизни говорят о том что свет распространяется прямолинейно. Солнечный свет луч прожектора луч лазера ассоциируются в нашем сознании с п...
16320. Дифракция Френеля 292 KB
  Лабораторная работа № 8 Дифракция Френеля Теоретические основы эксперимента Многие явления наблюдаемые в обыденной жизни говорят о том что свет распространяется прямолинейно. Солнечный свет луч прожектора луч лазера ассоциируются в нашем сознании с прямы...