Скляр Б. Цифровая связь (2003) (1151859), страница 219
Текст из файла (страница 219)
Однако если в заданном множестве не 10, а 100 возможных единиц, задача может стать вычислительно неосуществимой. Опишем задачу о рюкзаке через вектор рюкзака и вектор данных. Вектор рюкзака представляет собой л-кортеж разных целых чисел (аналогия множеству разных предметов содержимого рюкзака). аг а„а», ...,а„ Вектор данных — это л-кортеж двоичных символов. х =ха х,, ..., х„ 1, 188 кг 82 284 Рве. )4.19.
Задача о рюкзаке Рюкзак 5 — это сумма подмножества компонентов вектора рюкзака. 5 = ~а,х, = ах, где х, = О, 1 (14.40) 4=! Задачу о рюкзаке можно сформулировать следующим образом: при данном 5 и известгтом а определите х. Пример 14.6. Пример рюкзака Дано а = 1, 2, 4, 8, 16, 32 и 5 = ах =26. Найдите х. Рвв4евие Видно, что в этом примере х — это двоичлов представление 5. Преобразование из десятичного в двоичное окюкется более знакомым, если представить а как 24, 2', 2', 2', 24, 2', 2'.
Вектор данных х находится легко, поскольку а в этом примере является бмстровозрасьтающилп это означает, что каждый компонент набора л-кортежа а больше суммы предыдущих компонентов. Другими словами, а, >~а, 1=2,3, ...,л (14.41) 4! Если а является быстровозрастаюшим, то первый элемент х — х„= 1, если 5 2 а„(в противном случае, х„= 0); следующий элемент находится согласно соотношению 1 1 Ч КОиптО !АГтРм44 Г Отио! 4т! !ми 44ЯГО 4ями 1, если 5 — Ч~~ х,а, >а, х,= != +! О, в других случаях (14.42) где ! = л — 1, л — 2, ..., 1.
С помощью равенства (14М2) легко вычисляется х 010110. Пример 14.7. Пример рюкзака Дано а 171, 197, 459, 1191, 2410, 4517 и Я = ах 3798. Найдите х. Реигение Как и в примере 14.0, а является быстровозрастающим. Поэтому с помощью равенства (14.42) можно вычислить х. х = О!0110 14.5.5.
Криптосистема с открытым ключом, основанная на "лазейке" в рюкзаке Эта схема, известная также как схема Меркла-Хэллмана 115), основана на образовании вектора рюкзака, который не является быстровозрастаюшим. Следовательно, задача не является легкоразрешимой. При этом данная задача о рюкзаке обязательно включает лазейку, позволяющую авторизованным пользователям решить задачу. Сначала образуем быстровозрастающий л-кортеж. Затем выберем простое число М, при котором имеет место следующее неравенство: !! М> ~ а,'. (14.43) Выберем также случайное число Иг (1< И'<М) и сформируем И"!, удовлетворяющее следующему соотношению: 19% во модулю М = 1.
(14.44) Вектор а' и числа М, И' и И"' удерживаются скрытыми. Затем из элементов а' форми- руем а. (14.45) а, = И'а,' по модулю М Формирование а с использованием равенства (14.45) — это создание вектора рюкзака с лазейкой. Если нужно передать вектор х, то вначале х умножается на а, по дает чис- ло Б, которое передается через общедоступный канал.
С помощью равенства (14.45) 5 можно записать следующим образом: Я' = И" ~5 по модулю М = )т' ~ ~ (Ил,' по модулю М)я, по модулю М = !! !! Я=ах=ай а,х, = ~~~(Иа, помодулюМ)х, . (14.46) ! г=! !ы Авторизованный пользователь получает Я и, используя равенство (14.44), превращает его в У. =~~) (И' ~1Уа!'помодулю М)х, помодулю М= ю=! = ~~~а,'х, по модулю М = =~~> а,'х, (14.47) ю«! Поскольку авторизованный пользователь знает засекреченный быстровозрастающий вектор а', для отыскания х он может использовать У. 14.б.б.1. Использование схемы Меркла-Хеллмана Предположим, пользователь А желает создать общедоступную и конфиденциальную функции шифрования.
Сначала он рассматривает быстровозрастающий вектор а' = (171, 197, 459, 1191, 2410, 4517). х« а,' = 8945 г=1 Затем он выбирает простое число М, большее 8945, случайное число й', такое, что 1 ~ й'< М, и вычисляет и ', при котором й'й"' = 1 по модулю М. Пусть М = 9109 Пусть й' = 2251 скрыты тогда йl ! = 1388 После этого он образует вектор, который остаааяет "лазейку" в рюкзаке.
а, = а', 2251 по модулю 9109 а = 2343, б215, 3892, 2895, 5055, 2123 Пользователь А делает общедоступным вектор а, который, очевидно, не является быстровозрастающим. Предположим, что пользователь В желает послать сообщение пользователю А. Если х = 010110 — сообщение, которое нужно перелать, то пользователь В создает следующее число: 5 = ах = 14 165 и передает его пользователю А.
Пользователь А получает Я и превращает его в з . Я '= а 11 = й"'Я по модулю М = = 1388 141б5 помодулю9109= = 3798 Используя У = 3798 и быстровозрастающий вектор а', пользователь А легко находит х. Схема Меркла-Хэллмана сейчас считается взломанной (16), поэтому для реализации криптосистем с открытыми ключами используется алгоритм КБА (равно как и другие рассмотренные позднее).
943 !а Ч Кпиптппяптями и пт«пмтммм «п«ляямм боота Рг!часу Рпчасу, буквально: "весьма хорошая секретность" ) — это программа ретности, которая была создана Филиппом Циммерманом (РК41!р и опубликована в 1991 году как бесплатное программное обеспечеде-факто" стала стандартом для электронной почты и шифрования рсии 2.6 (наиболее широко используемая) оставалась неизменной вплоть до появления версии 5.0 (совместимой с версией 2.6). В табл.
14.9 приведены алгоритмы, используемые в версиях 2.6, 5.0 и более поздних. РОР версии 2.6 РОР версии 5.0 и более поздних Функция Используемый Используемый алгоритм 118! алгоритм 117! Н) ЕА Тройной" !)ЕЯ, САЯТ или Н)ЕА Шифрование сообщения е использова- нием алгоритма частного ключа с по- мощью ключа частного сеанса Шифрование ключа частного сеанса с помощью алгоритма частного ключа Цифровая подпись Хзщ-функция, используемая при соз- дании профиля сообщения лля цифро- вых подписей йбА или алгоритм Диффи- Хзллмана (вариант Элгемала) КБА и ()55 (от Х!ЯТ ) БНА- ! йбА йбА МО5 Как показано в табл. 14.9, РОР использует множество алгоритмов шифрования, включающих как схемы частного ключа, так и схемы открытого ключа.
При шифровании сообщения применяется алгоритм частного ключа (для каждого сеанса генерируется новый ключ сеанса). В качестве алгоритмов частного ключа, предлагаемых РОР, представлены Международный алгоритм шифрования данных (1и!егпайопа! Оеза!1па!1оп апг( Епгйгопгпепга! Аааос!а!юп — 1ОЕА), "тройной" ВЕБ и алгоритм САЯТ (названный в честь авторов Карлайла Адамса (Саг11з(е Адагпз) и Стэффорда Тевереса (бгайогд Тачагез) (19!). Для шифрования ключа каждого сеанса используется алгоритм открытого ключа. В качестве алгоритмов, использующих открытые ключи, РОР предлагает алгоритм КБА, описанный в разделе 14.5.3, и алгоритм Диффи-Хэллмана (О(Ше-Не!!шап).
Алгоритмы с открытыми ключами применяются также для создания цифровых подписей. РОР версии 5.0 использует алгоритм цифровой подписи (Р(я!га! Яйпашге А)йопгЬп — Р$А), заданный в стандартах цифровой подписи (!)1й!га! Яяпагцге Яапг(агд — 1)55) института Н(ЬТ. РОР версии 2.6 в своих цифровых подписях использует алгоритм КАЛА. Если имеющийся канал не защищен от изменений ключа, он более безопасен для использования алгоритма с ключом общего доступа. Для защищенного канала предпочтительно шифрование с частным ключом, поскольку это, как правило, лает лучшее быстродействие по сравнению с системами, использующими открытые ключи.
()(В(га! Явпагвге бгапдагб — Стандарт цифровой подписи, разработанный )Ч(5Т. )Чаг!опа! 1пьйщге ог бгапбагш апд Тесово!ову — Национальный институт стандартов и технологий США; отдел Министерства торговли США. олл Гняна 1л 1нисьооаяниеи гччнисЬоование Технология шифрования сообщения, применяемая РОР версии 2.6, изображена на рис. 14.20.
Перед шифрованием открытый текст сжимается с помощью 21Р- алгоритма. Система РОР использует Х1Р-метод, описанный Жаном-Лупом Гейли ()сап-Ьопр Оа!!у), Марком Элдером (Магй АЫег) и Ричардом Б. Уэльсом (К!с)загг! В. %а!ез) [181. Если сжатый текст короче несжатого, то шифроваться будет сжатый текст, в противном случае будет шифроваться несжатый. Небольшие файлы (приблизительно 30 символов для файлов АЗСП) нс выигрывают от сжатия.
К тому же, РРР распознает файлы, ранее сжатые с помощью распространенных технологий сжатия, таких как РКХ1Р, и не будет пытаться сжать их. Сжатие данных устраняет избыточные строки символов и приводит к более равномерному распределению символов. С помощью сжатия получаем более короткий файл для шифрования и дешифрования (что сокращает время, необходимое для шифрования, дешифрования и передачи файла). Сжатие также создаст препятствия некоторым криптоаналитическим атакам, использующим избыточность. Необходимо отметить, что сжатие файла должно предшествовать шифрованию (а не наоборот).
Почему стоит следовать этому правилу? Хороший алгоритм шифрования дает шифрованный текст с практически статистически равномерным распределением символов. Следовательно, если алгоритм сжатия данных следует после такого шифрования, он не будет давать никакого сжатия вообще.
Если некоторый шифрованный текст может быть сжат, то алгоритм шифрования, с помощью которого получен шифрованный текст, был неудачным. Алгоритм сжатия не должен обнаруживать избыточныс фрагменты в тексте, зашифрованном с помощью хорошего алгоритма. Как показано на рис.
14.20, РОР начинает шифрование файла с создания 128- битового ключа сеанса, используя генератор псевдослучайных чисел. Затем с помощью этого случайного ключа сеанса шифруется сжатый файл открытого текста, для чего применяется алгоритм частного ключа 1РЕА. После этого случайный ключ сеанса шифруется с помощью алгоритма открытого ключа КЗА; при этом используется открытый ключ получателя. Ключ сеанса, зашифрованный с помощью алгоритма КБА, и файл, зашифрованный с использованием алгоритма 1РЕА, посылаются получателю. Когда получателю нужно прочесть файл, вначале, с помощью алгоритма КЗА, дешифруется зашифрованный ключ сеанса. При этом используется частный ключ получателя. Затем дешифруется собственно шифрованный файл, при этом применяется дешифрованный ключ сеанса и алгоритм 1РЕА. После разархивации получатель может читать расшифрованный файл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
