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


 

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

79281. Планирование и прогнозирование потребности в персонале 13.31 KB
  Планирование потребностей в персонале как и любой хороший план базируется на предпосылках которые позволяют делать предположения относительно будущего. Если Вы разрабатываете планы потребностей в персонале Вам скорее всего понадобятся три вида прогнозов: один для разработки Ваших требований к персоналу другой для поиска кандидатов со стороны и третий для поиска кандидатов внутри организации. Прогнозирование потребности в персонале строится на основе анализа прогнозов спроса и предложения для определения перспективной нехватки или...
79282. Планирование производительности труда и показателей по труду 14.55 KB
  Производительность труда это плодотворность продуктивность производственной деятельности людей. Планирование производительности труда определение уровня производительности труда и темпов ее роста обеспечивающих конкурентоспособность организации. На уровень и динамику производительности труда влияет множество факторов.
79283. Нормирование труда и расчет численности персонала 44.89 KB
  Расчет численности персонала: Необходимая численность Чн это количество работников требующихся для выполнения производственного задания в установленный период времени в заданных организационно-технических условиях. Расчет численности на основе норм времени где Т∑ совокупная трудоемкость работ в плановом...
79284. Наем, отбор и прием персонала 19.63 KB
  Наем отбор и прием персонала Наем на работу представляет собой деятельность по привлечению специалистов обладающих профессиональными квалификационными качествами в соответствии с требованиями вакантных рабочих мест и должностей. Наиболее часто источники найма персонала группируются как внешние и внутренние активные и пассивные низко и высокозатратные кратко и долгосрочные. Как источники найма на работу могут рассматриваться: случай средние школы техникумы ПТУ ВУЗы в виде практик стажировок направлений клиенты и поставщики...
79285. Деловая оценка персонала 16.2 KB
  Делова оценка персонала– анализ соответствия профессиональных и личных характеристик (компетенций) индивида требованиям должности, которую он занимает или на которую он претендует, при помощи определенных критериев.
79286. Профориентация и трудовая адаптация персонала 13.38 KB
  Профориентация и трудовая адаптация персонала Профессиональная ориентация и адаптация выступают важным составным элементом системы подготовки кадров и являются регулятором связи между системой образования и производством. Профессиональная ориентация представляет собой систему мер по профинформации профконсультации профподбору и профадаптации которая помогает человеку выбирать профессию наиболее соответствующую потребностям общества и его личным способностям и особенностям. Сложились следующие формы профориентационной работы: ...
79287. Основы организации труда персонала 15 KB
  Основы организации труда персонала Модель организации труда как и модель любой организации может быть представлена в трех основных аспектах. Вопервых организация труда как структура. Она определенным образом располагает соединяет моменты труда орудия груда предметы труда и сам труд. Вовторых организация труда как динамическая система т.
79288. Высвобождение персонала 55.85 KB
  Высвобождение персонала Высвобождение персонала это вид управленческой деятельности предусматривающий комплекс мероприятий по соблюдению правовых норм и организационно-психологической поддержки со стороны администрации при увольнении работников. Виды высвобождения персонала из организации приведены на рис. тот вид высвобождения который практически не прогнозируется администрацией и как правило происходит для нее неожиданно. Однако с точки зрения работника это наиболее мягкий вид высвобождения: работник готов покинуть организацию и...
79289. Управление социальным развитием организации 11.87 KB
  Управление социальным развитием организации Говоря об управлении социальным развитием организации можно использовать термин Социальная политика организации которая характеризуется как часть политики управления персоналом и включающая в себя все цели и мероприятия связанные с добровольными социальными услугами организации. Социальная политика организации означает уважение признание заслуг и поощрение людей. Соответственно этому система дополнительных социальных льгот должна быть не только привлекательной для сотрудника но и...