Понятие и применение решетчатой диаграммы и кодового дерева

Одним очень наглядным способом описания и иллюстрации работы сверточных кодов является использование так называемого кодового дерева.

Рассмотрим сверточный (6.3)-код со схемой, изображенной на рис. 2.5.

Рис. 2.5

Соответствующее этому кодеру кодовое дерево - последовательность выходных состояний кодера при подаче на его вход цепочки входных символов 0 и 1 - приведено на рис. 2.6

Рис. 2.6

На диаграмме рис. 2.6 изображены входные и выходные последовательности кодера: входные — направлением движения по дереву (вверх - 0, вниз - 1), выходные — символами вдоль ребер дерева. При этом кодирование состоит в движении вправо по кодовому дереву.

Например, входная последовательность т = (01000........................................................... …….. кодируется

как U = (0011101100000..., последовательность m = (1010100000... – как U = (1110001000…

Если внимательно посмотреть на строение приведенного на рис. 2.6 кодового дерева, можно заметить, что начиная с четвертого ребра его структура повторяется, т.е. каким бы ни был первый шаг, начиная с четвертого ребра значения выходных символов кодера повторяются. Одинаковые же узлы могут быть объединены, и тогда начиная с некоторого сечения размер кодового дерева перестанет увеличиваться.

Другими словами, выходная кодовая последовательность в определенный момент перестает зависеть от значений входных символов, введенных в кодер ранее.

Действительно, из рис. 2.6 видно, что, когда третий входной символ вводится в кодер, первый входной символ покидает сдвиговый регистр и не сможет в дальнейшем оказывать влияния на выходные символы кодера.

С учетом этого неограниченное кодовое дерево, изображенное на рис. 2.6, переходит в ограниченную решетчатую диаграмму (кодовое дерево со сливающимися узлами) рис. 2.7.

Кодирование сверточными кодами с использованием решетчатой диаграммы, как и в случае с кодовым деревом, представляет собой чрезвычайно простую процедуру: очередные символы входной последовательности определяют направление движения из узлов решетки: если 0, то идем по верхнему ребру, если I - по нижнему ребру. Однако в отличие от кодового дерева решетчатая диаграмма не разрастается по ширине с каждым шагом, а имеет начиная с третьего сечения постоянную ширину.

В качестве примера закодируем с помощью решетчатой диаграммы несколько информационных последовательностей.

Пусть

т=(0110000……Соответствующая ей кодовая последовательность будет иметь вид: U = (001101011100..., или т = (110100..., тогда

U = (1101010010110000...;

или т = (000000..., тогда U = (1101010010110000

и т.д., проще не придумаешь.

21.Криптосистема шифрования данных RSA.

Алгоритм RSA предложили в 1978 г. три автора: Р. Райвест (Rivest), А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов.

Надежность алгоритма основывается на трудности факторизации больших чисел в произведение простых множителей. В криптосистеме RSA открытый ключ К_в, секретный ключ k_в, сообщение М и криптограмма С принадлежат множеству целых чисел , где N - модуль: N = P∙ Q. Здесь Р и Q - случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете. Множество Zn с операциями сложения и умножения по модулю N образует арифметику по модулю N. От­крытый ключ К_в выбирают случайным образом так, чтобы выполнялись условия: , НОД (К_в, (р (N)) =1, φ(N)=(P -1) (Q -1), где φ (N) - функция Эйлера (см. гл. 2). Второе из указанных выше условий означает, что открытый ключ К_в и значение функции Эйлера φ(N) должны быть взаимно простыми. Далее, исполь­зуя расширенный алгоритм Евклида, вычисляют секретный ключ k_в, такой, что

или (5.26)

Это можно осуществить, так как при известной паре простых чисел (Р, Q) можно легко найти φ (N). Заметим, что k_в и N должны быть взаимно простыми. Открытый ключ К_в используют для шифрования данных, а секретный ключ k_в - для расшиф­рования.

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

В качестве алгоритма быстрого вычисления значения С используют ряд по­следовательных возведений в квадрат целого М и умножений на М с приведени­ем по модулю N.

Обращение функции С = М^Кв (mod N), т.е. определение значения М по известным значениям С, К_в и N, практически не осуществимо при . Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, ис­пользуя пару (секретный ключ k_в, криптограмма С) по следующей формуле: . Подставляя в это уравнение значение С, получаем: или . Сопоставляя это выражение с фор­мулой расшифрования, получаем или, что то же самое, . Именно поэтому для вычисления секретного ключа k_в используют соотношение (5.26).

Следовательно, если криптограмму С=М^Кв(mod N) возвести в степень k_в , то в результате восстанавливается исходный открытый текст М, так как .

Таким образом, получатель, который создает криптосистему, защищает два параметра: 1) секретный ключ k_в и 2) пару чисел (Р, Q), произведение которых дает значение модуля N. С другой стороны, отправителю известны значения мо­дуля N и открытого ключа К_в. Противнику известны лишь значения К_в и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы "потай­ной ход" - тройку чисел {Р, Q, К_в}, вычислил бы значение функции Эйлера и определил значение секретного ключа k_в.

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