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.


 

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

155. Основи теплоізоляційної енергоефективності 401 KB
  Використання теплоізоляційних матеріалів (ТІМ) в будівництві. М'які ізоляційні матеріали настільки добре пропускають повітря. Теплоізоляційний матеріал з підвітряного боку будівлі потрібно спеціально захищати від вітру.
156. Проект организации строительного производства 369.5 KB
  Выбор и обоснование методов производства основных строительно-монтажных работ. Показатели расхода полуфабрикатов, изделий и материалов на 100м2. Проектирование общеплощадочного строительного генплана.
157. Неорганические (минеральные) вяжущие вещества 406 KB
  Неорганическими вяжущими веществами называют порошкообразные материалы, которые при замешивании с водой (гипс, известь, цемент) или с водными растворами солей.
158. Сезонные колебания уровней временного ряда 387.5 KB
  Определение наличия колебаний и их силы (размаха).Сущность, достоинства и недостатки экстраполяции. Сущность, условия применения корреляционо-регрессионного анализа. Апостериорные и априорные оценки точности прогнозов.
159. Гігієна середньої загальноосвітньої школи №6 міста Тернополя 169 KB
  Навчальні кабінети прибираються один раз на день (вологе прибирання), фізкультурний зали прибирається два рази. Відношення площі кватирки до площі підлоги. Провітрювання навчальних кабінетів здійснюється систематично, а у фізкультурних залах провітрювання наскрізне.
160. Теория естествознания 164.5 KB
  Уникальные объекты все чаще становятся предметом исследования естественных наук. Взаимосогласованное расположение частей объекта, образующее сбалансированную форму. При самоорганизации поведение самых отдаленных друг от друга областей системы становится согласованным.
161. Формирование вычислительной культуры учащихся 5-6 классов 684.5 KB
  Основные компоненты вычислительной культуры 5-6 классов и приемы их формирования некоторых из них. Система задач для умственного счета С. Рачинского. Методические рекомендации по обучению прикидке и оценке результатов вычислений в 5-6 классах.
162. Электротехника. Учебное пособие 931.25 KB
  Важнейшим электрическим явлением, которое рассматривает- ся в электротехнике. Короткое замыкание трансформатора. Асинхронные бесколлекторные машины. Эквивалентная схема двигателя. Расчет трехфазной цепи при симметричной нагрузке.
163. Теория информации. Информационные модели дискретных источников сообщений 709.11 KB
  Понятие информации относится к основополагающим категориям как философии, так и естественных наук. Информационные модели дискретных источников сообщений и их свойства. Эпсилон-энтропия гауссовских процессов. Методика расчета информационной производительности дискретных интерполяционных представлений процессов полиномами Лагранжа.