«Цифровая подпись»

Скачать 362.09 Kb.

Название	«Цифровая подпись»
страница	2/7
Дата публикации	01.04.2015
Размер	362.09 Kb.
Тип	Документы

100-bal.ru > Информатика > Документы

1 2 3 4 5 6 7

1.1.Стандарт ассимметричного шифрования RSA

Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. В 1993 году метод RSA был обнародован и принят в качестве стандарта (PKCS #1: RSA Encryption standart). RSA можно применять как для шифрования/расшифрования, так и для генерации/проверки электронно-цифровой подписи.

1.1.1.Генерация ключей

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :

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

Вычисляется их произведение n(=p*q)

Выбирается произвольное число e (e
Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.
Два числа (e,n) – публикуются как открытый ключ.
Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

1.1.2.Шифрование/расшифрование

Как же производится собственно шифрование с помощью этих чисел :

Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение, и

их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число 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). Получаем (x^e^*^d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m :

((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.

1 2 3 4 5 6 7

Похожие:

	Электронная цифровая подпись. Понятие, виды и практика их применения Цифровая подпись предназначена для аутентификации лица, подписавшего электронный документ. Кроме этого, использование цифровой подписи...		Рабочая программа дисциплины цифровая схемотехника для специальности... Программа дисциплины “Цифровая схемотехника” составлена в соответствии с современным развитием цифровой техники
	Гетманов В. Г. Цифровая обработка сигналов. Учебное пособие Гетманов В. Г. Цифровая обработка сигналов. Учебное пособие. М.: Изд-во нияу мифи. 2010. 232 с		Минздравсоцразвития России Отдел производственной практики Кафедра детской стоматологии Дневник заполняется ежедневно и отражает содержание и объем работы студента. В конце записи каждого дня должна быть подпись врача...
	Цифровая школа ресурсный центр сетевого взаимодействия в муниципальной...		1. 2 Цифровая схемотехника Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Рабочая программа по дисциплине В. В цифровая обработка сигналов Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Номинация проекта Реализуется в рамках инновационного проекта гимназии №10 «Цифровая школа» (2009-2013 г.)
	Л. В. Ким (подпись) (Инициалы, Фамилия)		Л. В. Ким (подпись) (Инициалы, Фамилия)
	Программа по формированию навыков безопасного поведения на дорогах... Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов. Учеб пособие для вузов. 2-е изд., перераб и доп. М		Программа испытаний на кафедре когнитивных технологий Направление... Сортировки за линейное время. Сортировка подсчётом. Цифровая сортировка. Сортировка «вычерпыванием»
	Программа по формированию навыков безопасного поведения на дорогах... Технологии: компьютер, проекционная система, мультимедийный комплекс, принтер, цифровая камера, сканер, при подготовке домашнего...		А. Э. Фотиади (подпись) (фио) Примерной основной образовательной программе высшего профессионального образования
	Подпись Закона Российской Федерации «Об образовании» проводится промежуточная аттестация, в 2-4, 5-8, 10—х классах школы		Л. В. Ким (подпись) (Инициалы, Фамилия) Русский анархизм о политике и государстве (М. А. Бакунин, П. Л. Лавров, П. А. Кропоткин)

Школьные материалы