Доброго времени суток!
Есть цифровой битовый поток! Известно, что данный поток скремблирован, но параметры скремблера неизвестны. Скремблер мультипликативный.
Как определить параметры скремблера? Для мультипликативного скремблера образующий полином?
Интересует алгоритм определения, а не готовые программы)

Вопрос интересный :-) Однако, иногда, в стартовой части сеанса, этот скремблер передается в открытом виде ( для синхронизации с приемной стороной). В других случаях, если для синхронизации не используется тот же скремблер, найти его в процессе передачи затруднительно...

Любой такой алгоритм будет явно или неявно учитывать статистические или структурные характеристики сообщения.

Если дескремблированное сообщение не имеет выраженных особенностей (преобладание нулей или единиц, периодичность, известный фрагмент...) то скорее всего ничего не получится.

Обычно также имеют в виду, что нормальные люди в качестве скремблера берут многочлены неприводимые и малого веса (очень часто три, реже пять).

Алгоритмы - в зависимости от объема указанной априорной информации.

а вот интересно, меня всегда мучил вопрос,что делается вначале, а что потом?

Сначала у цифрового пакета подситывается и добавляется контрольная сумма и затем всё это скремблируется, или же вначале всё это скремблируется, а потом считают и добавляют CRC?

если второй вариант, то можно подбирать параметры скремблирования методом перебора до тех пор, пока СRC не сойдётся. А если первый случай применяется, то правильность подбора и проверить нечем..

Сначала у цифрового пакета подситывается и добавляется контрольная сумма и затем всё это скремблируется, или же вначале всё это скремблируется, а потом считают и добавляют CRC?

По разному бывает - в зависимости от степени испорченности разработчика. Обычно, конечно же, скремблер в конце. Однако, насколько я понял, не факт, что CRC в принципе существует.

Читал, что для определения полинома используют метод перебора. Сначала дескремблируют входной массив проверяемым полиномом и вычисляют его(полученного массива) весовую характеристику, сравнивают ее с весовой х-кой исходного массива. Если х-ки совпадают или близки по значению(точно не помню), то принимается решение о том, что проверяемый вариант и есть искомым полиномом. Но как эти х-ки вычисляются на практике я не знаю :).

Может знающие люди на форуме подскажут...

Кстати, задача и правда упрощается, если использовать правила написанные asv - многочлены неприводимые и малого веса. К тому же, очень часто в промышленных решениях применяют стандартные полиномы: 9,11; 14,15; 3,20; 2,3,9,12 есть еще, но я не помню так сразу.
А если нет априорной информации о потоке после скремблера, то тут окольными путями не пройдешь, нужно знать конкретный метод.

И еще, в проге Дельта есть поиск скремблера. Интересно как там это организовано. Было бы интересно расколбасить такую штуку. Дайте алгоритм - я могу написать )

asv
Любой такой алгоритм будет явно или неявно учитывать статистические или структурные характеристики сообщения.

Если дескремблированное сообщение не имеет выраженных особенностей (преобладание нулей или единиц, периодичность, известный фрагмент...)

да, после дескремблирования поток имеет явно выраженный период!!! думаю, это упрощает задачу...известный фрагмент тоже есть.

Vengr
скорее всего характеристики исходного массива и дескремблированого с проверяемым полиномом должны отличаться. Тогда можно сделать вывод, что формирующий полином подобран верно

и после правильного дескремблирования СRC будет совпадать.Если она там вычисляется и добавляется и её алгоритм известен, конечно.
Но я думаю, что в настоящее время цифровых пакетов без контр суммы не бывает, иначе как проверить подлинность принятых данных?

Еще нашел информацию, что определить наличие скремблирования можно, если проверять схожесть дескремблированого потока шумоподобным потоком.

Предлагается два метода:
- представить поток в виде последовательности блоков различной длины (метод L-блоков)

- в виде односвязной цепи Маркова с двумя состояниями "0" и "1" (метод S-цепочек)

Для каждого метода существуют теоретические значения границ критериев, вычисляемых по символах входного массива. По критериям делается вывод о близости массива к шумоподобному.

А что это за критерии и как их вычислять???

Да, вижу темка не пошла. Разве на форуме мало людей этим интересующихся, или это "денежная" тема :) ?

