28564

Система RSA. Использование алгоритма Евклида для расчета секретного ключа d

Доклад

Информатика, кибернетика и программирование

Подобный блок может быть интерпретирован как число из диапазона 0; 2i1;; для каждого такого числа назовем его mi вычисляется выражение ci=mie mod n 3.По теорема Эйлера если число n представимо в виде двух простых чисел p и q то для любого x имеет место равенство Xp1q1 mod n =1 Для дешифрования RSAсообщений воспользуемся этой формулой. Возведем обе ее части в степень y: Xyp1q1 mod n = 1 y=1 Теперь умножим обе ее части на x : xyp1q11 mod n =...

Русский

2013-08-20

23.69 KB

33 чел.

42. Система  RSA. Использование алгоритма Евклида для расчета секретного ключа d.

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Адлеманом (L. Adleman). Эта асимметричная криптосистема в настоящее время является широко распространенной во всем мире. В основе алгоритма RSA лежат идеи алгоритма Диффи-Хеллмана.

Первым этапом любого асимметричного алгоритма шифрования является создание пары ключей: открытого и закрытого (с последующим свободным распространением открытого ключа).

Для алгоритма RSA этап создания ключей состоит из следующих операций:

  1.  Выбираются два простых числа p и q;
  2.  Вычисляется их произведение n = p*q;
  3.  Выбирается произвольное число e (e<n), такое, что НОД ( e, (p-1)(q-1))=1

, т. е. должно быть взаимно простым с числом  (p-1)(q-1);

  1.  методом Евклида решается в целых числах уравнение

e*d+ (p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах;

  1.  два числа (e, n) – публикуются как открытый ключ;
  2.  число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).

Собственно шифрование с помощью этих чисел производится следующим образом:

  1.  отправитель разбивает свое сообщение на блоки, равные k= [log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. Подобный блок может быть интерпретирован как число из диапазона   (0; 2i-1);;
  2.  для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e) mod n

3. Шифрование и расшифрование сообщений с применением алгоритма RSA

Блоки и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть, даже если злоумышленник знает числа e и n, то по значению ci прочесть исходные сообщения mi он не может выполнить иначе, как полным перебором .

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d.По теорема Эйлера если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство

( X(p-1)(q-1)) mod n =1

Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y):

                                                   (X(-y)(p-1)(q-1)) mod n = 1 (-y)=1

Теперь умножим обе ее части на x :

   (x(-y)(p-1)(q-1)+1) mod n = 1 *x = x

С помощью алгоритма Евклида можно рассчитать секретный ключ d (целое число), для которого e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. Следовательно, в последнем выражении предыдущего абзаца можно заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть, для того чтобы прочесть сообщение ci=((mi)e)mod n, достаточно возвести его в степень d по модулю m: ((ci)d)mod n = ((mi)e*d)mod n = mi.

Операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса секретной связи, а ключ сеанса шифруется асимметричным алгоритмом с помощью открытого ключа получателя и обычно помещается в начало передаваемого файла.

Для работы каждый абонент должен выработать секретный и открытый ключи. Предварительно должны быть выработаны большие простые числа p и q и вычислено их произведение n=pq. Затем выбирается число e – такое, что   1 < e < φ (n) и НОД ( e,φ (n))=1   , где φ (n) = (p-1)(q-1) – функция Эйлера от n.

Из уравнения ed=1(mod φ (n)) посредством расширенного алгоритма Евклида находится число d. Полученные числа e,n – открытый ключ пользователя, а d – секретный ключ.

Использование алгоритма Евклида для расчета секретного ключа d. Для расчета секретного ключа шифрования d требуется решить сравнение вида: e*d  1 mod  (n), где  (n) – функция Эйлера от числа n, e – открытый ключ шифрования, d – секретный ключ шифрования.

Вычисление секретного ключа d основано на общеизвестной алгебраической формуле для деления целых десятичных чисел:

a = b*q + r, где 1 <= r < b.

Требуется вычислить частное q и остаток r от деления числа a на число b. Применительно к поставленной задаче q - это функция Эйлера  (n), а число b – открытый ключ шифрования e. Деление следует выполнять до тех пор, пока остаток от деления r не станет равен 1. Если остаток от деления r оказался большим 1, то пара чисел (a, b) заменяется парой чисел (b, r) (общее правило: предыдущий делитель становится делимым на данном шаге, а предыдущий остаток - делителем) и деление продолжается дальше.

Расчет секретного ключа d выполняется по следующей формуле:

V(i) = V(i-2) + q(i)*V(i-1), где q(i) – текущее частное от деления.

Начальные условия при расчете секретного ключа d:

V(-1) = 0; V(0) = 1.

Окончательно, d = (-1)**к*V(к) (mod  (n)), где к – номер шага алгоритма, на котором остаток от деления r(k) оказался равным 1.

Абонент B зашифровывает и посылает A сообщение m, которое тот затем расшифровывает.

Зашифрование. Абонент B должен сделать следующее:

  1.  получить открытый ключ абонента А – пару чисел (e, n);
  2.  представить сообщение в виде числа m из интервала [0, n-1];
  3.  вычислить c=me mod n;
  4.  послать шифртекст с абоненту A;

