Криптографические протоколы

 

3.2. Алгоритмы реализации скрытого канала

Рассмотрим  два возможных алгоритма основанных на «подмене» псевдослучайного числа, генерируемого на третьем шаге. Подмена псевдослучайного числа – классический вариант созданий скрытого канала в электронной цифровой подписи. Причем возможна прямая подстановка скрываемого сообщения вместо случайного числа k, так как параметр k используется только при формировании подписи, и при проверке подписи не может быть определен без знания секретного ключа d.

3.2.1 Скрытый канал с общим секретным ключом

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

один тот же ключ подписи d. Скрываемые данные подменяют число k, а остальные шаги формирования подписи не изменяются.

Получателю, для восстановления скрываемой информации, потребуется вычислить:

                                               k ≡ e-1 (s – rd) (mod q)                                           

Эта формула следует из соотношения (s ≡ (rd+ke) (mod q).

Серьезным достоинством данного скрытого канала является то, что для обнаружения

и «вскрытия» необходимо узнать секретный  ключ подписи, что является достаточно сложной задачей. Более того никакими методами невозможно распознать наличие скрытого сообщения без знания закрытого ключа. Недостатком является то, что необходимость знания общего ключа, который одновременно является ключом подписи, в ряде случаев неосуществима.

3.2.2 Канал с использованием двух сообщений

Для создания данного канала отправителю  потребуется сгенерировать и подписать два

различных сообщения. Для обоих  сообщений выполняются шаги аналогичные  шагам формирования подписи, с тем  изменением, что псевдослучайные  числа k в обоих сообщениях являются одинаковыми и представляют собой скрываемую информацию.

В результате выполнения алгоритма  получаем две цифровые подписи: (r || s1) – для перво-

го сообщения и (r || s2) – для второго сообщения. Параметр r в обоих сообщениях одинаков, так как он зависит только от случайного числа k, которое мы подменяем в обоих случаях скрытым сообщением.

Скрытая информация может быть восстановлена  путем решения системы уравнений:

                           s1≡(rd+ke1) (mod q), s2≡(rd+ke2) (mod q),

из которой следует выражение:

                                             k = (s2–s1) (e2–e1)–1 (mod q)

позволяющее прочитать скрытое  сообщение.

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

ключа подписи. Однако, существует ряд  серьёзных проблем. Если злоумышленник  перехватит оба подписанных сообщения, ему также как и получателю, не составит труда вычислить k, так как для определения k не надо знать дополнительных параметров, и злоумышленник находится в условиях одинаковых с получателем сообщения. Эта проблема может решиться путем предварительного шифрования скрываемой информации общим ключом. Другая, более серьезная угроза связанна с тем, что линейная система уравнений содержит два неизвестных – случайное число k и ключ подписи d. То есть, злоумышленник, перехвативший два таких сообщения, может установить секретный ключ подписи отправителя по следующему алгоритму.

1. Вычисление e – хэш-кода сообщения,  взятого по модулю q.

Исследование возможности  создания скрытых каналов 19

2. Вычисление

v = r–1(mod q)

3. Вычисление

z1 = s1v (mod q), z2 = –ke1v (mod q).

4. Вычисление секретного ключа  d

d = z1 + z2 (mod q)= r–1 (s1–ke1) (mod q)

Таким образом трудоемкость операции нахождения секретного ключа сравнима с трудоемкостью проверки подписи, так как при проверке подписи  надо выполнить следующий набор  шагов:

1. Вычисление e – хэш-кода сообщения, взятого по модулю q.

2. Вычислить

v = e–1 (mod q).

3. Вычислить значения

z1 ≡ sv (mod q), z2 ≡ –rv (mod q).

4. Вычислить точку эллиптической  кривой

С = z1 P + z1 Q

Однако данная опасность хорошо известна из алгоритмов разделения секрета и решается

техническими методами передачи сообщений.

 

 

 

 

4.Криптосистема RSA.

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

Итак, имеем два отображения:

E: S --> T

D: T --> S

где S -- множество всевозможных незашифрованных  сообщений, T -- множество зашифрованных  сообщений. Буква "E" -- первая буква  слова "Encoding", буква "D" -- первая буква слова "Decoding". Отображение

E: s |--> t

переводит исходное сообщение s в зашифрованное  сообщение t, отображение 

D: t |--> s

переводит зашифрованное сообщение t обратно в s. Тот факт, что D является декодирующей процедурой, на математическом языке означает, что композиция отображений DE является тождественным отображением: для всякого s справедливо

D(E(s)) = s

или

DE = 1 (тождественное отображение  в S)

Все это справедливо для любой  схемы асимметричного кодирования. Перейдем непосредственно к схеме RSA, названной так по первым буквам фамилий ее авторов -- Rumley, Shamir, Adleman. Отметим сразу, что схема RSA обладает двумя дополнительными очень полезными свойствами.

1. Множество исходных сообщений  S совпадает с множеством закодированных сообщений T; в качестве этого множества используется кольцо вычетов по модулю m, где m -- произведение двух больших простых чисел (десятичная запись m имеет длину не меньше 200).

2. Не только DE = 1, но и ED = 1! Таким  образом, D и E -- два взаимно обратных отображения. Это позволяет владельцу секретной процедуры декодирования D применять ее для кодирования. При этом все могут раскодировать это сообщение, используя открытую процедуру E, но только владелец секретной процедуры D может послать его. Такая "обратная" схема применения открытого ключа позволяет удостоверить отправителя сообщения. В практических применениях (для аутентификации отправителя) обратная схема даже более важна, чем прямая.

Итак, в схеме RSA в качестве множества  исходных и зашифрованных сообщений используется кольцо вычетов Zm, где

m = p * q

-- произведение двух больших  простых чисел (длина десятичной  записи каждого из чисел p и  q не меньше 100). Всякое сообщение  представляется в виде элемента Zm. (Любое сообщение -- это последовательность битов, которую можно рассмотреть как большое целое число. Если длина сообщения больше, чем длина двоичной записи m, то оно разбивается на блоки, и каждый блок шифруется отдельно).

Число m открытое, однако разложение m на множители -- секретное. Разложение позволяет вычислить функцию Эйлера (следствие 3):

phi(m) = (p - 1) * (q - 1)

Нетрудно показать, что знание функции  Эйлера дает возможность разложить  число на множители, так что сложность  задачи взламывания открытого ключа  равна сложности задачи разложения на множители. Математики верят, что это действительно сложная задача, хотя никаких удовлетворительных оценок снизу в настоящее время не получено. (И вряд ли это NP-полная задача.)

 
Построение кодирующей процедуры E

Сгенерируем случайный элемент e в кольце вычетов по модулю phi(m), такой, что он обратим в этом кольце (т.е. взаимно прост с phi(m)). Пара (m, e) является открытым ключом. Отображение E состоит в возведении в степень e в кольце вычетов по модулю m.

E: s |--> s^e (mod m)

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

Построение декодирующей процедуры D

Для элемента e вычисляется обратный элемент d в кольце вычетов по модулю phi(m).

e * d == 1 (mod phi(m))

Это легко делается с помощью расширенного алгоритма Евклида. Пара (m, d) является секретным ключом. Отображение D состоит в возведении в степень d в кольце вычетов по модулю m.

D: t |--> t^d (mod m)

Покажем, что отображение D является левым обратным к E, т.е. для всякого  ссобщения s выполняется равенство D(E(s)) = s. Имеем

D(E(s)) == D(s^e) == (s^e)^d == s^(e*d) (mod m)

Так как e*d == 1 (mod phi(m)), имеем 

e*d = 1 + h * phi(m)

По следствию 4,

s^(e*d) = s^(1 + h*phi(m)) == s (mod m)

Итак, DE = 1. Аналогично доказывается, что ED = 1.

Суммируем все вышесказанное.

Рассматривается множество сообщений Zm, где m -- произведение двух больших  простых чисел: m = p*q. Число m является открытым, но его разложение на множители -- секретным. Знание разложения позволяет  вычислить функцию Эйлера phi(m) = (p-1)*(q-1). Случайным образом выбирается обратимый элемент e в кольце вычетов по модулю phi(m). Для него вычисляется (с помощью расширенного алгоритма Евклида) обратный элемент d в кольце вычетов по модулю phi(m). Отображение E задается парой (m, e) и состоит в возведении в степень e по модулю m:

E(s) = s^e (mod m)

Отображение D задается парой (m, d) и  состоит в возведении в степень d по модулю m:

D(t) = t^d (mod m)

Эти два отображения взаимно  обратны. Пара (m, e) является открытым ключом (public key), пара (m, d) является секретным ключом (private key).

Пример. Рассмотрим пример с небольшими числами, чтобы только проиллюстрировать  схему RSA. В реальных приложениях  используют большие целые числа, порядка 200-400 десятичных цифр.

Пусть m = 11*13 = 143. Вычислим функцию Эйлера phi(m) = 10*12 = 120. Выберем e = 113, тогда d = 17 -- обратный к e элемент в кольце Z₁₂₀.

Действительно,

113 * 17 = 1921 = 120 * 16 + 1

Пара (143, 113) составляет открытый ключ, пара (143, 17) -- секретный ключ. Отображение E состоит в возведении в степень 113 по модулю 143, отображение D -- в степень 17 по модулю 143. Рассмотрим произвольное сообщение s = 123. Тогда

E(123) == 123^113 (mod 143) == 41

Таким образом, 41 -- это закодированное сообщение. Применим к нему декодирующую процедуру:

D(41) == 41^17 (mod 143) == 123

Мы получили исходное сообщение.

Вопрос 6.

Принцип шифрования аналоговых сообщений (маскираторы). 

Ответ.

 

Средства защиты традиционной телефонии:

• маскираторы (разбиение спектра сигнала на несколько областей, поворот некоторых из них вокруг несущих частот и перемешивание, защита не очень надежная);
• скремблеры (спектр сигнала, в соответствии со специальным алгоритмом, делится на частотно-временные сегменты, после чего эти части перемешиваются по криптографическому ключу, защита более серьезная);
• генераторы шума (генерируется «белый шум» с одного конца линии, с другого пользователь говорит что-то секретное, а шумогенератор вычитает шум из сигнала).

 

Частотные преобразования

При частотной инверсии преобразование спектра речевого сигнала эквивалентно повороту частотной полосы сигнала вокруг некоторой средней частоты (F_и). Принцип данного преобразования сигнала показан на рис. 1: а) - исходный спектр сигнала, б) - спектр сигнала после инверсии.