Vengr Дык а куда ей идти? ;) Потока нет, что можно уже сказали. Вываливать алгоритмы если они у кого есть, ну дык извнините, те у кого они есть сами проги и пишут таж Дельта. А дайте мне точку опоры и я переверну мир, ну эт понятное желание, типо на рычажок нажать городо. :-) или это "денежная" тема кхм... да ну что вы, какая она денежная :)

Mesh, вы все правильно говорите. Но я как раз про то, что если есть у кого алгоритм, и он им может поделиться, то пусть не стесняется. Ведь RSCAN, наверное, про это и спрашивал в начале темы.
Я год назад писал универсальный аддитивный и мультипликативный скр., потому мне тоже очень интересна эта тема.

RSCAN, читал про DES и нашел, что метод S-блоков (S-box англ.) есть основой для этого алгоритма шифрования. Так что теорию по нему, думаю, следует искать именно там. Удачи! Если что нарою получше, то напишу.

метод S-блоков (S-box англ.) есть основой для этого алгоритма шифрования
Это из совсем другой оперы.

Еще нашел информацию, что определить наличие скремблирования можно, если проверять схожесть дескремблированого потока шумоподобным потоком.
Если у вас есть открытый фрагмент надо просто сопоставить скремблированный кусок и открытый, нарисовать систему линейных уравнений и решить ее. А не заниматься всякой теоретической ерундой.

asv
вот как раз так в Delta и сделано!!! не считаю эту программу ерундовой!!!

если метод S-блоков есть основой для алгоритмов шифрования то это не мешает ему быть основой для поиска наличия скремблирования. Тут больше в сторону односвязной цепи Маркова и сравнения потока с шумоподобным. Повторюсь, но дальше используют теоретические значения границ некоторых критериев. Другой вопрос уже - каких критерии ... Тут уже нужно пробовать все самому.

если метод S-блоков есть основой для алгоритмов шифрования то это не мешает ему быть основой для поиска наличия скремблирования.
Это совсем из другой оперы, хотите верьте, хотите нет. Кроме буквы S нет ничего общего.

Тут больше в сторону односвязной цепи Маркова и сравнения потока с шумоподобным
Зачем, если есть открытый кусок? Зачем использовать универсальную модель марковского источника, весьма слабую, есть есть возможность использовать гораздо более сильную модель, специфическую для Вашего случая?

Впрочем, дело хозяйское. В таком случае для начала Вам было бы неплохо разобраться, что такое марковский источник, тогда и вопросы о границах критериев отпадут. Но я бы на Вашем месте эффективность данного подхода не переоценивал, ибо чем больше априорной информации о потоке используется, тем проще найти скремблер.

asv
Зачем, если есть открытый кусок?

Хотелось бы разобраться вообще. Да, еще много непонятного. Буду разбираться. Спасибо за советы!

Можно несколько упростить задачу. Полиномы обратной связи мультипликативных скремблеров выбираются так, чтобы минимизировать влияние ошибочно принятых/декодированных битов на дескремблируемый поток ---- то есть, с минимальным количеством членов.

Вот несколько стандартных полиномов:

20, 3 - V35, Intelsat
18, 1 - Comtech proprietary
11, 9 - OM-73
23, 18
23, 5 - CDMA
43 - ATM

Сделайте перебор по всем стандартным скремблерам плюс перебор комбинаций из двух членов, скажем, до 20 степени.

Как понять, правильно ли выбран полином? Посчитайте например, энтропию, для фрагментов исходного потока данных. Посчитайте то же самое после пробного дескремблирования. Остановитесь, если после дескремблирования энтропия уменьшилась (появились участки открытого текста, заполненные нулями/ флагами HDLC и т.п.)

PS Дайте, кстати, поток --- я вам найду скремблер : )

Дайте, кстати, поток --- я вам найду скремблер : )

Спасибо, я и сам могу найти : ). Меня интересует именно алгоритм поиска:

Интересует алгоритм определения, а не готовые программы)

zhabazhab, я это к тому, что RSCAN же в начале все написал, что ему нужно.

Есть битовый поток, скорее исп сверт кодир или сверт турбо. Надо определить схему кодиров и полиномы. Раньше для обычного НСК 1/2 без обратн связи с полиномами 101 и 111 все определял методом гаусса матрицами, тут не проходит. Какие есть еще способы и как быть если схема будет с обр связью или кодир будет как в 3gpp (pccc)

