Запреты двоичных функций: статья

УДК - 004021

Запреты двоичных функций

Бабаш А.В.

Известно (см., например, [1]), что в науке и технике и, в частности,
в
различных
системах
обеспечения
безопасности
широко
применяются
генераторы
псевдослучайных
последовательностей.
Так,
например,
эти
генераторы используются в синхронных поточных криптосхемах в качестве
управляющих блоков поточных криптосхем. Основные требования к таким
генераторам сформулированы в [2, стр. 247]. Одно из этих требований
состоит
в
том,
что
последовательность,
вырабатываемая
генератором,
должна
иметь
большой
период.
Другое,
не
менее
важное,
требование
состоит в том, что статистические свойства выходной последовательности
генератора должны приближаться к свойствам случайной равновероятной
последовательности.
В
частности,
последовательности
таких
генераторов
должны содержать любые возможные k-граммы выходного алфавита при
небольших значениях k. Имеет определенный смысл решение вопроса о
принципиальной возможности получения заданных мультиграмм в выходных
последовательностях
генераторов
псевдослучайных
чисел
или
решение
обратной
задачи
о
том,
какие
мультиграммы
в
принципе
не
могут
быть получены на выходе генератора, какова минимальная длина таких
мулътиграмм. Как показано в [2] может оказаться, что число различных
мультиграмм,
снимаемых
с
управляющих
блоков
шифратора,
которые
участвуют в образовании шифра шифрующего блока, мало. Это, очевидно, в
худшую сторону отразится на криптографической стойкости рассматриваемого
шифратора. Исследование поставленных вопросов стимулируется и другими
соображениями. Например, зная мультиграммы, которые не могут быть
получены с некоторого блока генератора псевдослучайных чисел, можно, при
применении методов определения ключей такого генератора, отбраковывать эти
ключи, что может повысить эффективность этих методов.
Если
моделировать
функционирование
генераторов
псевдослучайных
чисел автоматами, то естественно возникает задача описания автоматов,
позволяющих выработать любую конечную последовательность элементов
выходного алфавита. Такие автоматы называются автоматами генераторами.
Слова, составленные из выходного алфавита автомата, которые не могут
присутствовать в выходных последовательностях автомата обычно называют
запретами. Минимальную длину запретов называют длиной запрета автомата.
В [3, 4] доказано, что если перечисляющий автомат имеет |S| состояний,
то существует распознающий автомат имеющий не более 2|S| состояний. Из
этого утверждения следует, что каждый автомат, не являющийся автоматом
генератором, таков, что длина его запрета ограничена величиной 2|S| − 1.

1

Прототипом выше указанных задач является задача изучения запретов
кодирующих устройств с конечной памятью без обратной связи (регистров
сдвига), или адекватная задача изучения запретов двоичных функций (см. [5,
6]). В работе [6] доказано, что для функций с запретом, оценка длина запрета
не превосходит величины 22n −1. Там же найдены классы двоичных функций с
оценкой длины запрета меньшей, чем 22n −1. В данной работе получена лучшая
оценка длины запрета для всех двоичных функций с запретом. Оценка имеет
порядок n223n.
Двоичную
проходную
линию
задержки
иногда
называют
(см.
[5])
кодирующим
устройством
(КУ)
и
определяют
как
устройство,
перерабатывающее
произвольную
входную
двоичную
последовательность
x1, x2, ..., xj, ... в выходную двоичную последовательность y1, y2, ..., yj, ... по
следующему закону:

yj = f(xj, xj+1, ..., xj+n−1),
j ∈ {1, 2, ...},

где f(z1, ..., zn) = f(z) - некоторая двоичная функция от n переменных. Без
ограничения общности далее предполагается, что n ≥ 2, переменные z1 и zn
являются существенными переменными в функции f(z1, ..., zn) = f(z).
Рассмотрим
бесконечную
систему
уравнений,
связывающих
значения
выходной последовательности КУ со значениями входной последовательности:

f(x1, x2, ..., xn) = y1,

f(x2, x3, ..., xn+1) = y2,

. . . . . . . . . . . . . . . . . . . . . ..

f(xj, xj+1, ..., xj+n−1) = yj,

