logo
Информационная безопасность / Информационная безопасность2006

Логическая операция xor как шифрование (дешифрование) потока бит.

Операция кодирования

Обратная операция декодирования

ci := xi XOR ci-1

yi := ci XOR ci-1

Пусть {xi} – исходная последовательность потока бит.x{0,1}. {.} – символ множества.i– номер по порядку символаxв последовательности, {ci} – кодированная (шифрованная, заксоренная) последовательность.

здесь x,c,y{0,1}

Реализация операций.

Здесь

– сумматор по модулю 2 c=aXORb.

a

b

c

0

0

0

0

1

1

1

0

1

1

1

0

– задержка информации на один такт

Например, с помощью D-триггера. Значение «а» на входе D запоминается триггером на выходе Q в момент прихода на вход c положительного перепада тактовых импульсов. На рисунках схем реализации генератор тактовых импульсов не показан.

Покажем, что yi = xi

Обозначим суммирование по модулю 2 – 

Тогда ci=xici-1(1)

yi=cici-1(2)

Т. к.: yi=cici-1=xici-1ci-1, аci-1ci-1= 0, тоyi=xi(3)

Или иначе (в общем случае):

т. к. ci-1=xi-1ci-2, (4)

то, подставляя в (2) величины (1) и (4), получим:

yi=xici-1xi-1ci-2.

Но из (2) имеем

ci-1ci-2=yi-1

Следовательно: yi=xixi-1yi-1

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

Преобразование xiyiможно рассматривать как частный случай теории цифровых фильтров дляxиy– двоичных чисел и сумм по модулю два. Согласно теории цифровых фильтров возмем для выражений (1) и (2)Z-преобразование.

с(z)=x(z)c(z)z-1y(z)=c(z)z-1y(z)=c(z)(1z-1)

x(z)=c(z)c(z)z-1x(z)=c(z)(1z-1)

Т.к. операции сложения и вычитания по модулю 2 тождественны

и по правилу сдвига Z-преобразования получаем

yi=xi

Совместную пару операций XORкодирования/декодирования получим и при взятии дополнительной операции отрицания¯ci

ci := xi XOR ci-1

xi := ci XOR ci-1

ci

¯ci

0

1

1

0

ci

¯ci

=1

T

ci

xi

=1

T

ci

xi

Теперь возьмем вместо одного элемента задержки несколько последовательно соединенных, т.е. регистр сдвига, а вместо одновходовой операции отрицания – логический преобразователь (ЛП), имеющий несколько входов и один выход

Снова получим совместную пару устройств кодирования/декодирования.

Такие устройства называют скремблерами/дескремблерами. ЛП удобно реализовать на микросхемах памяти (ПЗУ), содержащих 2nячеек. ТогдаNi– адресi-той ячейки.Qi– информация (0, 1) записанная в ней.

Формула работы скремблера.

ci=xiQi

Qi = φ(N)

N = ci-1 + 2  ci-2 + 22ci-3 + … + 2n-1ci-n

N– десятичный эквивалент двоичного числаci-1ci-2…ci-n(ci-1 – младший разряд) состояния регистра сдвигаRG1, являющегося адресом ячейки ПЗУ.

Итак, ci=xiφ(RG1)φ(N) =φ(RG1) (6)

Для дескремблера

yi=ciφ(RG1) (7)

Если функции для ЛП1 и ЛП2 одинаковы: φ(RG1) =φ(RG2), то выражения (6) и (7) аналогичны (1) и (2). Соответственно будем иметь и утверждение

yi=xi

Особенности свойств системы скремблер/дескремблер в общем случае с произвольной таблицей памяти ЛП не исследованы.

Получили широкое распространение и исследованы свойства системы скремблер/дескремблер с ЛП из линейки сумматоров по модулю два. Например:

T

T

T

T

T

T

З

a

b

c = a XOR b

десь для наглядности сумматор по модулю два обозначен