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

• работа по принципу stop-and-go;

• перемешивание двух ПСП под управлением третьей;

• многоступенчатая структура;

• использование S-блоков с изменяющейся в процессе работы таблицей замен;

• использование блоков пространственного сжатия информации;

• использование в качестве строительных блоков генераторов, функционирующих в конечных полях.

Одним из лучших поточных шифров является RC4 — шифр с переменным размером ключа, разработанный Р. Ривестом. Криптоалгоритм работает в режиме OFB, т. е. поток ключевой информации не зависит от открытого текста. Используются два 8-разрядных счетчика Q1 и Q2 и 8-разрядный блок замены (S-блок) (рис. 2.9), таблица замен имеет размерность 8 х 256 и яв­ляется перестановкой (зависящей от ключа) двоичных чисел от 0 до 255.

Рис. 2.9. Схема генератора ПСП RC4

Рассмотрим алгоритм работы 8-разрядного генератора ПСП RC4, точнее, процедуру генерации очередного байта гаммы. Пусть S(i) и γ - содержимое ячейки с адресом i таблицы замен S-блока и очередной байт гаммы.

Один такт работы генератора ПСП RC4:

1. Такт работы первого счетчика:

Q1 = (Q1 + 1) mod 28.

2. Такт работы второго счетчика:

Q2 = (Q2 + S(Q1)) mod 28.

3. Ячейки таблицы замен S-блока с адресами Q1 и Q2 обмениваются своим содержимым:

S(Q1)↔S(Q2).

4. Вычисление суммы содержимого ячеек таблицы замен S-блока с адресами Q1 и Q2:

Т = (S(Q1) + S(Q2)) mod 28.

5. Считывание содержимого ячейки таблицы замен S-блока с адресом T:

γ = S(T).

Таблица замен S-блока медленно изменяется при использова­нии, при этом счетчик Q1 обеспечивает изменение каждого эле­мента таблицы, a Q2 гарантирует, что элементы таблицы изме­няются случайным образом.

Криптографически стойкие генераторы ПСП могут быть по­строены на основе использования в цепи обратной связи так на­зываемых односторонних функций. Понятие односторонней функции является базовым для нового направления - криптогра­фии с открытым ключом.

По заданному аргументу х ∈ X легко вычислить значение та­кой функции F(x), в то же время определение х из F(x) трудновы­числимо, т. е. нет алгоритма для решения этой задачи с полино­миальным временем работы. Теоретически х по известному зна­чению F(x) можно найти всегда, проверяя по очереди все воз­можные значения x до тех пор, пока соответствующее значение F(x) не совпадет с заданным. Однако практически при значительной размерности множества X такой подход неосуществим.

Односторонней функцией называется функция F: X → Y, об­ладающая двумя свойствами:

• существует полиномиальный алгоритм вычисления значений F(x);

• не существует полиномиального алгоритма инвертирования функции F.

---

До сих пор ни для одной функции, кандидата на звание одно­сторонней, не доказано свойство 2.

Примером кандидата на звание односторонней функции являет­ся модульное возведение в степень, т. е. функция F(x) = ω^x mod р, где р - большое простое число, ω - примитивный элемент поля GF(p).

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

Односторонняя функция в качестве функции зашифрования неприменима, так как, хотя F(x) - надежно зашифрованное сооб­щение х, никто, в том числе и законный получатель, не сможет восстановить х. Обойти эту проблему можно с помощью одно­сторонней функции с секретом. Такова, например, функция Fk: X → Y; имеющая обратную F_k^-1: Y → X, однако узнать обрат­ную функцию только по Fk без знания секрета k невозможно.

Таким образом, односторонней функцией с секретом к, назы­вается функция F_k: X → Y, зависящая от параметра k и обладаю­щая тремя свойствами:

• при любом k существует полиномиальный алгоритм вычисле­ния значений F_k(x);

• при неизвестном k не существует полиномиального алгоритма инвертирования Fk;

• при известном k существует полиномиального алгоритма ин­вертирования Fk.

Функцию Fk можно использовать для зашифрования инфор­мации, а обратную ей функцию F_k-1 - для расшифрования.

При этом подразумевается, что тот, кто знает, как зашифровы­вать информацию» вовсе не обязательно должен знать, как рас­шифровывать. Так же как и в случае с односторонней функцией, вопрос о существовании односторонних функций с секретом от­крыт. Для практической криптографии найдено несколько функ­ций, кандидатов на звание односторонней функции с секретом. Для них второе свойство не доказано, однако известно, что задача инвертирования эквивалентна некоторой хорошо изученной и давно известной трудной математической задаче. Это означает, что второе требование к односторонней функции с секретом заменяется более слабым условием: при неизвестном k, вероятно, не существует полиномиального алгоритма инвертирования F_k-1.

2.3. ЛИНЕЙНЫЕ ГПСП

Важнейшим классом ПСП являются последовательности, формируемые генераторами на основе регистров сдвига с линей­ными обратными связями - LFSR (Linear Feedback Shift Register) [8]. Используемый при их анализе математический аппарат - теория линейных последовательностных машин и теория конечных по­лей (полей Галуа). Основными достоинствами этих генерато­ров являются:

• простота аппаратной и программной реализации;

• максимальное быстродействие;

• хорошие статистические свойства формируемых последова­тельностей;

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

---

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

Наиболее известные примеры использования LFSR и матема­тического аппарата полей Галуа:

• CRC-коды - идеальное средство контроля целостности ин­формации при случайных искажениях информации;

• реализация концепции самотестирования БИС и СБИС;

• поточные шифры А5, PANAMA, SOBER, SNOW и др.;

• блочный шифр RIJNDAEL, принятый в 2001 г. в качестве стандарта криптографической защиты XXI века - AES.

Исходная информация для построения двоичного LFSR - так называемый образующий многочлен. Степень этого многочлена определяет разрядность регистра сдвига, а ненулевые коэффициенты - характер обратных связей. Так, например, многочлену

Ф(х) = x8 + x7 + x5 + x3 + 1

соответствуют два устройства, показанные на рис. 2.10 и 2.11. В общем случае двоичному образующему многочлену степени N

Ф(х) = , a_N=a0=1, aj∈{0,1}, j=1,(N-1)

соответствуют устройства, показанные на рис. 2.12, a (LFSR1 – схема Фибоначчи) и б (LFSR2 - схема Галуа).

Рис. 2.10. Генератор Фибоначчи (LFSR1), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рис. 2.11. Генератор Галуа (LFSR2), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рассмотренные устройства могут использоваться только для генерации битовых ПСП. Если необходима n-разрядная последо­вательность, можно предложить два варианта действий. В первом случае выбираем образующий многочлен степени N > п (еще лучше N >> n), выбираем схему LFSR1 или LFSR2 и считываем очередной n-разрядный двоичный код с соседних разрядов реги­стра сдвига каждые п тактов работы LFSR. Во втором случае син­тезируем схему устройства, работающего в п раз быстрее исход­ного LFSR (иначе говоря, выполняющего за один такт своей ра­боты преобразования, которые в исходном LFSR выполняются за п тактов). Этот вариант особенно эффективен в тех случаях, ко­гда образующий многочлен генератора Фибоначчи имеет вид Ф(х) = xN + xi + 1, а i кратно п (рис. 2.13).

Рис. 2.12. Общий вид LFSR, соответствующих

Ф(х) = хN + а_N-1х^N-1 + ... + аiхⁱ + ... + а2х2 + а1х + 1:

a - схема генератора Фибоначчи; б - схема генератора Галуа.

БУ - блоки умножения на aj ∈ {0,1}; qj(t) ∈ {0,1};

при aj = 1 умножение на aj равносильно наличию связи; при aj = 0 умножение на aj равносильно отсутствию связи

Общий вид генератора двоичных последовательностей, соот­ветствующего уравнению

Q(t + 1) = T^k Q(t),

где Q(t) и Q(t+1) - состояния регистра генератора ПСП соответ­ственно в моменты времени t и t+1 (до и после прихода синхро­импульса); T - квадратная матрица порядка N вида

,

N - степень образующего многочлена

k - натуральное, показан на рис. 2.14. В частном случае при k = 1, получаем либо схему генератора Фибоначчи (T = T1), либо схему генератора Галуа (T = T2).

Рис. 2.13. Байтовый генератор ПСП:

а - битовый генератор Фибоначчи, соответствующий многочлену Ф(х) = х65 +x32 +1; б - байтовый генератор Фибоначчи, соответствующий Ф(х) = х65 + х32 + 1, qi - состояние i-гo разряда LFSR1, i =

---

Рис. 2.14. Генератор двоичных последовательностей, соответствующий уравнению Q(t +1) = TkQ(t)

Величина, на которую происходит умножение в каждом блоке умножения (БУ), определяется соответствующим коэффициентом aij сопровождающей матрицы:

Если аij = 0, это эквивалентно отсутствию связи между выхо­дом i-го разряда регистра генератора и входом j-го сумматора по модулю два. Если аij = 1, это эквивалентно наличию связи между выходом i-го разряда регистра генератора и входом j-го суммато­ра по модулю два.

Так как нулевое состояние регистра ГПК является запрещенным, максимально возможное число состояний устройства, а зна­чит, и максимально возможная длина формируемой двоичной последовательности, снимаемой с выхода любого из триггеров, равны 2N - 1. В этом случае диаграмма состояний генератора со­стоит из одного тривиального цикла и цикла максимальной длины 2N - 1.

Многочлен Ф(х) степени N называется примитивным, если он не делит нацело ни один многочлен вида xS - 1, где S < 2N - 1. Примитивные многочлены существуют для любого N. Показателем многочлена Ф(х) называется наименьшее натуральное число е, при котором хе - 1 делится на Ф(х) без остатка.

Пусть Ф(х) - примитивный многочлен степени N, тогда спра­ведливо следующее утверждение.