. . . . . . . . . . . . . . . . . . . . . . . . . . .

Возможны два случая:
1) для любого натурального числа k система уравнений

f(xj, xj+1, ..., xj+n−1) = yj,
j ∈ {1, 2, ..., k},

совместна при любых значениях правых частей, либо
2) найдется такое натуральное число k∗ и такой набор (y∗
1, ..., y∗
k∗) ∈ F k∗
2 , что
система уравнений

f(xj, xj+1, ..., xj+n−1) = y∗
j,
j ∈ {1, 2, ..., k∗},

2

несовместна, то есть отрезок выходной последовательности(y∗
1, ..., y∗
k∗) не может
быть получен с помощью данного КУ ни при каких значениях x1, x2, ..., xk∗+n−1
В первом случае говорят ([6]), что функция f(z) не имеет запрета, или
– функция f(z) без запрета. Во втором случае говорят, что функция f(z)
имеет запрет, или функция f(z) с запретом. При этом k∗-грамма (y∗
1, ..., y∗
k∗)
называется запретом функции f(z), а число k∗ - длиной запрета ([6]).
Заметим, что если (y∗
1, ..., y∗
m) - запрет функции f(z), то для любой
выходной последовательности y1, y2, ..., yj, ... , полученной с данного устройства,
(yj+1, ..., yj+m) = (y∗
1, ..., y∗
m) при всех натуральных j.
Для
формулировки
критерия
наличия
запрета
у
двоичной
функции
напомним одно понятие, которое представляет и самостоятельный интерес.
Функция f(z) называется сильно равновероятной ([6]), если для любого
натурального числа k и любого набора двоичных переменных y1, y2, ..., yk
система уравнений

f(xj, xj+1, ..., xj+n−1) = yj,
j ∈ {1, 2, ..., k}

имеет ровно 2n−1 решений.
Критерии наличия запрета двоичной функции
В [6] доказано следующее утверждение.
Теорема 1. Двоичная функция f(z) не имеет запрета тогда и только
тогда, когда она сильно равновероятна.
Кодирующее устройство с функцией f (z1, ..., zn) называется КУ с потерей
информации (см. [5]), если существуют две входные различные двоичные
последовательности x1, x2, ..., xL и x′
1, x′
2, ..., x′
L одинаковой длины L ≥ 2n − 1,
преобразуемые этим устройством в одну и ту же последовательность, такие, что
их начала длины n − 1 совпадают (x1, ..., xn−1) =
x′
1, ..., x′
n−1
и совпадают их

концы длины n − 1
xL−(n−2), ..., xL
=
x′
L−(n−2), ..., x′
L
. В противном случае
КУ называется КУ без потери информации. Данное понятие впервые ввел
Хаффмен [7]; при выполнении первого условия (КУ с потерей информации) КУ
называлось необратимым, в противном случае (КУ без потери информации) обратимым.
Замечание. В работах [6, 7] приведены равносильные определения КУ с
потерей информации (необратимых КУ). В них требовалось наличие различных
входных последовательностей с одинаковыми началами и концами длины n.
Теорема 2 [6]. Двоичная функция f(z) имеет запрет тогда и только
тогда, когда кодирующее устройство с этой функцией является кодирующим
устройством с потерей информации.
Оценки длины запрета двоичной функции
В теореме 2 работы [6] доказано, что если n ≥ 3 и для функции f(z1, ..., zn)
существует двоичный набор y∗
1, ..., y∗
m длины m, для которого система уравнений

f (xt, xt+1, ..., xt+n−1) = y∗
t , t ∈ {1, 2, ..., m}

3

имеет 2n−1 − α решений, где α ≥ 1, то функция f(z1, ..., zn) имеет
запрет длины, не более

m + 2n(2n−2 − 1)(m + n − 1).

Ниже в теореме 3 мы приводим и доказываем лучшую оценку длины запрета
двоичной функции. Обозначим через [υ] целую часть числа υ.
Теорема 3. Если для двоичной функции f(z1, ..., zn) существует двоичный
набор y∗
1, ..., y∗
mm, для которого система уравнений

f (xt, xt+1, ..., xt+n−1) = y∗
t , t ∈ {1, 2, ..., m},

