Криптографические генераторы. 
Системные и прикладные аспекты

Криптографические генераторы используются для выработки ключей криптосистем, случайных инициальных векторов и управляющей гаммы поточных шифров. Обозначим через ?(у) длину периода гаммы {у,} генератора, через Л (у) — ее линейную сложность.

Базовым элементом криптосхем многих генераторов является ЛРС с максимальной длиной периода, выходная гамма которого (ЛРИ) имеет и хорошие статистические свойства. В то же время линейный размах ЛРП равен ее порядку, что позволяет восстанавливать всю ЛРП по ее сравнительно небольшому отрезку. Следовательно, ЛРС слаб как генератор, и его использование следует сочетать с различными функциональными узлами и элементами памяти. Назначение последних — привнести в функции криптосистемы нелинейные свойства и зависимость каждого знака выхода от возможно большего числа знаков входа, не теряя положительные свойства ЛРП. Гамма такого генератора есть определенное усложнение ЛРП.

Фильтрующие генераторы.

Пусть Р — конечное поле порядка к. Фильтрующий генератор (ф.г.) над Р — это автономный автомат А^ Г = (Рп, Р, А, У), где функция переходов к реализует с помощью ЛРС длины п линейную подстановку пространства Рп, функция выходов / называется фильтром или фильтрующей функцией. Знаки гаммы заданы уравнениями.

где х е Р^п — начальное состояние ЛРС. Ф.г. называется нелинейным, если фильтр /{х_ь …, х_п) нелинейный. Ключевые элементы ф.г. — начальное состояние ЛРС, могут быть также характеристический многочлен ЛРС и фильтр /(х_х,…, х_п). Схема генератора дана на рис. 14.2.

Рис. 14.2. Фильтрующий генератор.

Отметим свойства ф.г.:

• 1) бе^(/г^/-1(х)) = ?е&(х), г > 1, так как все выходные функции ф.г. эквивалентны фильтру/(х_{,…, х_п) относительно циклической группы (к) линейных подстановок;
• 2) если ф.г. использует ЛРСтах-и и сбалансированный фильтр, то длина периода гаммы равна к^и — 1, и числа «1» и «О» на периоде гаммы сбалансированы;
• 3) нелинейные свойства гаммы обеспечиваются выбором нелинейного фильтра. Обозначим: Ф = degf (x_i9 …, х_п), тогда по следствию теоремы 9.7 линейная сложность Л (у) гаммы ф.г. не превышает ??(и, Ф) — числа различных конъюнкций от п переменных ранга от 0 до (I (не превышает ??(я, Ф) — 1 при /(0,…, 0) = 0). В случае Р = СД2) верна оценка Л (у) < ?(я, Ф).

Получение оценки снизу для Л (у) требует учета более глубоких свойств фильтра. Например, для некоторых булевых бент-функций доказано [23],.

что если п кратно четырем. В работах [16, 26] дана нижняя оценка при ЛРСтах-я: если однородный многочлен степени с1 (часть многочлена/(Дф …, х")) имеет вид где.

то Следовательно, для получения гаммы ф.г. с высокой линейной сложностью следует использовать фильтр /{х_х,…, х_п) большой степени нелинейности.

При простых п доля ф.г. на базе ЛРСшах-;?, у которых линейная сложность Л (у) достигает наибольшего значения $(я, Ф) [26], стремится к единице.

Комбинирующие генераторы (комб.г.) являются усложнением фильтрующих генераторов и построены на основе ЛРС-1 длины п_х, …, ЛРС-т длины п_т над Р, т > 1, и комбинирующей функции f (x_v …, х_т), на вход которой поступают знаки т ЛРП, вырабатываемых ЛРС-1,ЛРС-ш. Обозначим п = п_х + … + п_т, не теряя общности, положим: п_л < п₂ < … < п_т. Уравнения гаммообразования комб.г. имеют вид (справа ?-я выходная функция комб.г.):

где х№ — начальное состояние ЛРC-j, WxfII) есть i-я линейная выходная функция ЛРС-j, определенная в параграфе 8.6,7 = 1″ —, тп. Комб.г. изображен на рис. 14.3.

Рис. 143. Комбинирующий генератор.

Комбинирующий генератор называется нелинейным, если нелинейной является функция /(х_{у …, х_гп). Ключевые элементы комб.г. — начальные состояния всех ЛРС, могут быть также их характеристические многочлены и функция/(х_х,…, х_гп). Начальные состояния всех ЛРС образуют начальное состояние генератора. Начальное состояние комб.г. назовем неособенным, если начальное состояние каждого ЛРС отлично от нулевого. Наилучшие криптографические свойства комб.г. имеет в том случае, когда комбинирующая функция /(х_и …, х_т) зависит существенно от т переменных и начальное состояние является неособенным, иначе заданный комб.г. вырождается в комб.г. с меньшим числом ЛРС. Считаем, что далее эти условия безоговорочно выполнены.

Все выходные функции комб.г. эквивалентны /(х_х, …, х_п) относительно группы линейных подстановок пространства Р^п> поэтому с^/'(/₁б)(.г (¹)), …, 1_тЧ^^т))) = с1е^(г), I > 1.

Оценим линейную сложность гаммы генератора. Каждому каноническому полиному/(рс_х, …, х_т) над конечным полем Рпоставим в соответствие полином ^хт) ^наД кольцом целых чисел Z, полученный из.

^х_т) заменой всех ненулевых коэффициентов на единицу и заменой сложения и умножения в поле Р сложением и умножением в кольце И.

Теорема 14.1. Если /(х_Ху ^х_т) — канонический полином комбинирующей функции, то при любом неособенном начальном состоянии комб.г.

Му) ^/Мл…О- >

Оценка теоремы 14.1 для А (у) в некоторых условиях заменяется точным равенством: А (у) = /₂(п_Ху …, п_т). В частности, равенство верно [1, 26], если Р — простое поле, характеристические многочлены всех ЛРС комб.г. примитивны и имеют попарно взаимно простые степени.

При определенных ЛРС и функции/(х_{у…, х_т) гамма комб.г. имеет хорошие статистические свойства и большую длину периода ?(у). В частности, если ЛРС-1, ЛРС-/// генерируют последовательности, длины периодов которых …, Ь_т попарно взаимно просты, и функция/(х_{,…, ^х_т) биективна по каждой переменной, то ?(у) = Ь_{.Х_т по следствию теоремы 8.3. В случае Р = СЕ (2) условие на функцию /(х_Ху …, ^х_т) можно ослабить. Обозначим: 2(^х) — число единиц на периоде гаммы комб.г. при начальном состояниих;

Теорема 14.2. Пусть в комб.г. все ЛРС — максимального периода и длины их п_1у…, п_т попарно взаимно просты. Тогда ?(у) = т_т и при любом х верно 2^п~^т(-2^х~^п) < г_х(х) / ||/|| < 2^п~^т. >

Следствие. Если /(х_{1 …, х_т) равновероятна, то 2″ ^-1 — 2″"^я1 < г_х(х) < < 2^п~К >

Пример 14.1.

Генератор Геффе использует комбинацию генерирующих ЛРС-1, ЛРС-2 и управляющего Л РС-3. Комбинирующая функция/(х_х, х_2ух₃) =х₁х₃@х₂(х₃ © 1). В каждом такте знак гаммы при управляющем знаке «1» совпадает с выходным знаком ЛРС-1, а при управляющем знаке «О» — с выходным знаком ЛРС-2. Если все ЛРС имеют максимальные периоды и их длины щ, п₂, Щ попарно взаимно просты, то период гаммы равен произведению периодов ЛРС, а линейная сложность гаммы генератора равна щщ + п₂п₃ + п₂.1>

Пример 14.2.

Пороговый генератор использует комбинацию нечетного числа т регистров. Комбинирующая функция /(х_х, …, х,_п), называемая функцией мажорирования, равна 1 (х_{,…, х_т) > т / 2. При подходящих ЛРС длина периода гаммы порогового генератора равна произведению длин периодов ЛРС. При т = 3 и /(.гу, х₂, х₃) = = х_хх₂ © х_хх₃ 0 Х2?с₃ линейная сложность гаммы равна п_Лп₂ + п_хп₃ + п₂п₃. >