Свойство 1.1. Формируемая последовательность имеет макси­мальный период S = 2N - 1 тогда и только тогда, когда наиболь­ший общий делитель чисел S и k равен 1 (т. е. S и k взаимно про­сты).

Следствие. При k = 1 примитивность Ф(х) является необходимым и достаточным условием получения последовательности макси­мальной длины.

Последовательность максимальной длины принято называть М-последовательностью, а формирующий ее генератор - гене­ратором М-последовательности. Именно генераторы M-последовательностей обычно используются для формирования ПСП.

Каждая матрица V имеет характеристический многочлен φ(х) которым является определитель матрицы V - хЕ, т. е. φ(х) = |V - хЕ|, где Е - единичная матрица. Многочлен Ф(х) определяет только структуру генератора, свойства же последнего зависят именно от φ(х).

Свойство 1.2. Каждая квадратная матрица удовлетворяет своему характеристическому уравнению, т. е. φ(V) = 0.

Свойство 1.3. Характеристический и образующий многочлен ге­нератора связаны следующим соотношением:

φ(х) = Ф(x^-1)x^N,

т. е. являются взаимно обратными.

Примитивность φ(x) автоматически означает примитивность Ф(х) и наоборот.

Децимацией последовательности {qi(t)} по индексу k называет­ся формирование новой последовательности {q*_i(t)}, состоящей из k-х элементов {q_i(t)}, т. е. q*_i(t) = q_i(kt). Если период последо­вательности, полученной в результате децимации М-последовательности, равен максимальному, децимация называется собст­венной или нормальной.

Последовательность, снимаемая с выхода i-го триггера генератора, изображенного на рис. 2.14, является децимацией по индексу k последовательности, снимаемой с выхода i-го триггера генераторов, изображенных на рис. 2.12. Если Q - начальное состояние генератора, то последовательности состояний, в которых будут находиться устройства в следующие моменты времени, имеют вид

---

Q, QV, QV2, QV3, ...

(для устройства, изображенного на рис. 2.8) и

Q, QT, QT2, QT3, ...

(для устройств, изображенных на рис. 2.12, где Т = Т1 (а) или Т = Т2 (б)). Учитывая, что V = Tk, можно сделать вывод, что в ге­нераторе, показанном на рис. 2.14, за один такт осуществляются преобразования, которые в генераторах, показанных на рис. 2.12, происходят за k тактов. Таким образом, устройство, показанное на рис. 2.14, в котором содержимое первых k триггеров (при k ≤ N) полностью обновляется в каждом такте, может использо­ваться для генерации последовательности k-разрядных двоичных кодов, что нельзя сказать про устройства, показанные на рис. 2.12, которые формируют лишь сдвинутые копии одной и той же двоичной последовательности.

2.4. НЕЛИНЕЙНЫЕ ГПСП [7]

Генераторы последовательностей длиной pN.

Исключение запрещенного нулевого состояния всех разрядов генератора двоичных М-последовательностей позволяет уве­личить период формируемой последовательности и сделать его максимально возмож­ным, равным pN, и повысить ее качество. Например, при р = 2 вероятности появления 0 и 1 становятся равными 1/2. Последовательности длиной 2N называются последова­тельностями де Брейна (De Bruijn). Рассмотрим схему Фибоначчи. Уравнения работы генератора последовательности длиной 2N имеют вид

Q_j(t+1) = Q_j-1(t), j=.

Пусть p = 2ⁿ. Рассмотрим формирование последовательности длиной 2^nN, k = 1. Выберем α*GF(p), α* ≠ 0. Пусть

Тогда уравнения работы генератора последовательности длиной pnN имеют вид

Q_j(t+1)=Q_j-1(t), j = .

Рассмотрим формирование последовательности длиной p^N, р ≠ 2, в общем случае при произвольном k. Выберем α_i* GF(p), α_i* ≠ 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной pN имеют вид

где a_ji - коэффициенты матрицы T^k.

Пусть p = 2. Рассмотрим формирование последовательности длиной 2^nN при произвольном k. Выберем α_i* GF(p), α_i* ≠ 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной 2^nN имеют вид

Генераторы ПСП с предпериодом.

Рассмотрим принципы построения генераторов последовательностей произвольной длины.

Алгоритм построения генератора p-ичной последовательности длины S < pN:

1. Выбирается примитивный многочлен Ф(х) степени N.

2. Фиксируется произвольное ненулевое состояние Q0 генератора.

3. Моделируется t=pN-S тактов работы генератора ПСП и определяется состояние Qt.

4. Выполняется поразрядная операция XOR над кодами Q1 и Qt. Единичные биты результата определяют номера тех разрядов генератора, сигналы на входах которых необходимо инвертировать, когда генератор находится в состоянии Q0.

5. Управляемые инверторы реализуются на дополнительных элементах XOR, число которых и место в схеме генератора определяются результатом операции Q1 Qt.

---

Смотрите также файлы

• Раздатка.docx

• Доклад.docx

• Лекция 4.docx

• Лекция 5.docx

• Лекция 1.doc