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


 

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

60140. Засідання круглого столу: «Математики і лірики» 60 KB
  В свою чергу багато маткматиків віддали данину мазі поезії і навіть писали вірші поеми і романи. Мені хочеться багато писати і вчитися писати зізналась дівчина і ось через якісь цифри я не потраплю до університету.
60141. «Свіча запалена від серця» (загальношкільний виховний захід) 341.5 KB
  Слайд№ 1 Вчитель: Красиво і світло в нашій світлиці Квіти на вікнах стоять весняні. Гладить його по голові Слайд №2 Вчитель: Щовесни коли тануть сніги І на рясті просяє веселка Повні сил і живої снаги Ми вшановуєм пам’ять Шевченка.
60142. Ми тебе не забули, Тарасе! 476.5 KB
  Ведуча 1. 9 березня 1814 року народився Тарас Григорович Шевченко – великий поет України. Тарасе, наш Кобзарю, всюди Приходиш нині ти як свій Тебе вітають щиро люди На всій Україні моїй. Тарас вкраїнської землі Був найвірнішим сином.
60143. Классный час по профориентации: «Наш выбор» 156 KB
  Цели - расширить представления учащихся об различных профессиях; формировать позитивную оценку таких нравственных качеств, как целеустремленность, трудолюбие, скромность...
60144. Подорож до Карликанії 132.5 KB
  Мета. Узагальнити та систематизувати знання, вміння і навички учнів із теми «Подільність чисел»; показати на прикладах за допомогою ігрових моментів; практичну спрямованість математичних знань; удосконалювати навички виразного читання...
60145. Позакласний захід: «Формула кохання» 69.5 KB
  Ломоносов Більш ніж про кохання в світовій літературі тільки про смерть написано. Про емоції розкажуть виступи учнів про вплив речовин: адреналін норадреналін вазопресин серотонін З коханням складніше. На думку дослідників кохання -це хімічний процес...
60146. День Чорного моря - свято зі сльозами на очах 114 KB
  Обладнання: екологічний пакет Чорноморська скринька презентація Чорне море проектор комп’ютер виставка Відпочинок на Чорному морі відеокліпи про море. Хід виховного заходу Учень читає вірш на фоні морського шуму Безмолвное море лазурное море...
60147. Поэзии и музыки чарующий мир. Литературно-музыкальное путешествие 162 KB
  Прививать любовь к красоте слова и музыки. Посредством поэзии и музыки воспитывать любовь к родной природе ценить дружбу стремиться к самосовершенствованию. Библиотекарь: Ребята мы сегодня с вами собрались чтобы окунуться в прекрасный удивительный и чарующий мир поэзии и музыки.
60148. Виховний захід «Твори добро на радість людям» 276.34 KB
  Мета: Формувати в учнів уявлення про морально-етичні відношення у навколишньому середовищі; вчити виявляти шанобливе ставлення до батьків, старших, піклування про молодших; розвивати почуття чуйності і доброзичливості