zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



АНАЛІЗ ПОСЛІДОВНОСТЕЙ НА ВИХОДІ ЗСУВНОГО РЕГІСТРУ З ЛІНІЙНИМ ЗВОРОТНИМ ЗВ’ЯЗКОМ

 

Шрамченко Б.Л.

Україна, Київ,

Київський національний університет технологій та дизайну

 

Показано, каким образом из существования эквивалентных регистра Фибоначчи и регистра Галуа следует, что максимальный период последовательности на выходе регистра Фибоначчи равен 2r – 1, где r количество разрядов регистра. Установлено, что инверсный порядок отводов регистра Фибоначчи влечет инверсию последовательности на выходе.

 

Аналіз відповідності між двома конфігураціями регістру зсуву з лінійним зворотним зв’язком (РЗЛЗЗ)

Традиційним засобом, що використовується при побудові генераторів потокових ключів є РЗЛЗЗ [1]. У загальному випадку регістр з лінійним зворотним зв’язком можна представити як показано на рис. 1.

 

Рис. 1. РЗЛЗЗ (конфігурація Фібоначчі).

 

Мітка ci вказує на те, чи існує зв’язок, біля якого вона розташована на схемі. Якщо ci = 1, зв’язок існує, а якщо ci = 0, - ні. В літературі [2] ця схема отримала назву «конфігурація Фібоначчі».

Існує інша схема РЗЛЗЗ, що дозволяє отримати на виході ту ж саму послідовність. Ця схема (рис. 2) називається «конфігурацією Галуа».

 

Рис. 2. РЗЛЗЗ (конфігурація Галуа).

 

У регістрі Галуа кожне значення на виході (у кожному такті) додається до значення у відповідних розрядах. Тому тільки останній, правий біт дорівнює значенню на виході регістру. Усі інші розряди містять деякі проміжні значення.

Схема на рис. 1 показує, що член послідовності на виході, починаючи з r-го, є сумою за модулем 2 тих попередніх, яким відповідають одиничні коефіцієнти ci. Наприклад, у суму входить безпосередньо попередній член, якщо c1 = 1. Якщо c2 = 1, то у суму входить член послідовності, що передує поточному на дві позиції, і т.д. При цьому член, що передує на r позицій завжди є доданком, або cr º 1.

Якщо скористатися позначенням ait для стану комірки si у такті t, то для конфігурації Фібоначчі можна записати

та

" i | 1 < i £ r, ar-it+1 = ar-i+1t.

 

       Тому кожний член послідовності на виході регістру можна представити у вигляді

        

        

        І оскільки ait-r = a0t-r+i,

 

У конфігурації Галуа, що відповідає поданій конфігурації Фібоначчі, кожний член послідовності дорівнює сумі тих же попередніх. Однак формується кожний член не в одному такті, а - в r. При цьому кожний член послідовності на виході регістру додається до поточного стану тих комірок, що містять проміжний стан наступних елементів послідовності, і які відповідають одиничним коефіцієнтам ci.

Для конфігурації Галуа мають місце наступні співвідношення.

a r-1t- r+1 = a0 t- r,

a r-2t- r +2 = c r-1a0 t- r +1Å a r-1t- r +1,

a r-3t- r +3 = c r-2a0 t- r +2Å a r-2t- r +2,

a0t = c1a0 t-1Å a1t-1 .

 

Виконавши послідовно підстановки для ait-i, i = 1, r – 1, отримуємо

 

де cr = 1. Таким чином, побудована вказаним способом конфігурація Галуа дає на виході послідовність, що визначається тим же рекурентним співвідношенням, що і послідовність на виході поданої конфігурації Фібоначчі. Як бачимо, порядок, у якому застосовуються числа ci у конфігурації Фібоначчі, протилежний тому, що у конфігурації Галуа.

Для того, щоб регістр Галуа видавав на виході ту ж саму послідовність, що і регістр Фібоначчі, крім відповідності між відводами, треба, щоб мала місце і відповідність між початковими станами регістрів. Визначимо початковий стан (br-1, br-2, … , b0) регістру Галуа при поданому початковому стані (ar-1, ar-2, … , a0) регістру Фібоначчі.

Очевидно, що b0 = a0, як перший член послідовності на виході, що збігається з початковим станом комірки s0 в обох регістрах.

Далі, з рівняння b1 Å c1a0 = a1 отримуємо

b1 = c1 a0 Å a1.

Використовуючи співвідношення

b2 Å c2a0 Å c1 a1 = a2, маємо

b2 = c2a0 Å c1a1 Å a2.

