|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[117] Сначала выбираются два простых числа p и q, конгруэнтных 3 mod 4. Эти простые числа являются закр ы-тым ключом, а их произведение n =pq - открытым ключом. Для шифрования сообщения M (M должно быть меньше n), просто вычисляется C = M2 mod n Дешифрирование сообщения также несложно, но немного скучнее . Так как получатель знает p и q, он может решить две конгруэнтности с помощью китайской теоремы об остатках . Вычисляется m1 = С+1)/4 mod p m2 = (p - C(p+1)/4) mod p m3 = C<q+1)/4 mod q m4 = (q - C(q+1)/4) mod q Затем выбирается целые числа a = q(q-1 mod p и b = p(p-1 mod q). Четырьмя возможными решениями являются: M1 = (am1 + bm3) mod n M2 = (am1 + bm4) mod n M3 = (am2 + bm3) mod n M4 = (am2 + bm4) mod n Один из четырех результатов, M1, M2, M3 и M4, равно M. Если сообщение написано по английски, выбрать правильное Mi нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи ), способа определить, какое Mi - правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка . Williams Хью Вильямс (Hugh Williams) переопределил схему Рабина, чтобы устранить эти недостатки [1601]. В его схеме p и q выбираются так, чтобы p = 3 mod 8 q = 7 mod 8 Кроме того, используется небольшое целое число, S, для которого J(S,N) = -1. (J - это символ Якоби - см. раздел I I .3). N и S опубликовываются. Секретным ключом является k, для которого k = 1/2 (1/4 (p - 1) (q - 1) + 1) Для шифрования сообщения M вычисляется c1, такое что J(M,N) =(-1)c1 . Затем вычисляется M = (Sc1 *M) mod N. Как и в схеме Рабина, C = M2 mod N. И c2 = M mod 2. Окончательным шифротекстом сообщения является тройка: (C, ci, c2) Для дешифрирования C, получатель вычисляет M" с помощью Ck =± M" (mod N) Правильный знак M" определяет c2. Наконец M= (Sc1 * (-1) c1 *M") mod N Впоследствии Вильямс улучшил эту схему в [1603, 1604, 1605]. Вместо возведения в квадрат открытого текста сообщения, возведите его в третью степени . Большие простые числа должны быть конгруэнтны 1 по модулю 3, иначе открытый и закрытый ключи окажутся одинаковыми . Даже лучше, существует только одна уникальная расшифровка каждого шифрования. Преимущество схем Рабина и Вильямса перед RSA в том, что доказано, что они также безопасны, как и ра з-ложение на множители. Однако перед вскрытием с выбранным шифротекстом они совершенно беззащитны . Если вы собираетесь использовать эти схемы для случаев, когда взломщик может выполнить такое вскрытие (например, алгоритм цифровой подписи, когда взломщик может выбирать подписываемые сообщения ), не за- бывайте использовать перед подписанием однонаправленную хэш-функцию . Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется ун и-кальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что си с-тема столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с практической точки зрения добавление хэшир ования не может ослабить систему. Другими вариантами схемы Рабина являются [972, 909, 696, 697, 1439, 989]. Двумерный вариант описан в [866, 889]. 19.6 ElGamal Схему EIGamal [518,519] можно использовать как для цифровых подписей, так и для шифрования, его без опасность основана на трудности вычисления дискретных логарифмов в конечном поле . Для генерации пары ключей сначала выбирается простое число р и два случайных числа, g и x, оба эти числа должны быть меньше р. Затем вычисляется y = gx mod р Открытым ключом являются y, g и р. И g, и р можно сделать общими для группы пользователей. Закрытым ключом является x. Подписи ElGamal Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с р-1. Затем вычисляется a = gk mod р и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении: M = (xa + kb) mod (р - 1) Подписью является пара чисел: a и b. Случайное значение к должно храниться в секрете. Для проверки подписи нужно убедиться, что yaab mod р = gM mod р Каждая подпись или шифрование EIGamal требует нового значения к, и это значение должно быть выбрано случайным образом. Если когда-нибудь Ева раскроет к, используемое Алисой, она сможет раскрыть закрытый ключ Алисы x. Если Ева когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же к, то она сможет раскрыть x, даже не зная значение к. Описание ElGamal сведено в Табл. 19-5. Подписи ElGamal Открытый ключ: рпростое число (может быть общим для группы пользователей) g<р (может быть общим для группы пользователей) y=gx mod р Закрытый ключ: x<р Подпись: квыбирается случайным образом, взаимно простое с р-1 a(подпись) =gk mod р b(подпись), такое что M = (xa + kb) mod (р - 1) Проверка: Подпись считается правильной, если yaab mod р = gM mod р Например, выберем р = 11 и g = 2, а закрытый ключ x = 8. Вычислим y = gx mod p = 28 mod 11 = 3 Открытым ключом являются y = 3, g = 2 иp = 11. Чтобы подписать M = 5, сначала выберем случайное число k=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем a = gk mod p = 29 mod 11 = 6 и с помощью расширенного алгоритма Эвклида находим b: M = (xa + kb) mod (p - 1) 5 = (8*6 + 9*b) mod 10 Решение: b = 3, а подпись представляет собой пару: a = 6 и b = 3. Для проверки подписи убедимся, что yaab mod p = gM mod p 3663 mod 11 = 25 mod 11 Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки подлинности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4). Шифрование EIGamal Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения M сначала выбирается случайное число к, взаимно простое с p - 1. Затем вычисляются a = g mod p b = yk M mod p Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к-ста. Для дешифрирования (a,b) вычисляется M = b/ax mod p Так как ax = gkx (mod p) и b/ax = yk M/ax = gxk M/ gkx = M (mod p), то все работает (см. 13-й). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1) за исключением того, что y - это часть ключа, а при шифровании сообщение умножается на yk. Табл. 19-6. Шифрование EIGamal Открытый ключ: pпростое число (может быть общим для группы пользователей) g<p (может быть общим для группы пользователей) y=gx mod/? Закрытый ключ: x<p Шифрование: kвыбирается случайным образом, взаимно простое с p-1 a(шифротекст) =gk mod p b(шифротекст)= yk M mod p Дешифрирование: M (открытый текст) = b/ax mod p Скорость Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918]. Табл. 19-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 | ||