Есть битовый поток, скорее исп сверт кодир или сверт турбо. Надо определить схему кодиров и полиномы. Раньше для обычного НСК 1/2 без обратн связи с полиномами 101 и 111 все определял методом гаусса матрицами, тут не проходит. Какие есть еще способы и как быть если схема будет с обр связью или кодир будет как в 3gpp (pccc)

Любой турбокод имеет блочную структуру ---- в потоке должно быть синхрослово. Если последовательность битов не имеет периода, значит у вас просто свёрточный код.

Для свёрточников будут варианты:

Кроме простого НСК 1/2 может быть НСК 1/3, 1/4, а также НСК c перфорацией.

Выход кодера может быть пропущен через битовый перемежитель ---- блочный или свёрточный. Пары битов с выхода кодера НСК 1/2 могут быть сдвинуты друг относительно друга на N битов перед подачей на symbol mapper. На каждый байт битового потока из кодера может накладываться маска для синхронизации выхода декодера на границу байта. И т.д. И т.п.

"По фотографии" диагноз поставить трудно. Чтобы ответить на ваш вопрос, надо иметь битовый поток перед глазами.

В коде есть синхра, есть период Х (Х=4блока*N) N-фиксир длина, в N входят кодовые слова длиной 6 бит(скор 2/3), формата pipiiii, где p-провер бит, i-инф биты, как формир провер неизвестно, еще вроде есть хвост, длина 16, если есть идеи подскажите, спасибо...

может кто работал подскажите

Работал. Но не подскажу, потому как детский сад первая четверть. Хотя есть парочка толковых замечаний на абсолютно бестолково поставленную задачу. Что за скремблер, откуда взялся, зачем что-то искать и возможно ли здесь что-то найти в принципе? Вот первые исходные данные для решения задачи. Иначе: пойди туда не знаю куда, принеси то не знаю что. В последнем случае такие задачи решаются очень мощными средствами, которых уже давно ни у кого в распоряжении нет и быть не может. Так если ничего уже нет и быть не может в масштабах целых государств, то давайте решать эту задачу в масштабах одной ветки одного форума. Я конечно сильно преувеличиваю, у ТС нет и не может быть таких задач, но постановка вопроса выглядит именно так. Потому вопрос надо ставить по-конкретнее: я имею то-то и то-то, сделано по схеме из соседней ветки :) помогите найти полином :) или иначе: поймал из эфира поток, скорость 81бод, предположительно работает Т-206, помогите решить задачу. И доблестный serk сразу даёт ссылку на коллег из АНБ где эту задачу решают уже третье десятилетие и почему-то решить не могут :)

Я скажу больше, разглашая огромную государственную тайну :) такие вопросы решаются очень мощными силами, и мощь в данном случае представляет из себя не вычислительная техника, а мощь интеллектуальная, собираются лучшие математические мозги (не путать с математиками вообще) и годами долбят и долбят тему, иногда у них что-то получается, но чаще они терпят неудачу за неудачей. И вот ради того немногого что иногда получается, тратились колоссальные средства. Это не фобос-грунт угробить, это по-круче. Так что я для начала предлагаю ТС (пусть не обижается не меня) запустить фобос-грунт, привезти его на землю-матушку для исследования, а уж затем браться за решение более сложных задач, поставленных в общем виде.

И ещё в-догонку: когда-то в 90-х валялись у меня парочка профессиональных американских скремблера, которые наши вояки отобрали как трофеи где-то в горячих точках. Маленькие и удобненькие, цеплялись внутрь к очень маленьким и удобненьким радиостанциям предположительно американского спецназа, полностью рабочие вместе с этими самыми радиостанциями (были в 9х году), с тех пор не проверял. Есть желающие взять и разобрать где у них тот самый полином скремблера? Мне лично даже срисовать принципиальную схему скремблера абсолютно нереально. Нереально это и для целого НИИ, так интересно собрана эта самая принципиальная схема там. И это было у них 20 лет назад. Об том чтобы там чего-то разбирать в цифровых пакетах и пытаться найти формат кадра и где у него начало и где конец и где контрольная сумма вообще нет речи. Х.з. как оно работает.

много текста, бывает... только толку мало и вообще если комбинировать буквы русского алфавита много страшных аббревиатур получиться

serk
Речь идет о другом скремблере.

Не том, который шифратор, а о том, который приводит битовый поток к псевдослучайному виду, удобному для передачи в канал с точки зрения устойчивости работы схем тактовой синхронизации и помехоустойчивости в целом.

Как правило, это регистр с линейными обратными связями.