|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[134] s = td/k mod n (4) Результатом является s = md mod n Это можно легко показать td - (mke)d - mdk (mod n), поэтому td/k = mdk/k - md (mod n). Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожиданными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей . 23.13Передача с забыванием В этом протоколе, предложенном Майклом Рабином (Michael Rabin) [1286], Алиса с вероятностью 50 процентов удается передать Бобу два простых числа, p и q. Алиса не знает, успешно ли прошла передача (См. раздел 5.5.) (Этот протокол можно использовать для передачи Бобу любого сообщения с 50-процентной вероятностью успешной передачи, если p и q раскрывают закрытый ключ RSA.) (1)Алиса посылает Бобу произведение двух простых чисел: n = pq. (2)Боб выбирает случайное число x, меньшее n и взаимно простое с n. Он посылает Алисе: a = x2 mod n (3)Алиса, зная p и q, вычисляет четыре квадратных корня a: x, n-x, у и n-y. Она случайным образом выбирает любой из этих корней и посылает его Бобу. (4)Если Боб получает у или n-у, он может вычислит наибольший общий делитель x+у и n, которым будет либо p, либо q. Затем, конечно же, n/p = q. Если Боб получает x или n-x, он не может ничего вычислить. У этого протокола может быть слабое место : возможна ситуация, когда Боб может вычислить такое число a, что при известном квадратном корне a он сможет все время раскладывать n на множители. 23.14Безопасные вычисления с несколькими участниками Этот протокол взят из [1373]. Алиса знает целое число i, а Боб - целое число j. Алиса и Боб вместе хотят узнать, что правильно - i<j или i>j, но ни Алиса, ни Боб не хочет раскрыть свое число партнеру. Этот особый случай безопасных вычислений с несколькими участниками (см. раздел 6.2) иногда называют проблемой миллионера Яо [162, 7]. В приводимом примере предполагается, что i и j выбираются из диапазона от 1 до 100. У Боба есть открытый и закрытый ключи. (1)Алиса выбирает большое случайное число x и шифрует его открытым ключом Боба. c = Eb(x) (2)Алиса вычисляет c-j и посылает результат Бобу. (3)Боб вычисляет следующие 100 чисел: у,, = DB(c-i+u), для 1<u<100 DB обозначает дешифрирование закрытым ключом Боба. Он выбирает большое случайное число p. (Размер p должен быть немного меньше x. Боб не знает x, но Алиса может легко сообщить ему размер x.) он вычисляет следующие 100 чисел: zu = (Vu mod p), для 1<u<100 Далее он проверяет, что для всех uv zu - > 2 и что для всех u 0 < zu < p1 Если это не так, то Боб выбирает другое простое число и пробует снова. (4)Боб посылает Алисе эту последовательность чисел, соблюдая их точный порядок: zl, z2, . . . zj, zj+1 + 1, zj+2+1, . . . z100+1, p (5)Алиса проверяет, конгруэнтен ли ,-ый член последовательности x mod p Если это так, она делает вывод, что ,<j В противном случае она решает, что ,> j. (6)Алиса сообщает Бобу свои выводы. Проверка, которую Боб выполняет на этапе (3), должна гарантировать, что ни одно число не появится дважды в последовательности, генерированной на этапе (4). В противном случае, если za = zb, Алиса узнает, что a < j < b. Недостатком этого протокола является то, что Алиса узнает результаты вычислений раньше Боба. Ничто не помешает ей завершить протокол на этапе (5), отказавшись сообщать Бобу результаты . Она даже может солгать Бобу на этапе (6). Пример протокола Пусть они используют RSA. Открытым ключом Боба является 7, а закрытым - 23. n = 55. Секретное число Алисы, равно 4, секретное число Боба, j - 2. (Предположим, что числа , и j могут принимать только значения 1, 2, 3 и 4.) (1)Алиса выбирает x = 39 и c = EB(39) = 19. (2)Алиса вычисляет c-,=19-4=15. Она посылает 15 Бобу. (3)Боб вычисляет следующие четыре числа: y1 = Db{15+1) =26 y2 = Db{15+2) = 18 y3 = Db{15+3) =2 y4 = Db{15+4) = 39 Он выбирает p = 31 и вычисляет: z1 = (26 mod 31) = 26 z2 = (18 mod 31) =18 z3 = (2 mod 31) = 2 Z4 = (39 mod 31) = 8 Он выполняет все проверки и убеждается, что последовательность правильна . (4)Боб посылает Алисе эту последовательность чисел, соблюдая их порядок : 26, 18, 2+1, 8+1, 31, т.е., 26, 18, 3, 9, 31 (5)Алиса проверяет, конгруэнтно ли четвертое число X mod p Так как 9 Ф 39 (mod 31 ), то , > j. (6)Алиса сообщает об этом Бобу. Этот протокол можно использовать для создания намного более сложных протоколов . Группа людей может проводить секретный аукцион по сети . Они логически упорядочивают себя по кругу и, с помощью попарных сравнений, определяют, кто предложил большую цену . Чтобы помешать людям уже изменять сделанные предложения в середине аукциона должен использоваться какой-то протокол вручения битов. Если аукцион проводится по голландской системе, то предложивший наивысшую цену получает предмет за предложенную цену . Если аукцион проводится по английской системе, то он получает предмет за вторую высшую цену. (Это может быть выяснено во время второго круга попарных сравнений .) Аналогичные идеи применимы при заключении сделок, переговорах и арбитраже. 23.15 Вероятностное шифрование Понятие вероятностного шифрования было изобретено Шафи Голдвассером (Shafi Goldwasser) и Сильвией Микали [624]. Хотя их теория позволяет создать самую безопасную из изобретенных криптосистем , ранняя реализации была неэффективной [625]. Но более поздние реализации все изменили. Идеей вероятностного шифрования является устранение утечки информации в криптографии с открытыми ключами. Так как криптоаналитик всегда может расшифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифротекст C = E(M), и он пытается получить открытый текст M, он может выбрать случайное сообщение M и зашифровать его: C = EK(M). Если C = C, то он угадал правильный открытый текст. В противном случае он делает следующую попытку . Кроме того, вероятностное шифрование позволяет избежать даже частичной утечки информации об ориг и-нальном сообщении. При использовании криптографии с открытыми ключами криптоаналитик иногда может узнать кое-что о битах: XOR 5-го, 17-го и 39-го битов равно 1 , и т.п.. При вероятностном шифровании остается скрытой и такая информация. Таким способом можно извлечь не много информации, но потенциально возможность криптоаналитика расшифровывать случайные сообщения вашим открытым ключом может создать определенные проблемы . Каждый раз, шифруя сообщение, криптоаналитик может извлечь немного информации . Никто не знает, насколько значительна эта информация. Вероятностное шифрование пытается устранить эту утечку. Цель этого метода состоит в том, чтобы ни в ы-числения, проводимые над шифротекстом, ни проверка любых других открытых текстов не смогли дать кри п-тоаналитику никакой информации о соответствующем откр ытом тексте. При вероятностном шифровании алгоритм шифромания является вероятностным, а не детерминированным . Другими словами, многие шифротексты при расшифровке дают данный открытый текст , и конкретный шифро-текст, используемый в любом конкретном шифровании, выбирается случайным образом . C1 = EKM), C2 =C3 =. . . Ci = M = Dk(C1) = Dk(C2) = Dk(C3) = . . . = ZMC) При вероятностном шифровании криптоаналитику больше не удастся шифровать произвольные открытые тексты в поисках правильного шифротекста. Для иллюстрации пусть у криптоаналитика есть шифротекст Ci = EKM). Даже если он праильно угадает M, полученный при шифровании EKM) результат будет совершенно другим шифротекстом C: Cj. Сравнивая Ci и Cj, он не может по их совпадению определить правильность своей д о-гадки. Это поразительно. Даже если у криптоаналитика есть открытый ключ шифрования, открытый текст и ши ф-ротекст, он не может без закрытого ключа дешифрирования доказать, что шифротекст является результатом шифрования конкретного открытого текста. Даже выполнив исчерпывающий поиск, он может доказать только, что каждый возможный открытый текст является возможным открытым текстом . В этой схеме шифротекст всегда будет больше открытого текста . Этого невозможно избежать, это является результатом того, что многие шифротексты расшифровываются в один и тот же открытый текст . В первой схеме вероятностного шифрования [625] шифротекст получался настолько больше открытого текста, что он был бе с-полезным. Однако Мануэль Блюм (Manual Blum) и Голдвассер (Goldwasser) получили эффективную реализацию вероятностного шифрования с помощью генератора псевдослучайных битов Blum Blum Shub (BBS), описанного в разделе 17.9 [199]. Генератор BBS основан на теории квадратичных остатков. Существуют два простых числа, p и q, конгруэнтных 3 по модулю 4. Это закрытый ключ. Их произведение, pq = n, является открытым ключом. (Запомните свои p и q, безопасность схемы опирается на сложность разложения n на множители.) Для шифрования сообщения M сначала выбирается случайное x, взаимно простое с n. Затем вычисляется x0 = x2 mod n x0 служит стартовой последовательностью для генератора псевдослучайных битов BBS, а выход генератора используется в качестве потокового шифра. Побитно выполняется XOR M с выходом генератора. Генератор выдает биты bi (младший значащий бит xi, где xi = xi-12 mod n), поэтому M=M1, M2, M3, . . . Mt c = M1 © b1, M2 © b2, M3 © b3, . . . Mt © bt где t - это длина открытого текста Добавьте последнее вычисленное значение, xt, к концу сообщения, и дело сделано. Расшифровать это сообщение можно только одним способом - получить x0 и с этой стартовой последовательностью запустить генератор BBS, выполняя XOR выхода с шифротекстом. Так как генератор BBS безопасен влево, значение xt бесполезно для криптоаналитика. Только тот, кому известны p и q, может расшифровать сообщение. Вот как на языке C выглядит алгоритм получения x0 из xt: int xO (int p, int q, int n, int t, int xt) { int a, b, u, v, w, z; /* мы уже знаем, что HOfl(p,q) == 1 */ (void)extended euclidian(p, q, &a, &b); |
Среды: 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 | ||