Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм RSA.




Читайте также:
  1. Алгоритм безопасного хеширования SHA. Главный цикл алгоритма SHA.
  2. Алгоритм измерения температуры в прямой кишке
  3. Алгоритм измерения температуры тела пациенту
  4. Алгоритм морфологической характеристики эритроцитов.
  5. Алгоритм оказания помощи при клинической смерти
  6. Алгоритм освоения фазы
  7. Алгоритм построения графика
  8. Алгоритм проведения обеззараживания и мытья пробирок после работы с сывороткой, плазмой или мочой
  9. Алгоритм работы.
Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

Алгоритм RSA стоїть біля витоків джерел асиметричної криптографії. Він був запропонований трьома дослідниками-математиками Рональдом Рівестом (R. Rivest) , Аді Шаміром (A. Shamir) і Леонардом Адльманом (L. Adleman) у 1977-78 роках.

Першим етапом будь-якого асиметричного алгоритму є створення пари ключів: відкритого і закритого та поширення відкритого ключа “в усьому світі”. Для алгоритму RSA етап створення ключів складається з наступних операцій:

1. Вибираються два простих (!) числа p та q

2. Обчислюється їхній добуток n(=p*q)

3. Вибирається довільне число e (e<n), таке, що НОД(e,(p-1)(q-1))=1, тобто e повинно бути взаємно простим із числом (p-1)(q-1).

4. Методом Евкліда зважується в цілих числах (!) рівняння e*d+(p-1)(q-1)*y=1. Тут невідомими є змінні d та y – метод Евкліда саме і знаходить множину пар (d, y), кожна з яких є рішенням рівняння в цілих числах.

5. Два числа (e, n) – публікуються як відкритий ключ.

6. Число d зберігається в найсуворішій таємниці – це і є закритий ключ, що дозволить читати всі послання, зашифровані за допомогою пари чисел (e, n).

Як же здійснюється власне шифрування за допомогою цих чисел:

1. Відправник розбиває своє повідомлення на блоки, рівні k = [log2(n)] біт, де квадратні дужки позначають узяття цілої частини від дробового числа.

2. Подібний блок, як Ви знаєте, може бути інтерпретований як число з діапазону (0; 2k-1). Для кожного такого числа (назвемо його mi) обчислюється вираження ci=((mi)e)mod n. Блоки ci і є зашифроване повідомлення Їх можна спокійне передавати по відкритому каналі, оскільки операція підняття в степінь по модулі простого числа, є необоротною математичною задачею. Зворотна їй задача зветься “логарифмування в скінченому полі” і є на кілька порядків більш складною задачею. Тобто навіть якщо зловмисник знає числа e і n, те по ci прочитати вихідні повідомлення mi він не може ніяк, крім як повним перебором 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.



Насправді операції підняття до степені великих чисел досить трудомісткі для сучасних процесорів, навіть якщо вони здійснюються за оптимізованими за часом алгоритмами. Тому звичайно весь текст повідомлення кодується звичайним блоковим шифром (набагато більш швидким), але з використанням ключа сеансу, а от сам ключ сеансу шифрується саме асиметричним алгоритмом за допомогою відкритого ключа одержувача і поміщається в початок файлу.

 

Системи обробки графічної інформації: класифікація систем обробки графічної інформації; формати збереження графічної інформації; структура та формати графічного документа у середовищі Windows. Засоби Windows для роботи з графічною інформацією. Калькулятор. Початкові відомості про механізми обміну даними у середовищі операційної системи Windows. Службові програми.

Представлення даних на моніторі у графічному вигляді вперше було реалізовано всередині 50-х років для великих ЕОМ, що застосовувались в наукових і військових дослідженнях. Тепер, графічний спосіб відображення даних став дуже поширеним на усіх ПК. Графічний інтерфейс є необхідним майже для усіх програм, включаючи операційні системи.

Доверь свою работу кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

Дата добавления: 2015-09-15; просмотров: 6; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2022 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты