Основы теории принятая статистических решений 1051 80 страница

14.4. Поточное шифрование

Ранее мы определили разовое заполнение как систему шифрования со случайным од­норазовым ключом, который обеспечивает безусловную защищенность. Реализовать разовое поточное заполнение можно с использованием действительно случайного по­тока ключей (ключевая последовательность никогда не повторяется). Таким образом, совершенная секретность может достигаться для бесконечного числа сообщений, так как каждое сообщение шифруется с помощью разных частей случайного ключевого

Л А Л. Плтлиипо 1ммгЬг\г\п!Эим£1 "i
потока. Развитие схем поточного шифрования — это попытка имитации схем одно­моментного заполнения. Большой упор делается на генерации ключевых потоков, ко­торые должны выглядеть случайными. Реализовать такие последовательности можно с помощью соответствующих алгоритмов. Названная технология поточного шифрова­ния использует псевдослучайные последовательности; их название отражает тот факт, что они выглядят случайными для случайного наблюдателя. Статистические свойства двоичных псевдослучайных последовательностей подобны получаемым при случайном подбрасывании симметричной монеты. В то же время, разумеется, эти последователь­ности являются детерминистическими (см. раздел 12.2). Данные технологии популяр­ны, поскольку алгоритмы шифрования и дешифрования воплощаются с использова­нием регистров сдвига с обратной связью. На первый взгляд может показаться, что поточный псевдослучайный ключ может обеспечивать ту же защищенность, что и ме­тод одномоментного заполнения, поскольку период последовательности, порожденной линейным регистром сдвига, составляет 2^я ~¹ бит, где п — количество разрядов в реги­стре. Если псевдослучайная последовательность воплощается с помощью 50- разрядного регистра и дискретности в 1 МГц, последовательность будет повторяться каждые 2⁵⁰ - 1 микросекунды, или каждые 35 лет. В эпоху больших интегральных схем совсем несложно реализовать схему с 100 разрядами. В этом случае последователь­ность будет повторяться каждые 4 х 10¹⁶ лет. Следовательно, можно предположить, что поскольку псевдослучайная последовательность не повторяется в течение такого длительного периода, она может казаться действительно случайной и давать совер­шенную секретность. Но все же существует одно важное отличие псевдослучайной последовательности от действительно случайной последовательности, используемой в методе одномоментного заполнения. Псевдослучайная последовательность генериру­ется алгоритмом. Таким образом, если известен алгоритм, то известна и сама после­довательность. В разделе 14.4.2 будет показано, что из-за этой особенности схема шифрования, которая использует линейный регистр сдвига с обратной связью, слиш­ком уязвима к атаке известного открытого текста.

14.4.1. Пример генерирования ключа с использованием линейного регистра сдвига с обратной связью

В технологии поточного шифрования для генерации псевдослучайной ключевой по­следовательности обычно используются регистры сдвига. Регистр сдвига может быть превращен в генератор псевдослучайной последовательности путем введения контура обратной связи, который вычисляет новый элемент для первого разряда, основываясь на предыдущих п элементах. Говорят, что регистр является линейным, если линейна операция, производимая в контуре обратной связи. В разделе 12.2 мы уже рассматри­вали пример генератора псевдослучайной последовательности. На рис. 14.13 этот ге­нератор приведен повторно. В данном случае разряды регистра удобно нумеровать так, как показано на рис. 14.13, где п =4, а выходы разрядов 1 и 2 суммируются по модулю 2 (линейная операция) и передаются обратно на разряд 4. Если начальное со­стояние разрядов (х₄, х₃, х₂, х,) — это 1000, то следующие состояния будут выглядеть как 1000, 0100, 0010, 1001, 1100 и т.д. Выходная последовательность составлена из би­тов, снимаемых с крайнего правого разряда регистра, т.е. 111101011001000, где край­ний правый бит в последовательности является самым ранним, а крайний левый — наиболее поздним. При данном произвольном n-разрядном линейном регистре сдвига с обратной связью выходная последовательность в конечном счете периодична.

  Рис. 14.13. Пример линейного регистра сдвига с обратной связью

14.4.2. Слабые места линейных регистров сдвига с обратной связью

Схема шифрования, в которой для порождения ключевого потока применяются ли­нейные регистры сдвига с обратной связью (linear feedback shift register — LFSR), яв­ляется очень уязвимой по отношению к атакам. Чтобы определить отводы обратной связи, начальное состояние регистра и всю последовательность кода, криптоаналитику требуется всего 2п бит открытого текста и соответствующий им шифрованный текст. Как правило, 2п намного меньше периода 2"- 1. Проиллюстрируем эту уязвимость с помощью примера регистра, изображенного на рис. 14.13. Пусть криптоаналитику, который ничего не знает о внутренних связях регистра, удалось получить 2п = 8 бит шифрованного текста и их открытый эквивалент.

Открытый текст: 01010101 Шифрованный текст: 00001100

Здесь крайний правый бит получен первым, а крайний левый — последним.

Чтобы получить фрагмент ключевого потока 01011001 (рис. 14.14), криптоана­литик складывает обе последовательности по модулю 2. Ключевой поток показы­вает содержание регистров в различные моменты времени. Крайние правые четы­ре ключевых бита показывают содержание регистра сдвига в момент t_{. Если по­следовательно “сдвигать” эту четверку на один символ влево, то получим содержимое регистра в моменты t₂, t₃, f₄. Используя линейную структуру регистра сдвига, можно записать следующее:

g[10]x₄ + £3*3 + gix₂ + g Л = *5- (14.27)

Здесь х₅ — цифра, которая через контур обратной связи подана обратно на вход, а gi (= 1 или 0) определяет i-e соединение обратной связи. Таким образом, изучая содержание регистра в четыре момента времени, изображенных на рис. 14.14, можно написать следующие четыре уравнения с четырьмя неизвестными.

^(1) + Ы0) + Ы0) + Ы1)=1

#4(1) + £з(1) + £г(0) + Si(0) ⁼ 0 П4 28t

s4(0) + g₃(i) + s2(i) + si(0) = i ¹ ‘ ^;

5₄(l) + 53(0) + g2(l) + Sid) = 0

Решение уравнений (14.28), соответствующих регистру, изображенному на рис. 14.13, яв­ляется gi = l, #2=1. £з = 0, £₄ = 0. Таким образом, криптоаналитик узнал связи регистра, а также его начальное состояние в момент t_x. Следовательно, он может узнать последова­тельность в любой момент времени [3]. Обобщив этот пример на любой регистр сдвига с п разрядами, можно переписать уравнение (14.27) следующим образом:

*„₊1=!>*,• (¹⁴-²⁹> i = 1

Ключевой поток

Рис. 14.14. Пример уязвимости линейного регистра сдвига с обратной связью Уравнение (14.29) можно записать в матричной форме.

х = Xg,

где

	^xn + l		Si
	Хп + 2
X =		g =
	. ^Х2п.		_

*2 *2 Х₂ Х₃

... X,

X =

Можно показать [3], что столбцы X линейно независимы; таким образом, матрица X невырождена (ее определитель отличен от нуля) и имеет обратную. Следовательно,

g = X^_1x (14.31)

Обращение матрицы требует порядка и³ операций и, таким образом, легко выполняется на компьютере для любого разумного значения п. Например, если п = 100, то п³ = 10⁶, и ком­пьютеру со скоростью работы одна операция за 1 мкс для обращения матрицы понадобит­ся 1 с. Слабость регистра сдвига с обратной связью обусловлена линейностью уравнения

л «а л
(14.31). Использование нелинейной обратной связи в регистре сдвига делает задачу криптоа­налитика гораздо сложнее, если не вычислительно невозможной.

14.4.3. Синхронные и самосинхронизирующиеся системы поточного шифрования

Системы поточного шифрования можно разделить на синхронные и самосинхрони­зирующиеся. В первых ключевой поток генерируется независимо от сообщения; так что потеря символа во время передачи неизбежно требует повторной синхро­низации передачи и генераторов ключей приемника. Синхронный поточный шифр изображен на рис. 14.15. Начальное состояние генератора ключа инициали­зируется с помощью известного входа /₀. Шифрованный текст получается путем сложения по модулю 2 i-го символа ключа к, и i-го символа сообщения т,. Такие синхронные шифры обычно создаются для смешения (см. раздел 14.3.1), но не диффузии. Иными словами, шифрование символа не распространяется вдоль не­которого блока сообщения. По этой причине синхронные поточные шифры не имеют накопления ошибки.

Дешифрование

&

Рис. 14.15. Синхронный поточный шифр

При самосинхронизирующемся поточном шифре каждый ключевой символ опреде­ляется из фиксированного числа п предшествующих символов шифрованного текста (отсюда и название обратная связь по шифру). В таких системах происходит следую­щее: если символ шифрованного текста теряется во время передачи, ошибка накапли­вается для п символов, но после получения п верных символов шифрованного текста система восстанавливается.

В разделе 14.1.4 приводился пример обратной связи для шифрования с помощью автоматического ключа Вигнера. Показывалось, что преимуществом такой системы является: (1) генерация неповторяющегося ключа и (2) диффузия статистик открытого сообщения в шифрованном тексте. В то же время был и недостаток — ключ прояв­лялся в шифрованном тексте. Этой проблемы можно избежать, если при получении ключа пропустить символы шифрованного текста через нелинейный блок шифрова­ния. На рис. 14.16 изображен регистр сдвига генератора ключа, работающий в режиме обратной связи по шифру. Каждый выходной символ шифрованного текста с, (образованный путем сложения по модулю 2 символа сообщения т, и символа ключа к,) подается обратно на вход регистра сдвига. Как и ранее, инициализация происходит с помощью известного входа /₀. При каждой итерации выход регистра сдвига исполь­зуется как вход (нелинейного) блочного алгоритма шифрования Е_в. Символ младшего разряда на выходе Е_в становится следующим символом ключа к₁₊₁, который использу­ется в следующем символе сообщения m_l+i. Поскольку после нескольких первых ите­раций вход алгоритма зависит только от шифрованного текста, система является са- мосинхронизирующейся.

Рис 14 16 Шифрование в режиме обратной связи

14.5. Криптосистемы с открытыми ключами

Понятие систем с открытыми ключами было введено в 1976 году Диффи (Diffie) и Хэллманом (Heilman) [12]. В общепринятых криптосистемах алгоритм шифрования может быть обнаружен, поскольку защищенность системы зависит от сохранности ключа. Один и тот же ключ применяется как для шифрования, так и для дешифрова­ния. Криптосистемы с открытыми ключами используют два разных ключа: один — для шифрования, другой — для дешифрования. В таких криптосистемах общедоступными (без потери защищенности системы) могут быть не только алгоритм шифрования, но и ключ, применяемый для шифрования. Фактически это общедоступный каталог, по­добный телефонному каталогу, который содержит ключи шифрования всех абонентов. Держатся в секрете только ключи дешифрования. Пример такой системы приведен на рис. 14.17. Перечислим важные особенности криптосистемы с открытым ключом.

Абонент Л Абоненте   Рис. 14.17 Криптосистема с открытым ключом

1. Алгоритм шифрования Е_к и алгоритм дешифрования D_K являются обратимыми преобразованиями открытого текста М или шифрованного текста С, определяе­мыми ключом К.

2. Для каждого ключа К алгоритмы Е_к и D_K легко вычисляемы.

3. Для каждого ключа К определение D_K из Е_к вычислительно трудноосуществимо.

Г no do ЛЛ I I \л nai I ИлгЬпгшЯНИР

Такая система обычно способна обеспечивать защищенность переговоров между пользователями, которые никогда ранее не встречались или не общались. Например, как показано на рис. 14.17, пользователь А может послать сообщение пользователю В, найдя ключ шифрования пользователя В в каталоге и используя алгоритм шифрова­ния Е_в. Получив таким образом шифрованный текст С = Е_В(М), он передает его через общедоступный канал. Пользователь В — это единственный человек, который может дешифровать сообщение С, чтобы в результате получилось M = D_B(Q, с помощью сво­его алгоритма дешифрования D_B.

14.5.1. Проверка подлинности подписи с использованием криптосистемы с открытым ключом

На рис. 14.18 изображено применение криптосистемы с открытым ключом для проверки подлинности подписи. Пользователь А “подписывает” свое сообщение, используя свой алгоритм дешифрования D_A, что дает S = D_A(M) = Е_А\М). Затем для шифрования S он вос­пользуется алгоритмом шифрования Е_в пользователя бив результате получит сообщение С = E_H(S) = Е_В\Е_Л~\М)}, которое он передает через общедоступный канал. Когда пользователь В получает сообщение С, он сначала дешифрует его с помощью собственного алгоритма дешифрования D_B, что дает D_B(Q = Е_А~\М). Затем он использует алгоритм шифрования пользователя А, в результате чего получает Е_А[Е_А\М)] - М.

Если в результате получается вразумительное сообщение, оно точно было послано пользователем А, поскольку больше никто не знает секретного кода шифрования пользователя А, с помощью которого выполняется преобразование S = D_A(M). Отме­тим, что сообщение S зависит и от сообщения, и от подписи, а это означает, что не только В может быть уверен, что сообщения действительно приходят от А, но и Л уве­рен, что никто, кроме В, не сможет прочесть это сообщение.

А А  

В В   Рис. 14.18. Проверка подлинности подписи с использованием крипто­системы с открытым ключом

14.5.2. Односторонняя функция с “лазейкой”

Криптосистемы с открытым ключом основаны на понятии односторонних функций с “лазейками”. Определим одностороннюю функцию как легко вычисляемую, для которой невозможно вычислить обратную. Рассмотрим, например, функцию у = л⁵ + 12л³ + 107.x + 123. Должно бьггь очевидно, что при данном х легко вычислить у, но при данном у относительно сложно вычислить х. Односторонняя функция с “лазейкой” — это одно­сторонняя функция, для которой легко вычислить обратную, если известны некоторые особенности, используемые для создания функции. Как и лазейка, такие функции легко проходимы в одном направлении. Обратный процесс без специальной информации за­нимает невероятно много времени. Понятие “лазейки” будет применено в разде­ле 14.5.5, когда будет обсуждаться схема Меркла-Хэллмана (Merkle-Hellman).

14.5.3. Схема RSA

Сообщения в схеме Ривеста-Шамира-Адельмана (Rivest-Shamir-Adelman — RSA) сна­чала представляются как целые числа из интервала (0, п - 1). Каждый пользователь выбирает собственное значение п и пару положительных целых чисел ей d описан­ным ниже способом. Пользователь помещает свой ключ шифрования, числовую пару (и, е), в общедоступный каталог. Ключ дешифрования состоит из числовой пары (п, d), в которой d держится в секрете. Шифрование сообщения М и дешифрование шифро­ванного текста С определяются следующим образом:

Шифрование: С = Е(М) = (М)^е по модулю п Дешифрование: М = D(Q = (Cf по модулю п

Это легко вычислить. Результатом каждой операции являются целые числа из интер­вала (0, п - 1). В схеме RSA п получается в результате перемножения двух больших про­стых чисел р и q.

n-pq (14.33)

Несмотря на то что п общедоступно, р и q являются скрытыми из-за большой слож­ности в разложении п на множители. Затем определяется функция, называемая функ­цией Эйлера.

ф(и) = (р-1)(<7-1) (14.34)

Параметр ф(п) имеет интересное свойство [12]: для любого целого X из интервала (О, п - 1) и любого целого к имеет место следующее соотношение.

X = ⁺¹ по модулю п (14.35)

Следовательно, если все остальные арифметические действия выполняются по моду­лю п, арифметические действия в степени выполняются по модулю ф(п). Затем слу­чайным образом выбирается большое целое число d, являющееся взаимно простым с ф(и); это означает, что ф(п) и d не должны иметь общих делителей, отличных от 1. Это записывается следующим образом.

НОД [фОО, d] = 1 (14.36)

Плава 1A 11 li/irhnr\D£iLJi/io i/i not I иигЬпппяшир»

В данном случае НОД означает “наибольший общий делитель”. Этому условию будет удовлетворять любое простое число, большее наибольшего из (р, q). Далее находится целое е, 0 < е < ф(и),

ed по модулю ф(и) =1, (14.37)

что, вследствие равенства (14.35), равносильно выбору end, которые удовлетворяют следующему условию:

X = X^е* по модулю п. (14.38)

Следовательно,

E[D(X)] = D[E(X)] = X (14.39)

и возможно корректное дешифрование. Один из возможных способов взлома шифра при данном ключе (п, е) — это разложить п на множители р и q, вычислить ф(и) = (р - 1)(<7 - 1) и вычислить d из равенства (14.37). Все это, за исключением разложения п на множители, представляет собой простые действия.

Схема RSA основывается на том, что два больших простых целых числа р и q легко вы­брать и перемножить, но гораздо сложнее разложить на множители результат. Следова­тельно, произведение, как часть ключа шифрования, может быть сделано общедоступным, в то время как множители, которые могут “разоблачить” ключ дешифрования, соответст­вующий ключу шифрования, остаются скрытыми. Если длина каждого множителя состав­ляет порядка 100 разрядов, умножение может быть выполнено в доли секунды, а изнури­тельное разложение на множители результата может потребовать миллиарды лет [2].

14.5.3.1. Использование схемы RSA

Используя пример из работы [13], положим р = 47, q = 59. Следовательно, п = pq = 1773 и ф(и) =(р~ 1)01 ~ 1) = 2668. Параметр d выбирается взаимно простым с ф(и). На­пример, выберем d = 157. Затем вычислим значение е следующим образом (подробности приведены в следующем разделе).

ed по модулю ф(п) = 1 157е по модулю 2688 = 1 Следовательно, е = 17. Рассмотрим пример открытого текста.

ITS ALL GREEK ТО ME

Если заменить каждую букву двухразрядным числом из интервала (01, 26), соответст­вующим ее позиции в алфавите, и закодировать пробел как 00, открытое сообщение можно записать следующим образом:

0920 1900 0112 1200 0718 0505 1100 2015 0013 0500

Каждый символ выражается целым числом из интервала (0, п -1). Поэтому в данном при­мере шифрование может быть представлено в виде блоков по четыре разряда, так как это максимальное число разрядов, которое всегда дает число, меньшее п -1 = 2772. Первые че­тыре разряда (0920) открытого текста шифруются следующим образом:

С = {М)‘ по модулю п = (920)¹⁷ по модулю 2773 = 948.

Продолжая этот процесс для оставшихся разрядов открытого текста, получим следующее:

Открытый текст восстанавливается с помощью ключа дешифрования.

М = (С)'⁵⁷ по модулю 2773

14.5.3.2. Как вычислить е

Для вычисления е используется разновидность алгоритма Евклида вычисления НОД ф(я) и d. Сначала вычисляем последовательность значений х₀, х_ь х₂,..., где Хо = ф(гс), х, = d, а х, ₊ ] = х, _ 1 по модулю х„ пока не будет получено х_к - 0. Тогда НОД(дг₀, x_t) = х_к_ i. Для каждого х, вычисляются числа а, и Ь„ при которых х,- a,x_Q + bjc,. Если x_t_i = 1, то — мультипликативное обратное к х, по модулю х₀. Если Ь_к-_Х — отри­цательное число, решением является b_k. _t +ф(п).

Пример 14.5. Вычисление е с помощью d и ф(п)

Для предьщущего примера, в котором р = 47, q = 59, п = 2773 и d выбрано равным 157, примените алгоритм Евклида для проверки, что е = 17.

Решение

i__________ х, а, b, V;_

0 2668 1 0

1 157 0 1 16

2 156 1 -16 1

3 1 -1 17

Здесь

^xi + i =^х,-1~У,х, ■ ^ai + l ~^ai-1 ~ Ух^а1 b_{l +} j

Следовательно,

e = bj= 17.

14.5.4. Задача о рюкзаке

