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.


 

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

26244. Бизнес туризм 23.5 KB
  Свыше 73 его объема составляют корпоративные поездки так называемый corporate travel как индивидуальные деловые поездки так и для участия в мероприятиях проводимых промышленными и торговыми корпорациями. Сюда же относятся и инсентивтуры поездки организуемые компаниями в целях мотивации сотрудников занятых в основном продвижением и продажей производимого этой компанией товара. Поездки связанные с участием в съездах конференциях семинарах под эгидой политических экономических научных культурных религиозных и других...
26245. Обоснование севооборотов и проектирование участков в АгроГИС 101.5 KB
  Ключевые слова: повторное и бессменное возделывание предшественники чистые и занятые пары поля производственные участки чередование культур болезни вредители сорняки зерновые пропашные. Обоснование севооборотов В севообороте выращивают различные по биологии и технологии возделывания сельскохозяйственные культуры озимые яровые многолетние травы пропашные и др. В основе чередования культур в севооборотах лежит принцип плодосмена что означает строгое чередование культур различающихся биологическими особенностями и технологиями...
26246. Применение сенсорной техники для дифференцированного внесения пестицидов 79 KB
  Сформировать умение применять методы дифференцированного внесения средств защиты растений в режимах offline и online с применением сенсорной техники. Использование гербицидов наиболее частое мероприятие по защите растений по сравнеию с использованием фунгицидов и инсектицидов. Для дифференцированного внесения средств защиты растений используют offline и online способы. Это делает возможным в любое время обращаться к этой информации чтобы получать заданные значения для защиты растений.
26247. Организация системы семеноводства 95.5 KB
  Контроль качества семян апробация посевов. Разработать технологии производства семян заданной культуры в системе внутрихозяйственного семеноводства. Система семеноводства сельскохозяйственных растений представляет собой совокупность функционально взаимосвязанных физических и юридических лиц осуществляющих деятельность по производству оригинальных элитных семян элиты и репродукционных семян. При этом развитая система семеноводства должна представлять собой высокоэффективный механизм не только обеспечивающий потребность в...
26248. Использование дистанционных методов и прецизионной техники для внесения удобрений 96 KB
  Лекция Использование дистанционных методов и прецизионной техники для внесения удобрений Цели и задачи. Сформировать умение разрабатывать электронные картограммы по обеспеченности элементами питания кислотности солонцеватости и картызадания для дифференциального внесения удобрений в режиме off line а также способность разрабатывать агротребования для выполнения операций в режиме on line. Рассматриваются различные режимы дифференцированного внесения удобрений и мелиорантов off line и on line программное обеспечение и использование...
26249. Техническое обеспечение агротехнологий 90 KB
  Рассматривается методика определения потребности агротехнологий в технике и оптимизации Машинотракторного парка на основе использования научно обоснованных нормативов. Ключевые слова: оптимизация МТП нормативы потребности эталонные единицы тракторооснащенность плуги бороны культиваторы лкщильники комбинированные агрегаты опрыскиватели. Одним из способов оптимизации состава МТП является методика основанная на использовании научно обоснованных нормативов потребности в технике. Нормативы потребности в базовых технических средствах в...
26250. Внесение удобрений 70.5 KB
  Домашнее задание Внесение удобрений Цель и задачи. Сформировать умение оперативно принимать решение по выбору оптимальных норм способов и сроков внесения удобрений в различных агротехнологиях в зависимости от изменяющихся агроэкологических и производственных условий. Рассматриваются нормы сроки и способы внесения удобрений в том числе микроудобрений в зависимости от агроэкологических и производственных условий. Сроки и способы внесения удобрений.
26251. Оценка устойчивости ландшафтов и агроландшафтов и их антропогенной преобразованности 71 KB
  13 Практическое задание Оценка устойчивости ландшафтов и агроландшафтов и их антропогенной преобразованности Цели и задачи. Сформировать представление об устойчивости природных ландшафтов и агроландшафтах видах экологической устойчивости определяющих ее факторах о цене экологической устойчивости агроландшафтов и принципах ее обеспечения. Затраты на ее поддержание определяют цену устойчивости агроландшафта. Дать характеристику экологической агрономической и экономической устойчивости определенного агроландшафта.
26252. Оценка экологической емкости агроландшафта 49 KB
  14 Домашнее задание Оценка экологической емкости агроландшафта Цели и задачи. Сформировать представление о способности агроландшафта воспринимать антропогенную нагрузку при сохранении экологической устойчивости и критериях ее оценки. Формируется понятие экологической емкости агроландшафта и определяющие ее условия. Дать оценку экологической емкости агроландшафта на примере конкретного земельного массива Оценка экологическая емкость агроландшафта Чтобы обеспечить экологическую устойчивость агроландшафта необходимо задать такие параметры...