|
||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[114] в криптографии с открытыми ключами. Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению ? Более формально, дан набор значений Ml, M2, . . . , Mn и сумма S, вычислить значения bi, такие что S = blM1 + b2M2 + . . . + bnMn bi может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут. Например, массы предметов могут иметь значения 1, 5, 6, 11, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его масса была равна 24. В общем случае время, необходимое для решения этой проблемы, с ростом количества пре д-метов в куче растет экспоненциально . В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать сообщение как решение набора пр о-блем рюкзака. Предметы из кучи выбираются с помощью блока открытого текста, по длине равного количеству предметов в куче (биты открытого текста соответствуют значениям b), а шифротекст является полученной суммой. Пример шифротекста, зашифрованного с пом ощью проблемы рюкзака, показан на . Открытый текст 1 1 1 0 0 10 1 0 1 1 00 0 0 0 0 00 1 1 0 0 0 Рюкзак1 5 6 11 14 201 5 6 11 14 201 5 6 11 14 201 5 6 11 14 20 Шифротекст1+5+6+20=325+11+14=300=05+6=11 Рис. 19-1. Шифрование с рюкзаками Фокус в том, что на самом деле существуют две различные проблемы рюкзака , одна решается за линейное время, а другая, как считается, - нет. Легкую проблему можно превратить в трудную. Открытый ключ представляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для дешифриров а-ния сообщений. Закрытый ключ является легкой проблемой, давая простой способ дешифрировать сообщения . Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака . Сверхвозрастающие рюкзаки Что такое легкая проблема рюкзака? Если перечень масс представляет собой сверхвозрастающую последовательность, то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов . Например, последовательность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} - нет. Решение сверхвозрастающего рюкзака найти легко. Возьмите полный вес и сравните его с самым большим числом последовательности . Если полный вес меньше, чем это число, то его не кладут в рюкзак . Если полный вес больше или равен этому числу, то оно кладется в рюкзак . Уменьшим массу рюкзака на это значение и перейдем к следующему по величине числу последовательности . Будем повторять, пока процесс не закончится . Если полный вес уменьшится до нуля, то решение найдено. В противном случае , there isnt. Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес, 27, больше 18, поэтому 27 в рюкзак не кладется. вес, 13,меньше 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, получаем 5. Следующий вес, 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении . Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана , открытый текст, полученный из значения шифр о-текста 70, был бы равен 110101 . Не сверхвозрастающие, или нормальные, рюкзаки представляют собой трудную проблему - быстрого алг о-ритма для них не найдено. Единственным известным способом определить, какие предметы кладутся в рюкзак, является методическая проверка возможных решений, пока вы не наткнетесь на правильное . Самый быстрый алгоритм, принимая во внимание различную эвритсику , имеет экспоненциальную зависимость от числа во з-можных предметов. Добавьте к последовательности весов еще один член, и найти решение станет вдвое труднее. Это намного труднее сверхвозрастающего рюкзака, где, если вы добавите один предмет к последов а-тельности, поиск решения увеличится на одну операцию . Алгоритм Меркла-Хеллмана основан на этом свойстве . Закрытый ключ является последовательностью весов проблемы сверхвозрастающего рюкзака. Открытый ключ - это последовательность весов проблемы нормального рюкзака с тем же решением. Меркл и Хеллман, используя модульную арифметику, разработали способ пр е-образования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака. Создание открытого ключа из закрытого Рассмотрим работу алгоритма, не углубляясь в теорию чисел : чтобы получить нормальную последовател ь-ность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52}, и умножим по модулю m все значения на число n. Значение модуля должно быть больше суммы всех чисел последов а-тельности, например, 105. Множитель должен быть взаимно простым числом с модулем, например, 31. Нормальной последовательностью рюкзака будет 2*31 mod 105 = 62 3*31 mod 105 = 93 6*31 mod 105 = 81 13*31 mod 105 = 88 27*31 mod 105 = 102 52*31 mod 105 = 37 Итого - {62,93,81,88,102,37}. Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовател ь-ность рюкзака - открытым. Шифрование Для шифрования сообщение сначала разбивается на блоки, равные по длине числу элементов последов а-тельности рюкзака. Затем, считая, что единица указывает на присутствие члена последовательности, а ноль - на его отсутствие, вычисляем полные веса рюкзаков - по одному для каждого блока сообщения . Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использующее предыдущую последовательность рюкзака, будет происходить следующим образом : сообщение = 011000 110101 101110 011000 соответствует 93 + 81 = 174 110101 соответствует 62 + 93 + 88 + 37 = 280 101110 соответствует 62 + 81 + 88 + 102 = 333 Шифротекстом будет последовательность 174,280,333 Дешифрирование Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую посл е-довательность, а также значения n и m, использованные для превращения ее в нормальную последовательность рюкзака. Для дешифрирования сообщения получатель должен сначала определить n- , такое что n(n- )=1 (mod m). Каждое значение щифротекста умножается на n-1 mod m, а затем разделяется с помощью закрытого ключа, чтобы получить значения открытого текста. В нашем примере сверхвозрастающая последовательность - {2,3,6,13,27,52), m равно 105, а n - 31. Шифро-текстом служит 174,280,333. В этом случае n-1 равно 61, поэтому значения шифротекста должны быть умножены на 61 mod 105. 174*61 mod 105 = 9 = 3 + 6, что соответствует 011000 280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101 333*61 mod 105 = 48 = 2 + 6 + 13 + 27, что соответствует 101110 Расшифрованным открытым текстом является 011000 110101 101110. Практические реализации Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовател ь-ность не является сверхвозрастающей . Реальные рюкзаки должны содержать не менее 250 элементов . Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами , а длина модуля должна быть от 100 до 200 битов . Для получения этих значений практические реализации используют генераторы случайной последовательности . Вскрывать подобные рюкзаки при помощи грубой силы бесполезно . Если компьютер может проверять ми л-лион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10 46 лет. Даже мил- лион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую зве з- Безопасность метода рюкзака Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов . Сначала был раскрыт единственный бит открытого текста [725]. Затем Шамир показал, что в определенных обстоятельствах рюкзак может быть взломан [1415, 1416]. Были и другие достижения - [1428, 38, 754, 516, 488] - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel) [1418, 1419, 1421] обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной. Точные доказательства выходят за рамки этой книги, но их хор о-ший обзор можно найти в [1233, 1244]. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II [492, 494]. Варианты рюкзака После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны , как правило, с использованием одних и тех же криптографич е-ских методов, и их обломки были сметены со скоростного шоссе криптографии [260, 253, 269, 921, 15, 919, 920, 922, 366, 254, 263, 255]. Хороший обзор этих систем и их криптоанализ можно найти в [267, 479, 257, 268]. Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны . Криптосистема Lu-Lee [990, 13] была взломана в [20, 614, 873], ее модификация [507] также оказалась небезопасной [1620]. Вскрытия криптосистемы Goodman-McAuley приведены в [646, 647, 267, 268]. Криптосистема Pieprzyk [1246] была взломана аналогичным образом. Криптосистема Niemi [1169], основанная на модульных рюкзаках, взломана в [345, 788]. Новый, многостадийный рюкзак [747] пока еще не был взломан, но я не оптимистичен. Другим вариантом является [294]. Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest [356], несмотря на "специализированное вскрытие" [743] - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен [958]. Более того, учитывая легкость с которой пали все остальные варианты, д о-верять устоявшим пока вариантом, по видимому, неосторожно . Патенты Оригинальный алгоритм Меркла-Хеллмана запатентован в Соединенных Штатах [720] и в остальном мире (см. 18th). Public Key Partners (PKP) получила лицензию на патент вместе с другими патентами криптографии с открытыми ключами (см. раздел 25.5). Время действия патента США истечет 19 августа 1997 года. Табл. 19-1. Иностранные патенты на алгоритм рюкзака Меркла-
|
Среды: 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 | ||||||||||||||||||||||||||||||||||||||||||