Коды и шифры

M12. Восстановление двоичной линейной рекурренты по отрезку гаммы

Пример

По шифрованному тексту сообщения восстановлены следующие 15 двоичных знаков гаммы:

101010011000100,

записанные слева направо в порядке их выработки. Проверить, что они могут быть порождены линейной рекуррентой степени5.

Решение

Линейная рекуррента степени 5 имеет вид:

U_n = aU₍_n_-1) + bU₍_n_-2) + cU₍_n_-3) + dU₍_n_-4) + eU₍_n_-5),

где a, b, c, d и e - это неизвестные константы, равные либо 0, либо 1, поскольку все вычисления происходят по модулю 2.

Пронумеруем биты слева направо от 1 до 15 и подставим в рекуррентную формулу значения битов для n=6, 7, 8, 9 и 10. Таким образом, получаем пять линейных уравнений относительно неизвестных a, b, c, d и e:

a1 + b0 + c1 + d0 + e1 = 0 (A.1)

a0 + b1 + c0 + d1 + e0 = 0 (A.2)

a0 + b0 + c1 + d0 + e1 = 1 (A.3)

a1 + b0 + c0 + d1 + e0 = 1 (A.4)

a1 + b1 + c0 + d0 + e1 = 0 (A.5)

Из уравнений (A.1) и (A.3) находим, что a=1, и тогда из уравнения (A.4) следует, что d=0. Теперь из уравнения (A.2) получаем, что b=0, а из уравнения (A.1) находим c=0. Таким образом, получено решение данной системы из пяти уравнений:

U_n = U₍_n_-1) + U₍_n_-5).

Теперь необходимо проверить, что это решение дает правильные значения битов для n=11, 12, 13, 14 и 15. Легко видеть, что это действительно так. Итак, мы убедились в том, что только что найденная нами рекуррента степени 5 действительно порождает данный отрезок гаммы.

Как уже было сказано в главе 8, могут возникнуть ситуации, когда для данной степени k решение отсутствует, или когда решений будет несколько. В первом случае система уравнений оказывается несовместной, а во втором случае неоднозначности обычно устраняются при наличии дополнительных знаков гаммы. Эти ситуации проиллюстрированы следующими примерами.

Пример (более одного решения)

Проверить, что следующие 10 двоичных знаков гаммы

0110110110

могут быть порождены двумя двоичными линейными рекуррентами степени5.

Проверка

Допустим, рекуррента выглядит следующим образом:

U_n = aU₍_n_-1) + bU₍_n_-2) + cU₍_n_-3) + dU₍_n_-4) + eU₍_n_-5).

Пронумеруем биты слева направо от 1 до 10 и подставим в рекуррентную формулу значения последовательных разрядов для n=6, 7, 8, 9 и 10. Отсюда получаем систему уравнений:

aббббб+бcб+бdббббб=б1,

aб+бbббббб+бdб+бeб=б0,

ббббbб+бcббббб+бeб=б1,

aббббб+бcб+бdббббб=б1,

aб+бbббббб+бdб+бeб=б0,

которая имеет два истинных набора решений степени5 (т.е. таких, в которых e, коэффициент при U₍_n_-5), не равен нулю):

a=b=c=0, d=e=1

a=d=0, b=c=e=1.

Таким образом, мы получили две линейные рекурренты степени5:

U_n = U₍_n_-4) + U₍_n_-5)

U_n = U₍_n_-2) + U₍_n_-3) + U₍_n_-5).

Кроме того, существуют еще и решения, в которых e=0 (т.е. решения, степень которых отлична от 5), в том числе:

a=b=1, c=d=e=0,

которое соответствует рекурренте, имеющей степень 2:

U_n = U₍_n_-1) + U₍_n_-2).

Это показывает, что приведенная выше двоичная последовательность есть не что иное, как последовательность чисел Фибоначчи, приведенных по модулю 2.

Пример (отсутствие решения при заданной степени)

Проверить, что последовательности шести двоичных разрядов гаммы

011010

не может быть порождена никакой линейной рекуррентой степени 3.

Проверка

Если такая рекуррента существует, то она имеет вид:

U_n = aU₍_n_-1) + bU₍_n_-2) + c U₍_n_-3).

По имеющимся данным составим систему уравнений

aб+бbббббб=б0,

áááábá+ácá=á1,

aббббб+бcб=б0.

Складывая первое уравнение со вторым по модулю 2, получим

aá+ácá=á1,

что противоречит первому уравнению. Поэтому система уравнений несовместна, и ни одного решения степени3 не существует.

Содержание