Классическая задача о рюкзаке изображена на рис. 14.19. Рюкзак наполнен множест­вом предметов с указанием их веса в граммах. Зная вес наполненного рюкзака (шкала весов градуирована так, что вес пустого рюкзака вычитается), нужно определить со­держимое рюкзака. В этом простом примере решение легко найти методом проб и ошибок. Однако если в заданном множестве не 10, а 100 возможных единиц, задача может стать вычислительно неосуществимой.

Опишем задачу о рюкзаке через вектор рюкзака и вектор данных. Вектор рюкзака представляет собой я-кортеж разных целых чисел (аналогия множеству разных пред­метов содержимого рюкзака).

а = а\, а₂, ■■■, а_п Вектор данных — это л-кортеж двоичных символов.

X = Jtj, х₂,..., х_п

Л А II ||4/Кгм-кп^имА \л nAllll<l«f«nnOOUMO

  132 56 82 Рис. 14.19. Задача о рюкзаке Рюкзак S — это сумма подмножества компонентов вектора рюкзака.

S = х, = ах, где х, = 0,1

i = i

Задачу о рюкзаке можно сформулировать следующим образом: при данном S и из­вестном а определите х.

Пример 14.6. Пример рюкзака

Дано а = 1, 2, 4, 8, 16, 32 и S = ах =26. Найдите х.

Решение

Видно, что в этом примере х — это двоичное представление S. Преобразование из десятич­ного в двоичное окажется более знакомым, если представить а как 2°, 2¹, 2², 2\ 2\ 2⁵, 2⁶. Вектор данных х находится легко, поскольку а в этом примере является быстровозрастаю- щим; это означает, что каждый компонент набора л-кортежа а больше суммы предыдущих компонентов. Другими словами,

а,>^а_; 2 = 2,3,..., л (14.41)

;=i

Если а является быстровозрастающим, то первый элемент х — х„ = 1, если S>a_n(в против­ном случае, х_п = 0); следующий элемент находится согласно соотношению

14 S ^ПМПТПГМГТРМк! п ГЛ-к'ПиПЧ-JMM к'ПШЧЯШШ

1, ₍₁₄.₄₂₎

О, в других случаях где / = п - 1, п - 2,1. С помощью равенства (14.42) легко вычисляется х = 010110.

Пример 14.7. Пример рюкзака

Дано а = 171, 197, 459, 1191, 2410, 4517 и S = ах = 3798. Найдите х.

Решение

Как и в примере 14.6, а является быстровозрастающим. Поэтому с помощью равенства (14.42) можно вычислить х.

х = 010110

14.5.5. Криптосистема с открытым ключом, основанная на “лазейке” в рюкзаке

Эта схема, известная также как схема Меркла-Хэллмана [15], основана на образова­нии вектора рюкзака, который не является быстровозрастающим. Следовательно, за­дача не является легкоразрешимой. При этом данная задача о рюкзаке обязательно включает лазейку, позволяющую авторизованным пользователям решить задачу.

Сначала образуем быстровозрастающий л-кортеж. Затем выберем простое число М, при котором имеет место следующее неравенство:

П

