Скляр Б. Цифровая связь (2003) (1151859), страница 218
Текст из файла (страница 218)
Как и ранее, инициализация происходит с помощью известного входа 1о. При каждой итерации выход регистра сдвига используется как вход (нелинейного) блочного алгоритма шифрования Е,. Символ младшего Разряда на выходе Е, становится следующим символом ключа lг„н который используется в следующем символе сообщения т„ь Поскольку после нескольких первых итеРаций вход алгоритма зависит только от шифрованного текста, система является самосинхронизирующейся.
14 4 Паточное ~~~и~вооиинно Дешифрование Шифрование зо т, о, о, Рис 14 1б Шифрование в режиме обратной связи 14.5. Криптосистемы с открытыми ключами Понятие систем с открытыми ключами было введено в 1976 году Диффи (1л)(тзе) и Хэллманом (Не!1шап) (12]. В общепринятых криптосистемах аагоритм шифрования может быть обнаружен, поскольку защищенность системы зависит от сохранности ключа.
Один и тот же ключ применяется как для шифрования, так и для дешифрования. Криптосистемы с открытыми ключами используют два разных ключа: один — для шифрования, другой — для дешифрования. В таких криптосистемах общедоступными (без потери защищенности системы) могут быть не только алгоритм шифрования, но и ключ, применяемый для шифрования. Фактически это общедоступный каталог, подобный телефонному каталогу, который содержит ключи шифрования всех абонентов. Держатся в секрете только ключи дешифрования. Пример такой системы приведен на рис. 14.17.
Перечислим важные особенности криптосистемы с открытым ключом. А не Абонент В Ев пв Рис. 14. 17 Криптосистема с от»рытмм ключам 1. Алгоритм шифрования Е, и алгоритм дешифрования 1з» являются обратимыми преобразованиями открытого текста А4 или шифрованного текста С, определяемыми ключом К. 2. Для каждого ключа К алгоритмы Е» и О» легко вычисляемы.
3. Для каждого ключа К определение Р» из Е„вычислительно трудноосуществимо. Г тл 1!и и и пон» Л ттт винно Такая система обычно способна обеспечивать защищенность переговоров между пользователями, которые никогда ранее не встречались или не общались. Например, как показано на рис. 14.17, пользователь А может послать сообщение пользователю В, найдя ключ шифрования пользователя В в каталоге и используя алгоритм шифрования Е,.
Получив таким образом шифрованный текст С = Е,(М1, он передает его через общедоступный канал. Пользователь  — зто единственный человек, который может дешифровать сообщение С, чтобы в результате получилось М = Рв(С1, с помощью своего алгоритма дешифрования Ов. 14.5.1. Проверка подлинности подписи с использованием криптосистемы с открытым ключом Капал общего Пользование Ол Ев Каталог Дата Ед Каталог Рис. 14.18. Проверка подлинности подписи с использованием крипто- системы с открытым ключом таКК и и., 937 На рис. !4.18 изображено применение криптосистемы с открьпым ключом для проверки подлинности подписи.
Пользователь А "подписывает*' свое сообщение, используя свой алгоритм дешифрования О,, что лает Я= 0„(М1 = Е„'(М1. Затем для шифрования 5 он воспользуется алгоритмом шифрования Е, пользователя В и в результате получит сообщение С=Ее(Я = Е,(Е, '(М11, которое он передает через общедоступный канал. Когда пользователь В получает сообщение С, он сначала дешифрует его с помощью собственного алгоритма дешифрования Ре, что дает Ов(С)= Ег '(М1.
Затем он использует алгоритм шифрования пользователя А, в результате чего получает Ел(Е„г(МЦ = М. Если в результате получается вразумительное сообщение, оно точно было послано пользователем А, поскольку болыпе никто не знает секретного кода шифрования пользователя А, с помощью которого выполняется преобразование 5=О„(М1. Отметим, что сообщение 5 зависит и от сообщения, и от подписи, а зто означает, что не только В может быть уверен, что сообщения действительно приходят от А, но и А уверен, что никто, кроме В, не сможет прочесть это сообщение.
14.5.2. Односторонняя функция с "лазейкой" 14.5.3. Схема НЗА Сообщения в схеме Ривеста-Шамира-Адельмана (К)чеет-Б)тшп!г-Аде!щап — КБА) сначала представляются как целые числа из интервала (О, и — 1). Каждый пользователь выбирает собственное значение и и пару положительных целых чисел е и д описанным ниже способом. Пользователь помешает свой ключ шифрования, числовую пару (и, е), в общедоступный каталог. Ключ дешифрования состоит из числовой пары (и, д), в которой д держится в секрете.
Шифрование сообщения М и дешифрование шифрованного текста С определяются следующим образом: Шифрование: С = Е(М) = (М)' по модулю и Дешифрование: М= 11(С) = (С)епо модулю и (14.32) Это легко вычислить. Результатом каждой операции являются целые числа из интер- вала (О, и — 1). В схеме КБА и получается в результате перемножения двух больших ира- стых чисел р и д.
(!4.33) Несмотря на то что и общедоступно, р и д являются скрытыми из-за большой слож- ности в разложении и на множители. Затем определяется функция, называемая функ- цией Эйлера. ф(и) = (р — 1)(ф — 1) (14.34) Параметр ф(и) имеет интересное свойство [12): для любого целого Х из интервала (О, и — 1) и любого целого й имеет место следующее соотношение. Х = Хт~"~ по модулю и (14.35) Следовательно, если все остальные арифметические действия выполняются по модулю и, арифметические действия в степени выполняются по модулю ф(и). Затем случайным образом выбирается большое целое число д, являющееся взаимно простым с ф(и); это означает, что ф(и) и д не должны иметь общих делителей, отличных от 1.
Это записывается следующим образом. (14.36) НОД [ф(и), д) = 1 Г а я 1Л Н! ьпл я а пю~~иеьиииинии Криптосистемы с открытым ключом основаны на понятии односторонних функций с "лазейками". Определим односиюроннюю функцию как легко вычисляемую, для которой невозможно вычислить обратную. Рассмотрим, например, функцию у= х'+ 12хз+ 1О7х+ 123. Должно быть очевидно, что при данном х легко вычислить у, но при данном у относительно сложно вычислить х. Однасторониел функция с "лазейкой™ вЂ” это односторонняя функция, лля которой легко вычислить обратную, если известны некоторые особенности, используемые для создания функции. Как и лазейка, такие функции легко проходимы в одном направлении.
Обратный процесс без специальной информации занимает невероятно много времени. Понятие "лазейки" будет применено в разделе 14.5.5, когда будет обсуждаться схема Меркла-Хэллмана (МетИе-Нейптап), В данном случае НОД означает "наибольший общий делитель".
Этому условию будет удовлетворять любое простое число, большее наибольшего из (р, у), Далее находится целое е, 0<е< ф(л), еН по модулю ф(л) =1, (14.37) что, вследствие равенства (14.35), равносильно выбору е и Н, которые удовлетворяют следующему условию: Х = Х"~ по модулю л. (14.38) Следовательно, (14.39) Е(Р(Х)) = Р(Е(ХЯ = Х и возможно корректное дешифрование. Один из возможных способов взлома шифра при данном ключе (в, е) — это разложить п на множители р и д, вычислить ф(л) = (р — 1)(д — 1) и вычислить И из равенства (14.37). Все это, за исключением разложения л на множители, представляет собой простые действия. Схема ЙБА основывается на том, что два больших простых целых числа р и 9 легко выбрать и перемножить, но гораздо сложнее разложить на множители результат.
Следовательно, произведение, как часть ключа шифрования, может быть сделано общедоступным, в то время как множители, которые могут "разоблачить" ключ дешифрования, соответствующий ключу шифрования, остаются скрьпыми. Если длина каждого множителя составляет порядка 100 разрядов, умножение может быль выполнено в доли секунды, а изнурительное разложение на множители результата может потребовать миллиарды лет 12). 14.0.3.1. Использование схемы ВЗА Используя пример из работы 113), положим р = 47, д = 59. Следовательно, л = рд = 1773 и ф(в) = (р — 1)(9-1) = 2668.
Параметр И выбирается взаимно простым с ф(л). Например, выберем д = 157. Затем вычислим значение е следующим образом (подробности приведены в следующем разделе). ег по модулю ф(л) = 1 157е по модулю 2688 = 1 Следовательно, е = 17. Рассмотрим пример открытого текста Если заменить каждую букву двухразрядным числом из интервала (О1, 26), соответствукнцим ее позиции в алфавите, и закодировать пробел как 00, открытое сообщение можно записать следующим образом: 0920 1900 0112 1200 0718 0505 1100 2015 0013 0500 Каждый символ выражается целым числом из интервала (О, л — 1).
Позтому в данном примере шифрование может быть представлено в виде блоков по четыре разряда, так как это максимальное число разрядов, которое всегда дает число, меньшее л — 1 = 2772. Первые четыре разряда (0920) открытого текста шифруются следующим образом; С = (М)' по модулю л = (920)'~ по модулю 2773 = 948. Продолжая этот процесс для оставшихся разрядов открытого текста, получим следующее: 14 В Коиптосиг:т~ мы е от«пытимн ««очами 939 С= 0948 2342 1084 1444 2663 2390 0778 0774 0229 1655 тый текст восстанавливается с помощью ключа дешифрования. М = (С) 'и по модулю 2773 5.3.2.
Квк вычислить е я вычисления е используется разновидность алгоритма Евклида вычисления ф(п) и»ь Сначала вычисляем последовательность значений хь хь хь ..., где и), х, = г(, а х„, = х,, по модулю л„пока не будет получено х, = О. Тогда НОД(х,, ,. Для каждого х, вычисляются числа а, и Ь„при которых х, = а,х,+ Ь,т,. Если 1, то Ь»» — мультипликативное обратное к х, по модулю хь Если Ь,, — отриьное число, решением является Ь„» + ф(л). р 14.5.
Вычисление е с помощью»г* и ф(в) предыдущего примера, в котором р = 47, 9= 59, л = 2773 и аг выбрано равным !57, меннте алгоритм Евклида лля проверки, что е = 17. еиие Ь, у 2668 !57 !56 ! ! О ! -! О 1 !6 -!б ! !7 Здесь х»ы =х,, — у,х, а,,» = а, » — у,а, Ь„, =Ь,,-у,Ь, Следовательно, е = Ьз = 17. 14.5.4. Задача о рюкзаке Классическая задача о рюкзаке изображена на рис. 14.19. Рюкзак наполнен множеством предметов с указанием их веса в граммах. Зная вес наполненного рюкзака (шкала вссов градуирована так, что вес пустого рюкзака вычитается), нужно определить содержимое рюкзака. В этом простом примере решение легко найти методом проб и ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
