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

31 чел.

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


 

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

29243. Культурологическое образование в России 32 KB
  Главная сложность введения культурологии в систему высшего образования заключалась в том что отечественная культурологическая наука представляла и до сих пор представляет собой полностью эклектическую конструкцию. Первые шаги в организации специального культурологического образования были предприняты в одном из первых негосударственных вузов страны Российском открытом университете где в 1990 началось формирование факультета и кафедры искусствознания и культурологии. В 1995 на базе этого факультета была создана Высшая школа...
29244. Культура 41.5 KB
  Это совпадение имени симптоматично – оно лишний раз подчеркивает единство культуры народов включенных в орбиту европейского мира является знаком своеобразной культурной общности всех разноплеменных носителей европейских языков. Понятие цивилизация воспринимается как синоним слова культура В немецкой традиции впервые было сформулировано – и стало весьма популярным – представление о различии культуры и цивилизации. Со второй половины Х1Х века идея противопоставления культуры и цивилизации приобрела особое значение и...
29245. Религия как культурный феномен 30.5 KB
  Именно религия дает ответ на главный вопрос всех ценностнонормативных систем. Религия формирует у человека чувство независимости и уверенности в себе.Дюркгейм сравнивал религию в качестве интегратора социокультурных систем с клеем поскольку именно религия помогает людям осознавать себя как духовную общность скрепленную общими ценностями и общими целями.
29246. Феномен Ренессанса 37 KB
  Расцвет культуры Ренессанса приходится на XV XVI вв. В этой связи культура Ренессанса рассматривается как отрицание средневековья как антитеза средневековой схоластике. Такова самая общая в значительной мере поверхностная характеристика Ренессанса.
29247. Феномены русской, российской, советской культуры 52.5 KB
  Проблема самосознания русской культуры. Этапы становления русской идеи. Формирование русской национальной культуры на протяжении веков проходило в русле этнического разнообразия преодоления разобщенности в условиях интенсивного воздействия извне: соединение Запада и Востока наслоение различных этнических и региональных культурных типов временных компонентов конфессиональных общностей.
29248. Понятие культурной самоидентичности 32 KB
  Современные глобальные проблемы есть следствие логическое продолжение глубокой структурной несогласованности человеческой субъективности кризиса его самоидентичности. Распад социальной системы начинается с распада социальных связей и разрушения социальных субъектов кризиса их личностных ценностных ориентации и утраты самоидентичности. Проблема самоидентичности является стержнем ядром всей социальной проблематики.
29249. Символ. Смысловая структура символа 53.5 KB
  Языком культуры в широком смысле этого понятия называются те средства знаки символы тексты которые позволяют людям вступать в коммуникативные связи друг с другом ориентироваться в пространстве культуры. Язык культуры это универсальная форма осмысления реальности в которую организуются все вновь возникающие или уже существующие представления восприятия понятия образы и другие подобного рода смысловые конструкции носители смысла. Основной структурной единицей языка культуры с точки зрения семиотики являются знаковые системы.Любой...
29250. Культура как смысловое поле человеческой жизнедеятельности и способ реализации творческих возможностей человека 60.5 KB
  Речь не о какомто единственном и едином способе деятельности а о целом их ансамбле таком же сложном как и система созидательных способов деятельности деятельность распредмечивания изоморфносимметрична деятельности опредмечивания. Но и зеркально симметричным и возвращает нас к исходному пункту деятельности – человеку. Какими качествами он должен обладать чтобы выполнить эту функцию Человек – субъект деятельности.
29251. КУЛЬТУРА ЗАПАДНОЕВРОПЕЙСКОГО СРЕДНЕВЕКОВЬЯ 53.5 KB
  В этом исторически длительном социокультурном процессе развития феодального общества вырабатывался своеобразный тип отношений человека к миру качественно отличающий его как от культуры античного общества так и от последующей культуры Нового времени эпохи буржуазного производства. Именно христианство стало основной осью складывающегося с V века в Западной Европе мира которая влияла на все стороны жизни человека его духовные приоритеты устои общества. Следование этому образцу становилось смыслом жизни каждого человека так как...