М>^а{. (14.43)

Выберем также случайное число W ([ <W<M) и сформируем W⁴, удовлетворяющее следующему соотношению:

WW^{ по модулю М = 1. (14.44)

Вектор а' и числа М, W и W⁴ удерживаются скрытыми. Затем из элементов а' форми­руем а.

а, = Waf по модулю М (14.45)

Формирование а с использованием равенства (14.45) — это создание вектора рюкзака с лазейкой. Если нужно передать вектор х, то вначале х умножается на а, что дает чис­ло S, которое передается через общедоступный канал. С помощью равенства (14.45) S можно записать следующим образом:

п П '

S=ах=^У}'а₁х₁ = ^(Wa, по модулю M)x_t. (14.46)

1=1 (=1

Авторизованный пользователь получает S и, используя равенство (14.44), превращает его в S'.

П

S’ = W^_1S по модулю М = W~^[11] у¹ (Wal по модулю М)х, по модулю М =

(= 1

= У/W ^lWa' по модулю М)х, по модулю М = / = 1 П

- ^а'х, по модулю Л/ =

1 = 1

П

= ⁽¹⁴‘⁴⁷>

1 = 1

Поскольку авторизованный пользователь знает засекреченный быстровозрастающий вектор а' для отыскания х он может использовать S'.

14.5.5.1. Использование схемы Меркла-Хэллмана

Предположим, пользователь А желает создать общедоступную и конфиденциаль­ную функции шифрования. Сначала он рассматривает быстровозрастающий вектор а' = (171, 197, 459, 1191, 2410, 4517).

i = i

Затем он выбирает простое число М, большее 8945, случайное число W, такое, что

1 <W<M, и вычисляет W\ при котором W¹ = 1 по модулю М.

Пусть М = 9109 Пусть W = 2251 тогда W'¹ = 1388

После этого он образует вектор, который оставляет “лазейку” в рюкзаке.

а, - а', 2251 по модулю 9109 а = 2343, 6215, 3892, 2895, 5055, 2123

Пользователь А делает общедоступным вектор а, который, очевидно, не является бы- стровозрастающим. Предположим, что пользователь В желает послать сообщение пользователю А.

Если х = 010110 — сообщение, которое нужно передать, то пользователь В создает следующее число:

S = ах = 14 165 и передает его пользователю А.

Пользователь А получает S и превращает его в S'.

S'=a^<n= W'S по модулюМ =

= 1388 • 14 165 по модулю 9109 =

= 3798

Используя S' = 3798 и быстровозрастающий вектор а', пользователь А легко находит х.

Схема Меркла-Хэллмана сейчас считается взломанной [16], поэтому для реализа­ции криптосистем с открытыми ключами используется алгоритм RSA (равно как и другие рассмотренные позднее).

14 Ч КпмптпгмгтРми г* nwnkiTkiMM if тпиаклм

14.6. Pretty Good Privacy

PGP (Pretty Good Privacy, буквально: “весьма хорошая секретность”) — это программа обеспечения секретности, которая была создана Филиппом Циммерманом (Philip Zimmerman) [17] и опубликована в 1991 году как бесплатное программное обеспече­ние. Затем она “де-факто” стала стандартом для электронной почты и шифрования файлов. PGP версии 2.6 (наиболее широко используемая) оставалась неизменной вплоть до появления версии 5.0 (совместимой с версией 2.6). В табл. 14.9 приведены алгоритмы, используемые в версиях 2.6, 5.0 и более поздних.

Таблица 14.9. Сравнение PGP 2.6 и PGP5.0

Функция	PGP версии 2.6 Используемый алгоритм [17]	PGP версии 5.0 и более поздних Используемый алгоритм [18]
Шифрование сообщения с использова­нием алгоритма частного ключа с по­мощью ключа частного сеанса	IDEA	“Тройной” DES, CAST или IDEA
Шифрование ключа частного сеанса с помощью алгоритма частного ключа	RSA	RSA или алгоритм Диффи- Хэллмана (вариант Элгемала)
Цифровая подпись	RSA	RSA и DSS' (от NIST^1)
Хэш-функция, используемая при соз­дании профиля сообщения для цифро­вых подписей	MD5	SHA-1

Как показано в табл. 14.9, PGP использует множество алгоритмов шифрова­ния, включающих как схемы частного ключа, так и схемы открытого ключа. При шифровании сообщения применяется алгоритм частного ключа (для каждого се­анса генерируется новый ключ сеанса). В качестве алгоритмов частного ключа, предлагаемых PGP, представлены Международный алгоритм шифрования данных (International Desalination and Environmental Association — IDEA), “тройной” DES и алгоритм CAST (названный в честь авторов Карлайла Адамса (Carlisle Adams) и Стэффорда Тевереса (Stafford Tavares) [19]). Для шифрования ключа каждого се­анса используется алгоритм открытого ключа. В качестве алгоритмов, исполь­зующих открытые ключи, PGP предлагает алгоритм RSA, описанный в разделе 14.5.3, и алгоритм Диффи-Хэллмана (DifFie-Hellman).

---

Дата добавления: 2015-10-28