имеет число решений 2n−1 − α, , α ≥ 1, то функция f(z1, ..., zn) имеет
запретную комбинацию длины

m + (n + m − 1)
(n − 1) 2n−1 ln 2

α

.

В частности, длина запрета функции f(z1, ..., zn) не больше

m + (n + m − 1)
(n − 1) 2n−1 ln 2
.

Доказательство. Рассмотрим все двоичные наборы вида

y∗
1, ..., y∗
m, ym+1, ..., ym+n−1, y∗
1, ..., y∗
m, y2m+(n−1)+1, ..., y2m+2(n−1), ...
..., ykm+(k−1)(n−1)+1, ..., ykm+(k−1)(n−1)+n−1, y∗
1, ..., y∗
m
в качестве выходных последовательностей КУ с функцией f(z). Указанные
наборы построены следующим образом. Сначала идет двоичный набор y∗
1, ..., y∗
m,
затем произвольный двоичный набор длины n − 1, затем опять набор y∗
1, ..., y∗
m,
потом опять произвольный набор длины n − 1 и так далее.
Всего существует (2n−1)k различных наборов длины k(m + n − 1) + m
данного вида. Так как прообразы (решения) для рассматриваемых наборов
имеют длину (k+1)(m+n-1), а их общее число равно (2n−1 − α)k+1, то среднее
число прообразов для одного набора рассматриваемого вида равно

2n−1 − α

2n−1

k
·
2n−1 − α
.

Найдем натуральное число ¯k, при котором эта величина меньше 1. Такое ¯k
должно удовлетворять неравенству

1 −
α

2n−1

¯k+1
<
1

2n−1.

При этом ¯k функция f(z1, ..., zn) будет иметь запрет длины

¯k + 1
· m + ¯k · (n − 1) = m + ¯k (n + m − 1) .

4

Воспользуемся неравенством

1 − x < e−xдля
x > 0.

Имеем

1 −
α

2n−1

¯k+1
< e−
α(¯k+1)

2n−1 .

Найдем теперь ¯k из неравенства

e−
α(¯k+1)

2n−1 ≤
1

2n−1.

Логарифмируя обе части неравенства, имеем

−α
¯k + 1
2n−1
≤ − (n − 1) ln 2,

или

¯k ≥ (n − 1) · 2n−1 ln 2

α
.

¯k = (n − 1) · 2n−1 ln 2

α
,

получаем требуемое утверждение теоремы.
Следствие 1. Если двоичная функция f(z1, ..., zn) неравновероятна, то она
имеет запрет длины, не больше

1 + n
(n − 1) · 2n−1 ln 2
.

Данная оценка лучше оценки

1 + n2n(2n−2 − 1),

приведенной в следствии теоремы 2 работы [6].
Основной результат данной статьи содержится в теореме 4.
Теорема 4. Если двоичная функция f(z1, ..., zn) имеет запрет, то его длина
не больше

2n−2 2n−1 − 1
+ 1
· n · (
(n − 1) · 2n−1 ln 2
+ 1) + n2 − n + 1.

Доказательство. Пусть γ (f, k) - максимальное по всем возможным наборам
y1, ..., yk число решений системы уравнений

f (xj, xj+1, ..., xj+n−1) = yj, j ∈ {1, ..., k}.

Докажем сначала вспомогательную лемму.

5

Лемма
1.
Если
двоичная
функция
f(z 1,...,z n)
имеет
запрет,
то
существует такое

L ≤ 2n−1 (2n−1 − 1)

2
+ n,

при котором

γ (f, L · k − (n − 1)) ≥ 2k

при всех k ∈ {1, 2, ...}.
Доказательство. Сначала докажем наличие для КУ с функцией f
и
потерей информации различных входных последовательностей с одинаковыми
началами и концами длины n-1 перерабатывающихся в КУ в одну и ту же
выходную последовательность длины L − (n − 1), где

L ≤ 2n−1 (2n−1 − 1)

2
+ n.

По теореме 2 КУ с функцией, имеющей запрет, является КУ с потерей
информации. Среди всех пар входных последовательностей с одинаковыми
началами и концами длины n − 1, перерабатываемых КУ в одну и ту
же выходную последовательность, выберем пару (x1, ..., xL) и (x′
1, ..., x′
L) с
минимальной длиной L ≥ 2n − 1.
Рассмотрим для выбранной пары последовательностей последовательности
их (n-1)-грамм

