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.


 

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

82190. Містечко дитячих мрій 41 KB
  Так розпочалося дитинство мого дідуся. Взимку коли за вікном хурделиця і сніг ласкаво проситься до хати в мого дідуся оживають спогади про далеке минуле. Але слухаючи сповідь мого дідуся я поринаю в ті далек незрозумілі для мене часи сповнені дитячого смутку та горя. Так продовжувалося дитинство мого дідуся.
82191. Ми роду козацького діти, землі української цвіт 4.39 MB
  Розширити знання учнів про славне минуле українського народу, ознайоми ти з одним із відомих гетьманів України І.Мазепою, боротьбою українсько го народу за волю, незалежність, віру і щастя, виховувати любов до Украї ни, інтерес до історичного минулого, почуття національної свідомості та громадянської активності.
82192. Алкоголь — ворог №1 24.5 KB
  Ворога потрібно знати в обличчя: а вплив алкоголю на стравохід; б дія алкоголю на шлунок; в вплив алкоголю на кишківник; г вплив алкоголю на печінку; д вплив алкоголю на кров; е вплив алкоголю на серце; є вплив алкоголю на підшлункову залозу; ж вплив алкоголю на мозок.
82193. Сучасні українці — жертви алкогольної реклами 2.99 MB
  Текст вірша: Всі ті, хто за тверезу Україну Підняти хочуть Україну із руїни. Що не дає тобі цвісти, Вкраїно-ненько? Ой, страшний є у мене, лютий вороженько. Найбільша цінність наша — хто? Це наші діти. Їх, молодих, найбільше хоче він споїти. Ой, як голівоньку їм нелюди морочать: Позбавить розуму всю нашу молодь хочуть!
82194. Олимпийский урок 53.5 KB
  Познакомить с историей Олимпийских игр. Чего вы ожидаете от предстоящих зимних Олимпийских игр в России К нам приедет много гостей построят спортивные комплексы. Последние зимние Олимпийские игры прошли в Италии в городе Турине в 2006 г. XXII летние Олимпийские игры состоялись в Москве в1980 г.
82195. Осінь-чарівниця 891.5 KB
  Мета: учити дітей бачити зміни природи восени, виховувати у дітей естетичних почуття, любов до природи рідного краю, уміння розуміти її красу, уловлювати настрій, викликаний картинами природи; розширити кругозір дітей, сприяти розвитку інтересу до явищ природи та її загадок.
82196. Великие реформы 60 -70-х гг. XlX века 49.38 KB
  Начиная эту реформу правительство Александра ll надеялось провести модернизацию общества которая была так важна России в этот период. Однако отмена крепостного права не могла пройти бесследно для России так как господствовал крепостной строй. должны были способствовать ускорению или торможению модернизации России...
82197. Потребление. Потребитель. Права потребителей и их защита 51.95 KB
  Словарь урока: потребитель продавец недостаток товара материальный ущерб моральный вред гарантийный срок срок годности срок службы товара. Право на информацию о товарах услугах работах. Она нужна чтобы потребитель смог сделать правильный выбор для этого ему нужно знать качества и свойства того или иного товара.
82198. Реки России 104.5 KB
  Цель урока: Изучить особенности рек России. Расширить и углубить знания о реках. Сформировать понятия базис эрозии, уклон, падение реки, расход воды в реке, годовой сток, твёрдый сток. Показать влияние климата и рельефа на реки. Формировать умение определения уклона и падения реки.