Розглянуто задачу визначення виду скремблера, застосованого на передавальній стороні, на підставі сигналу з його виходу. Завдання такого роду є актуальною для систем радіомоніторингу і при створенні когнітивних систем прийому та обробки цифрового сигналу. Відомі технічні рішення, що дозволяють ідентифікувати структури як адитивного, так і мультиплікативного скремблера [1] - [4]. Однак публікацій, в яких наводився б алгоритм автоматичного визначення виду скремблера, немає. Пропонована стаття покликана частково заповнити цю прогалину. Наведено алгоритм, що забезпечує рішення зазначеного завдання, і результати його моделювання.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Кривоногов Олександр Сергійович, Кривоногова Катерина Олегівна


Linear Scrambler Identification

The article describes algorithm that allows determining scrambler type based on the signal from its output. The task of this kind is relevant for radio monitoring systems and when creating cognitive systems for digital signal receiving and processing. The identification algorithm determines the form of the scrambler both multiplicative and additive. There are no published papers providing algorithm for automatic determination of scrambler type. This article is intended to partly fill the gap. It provides a formal statement of the problem, an identification algorithm and simulation results.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва діє до: 2017
    Журнал
    Известия вищих навчальних закладів Росії. Радіоелектроніка
    Наукова стаття на тему 'АЛГОРИТМ ІДЕНТИФІКАЦІЇ ВИДУ Скремблювання БІНАРНИХ ДАНИХ'

    Текст наукової роботи на тему «Алгоритм ідентифікації ВИДУ Скремблювання БІНАРНИХ ДАНИХ»

    ?УДК 621.39

    А. С. Кривоногов

    Санкт-Петербурзький державний електротехнічний університет "ЛЕТІ" ім. В. І. Ульянова (Леніна)

    Е. О. Кривоногова

    АТ "Науково-інженерний центр електротехнічного університету"

    (Санкт-Петербург)

    Алгоритм ідентифікації виду скремблювання бінарних даних

    Розглянуто задачу визначення виду скремблера, застосованого на передавальній стороні, на підставі сигналу з його виходу. Завдання такого роду є актуальною для систем радіомоніторингу і при створенні когнітивних систем прийому та обробки цифрового сигналу. Відомі технічні рішення, що дозволяють ідентифікувати структури як адитивного, так і мультиплікативного скремблера [1] - [4]. Однак публікацій, в яких наводився б алгоритм автоматичного визначення виду скремблера, немає. Пропонована стаття покликана частково заповнити цю прогалину. Наведено алгоритм, що забезпечує рішення зазначеного завдання, і результати його моделювання.

    Скремблер, ідентифікація, радіомоніторинг, псевдослучайная послідовність

    У сучасних системах радіомоніторингу існує необхідність демодуляції і декодування радіосигналів сторонніх систем радіозв'язку без апріорної інформації про їх передавачі [1]. Для вирішення цього завдання використовуються "сліпі" алгоритми ідентифікації параметрів блоків обробки і формування сигналу, що використовуються на передавальній стороні. В результаті вирішення зазначеного завдання визначається структура передавача, що дозволяє побудувати відповідну їй приймальню частина і здійснити прийом сигналу.

    В даний час широко поширені цифрові системи радіозв'язку. Це призводить до необхідності розробки алгоритмів визначення (ідентифікації) блоків обробки і формування радіосигналів, властивих цим системам [1]. Одним з таких блоків є скремблер. Існує два види скремблеров, що розрізняються способом взаємодії з цифровим сигналом: адитивні і мультиплікативні [5]. У цій статті наведено алгоритм, що дозволяє за результатами аналізу сигналу з виходу передавача ідентифікувати вид використовуваного скремблера. При цьому передбачається, що вся супутня обробка (демодуляція, декодування і т. Д.) Сигналу, що передує дескремблирование, успішно здійснена.

    10

    На сьогоднішній день існує безліч публікацій, присвячених питанню ідентифікації структури скремблера (див., Зокрема [1], [2]). При цьому роботи, в яких вирішувалася б завдання визначення виду скремблювання, авторам цієї статті невідомі. Пропонована стаття покликана частково заповнити цю прогалину.

    Короткі теоретичні відомості. Скрембі-лирование використовується на передавальній стороні систем цифрової передачі інформації для зменшення ймовірності появи довгих послідовностей нулів і одиниць. Такі послідовності в переданому сигналі можуть порушити роботу систем синхронізації на приймальній стороні.

    Існує два види скремблеров - адитивні і мультиплікативні [1]. Їх узагальнені структури приведені на рис. 1, а і б відповідно. До складу обох видів скремблеров входить регістр зсуву з лінійним зворотним зв'язком (РСЛОС), описуваний породжує поліномом [6]

    а

    О (х) =? gix1,? = 0

    де а - пам'ять РСЛОС і gi е ОГ (2). Якщо коефіцієнт gi ф 0, відповідний ключ в схемі РСЛОС замкнутий. На практиці найбільшого поширення набули породжують поліноми з трьома або п'ятьма ненульовими коефіцієнтами.

    © Кривоногов А. С., Кривоногова Е. О. 2017

    Мал. 1

    У аддитивном скремблер РСЛОС використовується в якості генератора псевдослучайной послідовності (ПСП). Скремблирование в цьому випадку здійснюється додатком (в поле ОЕ (2)) ПСП до скрембліруемому сигналу. У мультипликативном випадку скрембліруемий сигнал надходить на вхід РСЛОС.

    Операцію скремблювання можна описати в поліноміальному вигляді. Якщо інформаційний сигнал, що складається з N біт, представлений у вигляді полінома [6]

    N-1

    Б (х) =? Цх ',' = 0

    де Б '- відповідає (N -1 -') -му біту послідовності, то поліном 5 "ті1 (х), що описує вихідний сигнал мультиплікативного скремблера, буде дорівнює [6]

    Smul (х) = D (х V G (x).

    (1)

    Якщо сигнал скремблируется адитивно, то поліном Sad (х), що описує вихідний сигнал адитивної скремблера, буде дорівнює [6]

    Sad (х) = I (х) xN / o (х) + D (х), (2)

    де I (х) - поліном, що характеризує внутрішній стан РСЛОС, причому його ступінь менше ступеня полінома G (х).

    Також для формування алгоритму необхідно описати в поліноміальному вигляді операцію мультиплікативного дескремблирования. Поліном D (х) на виході мультиплікативного де-скремблера розраховується як

    D (х) = Smul (х) G (х). (3)

    Вихідні дані і постановка задачі. Завдання ідентифікації виду скремблювання формулюється для моделі, представленої на рис. 2.

    Генератор бінарних даних імітує дані, що передаються в системах радіозв'язку. Він генерує потік бітів із заданою вірогідністю одиниці Р (Б '= 1) = 0.5 -т, ті (0, 0.5).

    Скремблер скремблируется надходять від генератора дані по адитивної або мультиплікативної схемою. При Скремблювання використовується апріорно відомий породжує поліном О (х) ступеня й з t ненульовими коефіцієнтами.

    Мал. 2

    Завдання ідентифікації полягає у визначенні виду використовуваного скремблера (мультиплікативний або адитивний) на підставі бінарного сигналу довжини N біт, що формується на його виході. Вихідними даними для вирішення завдання є ськремблірованний сигнал і породжує поліном О (х), інформація про який може бути отримана з використанням алгоритмів, описаних в [1], [2]. Також передбачається, що N »й.

    Опис алгоритму. Алгоритм ідентифікації полягає в мультипликативном дескремблірова-ванні аналізованого сигналу за допомогою дескрем-Блера, описуваних полиномами О (х) і 2т (\

    О (х), де т - параметр алгоритму. Згідно зі слів (3) це еквівалентно множенню полінома 5 (х), що описує сигнал з невідомим видом

    скремблювання, на поліноми О (х) і О (х) відповідно. Якщо сигнал був Ськремблірованний адитивно, то з урахуванням (2) в результаті перемноження вийдуть поліноми

    A (х) = S (х) G (х) =

    '/ (Х) х ^

    . G (х)

    + D (х)

    G (х) =

    = I (х) xN + D (х) G (х),

    (4)

    б

    а

    В (х) = Б (х) О2 (х) =

    = -1 (х) х ^ О2-1 (х) + Б (х) О2т (х). (5)

    Якщо сигнал був Ськремблірованний мультиплікативно, то з урахуванням (1) підсумком перемноження будуть поліноми

    V (х) = Б (х) О (х) = Б (х), (6)

    Г (х) = Б (х) О2т (х) = Б (х) О2т -1 (х). (7)

    Для того щоб прийняти рішення про вид скремблювання, необхідно проаналізувати статистичні властивості отриманих при де-Скремблювання послідовностей. Вираз (4) являє собою суму двох поліномів. Кількість ненульових коефіцієнтів в першому поліномі не перевищує ступеня полінома I (х) і в загальному випадку набагато меншою, ніж у другому доданку поліномі. Тому вплив першого полінома на статистичні властивості де-ськремблірованний послідовності можна вважати дуже незначним.

    Другий доданок в (4) описує потік інформаційних даних після мультиплікативного дескремблера. Імовірність появи ненульового біта на його виході відповідно до [1] в цьому випадку становить

    Р (А, = 1) =

    1 - [1 - 2 Р (Б, = 1)] '

    (8)

    де А, -? -й коефіцієнт полінома А (х).

    Висловивши праву частину (8) через т, отримаємо відхилення ймовірності Р (А, = 1) від 0.5:

    т1 = | 0.5 Р (А, = 1) | = (2т) Г / 2.

    (9)

    Розглянемо вираз (5). Перший доданок поліном не впливає на статистичні властивості дескремблірованной послідовності, і їм можна знехтувати, якщо кількість ненульових коефіцієнтів в ньому досить мало в порівнянні з другим доданком. Ця умова забезпечується вибором значення параметра т і протяжності аналізованого відрізка сигналу.

    Другий доданок в (5) описує потік інформаційних даних, підданий мультиплікативного дескремблирование, причому кількість відводів в дескремблере визначається числом

    2т I \

    ненульових коефіцієнтів в О (х). З урахуванням 12

    властивостей поліномів над полем ОГ (2) [6] кількіст -

    ство ненульових коефіцієнтів в О (х) буде дорівнює кількості ненульових коефіцієнтів в О (х). З урахуванням цієї властивості відхилення ймовірності Р (В, = 1) від 0.5 для даного випадку, де

    В, -? -Й коефіцієнт полінома В (х), складе

    Т2 = Т1. (10)

    Звернемося до виразів (6) і (7). При мультипликативном дескремблирование мультиплікативно Ськремблірованний сигналу згідно (6) на виході дескремблера сформується інформаційний сигнал. При цьому відхилення ймовірності Р (V, = 1) від 0.5, де V, -? -Й коефіцієнт полінома V (х), складе

    тз = т. (11)

    При дескремблирование з використанням

    полінома О (х) на виході дескремблера буде послідовність, описувана (7), для якої відхилення ймовірності Р (= 1) від 0.5, де

    Г -, -й коефіцієнт полінома Г (х), визначиться як

    Т4 = | 0.5 - Р (Г = 1) = (2т) г / 2, (12)

    де г - кількість ненульових коефіцієнтів в

    поліномі О2 1 (х).

    Для прийняття рішення про вид скремблювання необхідно порівняти (9), (10) і (11), (12). Якщо сигнал був Ськремблірованний адитивно, то в результаті дескремблирования з використанням

    полиномов О (х) і О2 (х) відхилення ймовірності будуть однаковими.

    Якщо ж сигнал був Ськремблірованний мультиплікативно, то в результаті дескремблирования з

    використанням поліномів О (х) і О2 (х) відхилення ймовірності будуть рівні Т3 і Т4 відповідно, причому Т3 >Т4.

    Таким чином, алгоритм ідентифікації включає наступні операції:

    - мультиплікативне дескремблирование сигналу з використанням поліномів О (х) і О2 (х);

    - оцінки відхилень ймовірності появи ненульового елемента та й ть на виході відповідних дескремблеров;

    V

    101

    108

    106

    104

    102 10е

    m = 3

    \

    ч

    I- 1 •••• З..

    0

    0.1

    0.2

    Мал. 3

    0.3

    0.4

    - розрізнення двох гіпотез про вид скремблера за результатами порівняння отриманих оцінок.

    Аналіз результатів моделювання. Безпосереднє порівняння оцінок відхилень ймовірності ненульового елемента в дескремблірован-ном сигналі та й ть є некоректним. Це пов'язано з тим, що отриманий набір оцінок має деякий розкид значень, що залежить від обсягу аналізованих даних. Оптимальне правило розрізнення двох гіпотез можна сформулювати тільки при наявності інформації про значення т. В загальному випадку такої інформації немає, що призводить до необхідності використання емпірично обраного порога розрізнення.

    Визначимо, наскільки різняться оцінки та і т ь при найгірших для ідентифікації умовах. Одним з таких умов є екстремальні значення величини т. В реальних системах зв'язку значення даного параметра часто не менше 0.01 і не перевищує 0.4 [1]. На рис. 3 наведено сімейство графіків залежності відносини т ^ Т4 від величини т для різних значень параметра т.

    З рис. 3 видно, що при т = 0.01 і т = 1 мінімальне відношення оцінок дорівнює 50. При

    РЛ

    0.020 0.010 0.005

    0.002

    N = 10

    ,5

    10 '

    _L

    0.01 0.03

    0.05 Рис. 4

    0.0 '

    0.09

    великих значеннях параметра т ця різниця зростає на кілька порядків. При т = 0.04 оцінки будуть відрізнятися приблизно в 1.25 рази при т = 1 і в 4.7 рази при т = 3. На підставі цього аналізу для роботи алгоритму вибрано значення т = 3, а в якості порогу прийняття рішення на користь мультиплікативного виду скрем-блірованія - співвідношення та / ть ^ 2.

    На рис. 4 наведені результати моделювання роботи алгоритму (проводилося 100 000 експериментів) у вигляді залежності ймовірності помилки алгоритму Рош (т) для різних значень

    довжини аналізованого сигналу.

    при т>0.1 жодної помилки за весь час моделювання не відбулося. Наявність помилок при малих значеннях т обумовлено великою дисперсією оцінок та й т ^. При цьому зі збільшенням обсягу аналізованого сигналу ця дисперсія падає, що призводить до зменшення ймовірності помилки алгоритму.

    На підставі наведених у цій статті даних можна стверджувати, що розроблений алгоритм може бути використаний для визначення виду скремблера в автоматизованих системах радіомоніторингу.

    СПИСОК ЛІТЕРАТУРИ

    1. Cluzeau M. Reconstruction of a Linear Scrambler // IEEE Trans. on Computers. 2007. Vol. 56, № 8. P. 1283-1291.

    2. Canteaut A., Filiol E. Ciphertext only Reconstruction of Stream Ciphers Based on Combination Generators. Berlin: Springer, 2001. 16 p.

    3. Johansson T., Jonsson F. Fast Correlation Attacks through Reconstruction of Linear Polynomials // Advances in Cryptology - CRYPTO 2000. 20th Ann. Int. Cryp-tology Conf. Santa Barbara, Aug. 20-24, 2000. Berlin: Springer, 2000. P. 300-315. (Lecture Notes in Computer Science 1807).

    Стаття надійшла до редакції 26 жовтня 2017 р.

    4. Canteaut A., Trabbia M. Improved Fast Correlation Attacks using Parity-Check Equations of Weight 4 And 5. // Advances in Cryptology - EUROCRYPT 2000, Int. conf. on the Theory and Applications of Cryptographic Techniques. Bruges, Belgium, May 14-16 2000 / Ed. by B. Preneel. Berlin: Springer, 2000. P. 579-594. (Lecture Notes in Computer Science 1880).

    5. Скляр Б. Цифрова Зв'язок. Теоретичні основи і практичне застосування: пров. з англ. 2-е изд. М .: Видавничий дім "Вільямс", 2003. 1104 з.

    6. Лідл Р., Нідеррайтер Г. Кінцеві поля: в 2 т. Т. 2 / пер. з англ. М .: Світ, 1988. 822 с.

    т

    т

    Для цитування: Кривоногов А. С., Кривоногова Е. О. Алгоритм ідентифікації виду скремблювання бінарних даних // Изв. вузів Росії. Радіоелектроніка. 2017. № 6. С. 10-14.

    Кривоногов Олександр Сергійович - магістр техніки і технологій за напрямом "Радіотехніка" (2010), асистент кафедри теоретичних основ радіотехніки Санкт-Петербурзького державного електротехнічного університету "ЛЕТІ" ім. В. І. Ульянова (Леніна), інженер Науково-дослідного інституту радіотехніки та телекомунікацій зазначеного університету. Автор трьох наукових публікацій. Сфера наукових інтересів - цифровий зв'язок. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Кривоногова Катерина Олегівна - магістр за напрямом "Радіотехніка" (2016), науковий співробітник АТ "Науково-інженерний центр електротехнічного університету" (Санкт-Петербург). Сфера наукових інтересів - цифровий зв'язок. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    A. S. Krivonogov Saint Petersburg Electrotechnical University "LETI" E. O. Krivonogova

    JSC "Research and Engineering Center of Electrotechnical University" (Saint Petersburg) Linear Scrambler Identification

    Abstract. The article describes algorithm that allows determining scrambler type based on the signal from its output. The task of this kind is relevant for radio monitoring systems and when creating cognitive systems for digital signal receiving and processing. The identification algorithm determines the form of the scrambler both multiplicative and additive. There are no published papers providing algorithm for automatic determination of scrambler type. This article is intended to partly fill the gap. It provides a formal statement of the problem, an identification algorithm and simulation results.

    Key words: Scrambler, Identification, Radiomonitoring, Pseudorandom Sequence

    REFERENCES

    1. Cluzeau M. Reconstruction of a Linear Scrambler. IEEE Trans. on Computers. 2007, vol. 56, no. 8, pp. 1283-1291.

    2. Canteaut A., Filiol E. Ciphertext only Reconstruction of Stream Ciphers Based on Combination Generators. Berlin, Springer, 2001., 16 p.

    3. Johansson T., Jonsson F. Fast Correlation Attacks through Reconstruction of Linear Polynomials. Advances in Cryptology - CRYPTO 2000. 20th Ann. Int. Cryptology Conf. Santa Barbara, August 20-24, 2000. Berlin, Springer, 2000., pp. 300-315. (Lecture Notes in Computer Science 1807).

    4. Canteaut A., Trabbia M. Improved Fast Correlation Attacks using Parity-Check Equations of Weight 4 And 5.

    Received October, 26 2017

    Advances in Cryptology - EUROCRYPT 2000, Int. conf. on the Theory and Applications of Cryptographic Techniques. Bruges, Belgium, May 14-16 2000. Ed. by B. Preneel. Berlin, Springer, 2000., pp. 579-594. (Lecture Notes in Computer Science 1880).

    5. Sklar B. Digital Communications. Fundamentals and Applicstions. 2nd ed. 2001, Upper Saddle River, Pren-tice Hall PTR, 2001., тисячі сімдесят-дев'ять p.

    6. Lidl R., Niederreiter H. Finite Fields. Cambridge University Press, 1985, 822 p.

    For citation: Krivonogov A. S., Krivonogova E. O. Linear Scrambler Identification. Izvestiya Vysshikh Uchebnykh Zavedenii Rossii. Radioelektronika [Journal of the Russian Universities. Radioelectronics]. 2017, no. 6, pp. 10-14. (In Russian)

    Aleksandr S. Krivonogov - Master's Degree in Radio Engineering (2010), Assistant Professor of the Department of Theoretical Bases of Radio Engineering of Saint Petersburg Electrotecnical University "LETI". The author of 3 scientific publications. Area of ​​expertise: digital communication. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Ekaterina O. Krivonogova - Master's Degree in Radio Engineering (2016 JSC Research and Engineering Center of Saint Petersburg Electrotechnical University "LETI". Area of ​​expertise: digital communication. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.


    Ключові слова: скремблерами / SCRAMBLER / ІДЕНТИФІКАЦІЯ / IDENTIFICATION / радіомоніторингу / RADIOMONITORING / псевдовипадкових послідовностей / PSEUDORANDOM SEQUENCE

    Завантажити оригінал статті:

    Завантажити