Методы и средства защиты компьютерной информации (стр. 5 )

Рассмотрим работу ЛРС на примере трехразрядного регистра, структура которого приведена на рис.2.10

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

Таблица 2.2

Результат работы генератора гаммы на основе ЛРС

Номер такта	Значения битов ЛРС	Бит гаммы
1	2	3
нач. сост	0	1	0	-
1	0	0	1	0
2	1	0	0	1
3	1	1	0	0
4	1	1	1	0
5	0	1	1	1
6	1	0	1	1
7	0	1	0	1
8	0	0	1	0

Из таблицы видно, что состояние ЛРС повторяется через 7 тактов (начальное состояние ЛРС совпадает с его состоянием на 7-м такте). Повтор состояния ЛРС означает, что и гамма будет периодически повторяться. Повторение гаммы снижает криптостойкость поточных шифров, позволяя криптоаналитику проводить анализ шифротекстов, полученных кодированием на одной и той же гамме. Поэтому при проектировании структуры ЛРС встает проблема достижения максимального периода повтора ЛРС. Для ЛРС длиной n бит максимальный период составляет 2n-1 тактов (состояние, когда все биты равны нулю, недопустимо, поскольку ЛРС любой структуры не выходит из этого состояния, зацикливаясь в нем). Построение ЛРС оптимальной структуры с точки зрения периода повторения гаммы имеет четкую математическую основу в виде теории неприводимых полиномов. Структура ЛРС описывается многочленом вида:

b1*xn+b2*xn-1+b3*xn-2+…+bn-1*x2+ bn*x+1,

где bi=0, если i-й бит слева не участвует в обратной связи, и bi=1, если участвует. ЛРС будет иметь максимально возможный период повторения гаммы, если описывающий его многочлен не раскладывается на произведение многочленов меньшей степени.

Основной проблемой ЛРС является их нестойкость к атаке на основе известного открытого текста. Даже если неизвестна внутренняя структура ЛРС, криптоаналитик с помощью алгоритма Берлекэмпа-Мэсси по известным 2N битам открытого текста и соответствующего шифротекста имеет возможность построить ЛРС, порождающую подобную последовательность. Поэтому современные поточные шифры строятся на основе нелинейных регистров сдвига (НРС). Нелинейные регистры сдвига строятся на основе линейных с добавлением в структуру нелинейных элементов: логического сложения и логического умножения. Наиболее популярными классами нелинейных регистров сдвига на сегодня являются фильтрующие, комбинирующие и динамические поточные шифры [6].

Фильтрующие НРС строятся с использованием дополнительной комбинационной схемы – фильтра – на выходах некоторых бит ЛРС (рис.2.11). Выход комбинационной схемы и является гаммой.

Комбинирующие НРС также используют комбинационную схему с нелинейными преобразованиями бит, но на вход этой комбинационной схемы подаются выходы нескольких ЛРС (рис.2.12).

При проектировании НРС комбинирующего типа необходимо следить, чтобы комбинационная схема равномерно перемешивала выходы каждого из ЛРС, иначе может возникнуть ситуация доминирования одного из ЛРС, когда его выход на подавляющем большинстве тактов совпадает с общим выходом НРС.

Динамические НРС также строятся на основе нескольких ЛРС, но здесь они вступают друг с другом в отношения «главный-подчиненный» (рис.2.13). В зависимости от выхода управляющего ЛРС на общий выход НРС подается либо выход первого, либо второго ЛРС.

В качестве примера поточного шифра, построенного на основе регистров сдвига, можно привести алгоритм A5, используемый для кодирования в стандарте GSM. A5 включает 3 ЛРС длиной 19, 22 и 23 бита на выход гаммы подается сумма по модулю 2 выходов всех регистров. Используется схема динамического НРС, когда каждый регистр тактируется в зависимости от состояния средних разрядов всех трех регистров сдвига.

Поточными являются также шифры RC4, SEAL, WAKE [12].

2.5. Асимметричное шифрование

Симметричное шифрование имеет недостатки, которые ограничивают возможности его применения в ряде конкретных случаев. В частности, зачастую невозможно организовать секретный канал для обмена ключами шифрования между участниками взаимодействия. Еще одним недостатком симметричных шифров является необходимость хранения большого количества ключей: для того чтобы в вычислительной сети могли конфиденциально попарно взаимодействовать N участников, необходимо наличие в системе N*(N-1)/2 ключей. Эти недостатки можно устранить, используя алгоритмы асимметричного шифрования. Например, для асимметричной системы достаточно иметь 2*N пар открытый/закрытый ключ, чтобы можно было организовать секретный канал между каждой парой участников.

2.5.1. Математические основы асимметричного шифрования

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

Для любого положительного целого числа n и любого a при делении a на n мы получаем некоторое целое частное q и остаток r, удовлетворяющий соотношению

a = qn + r,  0 ≤ r < n; q = int(a / n),

где int(x) обозначает наибольшее целое число, не превышающее x.
  Если a является целым, а n - положительным, то a mod n определяется как остаток от деления a на n. Таким образом, для любого целого числа a можно записать

a = int(a / n) * n + (a mod n).

Говорят, что два целых числа a и b являются сравнимыми по модулю n, если (a mod n) = (b mod n). Это записывается в виде: a º b mod n.

  Операции сравнения по модулю имеют следующие свойства:

1. a º b mod n, n | (a - b) (n | x означает, что n делит x нацело). 2. Из (a mod n) = (b mod n) следует a º b mod n. 3. Из  a º b mod n следует b º a mod n. 4. Из a º b mod n  и b º c mod n следует a º c mod n.

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

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n. 2. [(a mod n) - (b mod n)] mod n = (a - b) mod n. 3. [(a mod n) * (b mod n)] mod n = (a * b) mod n.

Пусть Zn обозначает множество всех не отрицательных целых чисел, которые меньше n:

Zn = {0, 1, 2, ... , (n - 1)}.

  Это множество называется ещё множеством вычетов (остатков) по модулю n. Для арифметических операций по модулю n в этом множестве выполняются следующие свойства: