Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Так как (г,/) = I, то из условия u(i -I,) = u(i - / ), і ^ 0,
следует, что для любых значений Z1, Z2, таких, что Z1 є O91 — 1, Z2 є 0, г — 1, выполняется равенство
и(і2-V = Ktf2-W)-
Отсюда, с учетом неравенства / < г, получаем, что
для Z1 є 0,/-1.
Это означает, что все регулярные выборки с шагом s из последовательности V9 начинающиеся с одного и того же
элемента с е 09q -1, совпадают. Тогда период любой выборки из последовательности v равен числу различных элементов из множества { ОД,..., q — 1 }, встречающихся в ней.
Будем говорить о выборке с шагом s из последовательности V, начинающейся с элемента v(i) как (/,л*)-выборке.
Обозначим подмножество элементов множества { 0, -1 } , встречающихся в фиксированной (/,$)-
выборке, через Sp(i9s), а его мощность через Jtl. Множество Sp(i9s) назовем носителем (i9s)-выборки. Заметим, что либо Sp(i9s) = Sp(J9S)9 либо Sp(i9s) nSp(j9s) = 09 i9Jel9s.
282
/ юточные системы шифрования
Будем считать, что первые г выборок (r<s) имеют различные носители, а любая из оставшихся s-r выборок совпадает с одной из первых г выборок. Тогда
q = kx +к2 + ... + кг Д > 1 ,/є I5г.
Так как период t последовательности V равен s • HOK(?j, к2 V5 кг), то для получения нижних оценок периода выходной последовательности у остается найти верхнюю оценку величины d = HOK (^1 Д2,.
Очевидно, что HOK (^1, к2кг)<к{ -к2.-..якг9 откуда
ГГ
Максимум функции
Таким образом, d <
\Г;
/ \
f(x)= ~ действительного переменного на отрезке [I, -S'] \х)
достигается при х =— и максимальное значение d равно eq/e. е
Теорема доказана.
§ 9.7. Методы анализа поточных шифров
Рассмотрим некоторые методы анализа поточных шифр-систем на примере шифров гаммирования.
В первую очередь необходимо исследовать вероятностные характеристики гаммы. Как мы уже знаем (см. гл. 6), имеются подходы к получению оценок вероятностей элементов неравновероятной гаммы по шифртексту, которые можно использовать при бесключевом чтении.
283
І лава 9
Второй подход связан с попытками линеаризации уравнений гаммообразования, то есть сведения задачи нахождения ключей криптографических алгоритмов к решению некоторой системы линейных уравнений.
При таком подходе определяющую роль играет линейная сложность исследуемых последовательностей. Значение линейной сложности определяет размеры системы линейных уравнений, которую надо решить для определения ключа по известной шифрующей гамме. Поэтому линейная сложность определяет эффективность криптоатаки на основе известного открытого текста для шифров гаммирования в классе методов линеаризации. Это обусловливает актуальность разработки методов построения псевдослучайных последовательное гей с высокой линейной сложностью.
К вопросу о статистических зависимостях в шифрующей гамме примыкают методы анализа, основанные на наличии у функции усложнения хороших приближений в классе линейных функций. Примером отображений, не имеющих линейных статистических аналогов хорошего качества, является класс бент-функций.
В случае наличия у функции усложнения линейного приближения криптоаналитик может заменить исследуемую схему схемой с линейной функцией усложнения. Если усложнению подвергалась линейная рекуррентная последовательность, то при такой замене результирующая гамма является суммой линейной рекурренты и некоторой случайной последовательности с “завышенной” вероятностью появления нуля. Тем самым задача сводится фактически к возможности определения ключа по “искаженному” выходу линейного регистра сдвига. Если число искажений невелико, то их появление не оказывает существенного влияния на сложность определения ключа.
Отметим, что функция усложнения может обеспечивать высокий уровень линейной сложности и хорошие статистические качества результирующей гаммы (например, равновероятность появления ее элементов), HO при этом она может иметь прибли-
284
I юточные системы шифрования
жение в классе линейных функций с большой вероятностью совпадения значений, что сводит на нет перечисленные положительные качества.
При оценке криптографических качеств поточных шифров, помимо алгебраических и статистических свойств шифрующей гаммы, необходимо учитывать также наличие между знаками гаммы зависимостей комбинаторного характера. Например, при использовании в качестве гаммы линейной рекуррентной последовательности с малым числом ненулевых коэффициентов в законе рекурсии может иметь место ситуация, когда значительное число знаков гаммы зависит лишь от небольшого числа знаков ключа. Если такая ситуация имеет место, то криптоаналитик получает возможность проверки гипотез о значениях части ключа, основываясь на статистических свойствах открытых сообщений, что является несомненной слабостью соответствующего алгоритма шифрования.
Таким образом, при создании криптографически стойких поточных шифрсистем необходимо учитывать возможности применения криптоаналитиком всей совокупности статистических, аналитических и комбинаторных свойств используемых преобразований. При этом дополнительные трудности создают постоянно возрастающие возможности вычислительной техники, позволяющие провести экспериментальные исследования тех характеристик поточных шифров, которые не удается изучить теоретически. В связи с этим необходимо подчеркнуть, что приведенные в данной книге требования к поточным шифрам являются необходимыми, но далеко не достаточными для создания стойких шифров. Вывод о криптографической стойкости конкретного шифра может быть сделан только на основе его комплексных исследований, проведенных с привлечением квалифицированных специа-листов-криптографов.
