Лабораторная работа № 3. Потоковые криптосистемы

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

C_i = E_Ki (M_i) = M_i Å K_i, M_i, K_i, C_i Î {0,1}. (3)

При дешифровании выполняется обратное преобразование D_Ki:

D_Ki (C_i) = C_i Å K_i = (M_i Å K_i) Å K_i = M_i. (4)

Символом «Å» обозначена операция сложения «ИСКЛЮЧАЮЩЕЕ-ИЛИ». Благодаря линейным свойствам этой операции при шифровании и дешифровании используется одинаковый ключевой поток K. Очевидно, что в этом случае длина K должна быть равна длине передаваемого сообщения. Однако обмен ключами большого размера зачастую невозможен. Поэтому на практике для формирования ключевого потока используют генераторы псевдослучайной последовательности (рис. 1). Начальные параметры I генераторов на стороне отправителя и получателя должны совпадать, они являются секретным ключом алгоритма. Псевдослучайная последовательность каждого генератора обладает определенным периодом, после которого значения повторяются. Поэтому необходимо выбирать такие генераторы ключа, чтобы этот период превышал длину шифруемой информации.

Рис. 1. Схема потоковой криптосистемы

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

Рассмотрим генераторы ключей на основе сдвиговых регистров с линейной обратной связью LFSR (Linear Feedback Shift Register). Они достаточно просто реализуются в программном и аппаратном виде, обладают высокой скоростью генерации и большим периодом ключа. Регистр LFSR состоит из двух частей: сдвигового регистра, выполняющего сдвиг своих разрядов влево на один разряд, и функции обратной связи, вычисляющей вдвигаемое в первый разряд значение. В обобщенном виде структура LFSR представлена на рис. 2.

Рис. 2. Обобщенная схема LFSR

Структуру конкретного регистра LFSR принято задавать с помощью характеристического (задающего) многочлена:

P (x) = a_m x^m + a_m- ₁ x^m- ¹ + … + a ₂ x ² + a ₁ x + 1, a_k Î {0,1}, k = 1, …, m. (5)

Степень многочлена m задает длину сдвигового регистра. Ненулевые коэффициенты a_k определяют разряды регистра, которые будут участвовать в формировании вдвигаемого в первый разряд значения. Через b_k (b_k Î {0,1}) обозначены текущие значения разрядов LFSR (k = 1, …, m). Новые значения разрядов b*_k (b*_k Î {0,1}) вычисляются по следующему закону:

	– функция обратной связи	(6)
– сдвиг.

Таким образом, новое значение для всех разрядов, кроме первого, берется из ближайшего младшего разряда. Символом обозначена многоместная операция сложения «ИСКЛЮЧАЮЩЕЕ-ИЛИ». Она используется для сложения значений из разрядов, которые отмечены ненулевыми коэффициентами a_k характеристического многочлена. Полученная сумма вдвигается в первый разряд LFSR. Очередной бит ключа K_i для потоковой криптосистемы равен значению старшего разряда LFSR b_m.

Пример 1. Построим сдвиговый регистр с линейными обратными связями, задаваемый характеристическим многочленом P (x) = x ⁴ + x + 1.

Схема регистра приведена на рис. 3. Если начальное состояние регистра I = 1111, то последовательность генерируемых состояний имеет вид

1111®1110®1101®1010®0101®1011®0110®1100®

1001®0010®0100®1000®0001®0011®0111®1111

Рис. 3. LFSR на основе многочлена P (x) = x ⁴ + x + 1

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

Свойства генерируемой последовательности определяются постоянными коэффициентами характеристического многочлена a_i. При их соответствующем выборе генерируемая последовательность K будет иметь максимально возможный период, равный 2 ^m – 1. Последовательность максимально возможного для данного генератора периода называется M-последовательностью. Основная задача синтеза генератора на основе LFSR – нахождение характеристического многочлена, позволяющего сформировать М-последовательность. Для того чтобы конкретный LFSR имел максимальный период, соответствующий многочлен должен быть примитивным. В общем случае не существует простого способа нахождения примитивных многочленов данной степени, проще выбирать многочлен случайным образом и проверять, является ли он примитивным. Эта задача аналогична задаче проверки на простоту случайно выбранного целого числа и решается с помощью вычислительной техники. Табл. 1 содержит некоторые примитивные многочлены.

Таблица 1

Примитивные многочлены

m	P (x)	m	P (x)	m	P (x)
	x ²³+ x ⁵ + 1		x ²⁹ + x ² + 1		x ³⁵ + x ² + 1
	x ²⁴ + x ⁴ + x ³ + x + 1		x ³⁰ + x ¹⁶ + x ¹⁵ + x + 1		x ³⁶ + x ¹¹ + 1
	x ²⁵ + x ³ + 1		x ³¹ + x ³ + 1		x ³⁷ + x ¹² + x ¹⁰ + x ² + 1
	x ²⁶ + x ⁸ + x ⁷ + x + 1		x ³² + x ²⁸ + x ²⁷ + x + 1		x ³⁸ + x ⁶ + x ⁵ + x + 1
	x ²⁷ + x ⁸ + x ⁷ + x + 1		x ³³ + x ¹³ + 1		x ³⁹ + x ⁴ + 1
	x ²⁸ + x ³ + 1		x ³⁴ + x ¹⁵ + x ¹⁴ + x + 1		x ⁴⁰ + x ²¹ + x ¹⁹ + x ² + 1

Использование LFSR для создания потоковых криптосистем предполагает наличие уязвимости, связанной с линейным характером генерируемой последовательности. Обладая парой «исходный текст – шифротекст» длиной всего 2 m бит, взломщик может восстановить характеристический многочлен и дешифровать все сообщение. Для защиты от этой атаки следует увеличивать размер используемого LFSR или использовать более сложные схемы генерации ключа. Рассмотрим, для примера, генератор Геффе (Geffe), представленный на рис. 4.

Рис. 4. Генератор Геффе

В нем используются три регистра с линейной обратной связью, объединённые нелинейным образом. Два регистра LFSR являются входами мультиплексора, а третий – управляет его выходом. Через x ₁, x ₂ и x ₃ обозначены выходы трёх LFSR, выход генератора Геффе x_G описывается так: x_G = (x ₁ and x₂) or (not x ₁ and x ₃). Период данного генератора равен , где m 1, m 2 и m 3 – длины первого, второго и третьего LFSR соответственно.

Благодаря простоте реализации, высокой скорости работы и сравнительно высокой криптостойкости потоковые шифраторы получили широкое распространение для шифрования информации средней степени секретности. Например, алгоритм A5, построенный на основе трех LFSR с прореженными обратными связями, входит в состав стандарта мобильной связи GSM.

Генератор «Стоп-пошел» Этот генератор использует выход одного LFSR для управления тактовой частотой другого LFSR. Тактовый выход LFSR-2 управляется выходом LFSR-1, так что LFSR-2 может изменять свое состояние в момент времени t только, если выход LFSR-1 в момент времени t–1 был равен 1.

Рисунок 5. Генератор «Стоп-пошел»

Задания

Вариант 1:

1. Реализуйте систему потокового шифрования файлов с помощью генератора ключевой последовательности на основе линейного сдвигового регистра с обратной связью LFSR₁

P (x)= x ²³+ x ⁵ + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ²⁹ + x ² + 1

P₂ (x)= x ³⁶ + x ¹¹ + 1

P₃ (x)= x ³⁹ + x ⁴ + 1

Вариант 2:

P (x)= x ²⁴ + x ⁴ + x ³ + x + 1

2. Модифицируйте программу из задания 1 путем реализации генератора «Стоп-пошел» с двумя регистрами LFSR₁, LFSR₂

P₁ (x)= x ³⁰ + x ¹⁶ + x ¹⁵ + x + 1

P₂ (x)= x ³⁷ + x ¹² + x ¹⁰ + x ² + 1

Вариант 3:

P (x)= x ²⁴ + x ⁴ + x ³ + x + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ³¹ + x ³ + 1

P₂ (x)= x ³⁸ + x ⁶ + x ⁵ + x + 1

P₃ (x)= x ⁴⁰ + x ⁹ + x ³ + x + 1

Вариант 4:

P (x)= x ²⁶ + x ⁸ + x ⁷ + x + 1

2. Модифицируйте программу из задания 1 путем реализации генератора «Стоп-пошел» с двумя регистрами LFSR₁, LFSR₂

P₁ (x)= x ³² + x ²⁸ + x ²⁷ + x + 1

P₂ (x)= x ⁴⁰ + x ²¹ + x ¹⁹ + x ² + 1

Вариант 5:

P (x)= x ²⁵ + x ³ + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ³³ + x ¹³ + 1

P₂ (x)= x ³² + x ²⁸ + x ²⁷ + x + 1

P₃ (x)= x ²⁶ + x ⁶ + x ² + x + 1

Вариант 6:

P (x)= x ²⁷ + x ⁸ + x ⁷ + x + 1

2. Модифицируйте программу из задания 1 путем реализации генератора «Стоп-пошел» с двумя регистрами LFSR₁, LFSR₂

P₁ (x)= x ³⁴ + x ¹⁵ + x ¹⁴ + x + 1

P₂ (x)= x ³¹ + x ³ + 1

Вариант 7:

P (x)= x ²⁸ + x ³ + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ³⁰ + x ²³ + x ² + x + 1

P₂ (x)= x ²⁵ + x ³ + 1

P₃ (x)= x ⁴⁰ + x ²¹ + x ¹⁹ + x ² + 1

Вариант 8:

P (x)= x ²⁴ + x ⁷ + x ² + x + 1

2. Модифицируйте программу из задания 1 путем реализации генератора «Стоп-пошел» с двумя регистрами LFSR₁, LFSR₂

P₁ (x)= x ³⁷ + x ¹² + x ¹⁰ + x ² + 1

P₂ (x)= x ²⁷ + x ⁸ + x ⁷ + x + 1

Вариант 9:

P (x)= x ²⁶ + x ⁶ + x ² + x + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ³² + x ²² + x ² + x + 1

P₂ (x)= x ²³+ x ⁵ + 1

P₃ (x)= x ²⁹ + x ² + 1

Вариант 10:

P (x)= x ²⁶ + x ⁶ + x ² + x + 1

2. Модифицируйте программу из задания 1 путем реализации генератора «Стоп-пошел» с двумя регистрами LFSR₁, LFSR₂

P₁ (x)= x ⁴⁰ + x ⁹ + x ³ + x + 1

P₂ (x)= x ³⁴ + x ¹⁵ + x ¹⁴ + x + 1

Вариант 11:

P (x)= x ²⁷ + x ⁵ + x ² + x + 1

2. Модифицируйте программу из задания 1 путем реализации схемы Геффе с тремя регистрами LFSR₁, LFSR₂ и LFSR₃

P₁ (x)= x ³⁵ + x ² + 1

P₂ (x)= x ²⁴ + x ⁴ + x ³ + x + 1

P₃ (x)= x ³² + x ²² + x ² + x + 1

Лабораторная работа № 3. Потоковые криптосистемы

Поиск по сайту