28567

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

Доклад

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

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

Русский

2013-08-20

15.87 KB

11 чел.

  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.


 

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

69775. Реалізація планування в Linux 55 KB
  Ядро Linux при плануванні не розрізняє процеси і потоки тому для визначеності ми надалі говоритимемо про планування процесів. Планування процесів реального часу в ядрі Стосовно процесів реального часу достатньо сказати що: вони завжди матимуть під час планування пріоритет...
69776. Розробка системи розпізнавання двох об’єктів розпізнавання образів 402 KB
  Мета роботи: Вивчити основні принципи роботи алгоритму розпізнавання образів Hamming classification. Пояснення Хемінгової мережі та її класифікація: задаємо фігури у вигляді координат ,задаємо їх колір(розмір) та запускаємо програму.
69777. КАРФАГЕН В ЦИВИЛИЗАЦИОННОМ ПРОСТРАНСТВЕ СРЕДИЗЕМНОМОРЬЯ 35.5 KB
  К тому же говоря о Карфагене обойти тему Финикии просто невозможно так как она важна для более ясного понимания некоторых аспектов истории карфагенской державы. Уже в начале II тысячелетия до нашей эры это были пусть и маленькие но процветающие города...
69778. Пути совершенствования маркетинговой стратегии предприятия 694.5 KB
  Результатом этого является предоставление потребителям услуг удовлетворяющих их потребности и получение организацией за счет увеличения объема реализации продукции прибыли необходимой для ее нормального и эффективного функционирования и лучшего удовлетворения запросов...
69779. СОВЕРШЕНСТВОВАНИЕ ТЕХНОЛОГИЙ РАСЧЕТОВ С ИСПОЛЬЗОВАНИЕМ ПЛАСТИКОВЫХ КАРТ 231.61 KB
  Рассмотреть теоретические аспекты пластиковых карт, как платёжного средства, виды пластиковых карт и их характеристики Исследовать порядок расчетов с использованием пластиковых карт в России; Исследовать платежные системы, используемые для расчетов пластиковыми картами...
69780. СТАНОВЛЕНИЕ ПРОФЕССИОНАЛЬНОЙ ИДЕНТИЧНОСТИ СТУДЕНТОВ ПЕДАГОГИЧЕСКОГО ВУЗА 55.03 KB
  Актуальность исследования. Традиционно в качестве основных критериев профессионального развития личности выступали критерии эффективности деятельности, но уже в работах Е.А. Климова отмечается недостаточность этих критериев для оценки уровня профессионализации.
69781. Личностные особенности больных с гипертонической болезнью 61.09 KB
  Клиническая картина гипертонической болезни. Стадии гипертонической болезни. Диагностика гипертонической болезни. Несмотря на успехи в лечении и профилактике гипертонической болезни за последние годы она еще пока продолжает оставаться объектом прицельного исследования медицины и смежных с ней областей.
69782. ОСНОВНЫЕ НАПРАВЛЕНИЯ ОРГАНИЗАЦИИ ОПЛАТЫ ТРУДА РАБОТНИКОВ УП «УКС МИНГОРИСПОЛКОМА» 221.78 KB
  Цель исследования: определить и проанализировать формы и системы оплаты труда выявить направления их совершенствования на предприятии. Задачи исследования: изучить экономическое содержание оплаты труда на предприятии; провести анализ форм и систем оплаты труда в УП УКС Мингорисполкома...
69783. Принципы подготовки газетных изданий к печати 103.45 KB
  Так как внешний вид стиль красота газеты зависит от того как вы создадите макет: поместите колонки вставите рисунки выберете шрифт для текста насколько сделаете его красочным и многое другое. Этим термином обозначают цифровую подготовку текста и изображения пригодных...