Рис. 1. Принцип работы частотного инвертора речевого сигнала.

 

Несколько более сложный по сравнению  с частотной инверсией способ преобразования сигнала обеспечивает скремблер с разбиением полосы речевого сигнала на поддиапазоны с частотной инверсией сигнала в каждом поддиапазоне (полосно-сдвиговый инвертор). Обычно используется разбиение полосы на 2 поддиапазона. Принцип такого частотного преобразования для 2-х поддиапазонов показан на рис. 2, где а) - исходный спектр сигнала; б) - спектр сигнала после преобразования, F_р - частота разбиения спектра сигнала; F_и1, F_и2 - частоты инверсии 1-го и 2-го поддиапазонов.

Рис. 2. Принцип работы полосно-сдвигового инвертора речевого сигнала при разбиении спектра сигнала на 2 поддиапазона.

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

Рис. 3. Принцип работы 4-х полосового скремблера.

Полосовой скремблер может быть реализован на основе быстрого преобразования Фурье (БПФ). В таком скремблере на передающей стороне производится прямое БПФ, частотная перестановка полос, а затем - обратное БПФ. На приемной стороне осуществляются аналогичные преобразования с обратной частотной перестановкой полос. В скремблерах с БПФ возможно достичь высокой степени защиты информации за счет увеличения количества перемешиваемых полос, однако на практике этот метод скремблирования в подвижной радиосвязи применяется редко в связи со сложностями технической реализации. Кроме этого, скремблеры с БПФ вносят в канал связи временную задержку.

Временные преобразования

Простейшим видом временного преобразования является временная инверсия, при которой исходный сигнал делится на последовательность временных сегментов и каждый из них передается инверсно во времени - с конца к началу. Принцип работы временного инвертора показан на рис. 4.

Рис. 4. Принцип работы временного инвертора.

В скремблере с временными перестановками речевой сигнал делится на временные кадры, каждый из которых в свою очередь подразделяется на сегменты, а затем сегменты речевого сигнала подвергаются перестановке. Принцип работы такого скремблера с фиксированным окном и числом временных сегментов в кадре, равном 6, показан на рис. 5.

Рис. 5. Принцип работы скремблера с временными перестановками.

Роллинговые скремблеры

Все рассмотренные выше скремблеры предполагают фиксированные параметры  преобразования сигнала (фиксированные  ключи) в течение передачи речевого сообщения и поэтому называются статическими.

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

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

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