рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Алгоритм асимметричного шифрования RSA

Алгоритм асимметричного шифрования RSA - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Алгоритм Rsa Предложили В 1978 Г. 3 Автора: Райвест (Rivest),...

 

Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и электронной цифровой подписи. В системах с открытым ключом исключают явную передачу по открытым каналам секретных постоянных данных - секретных ключей для шифрования.

Надежность алгоритма основывается на большой вычислительной сложности:

- факторизации (разложения на простые сомножители) больших чисел

 

- и вычисления дискретных логарифмов.

 

Сложность вычисления дискретных логарифмов заключается в том, что по известному числу Ко (открытому ключу) и зашифрованному тексту C математически сложно подобрать секретный ключ Kc и исходный текст M, для которых будет выполняться равенство М = CKc mod N, где C = MKо mod N.

Асимметричные алгоритмы применяются в основном в процедурах


 

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

В алгоритме выбираются случайные большие простые числа Р и Q, равной длины (с одинаковым количеством двоичных или десятичных разрядов, необходимых для хранения числа), которые являются секретом. Данные числа образуют модуль N, используемый для нормирования результатов: N = P? Q.

Открытый ключ Ко выбирается случайным образом так, чтобы одновременно выполнялись условия:

1< ≤ j(N),

НОД(, j(N)) = 1,

j(N)=(P-1)(Q-1),

где j(N) - функция Эйлера (раздел 1.6). Функция Эйлера j(N) указывает

 


количество положительных целых чисел в интервале


1, N -1 , которые


 

взаимно простые с числом N. Второе условие означает, что открытый ключ и функция j(N) должны быть взаимно простыми (использование алгоритма Евклида, раздел 1.1).

Далее, используя расширенный алгоритм Евклида (раздел 2.2), вычисляется секретный ключ как обратный элемент к , такой, что

-1


Kc ? Ко ≡ 1 mod j(N) или Kc = Ко


mod((P-1)(Q-1)).


 

Для вычисления Kc числа j(N) и Ко должны быть взаимно простыми, то есть чтобы выполнялось условие НОД(j(N), Ко) = 1.

Открытый ключ используют для шифрования данных, а секретный ключ Kc - для расшифровки.

Открытый текст M перед шифрованием разбивается на числовые блоки

 

Mi, не превосходящих N.

 

При шифровании выполняется преобразование открытого текста M с открытым ключом Ко по следующей формуле (возведение в степень с нормированием результата по модулю выполняется с помощью схемы


 


Горнера, раздел 1.7):


 

 

C = MKо mod N.


 

Задача расшифровки зашифрованного текста С решается с использованием пары чисел - секретного ключа Kc и зашифрованного текста

С - по формуле:

 

М = CKc mod N.

 

Процесс расшифровки можно записать как D(E(M)) = M (D - операция расшифровки, E - операция шифрования). Тогда M = (MKо)Kc mod N.

Рассмотрим вопрос: почему для целого числа M, удовлетворяющего неравенству 0 ≤ M N-1, выполняется тождество D(E(M)) = M.

Условие Kc ? Ко ≡ 1 mod j(N) можно записать в виде Kc ? Ко = 1 +

 

j(N)? t, где t - некоторое целое число. Тогда (MKо)Kc mod N = M1 + j(N)?t mod N =

 

= [M? Mj(N)?t] mod N = M? (Mj(N)) t mod N.

 

Если числа M и N взаимно простыми, то по теореме Эйлера (раздел 1.6)

 

Mj(N) ≡ 1 mod N. В результате, M? (Mj(N)) t mod N = [(M mod N)?

 

? (Mj(N)t mod N)] mod N = M? (1) t mod N = M? 1 mod N = M.

 

Доказательство тождества D(E(M)) = M для общего случая (когда

 

N и M не являются взаимно простыми). Покажем: почему работает RSA.

 

 

Чтобы однозначно поставить в соответствие С и М, требуется выполнение усдовия

e · d ≡ 1 mod φ(m), m=N

С = Me mod m; m = p·q; M<m.

 

Сd mod m = M = Me·dmod m = M(1+φ(m)k) mod m = M · Mφ(m)k mod m = M

 

mod m,

 

так как e·d ≡ 1 mod φ(m)

 

e·d = 1 + φ(m)·k,

 

