3.8 Шифрование

Если для передачи сообщений используется открытый канал (например, канал радиосвязи), то все субъекты, способные передавать и принимать сигналы, делятся на две группы:

1) законные пользователи, то есть те, кто имеет право передавать сообщения на определённой частоте, в определённом формате и т.д., либо те, кому предназначены эти сообщения в данный момент;

2) незаконные пользователи (злоумышленники, подслушивающие).

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

Содержание данного раздела – это анализ методов, позволяющих уменьшить вред, приносимый незаконным приёмом сообщений.

Наиболее радикальная мера – это обеспечение скрытности передачи, то есть использование для передачи сигналов, которые внешне не отличаются от естественного шума (шумоподобных сигналов), но не являются таковыми. Даже для обнаружения факта передачи таких сигналов необходимо детальное знание способа их формирования, поэтому для незаконного пользователя обычно сам факт передачи сообщения остаётся незамеченным. Возможные способы частичного решения этой трудной задачи рассмотрены в части 2 данного пособия.

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

Цели шифрования:

1) обеспечение конфиденциальности, то есть воспрепятствование раскрытию смысла сообщения, перехваченного незаконным пользователем;

2) аутентификация, то есть предотвращение передачи по сети сообщений, незаконно внедрённых в открытый канал (см. выше);

3) обеспечение электронной подписи, то есть убедительной гарантии того, что данное сообщение было передано конкретным лицом и ни кем иным;

4) идентификация, то есть проверка того, что оборудование, используемое для передачи, соответствует стандарту, не находится в розыске и т.п.

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

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

Криптоаналитик – это тот, кто производит оценку открытого (переданного) текста посредством анализа шифрованного сообщения, полученного из общедоступного канала, без использования ключа. С его стороны возможны следующие угрозы:

1) атака только шифрованного сообщения при наличии некоторой информации о языке, на котором передаётся текст, и об общих принципах шифрования;

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

При последовательном (многократном) использовании ключа все шифросистемы делятся на два класса:

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

2. защищённые по вычислениям на x лет, то есть при использовании самых современных компьютеров защита системы может быть взломана в среднем за x лет, при этом, естественно, выбирают такой способ шифрования, чтобы единственным возможным для криптоаналитика методом был метод перебора.

Существуют два основных класса систем шифрования: симметричные и асимметричные.

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

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

Тогда текст «баба гадала» будет зашифрован как «гдгд адлдбд».

Основные недостатки:

1. малое количество возможных ключей (перестановок);

2. длинное сообщение можно расшифровать, используя статистический анализ, основанный на том, что в любом реальном языке буквы алфавита используются неодинаково часто, причём эти частоты заранее известны.

О

Таблица 3.6

Система перестановок

букв алфавита

Буква алфавита	Замена
а	д
б	г
в	в
г	а
д	л
л	б

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

В сущности, разновидностью метода перестановки является метод шифрования платных передач в системах непосредственного телевизионного спутникового вещания. Каждая строка телевизионного кадра делится на две части в точке, положение которой задаётся очередным 256-ичным числом с генератора псевдослучайной числовой последовательности, и обе части передаются в обратном порядке. Разумеется, в приёмнике законного пользователя имеется точно такой же генератор, синхронизированный во времени с генератором передатчика.

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

Метод скремблирования (гаммирования) основан на том, что на символы открытого текста Х накладываются символы ключа - псевдослучайной последовательности чисел (ПСП), обычно путём суммирования.

Если текст и ПСП состоят из двоичных символов, для шифрования и дешифрования применяется суммирование по модулю 2. Пример приведён в табл. 3.7, где Y - зашифрованное сообщение, Z - расшифрованное сообщение.

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

Г

Шиф-ратор	X ПСП Y	01101001… 01011100… 00110101…
Дешиф-ратор	Y ПСП Z	00110101… 01011100… 01101001…

Таблица 3.7 – Применение метода скремблирования

лавный недостаток: если криптоаналитику стали известны 2r соседних элементов ПСП, по ним легко восстановить всю ПСП, то есть ключ шифрования.

Метод скрелибрирования применяется, например, для шифрования речи в сотовых системах стандарта GSM.

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

Огромное достоинство метода: отпадает необходимость распределения секретных ключей, так как каждый абонент сам изготавливает (вычисляет) для себя оба ключа.

Идея метода заключается в использовании так называемых односторонних функций Y=f(X), где X – большое целое число, соответствующее переданному тексту, Y – большое целое число, соответствующее зашифрованному сообщению.

Односторонние функции обладают следующими свойствами:

1) для вычисления Y по X (шифрование) существует алгоритм полиномиальной сложности, для которого необходимое число операций умножения равно

,

(3.62)

где n и a – большие целые числа. Например, взяв не очень большие значения a=2, n=200, получим , то есть сравнительно мало операций;

2) для вычисления X по Y (дешифрование) известны лишь алгоритмы экспоненциальной сложности, для которых число операций

.

(3.63)

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

Чтобы не ставить законного пользователя в такие же трудные условия, в которых оказался криптоаналитик, математики разработали подкласс односторонних функций с “лазейкой” Z, которые при неизвестном значении ключа Z (для криптоаналитика) обладают тем же свойством (3.63), но при известном Z (для законного пользователя) для вычисления X по Y также существует алгоритм полиномиальной сложности.

Одним из самых известных алгоритмов шифрования такого рода является метод RSA (авторы Rivest – Shamiz - Adleman), в основе которого лежит трудоёмкая задача разложения (факторизации) большого целого числа на простые сомножители.

Генерирование ключей проводится пользователем в следующем порядке:

1) задаются два больших положительных целых простых числа р и q и произвольное большое число d;

2) вычисляется n=pq и решается уравнение

(3.64)

относительно неизвестного целого числа e, где amodb обозначает остаток от деления целого числа a на целое число b;

3) пара чисел (e,n) распространяется среди остальных пользователей в качестве открытого ключа, а пара чисел (d,n) есть секретный ключ.

В процессе шифрования:

1) передаваемый текст представляется как целое число X в интервале (0,…,n-1);

2) пользуясь открытым ключом, по формуле

(3.65)

находят целое число Y из интервала (0,…,n-1), соответствующее зашифрованному сообщению;

3) число Y представляют в двоичной форме, если для передачи используется двоичный канал.

В процессе дешифрования:

1) принятое зашифрованное сообщение представляют в виде целого числа Y из интервала (0,…,n-1);

2) пользуясь своим секретным ключом, находится целое число X

;

(3.66)

3) переводят число X в двоичную или иную форму, удобную для дальнейшей обработки текста.

Чтобы взломать шифр, нужно по известным n и e определить числа р и q, то есть разложить n на простые сомножители. Если учесть, что число n может содержать 200 и даже более десятичных знаков, а факторизация проводится методом перебора, перед криптоаналитиком стоит практически неразрешимая задача.

Впрочем, и для законного пользователя шифрование и дешифрование методом RSA – также достаточно трудоёмкие операции. Поэтому перспективными являются гибридные методы: асимметричная система применяется лишь для передачи ключа шифрования, а симметричная – для шифрования и дешифрования сообщений с использованием этого ключа.