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.


 

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

53518. Калейдоскоп знань – нетрадиційна форма проведення уроків 707 KB
  Такі уроки допомагають учителю урізноманітнювати роботу учнів знімають напруження від звичної навчальної діяльності переключають увагу школярів вони є цінним засобом виховання розумової активності дітей що активізує психічні процеси викликає в учнів живий інтерес до процесу пізнання. Навчальний день для учнів 1 і 2 класів починається з лінійки де кожному класу вручається свій маршрутний лист. У маршрутному листі записуються уроки які будуть проводитися для учнів даного класу: математика українська мова читання музика Я і Україна. З...
53519. Геометричні перетворення 2.37 MB
  Яку найменшу кількість клітинок треба заштрихувати щоб фігура на рисунку мала вісь симетрії А. 6 Вісь симетрії Достатньо замалювати три клітинки. Які літери мають вісь симетрії А які центр симетрії № 5. За якою ознакою складені наступні літери алфавіту: А Д М Т П Ш вертикальна вісь симетрії В Е З К С Ю Є горизонтальна вісь симетрії Ж Н О Ф Х вертикальна та горизонтальна вісь симетрії Б Г Л Р У Ц Ч Щ Я літери не мають ні горизонтальної ні вертикальної вісі симетрії Паліндром це абсолютний прояв...
53520. Літературний калейдоскоп. Хороша книга 67 KB
  Сприяти формуванню читацьких смаків, Розширювати читацькі інтереси учнів; заохочувати до читання книг; розвивати пам'ять учнів, уміти переказувати та розповідати цікаві уривки з прочитаних творів; виховувати любов до книги.
53521. Математичний калейдоскоп 1.07 MB
  Перевірити знання учнів 5 класу з вивчених тем; розвивати логічне мислення, увагу, творчі здібності, вміння працювати в групі; виховувати наполегливість, взаємодопомогу.
53522. Я не мислю України без калини 35 KB
  Це харчова, лікарська, медоносна рослина. З неї готують варення, повидло, компоти, киселі, мармелад, начинку для цукерок, муси, приправи для мясних страв, чайно-кавовий сурогат. Калина - пізньовесняний медонос та фарбувальна рослина.
53523. Без верби й калини нема України 176 KB
  Розширити знання дітей про вербу і калину, як рослини-символи України; показати, як оспівував їх український народ; розвивати спостережливість, творчі здібності, тренувати пам’ять, мислення, зв’язне мовлення учнів; виховувати у дітей любов до рідного слова, до національний традицій, народної мудрості, до краси і гармонії навколишнього світу, любов до рідного краю.
53524. Посадіть калину коло серця 96 KB
  Нема такого села де б за тином чи біля криниці у лузі чи на березі річки не росла не квітла б навесні рясним білим цвітом не румяніла червоними ягідками з осені аж до зими калина. Калина - символ України. А коли зима приходить стоїть калина у червоному намисті урочиста і красива. Копали криницю недалеко від того місця де росла калина то вода буде чистою й смачною.
53525. Соціально-економічний розвиток Канади наприкінці ХХ – на початку ХХІ століть 3.92 MB
  Вчитель інформатики: Сьогодні у нас незвичайний урок на якому ми будемо застосовувати набуті на інформатиці знання до розвязування питань які виникли з іншого предмета а саме історії. Вчитель історії; Перевірку домашнього завдання ми пропонуємо здійснити через розгадування кросворду. Вчитель інформатики: Для цього на робочому столі відкрийте папку Історія та інформатика і файл ДОМАШНЄ ЗАВДАННЯ. Вчитель історіїї; Ви отримали слово Харпер.