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.


 

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

82531. Память. Виды памяти 72.5 KB
  Виды памяти Память психический познавательный процесс направленный на запечатление сохранение воспроизведение и забывание той или иной информации. В структуре памяти можно выделить четыре относительно самостоятельных процесса: запоминание воспроизведение сохранение и забывание усвоенной ранее информации. Запоминание процесс памяти обеспечивающий удержание материала путём связывания новой информации с прошлым опытом. Запоминание Механическое зубрёжка Осмысленное логическое...
82532. Особенности памяти у детей с задержкой психического развития (ЗПР) 25.5 KB
  У детей с психофизическим инфантилизмом наблюдаются: уменьшение объема и скорости запоминания; неумение рационально организовать и контролировать свою работу; преобладание зрительной памяти над слуховой; У детей с ЗПР соматогенного генеза отмечается недоразвитие кратковременной памяти проявляющееся в снижении скорости запоминания в медленном нарастании продуктивности запоминания снижении объема памяти. У детей с ЗПР церебральноорганического генеза наблюдаются разнообразные нарушения памяти: повышенная тормозимость следов под...
82534. Особенности памяти у детей с нарушениями слуха 36 KB
  Образный материал глухие школьники непосредственно запоминают более успешнее чем слышащие так как у них зрительный опыт богаче. Но в то же время можно встретить в литературе данные что в дошкольном возрасте глухие хуже запоминают места расположения предметов в младшем школьном возрасте путают места расположения предметов сходных по изображению или реальному функциональному назначению. Глухие школьники младших классов применяют вспомогательные средства для запоминания. При запоминании ряда сходных предметов глухие плохо умеют...
82535. Особенности памяти у детей с нарушениями опорно-двигательного аппарата 33 KB
  При обследовании и лечении детей с ДЦП в возрасте от года до 15 лет выявлено что недостаточность ВПФ по типу психического недоразвития и ЗПР отмечена в среднем в 407 случаев. Анализ особенностей памяти у детей с диплегической формой ДЦП показал что ребята лучше запоминали смысловые структуры чем изолированные цифры и слова. При гиперкинетической форме ДЦП у детей выявлены трудности запоминания в слухоречевой модальности.
82536. Особенности памяти у детей с нарушениями интеллекта 28.5 KB
  Замский умственно отсталые дети усваивают новое очень медленно быстро забывают воспринятое не умеют вовремя воспользоваться приобретёнными знаниями и умениями на практике. Ослабление активного внутреннего торможения обусловливающее недостаточную концентрированность очагов возбуждения делает воспроизведение учебного материала многими умственно отсталыми детьми крайне неточным. Чаще всего физиологической основой забывчивости умственно отсталых детей является не угасание условных связей как при обычном забывании а временное внешнее...
82537. Особенности памяти у детей с нарушениями речи 40 KB
  Наиболее специфична следовательно значима для развития речи слуховая память. Без моторной памяти невозможно освоение экспрессивной речи устной и письменной. Зрительная память необходима для освоения письменной речи а также для связи между первой и второй сигнальной системами.
82538. Мышление, его виды и мыслительные операции 35 KB
  В зависимости от характера деятельности и ее конечных целей доминирует тот или иной вид мышления. Однако по степени своей сложности по требованиям которые они предъявляют к интеллектуальным и другим способностям человека все виды мышления не уступают друг другу. Виды мышления: Нагляднодейственное мышление представляет собой совокупность способов и процесс решения практических задач в условиях зрительного наблюдения за ситуацией и выполнения действий с представленными в ней предметами. Необходимые для мышления образы представлены в...