Рис. 4 Регистр с линейной обратной связью
В данной части документа приводится короткий обзор нескольких механизмов шифрования, необходимых для понимания некоторых процедур обеспечения секретности в GSM.
Симметричными алгоритмами называются алгоритмы, использующие один и тот же ключ как для шифрования данных, так и для их последующей расшифрования. Например, если обозначить данные переменной P, шифрованные данные переменной C, шифрование с ключом x - функцией Ex() и, соответственно, расшифровку с ключом x - Dx(), то симметричный алгоритм будет выглядеть следующим образом:
C=Ex(P)В хороших алгоритмах шифрования секретность данных в основном зависит от секретности ключа, и соответственно, в случае симметричных алгоритмов, от решения проблемы управления ключами. Наиболее широко известным симметричным алгоритмом является алгоритм Стандартного Шифрования Данных (Data Encryption Standard - DES). Симметричные алгоритмы подразделяются на алгоритмы шифрования блоками (Block Ciphers) и алгоритмы шифрования потока данных (Stream Ciphers).
При шифровании блоками, как следует из самого названия метода, все данные подразделяются на блоки или группы битов. DES использует 56-битовый ключ и имеет дело с 64-битовыми блоками, выдавая в обратном порядке 64 бита шифрованных данных на каждые 64 бита входных. Далее алгоритмы шифрования блоками характеризуются типами операций, таких как электронная книга кодов (Electronic code book - ECB), цепочка шифрованных блоков (cipher block chaining - CBC) и шифрованной обратной связью (cipher feedback - CFB). В случаях операций, таких как CBC и CFB, шифрация последующих блоков основывается на результатах одной или более предыдущих шифраций. Применение всех этих типов операций представляется весьма желательным, поскольку они нарушают соответствие один-к-одному, между шифрованными и входными блоками (как в случае ECB). Шифрование блоками может комбинироваться с шифрованием потока данных.
Шифрование потока данных оперирует на основе бит-за-битом подаваемых данных, выдавая для каждого входного бита, отдельный шифрованный бит. Шифрование потока данных обычно реализуется применением операции исключающего или (Exclusive-or - XOR) для потока ключа и потока данных. Секретность шифрования потока данных, таким образом, целиком зависит от свойств потока ключа.
Регистр с линейной обратной связью или Сдвиговый линейный регистр с обратной связью (Linear Feedback Shift Registers - LFSRs) являются компонентой ключа во многих алгоритмах шифрования потоков данных. В LFSC сигнал обратной связи формируется линейной логической схемой (linear logic - система из комбинационных и, возможно, последовательных схем, в которой комбинационная часть состоит только из вентилей "исключающее или". В недвоичных системах вместо вентилей "исключающее или" используются сумматоры и вычитатели по модулю q). В регистре с обратной линейной связью осуществляется обращение свертки внешней входной последовательности с последовательностью комбинационных коэффициентов (convolution). Если представить внешний входной сигнал в виде многочлена, в котором степени независимой переменной означают временную задержку, а комбинационные коэффициенты аналогичным образом представить в виде второго многочлена, то регистр с линейной обратной связью можно рассматривать как устройство деления первого многочлена на второй. В системах кодирования или цифровой обработки сигналов регистры с обратной связью могут быть двоичными или q-ичными и могут реализовываться программно или аппаратно. При отсутствии внешней входной последовательности регистр с внешней обратной связью может сам по себе использоваться для формирования m-последовательностей (периодическая последовательность максимальной длины, используется в качестве псевдослучайной последовательности) или при обеспечении параллельной загрузки сдвигового регистра исходным словом может работать как кодер (encoder) симплексных кодов (simplex codes). В обоих указанных применениях требуется, чтобы коэффициенты логической схемы соответствовали примитивному многочлену. Статистические свойства регистров с линейной обратной связью, такие как функция автокорреляции и спектральная плотность, делают их очень полезными для других приложений, таких как генерация псевдо-шума. Регистры с линейной обратной связью могут быть очень просто реализованы в "железе".
Последовательность максимальной длины, или m-последовательность равна 2n-1, где n - степень регистра сдвига. Пример m-последовательности приводится на Рис.4.. Этот LFSR генеририрует периодические m-последовательности, содержащие следующие состояния (1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110).
Для того, чтобы сформировать m-последовательность, внешняя входная последовательность LFSR должна соответствовать примитивному многочлену степени n по модулю 2.
Часто реализация алгоритмов шифрования потоков данных представляет из себя множественные LFSR, различными способами соединенные между собой и со схемами синхронизаторов (clocking schemes). Алгоритм A5, используемый для кодирования речи и сигнальных данных в GSM, представляет из себя алгоритм шифрования потоков данных, базирующийся на трех управляемых синхронизаторами LFSR.