Расшифрование. Для получения открытого текста абонент A, используя секретный ключ d, вычисляет m=cd mod n; если, ed=1(mod φ (n)), (e, φ (n))=1, (m,n) =1, то (me)dmod n =m. Поскольку ed=1(mod φ (n)), то ed=1+k φ(n), где k – некоторое целое положительное число. Из теоремы Эйлера следует, что

                                                    m φ(n)=1(mod n) при (m,n)=1

Поэтому (me)d(mod n)= (m1+kφ(n))(mod n)=m(mφ(n))k (mod n)=m

 

Криптостойкость алгоритма 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.

В настоящее время рекомендуется выбирать n размером 1024 и 2048 бит.


 

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

75452. Финансовый анализ в рамках системы 1С 23.5 KB
  Финансовый анализ в рамках системы 1С Управленческий и финансовый учет Комплексная конфигурация позволяет вести одновременно два вида учета торговой деятельности: управленческий и финансовый учет. Финансовый учет ведется для правильного отражения деятельности всех фирм составляющих компанию в бухгалтерском учете. Управленческий и финансовый учет существуют как бы параллельно . Для этого у документов существует специальный реквизит Тип учета который может принимать значения Управленческий Финансовый Общий .
75453. Состав таблицы реляционной БД 23 KB
  Состав таблицы реляционной БД Реляционная база данных это совокупность отношений содержащих всю информацию которая должна храниться в БД. Иначе говоря в каждой позиции таблицы на пересечении строки и столбца всегда имеется в точности одно значение или ничего. Строки таблицы обязательно отличаются друг от друга хотя бы единственным значением что позволяет однозначно идентифицировать любую строку такой таблицы. Столбцам таблицы однозначно присваиваются имена и в каждом из них размещаются однородные значения данных даты фамилии целые...
75454. Организация бухучета в системе 1С 28 KB
  Организация бухучета в системе 1С На крупных предприятиях бухгалтерский учет организуется по двухуровневой системе управления управленческий и финансовый учет. Сметы нормативы калькуляции оптимальные соотношения затрат и результатов объекты управленческого учета. Информация управленческого учета имеет четко выраженную внутреннюю направленность. Информация финансового учета широко используется внешними потребителями инвесторами кредиторами и другими организациями и предприятиями.
75455. Назначение и цель анализа безубыточности в ИС Project Expert 23.5 KB
  Назначение и цель анализа безубыточности в ИС Project Expert Целью анализа безубыточности является выяснение влияния объема сбыта на уровень издержек и прибыли. Анализ даёт возможность решать ряд важных задач управления и планирования работы предприятия: формирование оптимальной номенклатуры изделий обоснование производственной программы определение стратегии и тактики ценообразования вычисление точки безубыточности производства Анализ безубыточности базируется на следующих предпосылках т. При соблюдении перечисленных условий легко...
75456. Понятие и содержание метаданных системы 1С: Предприятие 99 KB
  Понятие и содержание метаданных системы 1С: Предприятие Метаданные данные о данных совокупность объектов метаданных настроенных на хранение и обработку информации о хозяйственной деятельности конкретного предприятия. Формально объекты метаданных объединяются в виде дерева метаданных которое появляется при открытии окна Конфигурация Конфигуратора системы рис. Дерево метаданных Наряду с понятием метаданные используется термин структура метаданных. Данный термин более точно отражает суть метаданных как сложной структуры...
75457. Технология «клиент-сервер» для распределенных БД 103.5 KB
  Информационную основу системы клиент-сервер составляет распределенная база данных которая хранится на одном или нескольких серверах и с запросами к которой обращаются клиенты. Беглый обзор научной и профессиональной литературы показывает что о вычислениях...
75458. Последовательность разработки инвестиционного проекта в ИС Project Expert 24 KB
  Project Expert - одна из самых известных программ для составления бизнес-планов, она практически полностью автоматизирует составление бизнес-плана инвестиционного проекта...
75459. Реконфигурация системы БУ (1С) 21.5 KB
  Реконфигурация системы БУ 1С Системы комплексной автоматизации бухгалтерского учета потенциально способны решать любые задачи по всем разделам бухгалтерского учета. Такая функциональность обеспечена возможностью реконфигурации типовой модели учета реализованной в базовой версии например в программе 1C: Бухгалтерия 7. Таким образом помимо задач бухгалтерского учета стали автоматизироваться задачи оперативного управления. Например программы 1C: Бухгалтерия и 1C: Торговля и Склад рассматриваемые в комплексе являются системой...
75460. Этапы проектирования реляционных баз данных 30.5 KB
  Анализ предметной области заключается в получении от пользователя неструктурированных описаний прикладных задач базы данных выработке четкого определения и классификации элементов рассматриваемой предметной области. На основе собранной информации строится вербальная модель предметной области. Концептуальное проектирование состоит в формализации вербальной модели предметной области путем формирования ее концептуальной модели в виде схемы сущностьсвязь либо ERсхемы...