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

36 чел.

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 бит.


 

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

18431. Средства измерения и представления информации 31 KB
  Лекция 15. Средства измерения и представления информации. Средства измерения и представления информации. Устройства данной группы предназначенные для визуального представления информации человекуоператору и для выдачи сигналов в группу специальных средств обр
18432. Аналоговые и цифровые вторичные приборы ГСП 67 KB
  Лекция 16. Аналоговые и цифровые вторичные приборы ГСП. Приборы выдачи информации. Различают аналоговые и дискретные методы выдачи измерительной информации. В обоих случаях простейшей формой выдачи является отображение результатов измерения на визуально считыв
18433. Классификация и общая характеристика средств управления 41 KB
  Лекция 17. Классификация и общая характеристика средств управления. Для эффективного использования полученной ИИС информации об объекте управления необходимо ее проанализировать выработать по определенным алгоритмам соответствующие команды и передать их к объек
18434. Законы регулирования, регуляторы, исполнительные механизмы и регулирующие органы 106 KB
  Лекция 18. Законы регулирования регуляторы исполнительные механизмы и регулирующие органы. Промышленные автоматические регуляторы. Одной из основных частей низовой локальной системы автоматического регулирования САР является регулятор. В общем случае регулято
18435. Программно-технические комплексы 76.5 KB
  Лекция 19. Программнотехнические комплексы. В настоящее время автоматизация большинства технологических процессов осуществляется на базе универсальных микропроцессорных контроллерных средств которые в России получили название программнотехнических комплексо
18436. Электрические исполнительные механизмы 46.5 KB
  Лекция 20. Электрические исполнительные механизмы. Назначение. Механизмы исполнительные электрические однооборотные постоянной скорости МЭО и МЭОФ предназначены для перемещения регулирующих органов в системах автоматического регулирования технологическими пр
18437. Регулирующие органы 91 KB
  Лекция 21. Регулирующие органы. Регулирующие органы служат для изменения количества вещества или энергии подводимых к объекту регулирования или отводимых от него по определенной программе или поддержание на определенном уровне. Чаще всего с помощью регулирующих
18438. История языка PHP. Установка ПО для работы с PHP 780 KB
  Серверные технологии разработки webсайтов История языка PHP. Установка ПО для работы с PHP. История PHP Язык PHP был разработан как инструмент для решения чисто практических задач. Его создатель Расмус Лердорф хотел знать сколько человек читают его onlineрезюме и написал ...
18439. Конструкции и типы данных PHP 223.5 KB
  Серверные технологии разработки webсайтов Конструкции и типы данных PHP Основной синтаксис Первое что нужно знать относительно синтаксиса PHP это то как он встраивается в HTMLкод как интерпретатор узнает что это код на языке PHP. В предыдущей лекции мы уже говорили об