Продовжуючи аналогічно, для будь-якого i < r можемо записати

bi = cia0 Å ci-1a1 ÅÅ c1a i-1 Å a i.

 

Застосування поліномів для аналізу поведінки РЗЛЗЗ

Кожному стану регістру, незалежно від конфігурації, можна поставити у відповідність поліном

ar-1 x0 Å ar-2 x1 ÅÅ a0 xr-1.

Коефіцієнти цього поліному належать полю GF(2). Сума двох поліномів з коефіцієнтами (ar-1, ar-2, … , a0) та (br-1, br-2, … , b0), відповідно, визначається як поліном з коефіцієнтами ((ar-1 Å br-1, ar-2 Å br-2 , … , a0 Å b0). При множенні двох таких поліномів коефіцієнт при кожному xi (i= 0, 2r – 2) добутку визначається як

ar-1br-i+1 Å ar-2br-i+2 ÅÅ a r-i+1 br-1.

Поліном, який відповідає наступному стану регістру, утворюється множенням поліному, що відповідає поточному стану, на x (так відображається зсув) та виконанням деякої додаткової операції. У конфігурації Галуа, ця додаткова операція полягає у тому, що коли у поточному стані a0 = 1, до результату добутку додається поліном

xr Å c1 xr-1 Å c2 xr-2 Å Å cr-1 x Å 1.

А це означає, що множення поточного поліному на x здійснюється за модулем c(x) = xr Å c1 xr-1 Å c2 xr-2 Å Å cr-1 x Å 1, оскільки визначена вище операція додавання поліномів збігається з операцією віднімання. Таким чином множина станів регістру Галуа утворює кільце з визначеною раніше операцією додавання поліномів та множенням за модулем c(x).

Розглянемо приклад двох регістрів (регістр Фібоначчі на рис. 3 та регістр Галуа на рис. 4, що породжують однакові послідовності). В обох регістрах c1 = c3 = 1, а c2 = 0. Тому c(x) = x4 Å x3 Å x Å 1. Приклад роботи цих регістрів, які формують однакові послідовності на виході, представлений у табл. 1 для регістру Фібоначчі та у табл. 2 - для регистру Галуа.

 

Рис. 3. Приклад чотирьохрозрядного регістру Фібоначчі.

 

Рис. 4. Чотирьохрозрядний регістр Галуа, що відповідає регістру на рис. 3.

 

Таблиця 1

 

Таблиця 2

a3

a2

a1

a0

a(x)

1

0

0

1

x3Å 1

0

1

0

0

x

0

0

1

0

x2

1

0

0

1

x3Å 1

 

 

 

b3

b2

b1

b0

b(x)

0

0

1

1

x3Å x2

1

1

0

0

x4Å x3(mod g(x)) = xÅ 1

0

1

1

0

x2Å x

0

0

1

1

x3Å x2

 

 

У розглянутому прикладі T = 3.

У випадку, коли c(x) – простий, для регістру Галуа поліноми a(x) степеню не більше r-1 утворюють поле GF(2r) [3] з операцією додавання a(x) + a*(x) = a r-1 Å a* r-1 Å (a*r-2 Å a*r-2)x ÅÅ (a*1 Å a*1)x r-2Å (a*0 Å a*0) x r-1. При цьому у поліному степеню k < r – 1 усі коефіцієнти при степенях x більше k дорівнюють нулю. Операція множення виконується за модулем c(x).

У цьому полі поліном x породжує деяку підгрупу x, x2, … , xm mod c(x) = 1. Це означає, що при будь-якому початковому стані регістру з відповідним поліномом a(x) наступним станам відповідають поліноми xa(x) mod c(x), x2a(x) mod c(x), … , xm a(x) mod c(x) = a(x). Звідси випливає, що період послідовності на виході регістру Галуа дорівнює m. Оскільки xm mod c(x) = 1, то (xm + 1) mod c(x) = 0, або c(x) ділить xm + 1.

У випадку, коли m = 2r – 1, x породжує усю мультиплікативну групу, і період на виході регістру досягає максимального значення, а поліном c(x) називають примітивним.

Будемо називати регістр Фібоначчі та регістр Галуа еквівалентними, якщо на їх виходах утворюються однакові послідовності. Розглянемо зв’язок між поліномами g(x) = xr Å gr-1xr-1 Å gr-2xr-2 ÅÅ g1x Å 1 та c(x) = xr Å cr-1xr-1 Å cr-2xr2 ÅÅ c1x Å 1, що відповідають еквівалентним регістрам RG та RF. Коефіцієнти цих поліномів задовольняють умові

                         _____

gi = cr-i, i = 1, r-1.

Вище було показано, що на виході еквівалентних регістрів утворюється послідовність з максимальним періодом, що дорівнює 2r – 1, тоді і тільки тоді, коли поліном g(x) примітивний. Покажемо, що цій же умові задовольняє і поліном c(x). Для цього розглянемо регістр Фібоначчі RF1, у якого відводи c1i, задовольняють умові

                               _____

c1i = gi = cr-i, i = 1, r-1.

 

Схема регістру показана на рис. 5.

 

Рис. 5. Схема регістру RF1.

 

На виході цього регістру утворюється послідовність максимального періоду тоді і тільки тоді, коли поліном c(x) примітивний. Зіставимо послідовності на виході регістрів RF та RF1. Нехай, у такті t (t > r) стан регістру RF - (atr-1, atr-2, … , a1t, at0), а регістру RF1 - (a0t, a1t,…, atr-2 , a tr-1). У регістрі RF1 a0t міститься у комірці sr-1, a1t, - у sr-2 , і так далі, a tr-1 - у s0.

 Тоді у наступних r тактах на виходах регістрів формуються взаємно інверсні послідовності (для кожного елементу наступний у одній послідовності дорівнює попередньому для цього елементу у іншій послідовності). Наприклад, у послідовності на виході регістру RF наступним елементом після at0 є a1t, і на виході регістру RF1 елементу at0 передує a1t.

Для того, щоб показати, що з взаємної інверсії станів у деякому такті t випливає повна взаємна інверсія послідовностей на виході регістрів, достатньо показати, що елемент на виході регістру RF у такті t+r дорівнює елементу на виході регістру RF1 у такті t-1.

Визначимо значення x, що міститься у комірці s0 регістру RF1 у такті t-1. У цьому такті a tr-1 міститься у комірці s1, at r-2 - у s2 , і так далі, a t1 - у s r-1. Тому

a t0 = c r-1 a t1 Å c r-2 a t2 ÅÅ c 2 at r-2 Å c 1 at r-1 Å x.

Звідки

x = a t0 Å c r-1 a t1 Å c r-2 a t2 ÅÅ c 2 at r-2 Å c 1 at r-1 .

У регістрі RF (рис. 1)

a t+r0 = at+1 r-1 = a t0 Å c r-1 a t1 Å c r-2 a t2 ÅÅ c 2 at r-2 Å c 1 at r-1 .

Таким чином at+r0 у регістрі RF дорівнює at-10 у регістрі RF1. Як наслідок, послідовності на виході регістрів RF та RF1 взаємно інверсні. А звідси випливає, що поліном c(x) – примітивний тоді і тільки тоді, коли g(x) – примітивний.

Розглянемо роботу регістрів RF та RF1, з якими асоційовані примітивні поліноми c(x) = x4 Å x3 Å 1 і g(x) = x4 Å x Å 1 відповідно. Послідовності станів обох регістрів представлені у табл. 3, де стани комірок регістру RF1 позначені буквою b.

 

Таблиця 3

 

регістр RF

регістр RF1

Такт

a3

a2

a1

a0

b 3

b 2

b 1

b 0

0

1

1

0

0

0

0

1

1

1

0

1

1

0

1

0

0

1

2

1

0

1

1

0

1

0

0

3

0

1

0

1

0

0

1

0

4

1

0

1

0

0

0

0

1

5

1

1

0

1

1

0

0

0

6

1

1

1

0

1

1

0

0

7

1

1

1

1

1

1

1

0

8

0

1

1

1

1

1

1

1

9

0

0

1

1

0

1

1

1

10

0

0

0

1

1

0

1

1

11

1

0

0

0

0

1

0

1

12

0

1

0

0

1

0

1

0

13

0

0

1

0

1

1

0

1

14

1

0

0

1

0

1

1

0

15

1

1

0

0

0

0

1

1

 

У поданій таблиці ai mod150 = b(3- i) mod150: a00 = b30, a10 = b20, a20 = b10, … , a130 = b50, a140 = b40, що свідчить про те, що послідовності на виходах регістрів взаємно інверсні.

 

Література

1. Смарт Н. Криптография. – М.: Техносфера, 2005.

2. Шнайер Б. Прикладная криптография. Издание 2-е. Протоколы, алгоритмы и исходные тексты на языке Си. – М.: Триумф, 2002.

3. Мао В. Современная криптография: теория и практика. – М.: Изд. дом «Вильямс», 2005.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info