˜x1, ˜x2, ..., ˜xL−n+1, ˜xL−n+2, ˜x′1, ˜x′2, ..., ˜x′L−n+1, ˜x′L−n+2,

где

˜x1 = ˜x′
1, ˜xL−n+2 = ˜x′
L−n+2
,

˜xj = xj, xj+1, ..., xj+n−2,
˜x′
j = x′
j, x‘j+1, ..., x‘j+n−2,
j ∈ {1, ..., L - n + 2}.

Так как выбранные последовательности перерабатываются КУ в одну и ту же
выходную последовательность и имеют минимальную длину, то

1) ˜xj ̸= ˜x′
j,
j ∈ {2, ..., L - n + 1},

2)
˜xj
˜x′
j

̸=
˜xk
˜x′
k

,
j, k ∈ {2, ..., L - n + 1},
j ̸= k,

3)
˜xj
˜x′
j

̸=
˜x′
k
˜xk

,
j, k ∈ {2, ..., L - n + 1},
j ̸= k.

Поэтому, исходя из элементарных комбинаторных фактов, имеем

L − n + 2 − 2 ≤ C2
2n−1 = 2n−1 (2n−1 − 1)

2
,

6

или

L ≤ 2n−1 (2n−1 − 1)

2
+ n.

Лемма 4 доказана.
Продолжим доказательство теоремы 7. Пусть функция f(z) имеет запрет.
По лемме 4 имеем

γ (f, Ln − (n − 1)) ≥ 2n > 2n−1

при некотором

L ≤ 2n−1 (2n−1 − 1)

2
+ n.

Следовательно, найдется набор двоичных переменных y∗
1, ..., y∗
m длины m =
L · n − (n − 1), при котором число решений системы уравнений

f (xj, xj+1, ..., xj+n−1) = y∗
j,
j ∈ {1, ..., m},

есть величина 2n−1 − α, где α ≥ 1. По теореме 3 функция f(z) имеет запретную
комбинацию длины

m + (n + m − 1)
(n−1)2n−1 ln 2

α
≤ L · n − n + 1 + L · n
(n−1)2n−1 ln 2

α
≤

≤
2n−1(2n−1−1)

2
+ n
· n · [(n − 1) 2n−1 ln 2] +
2n−1(2n−1−1)

2
+ n
· n − n + 1
,

Последняя величина совпадает с величиной

2n−2 2n−1 − 1
+ 1
· n · (
(n − 1) · 2n−1 ln 2
+ 1) + n2 − n + 1,

что и требовалось показать.
Теорема 4 оценивает минимальную длину запрета произвольной двоичной
функции f(z), имеющей запрет. Заметим, что ранее полученная для этого
случая оценка имела вид: 22n-1 (см.[6], стр. 50).

Литература

[1] Варфоломеев А.А., Жуков А.Е., Пудовкина М.А. Поточные криптосхемы.
Основные свойства и методы анализа стойкости. М.: МИИ, 2000, 243 стр.
[2] Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы
криптографии. М.: Гелиос АРВ, 2002, 480 стр.
[3] Лупанов О.Б. О сравнении двух типов конечных источников. - Проблемы
кибернетики, М., Физмат-гиз, том 9, 1963, с. 321-326.
[4] Ершов Ю.Л. О гипотезе В.А. Успенского. - Алгебра и логика, (семинар),
том 1, №4, 1962, с. 45-48.

7

[5] Preparata F. P. Convolutional transformations of binary sequences: Boolean
functions and their resynchronizing properties. - IEEE Trans. Electron. Comput.,
1966, v. 15, N 6, p. 398-909.
[6] Сумароков С.Н. Запреты двоичных функций и обратимость для одного
класса кодирующих устройств. - Обозрение прикладной и промышленной
математики. Том 1, вып. 1, 1994, c. 33-55.
[7] Huffman D.A. Canonical forms for information-lossless finite state logical
machines. - IRE Trans. Circuit Theory, v. 6, spec. suppl.,1959, p. 41-59.

8