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.


 

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

32429. Стеганография(СГ). Цифровые водяные знаки 18.79 KB
  форматы либо избыточность аудио графической информации. В первом случаем можно использовать для упрятывания информации зарезервированные поля компьютерного формата данных. : небольшое количество информации низкая степень скрытности. Виды стеганографии: Суррогатная – данные информации обычно шумят и необходимо заменять шумящие биты скрываемой информацией.
32430. Направления в области ЗИ от НСД , Показатели защищенности СВТ, порядок оценки класса защищенности СВТ, понятие и подсистемы АС , Классификация СВТ и АС по уровню защищенности от НСД 1.07 MB
  Первое связано с СВТ второе – с АС. СВТ – средства вычислительной техники. СВТ совокупность программ и технических элементов систем обработки данных способная функционировать как самостоятельно так и в составе других систем.
32431. Классификация СЗИ по уровню контроля отсутствия недекларируемых воздействий 20.5 KB
  Классификация распространяется на ПО предназначенное для защиты информации ограниченного доступа. Для ПО используемого при защите информации отнесенной к государственной тайне должен быть обеспечен уровень контроля не ниже третьего. Самый высокий уровень контроля первый достаточен для ПО используемого при защите информации с грифом ОВ. Второй уровень контроля достаточен для ПО используемого при защите информации с грифом CC.
32432. Биометрические методы идентификации 19.11 KB
  Располагается на расстоянии 50 см и сравнивает ткани вокруг зрачка Стандарты биометрической аутентификации можно разделить на несколько иерархических категорий: I Стандарты определяющие требования для систем использующих биометрические технологии II Стандарты определяющие требования к процедуре использования биометрического распознавания в различных областях III Стандарты определяющие программный интерфейс PI для разработки биометрических систем IV Стандарты определяющие единый формат биометрических данных V Стандарты представления и...
32433. Электронные идентификаторы iButton 21.32 KB
  Все iButton имеют ПЗУ где хранится информация в виде поликремниевых проводников что не требует энергии для хранения. Это ПЗУ содержит 6 байтовый серийный номер – уникальный. Таблетки DS 2404S01 – двухпортовая память содержит 64битную память ПЗУ. Группы: Для работы с содержимым ПЗУ.
32434. Secret Net5.0-C, архитектура СЗИ НСД, состав семейства, администрирование системы и пользователей, организация разграничения доступа, контроль целостности, аудит 4.13 MB
  0C архитектура СЗИ НСД состав семейства администрирование системы и пользователей организация разграничения доступа контроль целостности аудит.Разграничение доступа и зашиты ресурсов.Разграничение доступа к устройствам компьютера. Механизм разграничения доступа к устройствам РДУ предназначен для разграничения доступа к устройствам с целью предотвращения несанкционированной утечки информации с защищаемого компьютера.
32435. Электронные ключи 16.58 KB
  На базе программируемых логических матриц Реализуют функцию x и y – могут представлять последовательность чисел Электронные ключи энергозависимой программируемой памятью имеется возможность дистанционного перепрограммирования ключей. Возможность усиленной защиты за счет встраиваемой функции. Возможность защиты от НСД к данным за счет их шифрования с использованием параметров электронного ключа. Возможность выбирать схему защиты.
32437. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ 157.5 KB
  Пусть Х – случайная величина с функцией распределения Fx. Если функция распределения дифференцируема то ее производная Fx = fx называется плотностью распределения а сама случайная величина Х – непрерывно распределенной случайной величиной. Отсюда следует что функция распределения непрерывной случайной величины является первообразной от плотности распределения: Утверждение 8. Вероятность того что случайная величина Х принимает значения из отрезка [а b] равна интегралу по этому отрезку от плотности распределения случайной величины Х.