какая логическая операция лежит в основе скремблирования
Скремблер: надёжно и просто
Эта статья написана для того, чтобы рассказать читателю, что такое скремблеры, обозначить области их применения и затронуть некоторые практические тонкости, а также раскрыть секреты алгоритма скремблирования.
Зачем и почему?
Иногда возникает необходимость зашифровать трафик, не прибегая к методам, требующим много времени и ресурсов на шифровку и расшифровку, а также реализацию алгоритма. Такое случается, когда мы стараемся защитить данные от пользователей или примитивных троянов со снифферами (анализаторами трафика), но эти данные не стоят того, чтобы прибегать к серьезным методам шифрования, так как нам не требуется высокая криптостойкость. Со стороны методов связи бывает необходимо уменьшить уровень излучаемых помех, распределив энергию равномерно, и повысить надежность синхронизации устройств. С этими задачами и справляется скремблирование.
Что же такое скремблер?
Скремблер (от англ. to scramble – перемешивать, шифровать) – это алгоритм, разработанный для побитной последовательной передачи информации, позволяющий зашифровать цифровой поток таким образом, что на выходе получается последовательность, обладающая свойствами случайной: равновероятным появлением нуля и единицы. Именно это позволяет надежно выделить тактовую частоту и постоянную мощность передаваемого сигнала, что и дает надежность синхронизации. Стоит отметить, что такое преобразование потока не меняет скорость передачи, а также является обратимым, то есть данные восстанавливаются обратным алгоритмом.
Как это работает?
У нас имеется передающая сторона, на которой выполняется скремблирование, а также принимающая сторона, на которой соответственно выполняется дескремблирование, то есть обратная операция. Исходная последовательность подается на вход скремблера, а также именно она выделяется дескремблером из принятой зашифрованной последовательности.
Главной частью скремблера является линейный n-каскадный регистр сдвига с обратными связями, генерирующий псевдослучайную последовательность (ПСП) максимальной длины 
. Основная операция, производимая при шифровании – сложение по модулю 2, то есть XOR (исключающее ИЛИ).
Типы скремблеров
По типу взаимодействия с регистром скремблеры делятся на два типа: самосинхронизирующиеся (СС-скремблеры) и аддитивные (АД-скремблеры или же скремблеры с установкой). И те, и другие имеют свои плюсы и минусы, которые станут ясны после более подробного рассмотрения алгоритмов.
СС-скремблер
Отличительной чертой самосинхронизирующегося скремблера является то, что шифрование производится на основе самой скремблированной последовательности, поступающей на вход регистра сдвига. Следствием этого является отсутствие необходимости предустановки состояний скремблера и дескремблера в идентичное начальное состояние, синхронизация происходит сама по себе. При потере синхронизации восстановление состояния не превышает числа тактов, равного числу ячеек регистра скремблера.
Сам алгоритм скремблирования в этом случае можно рассмотреть на простейшем примере.
CC-скремблер
Несложно заметить, что при выполнении такого алгоритма большую опасность представляет «лавинный эффект» вследствие размножения ошибок. Это происходит именно из-за того, что для шифрования каждого следующего бита используется результат шифрования предыдущих. А значит, что при ошибке в одном бите мы получим уже n неправильно зашифрованных бита (где n – число обратных связей регистра), которые впоследствии приведут к ошибке в 2n и так далее. Другой проблемой самосинхронизирующихся скремблеров является то, что первые k битов входящей последовательности в принципе не будут зашифрованы. К счастью, этого легко избежать искусственным добавлением шума в начало последовательности.
АД-скремблер
Аддитивные скремблеры не получают на вход регистра результат шифрования, чем избегают распространения ошибок и лавинного эффекта, однако скремблер и дескремблер требуют предварительной установки состояния регистра – ключа. На вход регистра поступает линейная комбинация уже находящихся в нем бит, она же суммируется с входящим сигналом, в результате чего и получается зашифрованная последовательность.
Сам алгоритм скремблирования в этом случае можно рассмотреть на простейшем примере.
АД-скремблер
На практике чаще всего применяются именно аддитивные скремблеры, так что далее проанализируем особенности этого алгоритма.
Синхронизация
В АД-методе скремблирования важную роль играет синхронизация состояний регистров скремблера и дескремблера, ведь при ее потере вся дальнейшая информация неизбежно теряется. Для поддержания синхронизации на практике используются такие методы, как добавление в поток информации синхронизирующих битов, заранее известных приемной стороне, что позволяет ей при ненахождении такого бита активно начать поиск синхронизации с отправителем, и использование высокоточных генераторов временных импульсов, что позволяет в моменты потери синхронизации производить декодирование принимаемых битов информации «по памяти» без синхронизации. Стоит отметить, что именно необходимость в синхронизации скремблеров привела Джеймса Х. Эллиса к идее криптосистем с открытым ключом, что впоследствии привело к созданию алгоритма шифрования RSA и протокола Диффи-Хеллмана.
Зацикливание и построение алгоритма
Разрядность скремблера – разрядность устройства памяти – идентична длине ключа для блочных шифров. От нее напрямую зависит криптостойкость данной системы. При длительном скремблировании неизбежно возникает зацикливание, то есть через определенное число тактов регистр возвращается в исходное состояние, после чего шифрование будет циклически повторяться. Это повторение происходит непосредственно из-за того, что в n ячейках регистра возможны только 
комбинаций бит, а значит, максимум через 
комбинаций состояние станет идентичным начальному. А значит, мы хотим достигнуть именно этой максимальной длины.
К счастью, для скремблера любой разрядности n существует такая комбинация обратных связей, при которой период 
реализуем. То есть за 
тактов значения в регистре ни разу не повторятся. Оказывается, для этого достаточно, чтобы скремблер был построен на основе неприводимого полинома степени n, не представимого по модулю 2 в виде произведения никаких других полиномов. Выбранные таким способом обратные связи и используются в схемах скремблирования, при этом мы получаем генератор последовательностей наибольшей длины (ПНД).
Алгоритм построения следующий:
находим неприводимый полином степени n
отбрасываем старший разряд в его двоичном представлении, так как он несет информацию только о степени этого полинома
по полученному двоичному представлению строим скремблер, 1 на соответствующих разрядах говорят о наличии обратной связи, 0 – об ее отсутствии
Так, например, для 15-ти разрядного регистра мы имеем неприводимый полином 
с двоичным представлением 1000000000000011 . После отбрасывания старшего бита получаем 000000000000011 , то есть скремблер с алгоритмом: 
.
Что в итоге?
Скремблирование – достаточно простой алгоритм, используемый для шифрования алфавитно-цифровой, графической, а также речевой информации для последующей передачи ее по системам связи.
Современные скремблеры несколько отличаются от их более ранних аналогов, так как для повышения криптостойкости совмещаются с асимметричными алгоритмами шифрования.
Тем не менее скремблеры повсеместно применяются и сейчас, как из-за простоты реализации, так и из-за других очевидных преимуществ данного алгоритма.
Логическое кодирование
Логическое кодирование употребляется для совершенствования потенциальных кодов на подобии:
Логическое кодирование используется для уменьшения длинных последовательностей одинаковых бит, приводящие к неизменному потенциалу, вставками бинарных единиц.
Для логического кодирования разработаны два основных способа уменьшения длинных последовательностей одинаковых бит:
Избыточные коды
Избыточные коды базируются на разделение начальной последовательности бит на порции, которые нередко именуют символами. После чего, исходный символ подменяют на новый, содержащий наибольшее количество бит нежели исходный.
Код 4В/5В затем передается по линии с помощью физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям нулей. Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не могут встретиться более трех нулей подряд.
Использование таблицы перекодировки является очень простой операцией, поэтому этот подход не усложняет сетевые адаптеры и интерфейсные блоки коммутаторов и маршрутизаторов.
Скремблирование
Скремблирование (англ. scramble — перемешивать) — разновидность кодирования информации, для передачи по каналам связи и хранения, улучшаюшая спектральные и статиcтические характеристики.
Скремблирование есть приведение информации к виду, по различным характеристикам похожему на случайные данные.
Перемешивание данных скремблером перед передачей их в линию с помощью потенциального кода является другим способом логического кодирования.
Методы скремблирования заключаются в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Например, скремблер может реализовывать следующее соотношение:
где Вi, — двоичная цифра результирующего кода, полученная на i-м такте работы скремблера, Ai — двоичная цифра исходного кода, поступающая на вход скремблера, Вi-3 и Bi-5 — двоичные цифры результирующего кода, полученные на предыдущих тактах работы скремблера, соответственно на 3 и на 5 тактов ранее текущего такта, операция исключающего ИЛИ (сложение по модулю 2).
Например, для исходной последовательности 111000000001 скрэмблер даст следующий результирующий код:
Таким образом, на выходе скремблера появится последовательность 111110001100, в которой нет последовательности из восьми нулей, присутствовавшей в исходном коде.
После получения результирующей последовательности приемник передает ее дескремблеру, который восстанавливает исходную последовательность на основа¬нии обратного соотношения:
Произведем обратную операцию с последовательностью 111110001100, для получения исходной последовательности:
Получаем исходную последовательность: 111000000001.
Различные алгоритмы скремблирования отличаются количеством слагаемых, дающих цифру результирующего кода, и сдвигом между слагаемыми. Так, в сетях ISDN при передаче данных от сети к абоненту используется преобразование со сдвигами в 5 и 23 позиции, а при передаче данных от абонента в сеть — со сдвигами 18 и 23 позиции.
Для улучшения кода AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами:
Скремблеры
В последнее время сфера применения скремблирующих алгоритмов значительно сократилась. Это объясняется в первую очередь снижением объемов побитной последовательной передачи информации, для защиты которой были разработаны данные алгоритмы. Практически повсеместно в современных системах применяются сети с коммутацией пакетов, для поддержания конфиденциальности которой используются блочные шифры. А их криптостойкость превосходит, и порой довольно значительно, криптостойкость скремблеров.
Суть скремблирования заключается в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах является XOR – «побитное исключающее ИЛИ». Параллельно прохождению информационного потока в скремблере по определенному правилу генерируется поток бит – кодирующий поток. Как прямое, так и обратное шифрование осуществляется наложением по XOR кодирующей последовательности на исходную.
Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа по следующему алгоритму. Из текущего набора бит выбираются значения определенных разрядов и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение («0» или «1») помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом (см. рис.1).
Рис.1.
Из теории передачи данных криптография заимствовала для записи подобных схем двоичную систему записи. По ней изображенный на рисунке скремблер записывается комбинацией «100112» – единицы соответствуют разрядам, с которых снимаются биты для формирования обратной связи.
Рассмотрим пример кодирования информационной последовательности 0101112 скремблером 1012 с начальным ключом 1102.
скремблер код.бит инф.бит рез-т 1 1 0 _ \ \ \_ 1 1 1 _ \_ \ \ \_ 0 XOR 0 = 0 0 1 1 _ \_ \ \ \_ 1 XOR 1 = 0 1 0 1 \_ \ \ 1 XOR 0 = 1и т.д.
Как видим, устройство скремблера предельно просто. Его реализация возможна как на электронной, так и на электрической базе, что и обеспечило его широкое применение в полевых условиях. Более того, тот факт, что каждый бит выходной последовательности зависит только от одного входного бита, еще более упрочило положение скремблеров в защите потоковой передачи данных. Это связано с неизбежно возникающими в канале передаче помехами, которые могут исказить в этом случае только те биты, на которые они приходятся, а не связанную с ними группу байт, как это имеет место в блочных шифрах.
Декодирование заскремблированных последовательностей происходит по той же самой схеме, что и кодирование. Именно для этого в алгоритмах применяется результирующее кодирование по «исключающему ИЛИ» – схема, однозначно восстановимая при раскодировании без каких-либо дополнительных вычислительных затрат. Произведем декодирование полученного фрагмента.
Число бит, охваченных обратной связью, то есть разрядность устройства памяти для порождающих кодирующую последовательность бит называется разрядностью скремблера. Изображенный выше скремблер имеет разрядность 5. В отношении параметров криптостойкости данная величина полностью идентична длине ключа блочных шифров, который будет проанализирован далее. На данном же этапе важно отметить, что чем больше разрядность скремблера, тем выше криптостойкость системы, основанной на его использовании.
Схемы с выбранными по данному закону обратными связями называются генераторами последовательностей наибольшей длины (ПНД), и именно они используются в скремблирующей аппаратуре. Из множества генераторов ПНД заданной разрядности во времена, когда они реализовывались на электрической или минимальной электронной базе выбирались те, у которых число разрядов, участвующих в создании очередного бита, было минимальным. Обычно генератора ПНД удавалось достичь за 3 или 4 связи. Сама же разрядность скремблеров превышала 30 бит, что давало возможность передавать до 2 40 бит = 100 Мбайт информации без опасения начала повторения кодирующей последовательности.
Рис.2.
Существенным недостатком скремблирующих алгоритмов является их нестойкость к фальсификации. Подробнее данная проблема рассмотрена на следующей лекции, применительно к созданию целых криптосистем.
Логическое кодирование, избыточные коды, скремблирование.
Логическое кодирование.
Избыточные коды.
Избыточные коды основаны на разбиении исходной последовательности бит на порции, которые называют символами. Каждый исходный символ заменяется на новый, который имеет большее количество бит, чем исходный. Например, логический код 4В/5В заменяет исходные символы длиной в 4 бита на символы в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных.
Избыточные коды также позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.
Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния.
Для обеспечения заданной пропускной способности линии передатчик, использующий избыточный код, должен работать с повышенной тактовой частотой.
Скремблирование.
Скремблирование не изменяет длину исходного кода, но изменяет последовательность следования 1 и 0. Методы скремблирования заключаются в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Наиболее часто используется операция «исключающее ИЛИ».
После получения результирующей последовательности приемник передает ее дескрэмблеру, который восстанавливает исходную последовательность на основании обратного соотношения.
Различные алгоритмы скремблирования отличаются количеством слагаемых и сдвигом между слагаемыми.
Различают две основных схемы скремблеров: самосинхронизирующиеся и аддитивные скремблеры.
Особенностью самосинхронизирующего скремблера является то, что он управляется самой скремблированной последовательностью, т.е. той, которая поступает в канал. Поэтому не требуется специальной установки состояний скремблера и дескремблера, т.к. они оказываются идентичными в результате записи в их регистры сдвига скремблированной последовательности. На приемной стороне выделение информационной последовательности происходит сложением по модулю два принятой скремблированной последовательности с псевдослучайной последовательностью (ПСП) регистра. Одним из недостатков самосинхронизирующихся скремблеров-дескремблеров является свойство размножения ошибок.Данный недостаток ограничивает число обратных связей в регистре сдвига. Второй недостаток самосинхронизирующихся скремблеров связан с возможностью появления на его входе так называемых «критических ситуаций», когда выходная последовательность приобретает периодический характер с периодом, меньшим длины ПСП. Для предотвращения таких ситуаций в скремблере и дескремблере предусматриваются специальные дополнительные схемы контроля, которые выявляют периодичность элементов на входе и нарушают ее.
Аддитивные скремблеры (с начальной установкой) позволяют производить установку начальных состояний регистров. Результирующий сигнал не поступает на вход регистра, и размножения ошибок не происходит. Недостатки самосинхронизирующихся скремблеров отсутствуют при аддитивном скремблировании. Однако в этом случае требуется предварительная идентичная установка состояний регистров скремблера и дескремблера.
Суммируемые в скремблере последовательности независимы, поэтому критических ситуаций не наступает. Отсутствие эффекта размножения ошибок и необходимость специальной защиты от нежелательных ситуаций делают способ аддитивного скремблирования предпочтительнее и экономически эффективнее, если не учитывать затрат на решение задачи взаимной синхронизации пары скремблер – дескремблер.
Исправление ошибок, код Хемминга.
Исправление ошибок.
Обработка и передача больших массивов информации, особенно в условиях помех, сопровождается появлением ошибок. Для большинства видов информации появление ошибок недопустимо (системы управления, математические расчеты и т.д.). Во многих случаях лучше исправлять уже возникшие ошибки, чем пытаться их предотвратить.
Код Хемминга.
Одна из простейших, но эффективных процедур исправления ошибок разработана Р. Хеммингом в 1948 г. и широко используется для защиты данных. Суть метода наглядно иллюстрируется диаграммами Венна. Пусть необходимо защитить слово длиной 4 бита, например 1110. Четыре бита информации хранятся в четырех областях, образованных пересечением трех окружностей (Рис.а). Затем записываются три бита четности (Рис. б) по правилу: полное число единиц в каждой окружности должно быть четным. Ошибка устранимого типа (только в одном бите из четырех) обнаруживается при проверке битов четности (Рис. в). Видно, что нарушение произошло в области пересечения окружностей А и С, но за пределами окружности В (Рис. г). Т.е. применение кода Хемминга позволяет локализовать сбойный бит, следовательно, исправить его.
В коде Хемминга для защиты четырехразрядного слова от одиночных ошибок требуется применение семиразрядного кодового слова. Поэтому этот код называют (7,4). Таким же двухпозиционным цифровым обозначением, состоящим из длины кодового и защищаемого слова, называют другие типы кодов защиты от ошибок.
Если в защищаемом слове возникают две и более ошибок, то код Хемминга не позволяет их исправить. Действительно, при возникновении двух ошибок код Хемминга определит эту ситуацию как появление одной ошибки, и попытка исправить ее приведет к появлению новых. Этот эффект может быть устранен введением дополнительного бита четности, расположенного за пределами пересекающихся окружностей (код Хемминга 8,4). Он не позволяет исправить двойные ошибки, но дает возможность блокировать введение новых ошибок. Используются другие разновидности кодов защиты: (16,11), (32,26), (64, 57). Их трудно представить в виде диаграмм Венна, но они просто реализуются аппаратным методом. Защита информации кодом Хемминга отличается высоким быстродействием.
Скремблирование
Скремблирование (англ. scramble — перемешивать) — разновидность кодирования информации, для передачи по каналам связи и хранения, улучшаюшая спектральные и статиcтические характеристики.
Примечание: Слово скремблер также имеет иное значение — это устройство для шифрования аналогового (телефонного, телевизионного) сигнала.
Скремблирование есть приведение информации к виду, по различным характеристикам похожему на случаные данные. Скремблирование выравнивает спектр сигнала, частоты появления различных символов и их цепочек.
Технология скремблирования
Наиболее распространённый способ скремблирования — смешивание сигнала с генератором псевдослучайных чисел. Аппаратные реализации скремблирования часто используют ГСЧ на сдвиговом регистре с линейной обратной связью.
Скремблирование применяется практически во всех современных средствах передачи информации и носителях. В частности, скремблирование используют: модем; жёсткий диск; компакт-диск и DVD.
Смотреть что такое «Скремблирование» в других словарях:
скремблирование — Простейший способ шифрования. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN scrambling … Справочник технического переводчика
скремблирование — 01.02.18 скремблирование [ scrambling]: Перестановка или перегруппировка данных для повышения безопасности хранящихся данных или эффективности схем защиты от ошибок. Источник … Словарь-справочник терминов нормативно-технической документации
скремблирование речевого сигнала — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN voice scrambling … Справочник технического переводчика
повторное скремблирование — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN rescrambling … Справочник технического переводчика
Скремблер — (англ. scrambled зашифрованный) программное или аппаратное устройство (алгоритм), выполняющее скремблирование. Скремблирование это обратимое преобразование цифрового потока без изменения скорости передачи с целью получения… … Википедия
DVB-T2 — Список стандартов цифрового телевизионного вещания Стандарты DVB (Европа) DVB S (Цифровое спутниковое ТВ) DVB S2 DVB T (Цифровое эфирное ТВ) DVB T2 DVB C (Цифровое кабельное ТВ) DVB C2 DVB H (Мобильное ТВ) DVB SH (спутниковое/мобильное) … Википедия
Шифрование в аналоговой телефонии — Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения. Существуют два класса систем связи: цифровые и аналоговые … Википедия
ГОСТ Р ИСО/МЭК 19762-1-2011: Информационные технологии. Технологии автоматической идентификации и сбора данных (АИСД). Гармонизированный словарь. Часть 1. Общие термины в области АИСД — Терминология ГОСТ Р ИСО/МЭК 19762 1 2011: Информационные технологии. Технологии автоматической идентификации и сбора данных (АИСД). Гармонизированный словарь. Часть 1. Общие термины в области АИСД оригинал документа: Accredited Standards… … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р 53531-2009: Телевидение вещательное цифровое. Требования к защите информации от несанкционированного доступа в сетях кабельного и наземного телевизионного вещания. Основные параметры. Технические требования — Терминология ГОСТ Р 53531 2009: Телевидение вещательное цифровое. Требования к защите информации от несанкционированного доступа в сетях кабельного и наземного телевизионного вещания. Основные параметры. Технические требования оригинал документа … Словарь-справочник терминов нормативно-технической документации
RC4 — (англ. Rivest Cipher 4 или англ. Ron’s Code, также известен как ARCFOUR или ARC4 (англ. Alleged RC4)) потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах… … Википедия