aφ(m)k ≡ 1k mod m, (a,m) = 1

 

Необходимо доказать, что p·q | (Med – M) для любых М

 

Med mod p = M mod p

 

Med mod q = M mod q


 

p| (Med – M)

 

q| (Med – M)

 

(M · Mφ(m)k ) mod p = M · M(p-1)(q-1)k mod p = M mod p

 

(M · Mφ(m)k ) mod q = M · M(p-1)(q-1)k mod q = M mod q

 

M · M(p-1)(q-1)k mod p = 1

 

M · M(p-1)(q-1)k mod q = 1

 

Следовательно, p·q| (Med – M). По теории сравнимости: если одно и тоже число делится на p и на q, то оно делится и на их произведение.

 

В криптосистеме RSA открытый ключ Ко и секретный ключ Кс

 


принадлежат множеству целых чисел


2, j( N ) , а сообщение М и


 


криптограмма С - множеству целых чисел

 

Элементами системы являются:


0, N - 1, где N - модуль.


 

- открытые - открытый ключ Ko, модуль N и шифротекст C;

 

- закрытые - секретный ключ Kc, простые числа P и Q, и исходный текст M.

Особенности алгоритма RSA.

 

Чтобы алгоритм RSA имел практическую ценность, необходимо:

 

- генерировать большие простые числа без больших временных затрат;

 

- уметь оперативно вычислять значения ключей Кc и Кo.

 

Для нахождения чисел P и Q из N перед злоумышленником существует задача разложения числа N на множители. Для получения открытого текста M из закрытого текста C, без знания секретного ключа Kc, возникает проблема нахождения дискретного логарифма. Обе эти задачи имеют вычислительную экспоненциальную сложность.

Реализация RSA примерно в 100-1000 раз медленнее соответствующей реализации симметричного алгоритма.

Недостаток алгоритма RSA - существует малая вероятность того, что шифровка числа M возведением в степень Кo по модулю N может не изменить открытый текст M, то есть MKо M mod N.


 

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

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

 

 

Рис. 4.1. Оценки длин ключей для асимметричных систем

 

Пусть пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. Пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Элементы криптосистемы RSA должен формировать получатель сообщения - пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.

Действия пользователя B.

 

1. Выбираются 2 произвольных больших простых числа Р и Q.

 

2. Вычисляется значение модуля N = Р ? Q.

 

3. Вычисляется функция Эйлера: j(N) = (P-1)(Q-1) и выбирается случайным образом значение открытого ключа Ко, удовлетворяющего условиям:


 

1< ≤ j(N),

НОД(, j(N)) = 1 (алгоритм Евклида, раздел 1.1).

4. Вычисляется значение секретного ключа Kc (расширенный алгоритм

 

Евклида, раздел 2.2) решением сравнения

 

-1


Kc Ко


mod j(N).


 

5. Пользователю А пересылается пара чисел (N, Ко) по незащищенному каналу.

Действия пользователя A, передающего пользователю В сообщение М.

 

6. Исходный открытый текст М разбивается на n блоков чисел Mi < N,

 

i = 0, n - 1.

 

7. Текст, представленный в виде последовательности чисел Мi,


 

шифруется по формуле Сi = МiКo mod N,


 

i = 0, n - 1


 

(схема Горнера, раздел


 

1.7); отправляется криптограмма C0, С1, ..., Сn-1 пользователю В.

 

Действия пользователя B.

 

8. Расшифровывается полученная криптограмма C0, С1, ..., Сn-1 с помощью секретного ключа Kc по формуле Mi = СiКc mod N. В результате будет восстановлена последовательность чисел Мi, образующих исходное сообщение М.

Пример4.1. Проведем шифрование и расшифровку сообщения "ЭБФ". Будем использовать русские прописные буквы (перевод букв алфавита в

числа представлен в табл.4.1).

 

Таблица 4.1. Номера букв русского алфавита

 

А Б В Г Д Е Ж З И Й К Л М Н О П
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

 

 

Действия пользователя В.

 

1. Выбираются некоторые Р = 3 и Q = 11.

 

2. Вычисляется модуль N = P? Q = 3? 11 =33.

 

3. Вычисляется значение функции Эйлера для N = 33:

 

j(N) = j(33) = (Р-1)(Q-1) = 2? 10 = 20.


 

