|
||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[244]
Рис. 33.4 Работа процедуры MODULAR-ExPONENTATION при а = 7, Ъ = 560 = (1000110000) и п = 561. Показаны значения переменных после очередного исполнения тела цикла for. Процедура возвращает ответ 1. 33.6-1 Найдите порядки всех элементов вНайдите наименьшую образующую этой группы и укажите индексы всех элементов этой группы. 33.7-2 Предложите алгоритм вычисления ab mod га, который обрабатывает биты двоичной записи Ь справа налево (от старших к младшим). 33.7-3 Объясните, как вычислить a~l mod га для а £ Z* при помощи процедуры Modular-Exponentation, если известно значение <р(п). 33.7. Криптосистема RSA с открытым ключом Криптосистемы с открытым ключом позволяют обмениваться секретными сообщениями по открытому каналу, не договариваясь заранее о ключе шифре; даже перехватив весь разговор от начала до конца, враг не узнает секретного сообщения. Кроме того, эти же методы позволяют добавлять к сообщению «цифровую подпись», удостоверяющую, что сообщение не фальсифицировано врагами. Проверить аутентичность подписи легко, а а подделать её крайне трудно. Понятно, что такие методы находят широкое применение в банках, при подписывании контрактов, денежных переводах и т.п. Криптосистема RSA основана на таком обстоятельстве: в настоящее время известны эффективные алгоритмы поиска больших простых чисел, но не известно сколько-нибудь приемлемого по времени работы алгоритма разложения произведения двух больших простых чисел на множители. Мы рассмотрим эти задачи (проверка простоты и разложение на множители) в разделах 33.8 и 33.9. Криптосистемы с открытым ключом. При использовании таких систем каждый участник переговоров имеет открытый ключ (public key) и секретный ключ (secret key). В системе RSA ключ состоит из пары целых чисел. Участников переговоров может быть несколько, но для примера мы будем говорить о переговорах Алисы (А) и Боба (В). Их открытые ключи мы будем обозначать Ра и Рв, а секретные - Sb и Sb- Каждый участник сам создаёт два своих ключа. Секретный ключ он хранит в тайне, а открытый сообщает остальным участникам (и вообще всем желающим, например, через газеты или Internet; открытые ключи всех заинтересованных лиц можно публиковать в специальных справочниках и т.п.). Обозначим через V множество всех возможных сообщений (например, это может быть множество всех битовых строк). Потребуем, чтобы каждый ключ задавал перестановку множества V, и через Ра() и Sa() будем обозначать перестановки, соответствующие ключам Алисы. Мы считаем, что каждая из перестановок Ра() и $а() может быть быстро вычислена, если только известен соответствующий ключ. Мы хотим, чтобы ключи одного участника задавали взаимно обратные перестановки, то есть чтобы M = SA(PA(M)),(33.37) и M = PA(SA(M)).(33.38) было выполнено для любого сообщения М £ V. Самое главное - чтобы никто, кроме Алисы, не мог вычислять функцию Sa() за разумное время; именно на этом основаны все полезные свойства криптосистемы, перечисленные выше. Потому-то Алиса и держит значение Sa в секрете: если кто-либо узнает её секретный ключ, он сможет расшифровывать адресованные ей сообщения, подделывать её подпись или перевирать сообщения, которые она отправляет от своего имени. Главная трудность при разработке криптосистем состоит в том, чтобы придумать функцию SaQ, Для которой трудно было бы найти быстрый способ вычисления, даже зная такой способ для обратной функции PaQ- Опишем процесс пересылки шифрованного сообщения. Допустим, Боб желает послать Алисе секретное сообщение. Это происходит так: •Боб находит Ра - открытый код Алисы (по справочнику или прямо от Алисы) •Боб зашифровывает своё сообщение М и посылает Алисе шифровку (ciphertext) С = Ра(М). •Алиса получает С и восстанавливает изначальное сообщение M = SA(C). Этот процесс показан на рис. 33.5. надписи: encrypt - шифрование communication channel - линия связи eavesdropper - злоумышленник decrypt - расшифровка Боб, Алиса Рис. 33.5 33.5 Шифрование с открытым ключом. Боб шифрует сообщение М с помощью функции Ра и получает шифровку С = Ра(М). Функции Sa() и Ра{) взаимно обратны, поэтому Алиса может восстановить исходное сообщение М по шифровке: М = Sa(C). Никто, кроме Алисы, не знает способа вычисления Sa (), поэтому сообщение М останется секретным, даже если злоумышленник подслушает С и знает Ра- sign - вычисление подписи verify - проверка подписи accept - сообщение подлинное Рис. 33.6 33.6 Цифровая подпись в системе с открытым ключом. Алиса подписывает своё сообщение М, прикладывая к нему цифровую подпись <т = Sa(M). Боб, получая от Алисы пару (М, <т), проверяет соотношение М = Ра(&)- Если оно выполняется, подпись и само сообщение подлинны. Теперь объясним, как снабдить сообщение электронной подписью. Пусть Алиса хочет послать Бобу ответ М, подписанный электронной подписью (рис. 33.6). •Алиса вычисляет электронную подпись (digital signature) а = Sa(M). •Алиса посылает Бобу пару (М,а), состоящую из сообщения и подписи. •Боб получает пару (М7, а) и убеждается в подлинности подписи, проверив равенство М = Ра(сг). Если участников переговоров много, будем считать, что каждое сообщение М должно начинаться с имени отправителя - прочтя его, можно узнать, чей ключ надо использовать для проверки. Если равенство выполняется, то можно быть уверенным в том, что сообщение действительно было послано отправителем и дошло в неизменённом виде. Если же равенство не выполнено, сообщение было повреждено помехами или фальсифицировано. Таким образом, цифровая подпись выполняет функции обычной. Подлинность цифровой подписи может проверить каждый, знающий открытый ключ Алисы. Прочитав сообщение Алисы, Боб может переслать другим участникам переговоров, и те тоже смогут убедиться в его подлинности. Например, подписанным документом может быть банковское поручение о перечислении денег со счёта Алисы на счёт Боба - и банк будет знать, что оно настоящее, а не фальсифицировано Бобом. При таком сценарии содержимое подписанного сообщения не |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||||||||||||||||||||||