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.


 

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

27804. Принципы организации и функции детского досуга 65.5 KB
  Досуг детей подростков и юношества развивается по своим законам принципам теоретически обоснованным и апробированным на практике.Принцип всеобщности и доступности возможность приобщения вовлеченности всех детей подростков и юношества в сферу деятельности досуговых учреждений с целью удовлетворения творческих потенций подрастающего поколения их досуговых запросов и интересов. Принцип самодеятельности основывается на творческой активности увлеченности и инициативе детей подростков и юношества с одной стороны и их поощрении...
27805. Ресоциализация 32.5 KB
  в собственных глазах подростка должна быть развенчана вся атрибутика той уличной субкультуры которая до сих пор для него имела исключительную значимость. В это время становится очевидной инерционность прежних социальных установок подростка оценок его поведения общественного мнения в школе в кругу друзей. Коррекция имеет следующие функции: восстановительную предполагающую восстановление тех положительных качеств которые преобладали у подростка до появления трудновоспитуемости обращение к памяти подростка о его добрых делах; ...
27806. Социально - психологический портрет современного подростка 32.5 KB
  Подростковый возраст как наиболее сложный этап в развитии ребенка Подростковый возраст период жизни человека от детства к юности в традиционной классификации от 1112 до 1415 лет. [11] Подростковый возраст протекает очень бурно самый затяжной и самый острый. Можно говорить о трех кризисах которые сливаются воедино и переживаются подростками а значит о трех группах причин которые делают возраст труднее. Возрастает контроль над инстинктом эмоциями.
27808. ЭТИЧЕСКИЕ НОРМЫ ПОВЕДЕНИЯ ПСИХОЛОГОВ-КОНСУЛЬТАНТОВ В ОБЛАСТИ ИНДИВИДУАЛЬНОГО И СЕМЕЙНОГО ПСИХОЛОГИЧЕСКОГО КОНСУЛЬТИРОВАНИЯ 26.49 KB
  Этические нормы устанавливают обязательные правила профессиональной психологической деятельности психологаконсультанта. ЭТИЧЕСКИЕ НОРМЫ Общие нормы Границы компетентности Психологиконсультанты занимаются профессиональной деятельностью только в границах своей компетентности которая определяется образованием формами повышения квалификации и соответствующим профессиональным опытом. Психологиконсультанты осуществляют профессиональную деятельность в новых областях или используют новые методики только после их соответствующего изучения...
27809. Усыновление 44.08 KB
  Рассмотрение дел об установления усыновления ребенка производится судом в порядке особого производства по правилам предусмотренным гражданским процессуальным законодательством. Права и обязанности усыновители и усыновленного ребенка статья 137 настоящего Кодекса возникают со дня вступления в законную силу решения суда об установлении усыновления ребенка. Суд обязан в течение трех дней со дня вступления в законную силу решения суда об установлении усыновления ребенка направить выписку из этого решения суда в орган записи актов...
27810. СОЦИАЛЬНЫЙ ПЕДАГОГ СЕМЕЙНОГО ТИПА 22.49 KB
  В задачи семейного социального педагога входит постановка диагноза: каковы условия жизни семьи возможности для воспитания какую помощь необходимо оказать. В работе с детьми внимание педагога направлено на повышение уровня их развития с тем чтобы выровнять возможности для социального старта восполнить ущерб нанесенный формированию личности семейными обстоятельствами. Формы работы семейного социального педагога разнообразны: непосредственное участие в воспитании детей уходе за ними больными членами семьи. Разнообразно...
27811. Основными направлениями деятельности социального педагога 19.57 KB
  Основными направлениями деятельности социального педагога работающего в школеинтернате являются: определение правового статуса ребенка поступившего в учреждение получение сведений о ребенке дата рождения место нахождение родителей и родственников состояния жилищнобытовых условиях проживания ребенка состояние здоровья оформление детей в школуинтернат обеспечение конституционных прав и законных интересов.В государственные детские учреждения образования детские дома дома ребенка школыинтернаты всех типов могут...
27812. ПРОГРАММА РАБОТЫ С ДЕТЬМИ « ГРУППЫ РИСКА» 26.41 KB
  Известно что каждый человек стремиться реализовать свой потенциал постоянно совершенствоваться найти свое место в жизни. В настоящее время наблюдаются положительные тенденции в экономической жизни региона в оздоровлении общества. Еще недавняя нестабильность экономики бытовые неурядицы недостаточный уровень семейного воспитания а порой и полное его отсутствие нездоровый образ жизни в социуме привели к таким явлениям как обнищание отдельных семей асоциальное поведение детей и взрослых безработица низкий уровень этического...