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.


 

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

55786. Ой, не вітер в полі грає, не орел літає – ото Сірко з товариством по степу гуляє! 61.5 KB
  Мета: увіковічення та вшанування визначного військово-політичного діяча козацького періоду Івана Сірка; популяризація козацьких звичаїв та традицій серед учнівської...
55787. ПОЛІТИКА ВЛАДИ У ЦАРИНІ КУЛЬТУРИ В 1921-1928 рр. УКРАЇНІЗАЦІЯ (КОРЕНІЗАЦІЯ) 311 KB
  Мета: методична удосконалення методики проведення лекціїдіалогу та активізації пізнавальної діяльності студентів шляхом використання групових форм роботи...
55788. Які правила визначають гармонію людини із собою та найближчим оточенням 245 KB
  Стежка Правдивості Команди слухають визначення понять Додаток 3 які вивчали на попередніх уроках етики потім радяться 30 секунд і записують кожне слово на окремому аркуші паперу.
55789. Розвиток розумових здібностей учнів засобами математики 4.37 MB
  Система роботи вчителя на уроці Документи які відображають офіційну оцінку роботи вчителя. З певністю можу сказати що наукове товариство дає навички роботи з науковою літературою ресурсами Інтернету вчить учнів формулювати свої думки планувати роботу. Організація науководослідної роботи учнів та вчителів Положення про роботу наукового товариства Інтелект Загальні положення Наукове товариство Інтелект обєднує учнів школи зацікавлених у підвищенні свого інтелектуального та культурного рівня які...
55790. Розвиток здібностей школярів до словесної творчості на уроках української літератури в 5 класі 101 KB
  Як запалити у дитини вогник творчого розповідання У педагогічній науці і практиці постійно ведеться інтенсивний пошук дієвих і цікавих дітям методів і прийомів навчання спрямованих на розвиток їхньої словесної творчості.
55791. Развитие творчества и художественных способностей детей средствами изобразительной деятельности 44.5 KB
  На все руки мастер Если краска есть у вас Кисть не обязательна: Можно пальцем рисовать Просто замечательно Пальцем я зеленой краской Нарисую огурец Помидорку красной краской Вот какой я молодец...
55792. Розвиток критичного мислення школярів на уроках української літератури. Як вчити добувати необхідну інформацію з друкованого джерела та критично її осмислювати 56.5 KB
  Метод Читання тексту з позначками. Метод Читання в парах Узагальнення в парах. Ця стратегія розрахована на читання тексту в парах і є ефективною при роботі з художніми творами.
55793. Розвиток процесів сприймання у молодших школярів на уроках природознавства 58 KB
  Для розвитку процесів сприймання варто використовувати спеціальні прийоми вправи завдання. Для розвитку такої чутливості необхідно привчати школярів насамперед прислухатися й розрізняти...
55794. Розвиток розумових та творчих здібностей учнів шляхом використання методів розвиваючого навчання 106 KB
  Головне щоб вони відповідали змісту матеріалу та віку учнів збагачували знання розвивали науковий світогляд мислення практичні вміння а отже й активність.