Выбирается в качестве открытого ключа Кo произвольное число, удовлетворяющее условиям: 1 < Кo ≤ 20, НОД(Кo, 20) = 1.

Пусть Кo = 7.

 

4. Вычисляется значение секретного ключа Кc (расширенный алгоритм

 

Евклида, раздел 2.2) решением сравнения


 

o
Кс ≡ К -1


 

mod j(N) = 7-1


 

mod 20 ≡ 3.


 

5. Пересылается пользователю А пара чисел (N = 33, Кo = 7).

 

Действия пользователя А.

 

6. Шифруемое сообщение представляется как последовательность

 


целых чисел в диапазоне


0, 32 . Пусть букве 'А' соответствует число 1, букве


 

'Б' - число 2, букве 'В' - число 3. Тогда сообщение "ЭБФ" можно представить как последовательность чисел 30 02 21, то есть М1 = 30, М2 = 2, М3 = 21.

7. Текст, представленный в виде последовательности чисел M1, М2 и

 

М3, шифруется с использованием ключа Ко = 7 и N = 33, по формуле

 

Ci = МКо mod N = M7 mod 33.

 

Получается

 

С1 = 307 (mod 33) = 24, C2 =2 7 (mod 33) = 29, C3 = 217 (mod 33) = 21.

Пользователю В отправляется криптограмма C1C2C3 = 24, 29, 21.

 

Действия пользователя В.

 

8. Расшифровывается принятая криптограмма С1С2С3 по формуле

 

Mi = СiKc mod N = Ci3 mod 33 на основе секретного ключа Kc = 3.

 

Получается

 

M1 = 243 mod 33 = 13824 mod 33 = 30, M2 = 293 mod 33 = 24389 mod 33 = 2, M3 = 213 mod 33 = 9261 mod 33 = 21.

Таким образом, было восстановлено исходное сообщение: "ЭБФ". Дополнительные примеры для решения.

Зашифруйте и расшифруйте первые буквы своих инициалов с


 

помощью алгоритма RSA, используя свои параметры алгоритма.

 

Вопросы для самопроверки.

 

1. Для чего предназначен алгоритм RSA?

 

2. На сложности разрешения каких математических задач базируется

 


RSA?


 

3. Какие параметры формирует шифрующая сторона? Какие условия


 

накладываются на них?

 

4. Как вычисляется секретный ключ в RSA?

 

5. Какие параметры RSA являются открытыми и секретными?

 

6. Как производится шифрование информации?

 

7. Как производится расшифровка информации?

 

8. Какими особенностями обладает алгоритм RSA?

 

9. Поясните упрощенный алгоритм вычисления обратных элементов?

 

10. Какая тенденция по размеру используемых ключей наблюдается в мире?

11. Какие алгоритмы теории чисел и конечных полей используются в алгоритме RSA?

12. Какие математические операции используются в алгоритме RSA?

 

– Конец работы –

Эта тема принадлежит разделу:

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм асимметричного шифрования RSA

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование.
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от

Алгоритм Евклида
  Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Алгоритм РАЕ Кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел.
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0.
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Мультипликативная функция
  Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

Для возведение натуральных чисел по модулю в большие степени
    Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.     Имеется целое число

Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида   y = a x mod m , (1.1)   где a ÎN - основание степени,  

Сравнимость по модулю. Модулярная арифметика
    Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.   Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив

Свойства операций сравнения
    В криптографии существуют шифры и по простому модулю и по составному модулю.   Нужно знать когда применять простой модуль, а когда состав

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
  Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2 xn ≡ a mod p – квадратичный выч

ЭЛЕМЕНТЫ ТЕОРИИ КОНЕЧНОГО ПОЛЯ Простейшие алгебраические структуры
  Под алгебраической структурой будем понимать некоторое множество   S с одной или несколькими операциями на нем.   Пусть S х S обозначае

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9].
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

Pound; b£ n-1
  Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:     (1) bn-1≡ 1(mod n),  

Числа Кармайкла
  Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».     Заметим

Процедура получения устойчивых простых чисел
  1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t На основе этих двух операций получаем про

М-последовательности. ГПСЧ типа ЛРС1
  Опр ед ел ени е. Последовательностью над полем   GF ( p)   будем   назы

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

Раунд преобразования алгоритма RIJNDAEL
  RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги