Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием
Досліджено періоди повторення і статистичні характеристики псевдовипадкової бітової послідовності для прогнозування статистично безпечного ключового простору генераторів на основі модифікованого адитивного генератора Фібоначчі із запізненням. The investigation of repetition periods and statistical c...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2016 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/208273 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием / В.Н. Максымовыч, М.Н. Мандрона, О.И. Гарасимчук, Ю.М. Костив // Проблемы управления и информатики. — 2016. — № 6. — С. 97-102. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-208273 |
|---|---|
| record_format |
dspace |
| spelling |
Максымовыч, В.Н. Мандрона, М.Н. Гарасимчук, О.И. Костив, Ю.М. 2025-10-24T15:28:24Z 2016 Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием / В.Н. Максымовыч, М.Н. Мандрона, О.И. Гарасимчук, Ю.М. Костив // Проблемы управления и информатики. — 2016. — № 6. — С. 97-102. — Бібліогр.: 11 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208273 004.056; 004.421.5 10.1615/JAutomatInfScien.v48.i11.70 Досліджено періоди повторення і статистичні характеристики псевдовипадкової бітової послідовності для прогнозування статистично безпечного ключового простору генераторів на основі модифікованого адитивного генератора Фібоначчі із запізненням. The investigation of repetition periods and statistical characteristics of pseudorandom bit sequence for predicting statistically safe key space of generators based on the modified additive lagged Fibonacci generator is performed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием Дослідження характеристик модифікованого адитивного генератора Фібоначчі із запізненням A study of characteristics of Fibonacci modified additive generator with lag Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием |
| spellingShingle |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием Максымовыч, В.Н. Мандрона, М.Н. Гарасимчук, О.И. Костив, Ю.М. Методы обработки информации |
| title_short |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием |
| title_full |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием |
| title_fullStr |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием |
| title_full_unstemmed |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием |
| title_sort |
исследование характеристик модифицированного аддитивного генератора фибоначчи с запаздыванием |
| author |
Максымовыч, В.Н. Мандрона, М.Н. Гарасимчук, О.И. Костив, Ю.М. |
| author_facet |
Максымовыч, В.Н. Мандрона, М.Н. Гарасимчук, О.И. Костив, Ю.М. |
| topic |
Методы обработки информации |
| topic_facet |
Методы обработки информации |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Дослідження характеристик модифікованого адитивного генератора Фібоначчі із запізненням A study of characteristics of Fibonacci modified additive generator with lag |
| description |
Досліджено періоди повторення і статистичні характеристики псевдовипадкової бітової послідовності для прогнозування статистично безпечного ключового простору генераторів на основі модифікованого адитивного генератора Фібоначчі із запізненням.
The investigation of repetition periods and statistical characteristics of pseudorandom bit sequence for predicting statistically safe key space of generators based on the modified additive lagged Fibonacci generator is performed.
|
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208273 |
| citation_txt |
Исследование характеристик модифицированного аддитивного генератора Фибоначчи с запаздыванием / В.Н. Максымовыч, М.Н. Мандрона, О.И. Гарасимчук, Ю.М. Костив // Проблемы управления и информатики. — 2016. — № 6. — С. 97-102. — Бібліогр.: 11 назв. — рос. |
| work_keys_str_mv |
AT maksymovyčvn issledovanieharakteristikmodificirovannogoadditivnogogeneratorafibonaččiszapazdyvaniem AT mandronamn issledovanieharakteristikmodificirovannogoadditivnogogeneratorafibonaččiszapazdyvaniem AT garasimčukoi issledovanieharakteristikmodificirovannogoadditivnogogeneratorafibonaččiszapazdyvaniem AT kostivûm issledovanieharakteristikmodificirovannogoadditivnogogeneratorafibonaččiszapazdyvaniem AT maksymovyčvn doslídžennâharakteristikmodifíkovanogoaditivnogogeneratorafíbonaččíízzapíznennâm AT mandronamn doslídžennâharakteristikmodifíkovanogoaditivnogogeneratorafíbonaččíízzapíznennâm AT garasimčukoi doslídžennâharakteristikmodifíkovanogoaditivnogogeneratorafíbonaččíízzapíznennâm AT kostivûm doslídžennâharakteristikmodifíkovanogoaditivnogogeneratorafíbonaččíízzapíznennâm AT maksymovyčvn astudyofcharacteristicsoffibonaccimodifiedadditivegeneratorwithlag AT mandronamn astudyofcharacteristicsoffibonaccimodifiedadditivegeneratorwithlag AT garasimčukoi astudyofcharacteristicsoffibonaccimodifiedadditivegeneratorwithlag AT kostivûm astudyofcharacteristicsoffibonaccimodifiedadditivegeneratorwithlag |
| first_indexed |
2025-11-26T00:43:00Z |
| last_indexed |
2025-11-26T00:43:00Z |
| _version_ |
1850600820350910464 |
| fulltext |
© В.Н. МАКСЫМОВЫЧ, М.Н. МАНДРОНА, О.И. ГАРАСИМЧУК, Ю.М. КОСТИВ, 2016
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 6 97
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 004.056; 004.421.5
В.Н. Максымовыч, М.Н. Мандрона, О.И. Гарасимчук, Ю.М. Костив
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК
МОДИФИЦИРОВАННОГО АДДИТИВНОГО
ГЕНЕРАТОРА ФИБОНАЧЧИ
С ЗАПАЗДЫВАНИЕМ
Введение
Генераторы псевдослучайных последовательностей используются в различных
областях науки и техники, в частности при моделировании различных процессов
в сложных информационных системах, в аппаратных и программных системах защи-
ты информации, в средствах криптографического преобразования информации.
С развитием информационно-телекоммуникационных систем актуальным
остается вопрос обеспечения защищенности данных при передаче их по каналам
связи. В настоящее время обеспечение конфиденциальности, целостности или до-
ступности данных решается с использованием криптографических методов
защиты информации, в том числе различных алгоритмов шифрования, цифровых
подписей, кодов аутентификации сообщений и др.
Один из основных элементов криптографических систем, от характеристик
которых зависит качество всей криптографической системы, — средства генери-
рования ключей или генераторы псевдослучайных последовательностей (ГПП).
Установлено, что характеристики систем безопасности зависят от характеристик
их криптографических подсистем, которые определяются не только использован-
ными методами, но и качественными показателями использованных псевдослу-
чайных последовательностей. Поскольку безопасность криптосистемы сосредото-
чена на ключе, то при использовании ненадежного процесса генерации ключей
вся криптосистема становится уязвимой [1]. Поэтому актуальны вопросы форми-
рования новых алгоритмов генерации псевдослучайных последовательностей.
Цель данной публикации — исследование периодов повторения и стати-
стические характеристики псевдослучайной битовой последовательности для
прогнозирования эффективного (статистически безопасного) ключевого про-
странства генераторов на основе модифицированного аддитивного генератора
Фибоначчи с запаздыванием (МАГФЗ).
Исследование классических и модифицированных аддитивных
генераторов Фибоначчи с запаздыванием
Среди различных типов генераторов псевдослучайных битовых последователь-
ностей (ГПБП) можно выделить аддитивные генераторы Фибоначчи с запаздыванием
(АГФЗ) [2–5], преимущества которых — простота построения и быстродействие.
В общем виде работа АГФЗ описывается уравнением
,mod)( MXXXXX midicibii (1)
где Хі — текущее значение числа, biX , ciX , diX , …, miX — предыдущие
значения псевдослучайных чисел на определенных выбранных тактах.
98 ISSN 0572-2691
При аппаратной реализации для упрощения построения генератора прини-
мают nM 2 , где n — количество двоичных разрядов структурных элементов
схемы: регистров и комбинационных сумматоров. При этом статистические
характеристики выходной псевдослучайной последовательности ухудшаются.
В работах [6–8] предложены ГПБП на основе МАГФЗ, работающих в соот-
ветствии с уравнением
.2mod)...( n
midicibii aXXXXX (2)
Здесь значение переменной а определяется логическим уравнением
zaaaaa ...210 , (3)
где ia ( zi ...,,1,0 ) — значение двоичных разрядов числа iX .
Введение в процесс генерирования последовательностей числа а вызывает
определенную путаницу — зависимость каждого бита числа iX , а также и младшего
бита от всех других его битов, что позволяет значительно улучшить статистиче-
ские характеристики ГПБП.
При использовании МАГФЗ в криптографических устройствах в режиме
одноразового блокнота криптографическим ключом является значение начальных
цифр в регистрах генератора. Величина множества этих значений будет определять
криптостойкость шифров, в которых используется генератор, к атаке «грубая сила».
Следовательно, существует необходимость дополнительного исследования ГПБП
на основе МАГФЗ на всем множестве значений начальных чисел в регистрах.
Эта задача для достаточно больших количеств регистров и их разрядов такова,
что ее нельзя решить путем моделирования всех возможных вариантов исходной
битовой последовательности и их исследования. Однако не исключена возмож-
ность исследовать характеристики таких устройств на определенных подмноже-
ствах начальных значений, выявляя закономерности с последующей экстраполя-
цией этих результатов на все множество начальных значений.
В работе исследованы периоды повторения и статистические характеристики
псевдослучайной битовой последовательности для прогнозирования эффективного
статистически безопасного ключевого пространства генераторов на основе МАГФЗ.
Исследования проводились для генератора, который реализует функцию
n
ii³ àXXÕ 2mod)( 83 . (4)
Схема устройства ГПБП на основе МАГФЗ приведена на рис. 1. В его состав
входят: комбинационный сумматор (КС), регистры Рг1–Рг9 и логическая схема (ЛС).
Выходная битовая последовательность снимается с выхода младшего разряда Рг1.
Она формируется под влиянием следующих факторов:
— количество регистров генератора;
— определение регистров, числа в которых арифметически добавляются в КС;
— количество разрядов регистров, n;
— количество разрядов Рг1, подключенных к ЛС;
— начальные состояния Рг1–Рг9.
В данной работе первые два фактора зафиксированы неизменными в соответ-
ствии со структурой схемы устройства рис. 1.
Xi–1 Xi Xi–2
Xi–3 Xi–7 Xi–8
Xi–4 Xi–5
Xi–6
Выход
fT
a
Рис. 1
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 6 99
На рис. 2 (a — a = 0, б — 0aa , в — 10 aaa , г — 210 aaaa ) при-
ведены результаты исследования периодов повторения выходной последователь-
ности генератора при n = 3, которые определялись с помощью имитационного
моделирования и фиксировались в моменты, когда повторялись начальные значе-
ния чисел во всех регистрах. При этом осуществлен перебор всех возможных ком-
бинаций исходных чисел в регистрах Рг4 и Рг9: )0(3iX и )0(8iX , а в других
регистрах зафиксировались случайным образом выбранные начальные значения
3)0( iX , 7)0(1 iX , 5)0(2 iX , 3)0(4 iX , 1)0(5 iX , 7)0(6 iX ,
5)0(7 iX . Начальные значения чисел в Рг4 и Рг9 представлены переменной Q(0)
и определяются уравнением
)0(2)0((0) 83 i
n
i XXX . (5)
0 20 40 60
1E+0
8
1E+1
8
1E+2
8
1E+3
8
1E+4
8
1E+5
8
1E+6
8
1E+7
8
Х(0)
Тр
0 20 40 60
1E+0
8
1E+1
8
1E+2
8
1E+3
8
1E+4
8
1E+5
8
1E+6
8
1E+7
8
Х(0)
Тр
а б
Х(0)
Тр
0 20 40 60
1E+0
8
1E+1
8
1E+2
8
1E+3
8
1E+4
8
1E+5
8
1E+6
8
1E+7
8
Х(0)
Тр
0 20 40 60
1E+0
8
1E+1
8
1E+2
8
1E+3
8
1E+4
8
1E+5
8
1E+6
8
1E+7
8
в г
Рис. 2
Периоды повторения исследовались при различном количестве разрядов
регистра Рг1, подключенных к ЛС, т.е. при различных значениях переменной а
в соответствии с уравнением (3). Заметим, что случай a = 0 (рис. 2, а) соответствует
класическому АГФЗ, в котором отсутствует ЛС.
Из анализа результатов следует, что включение в состав генератора ЛС
существенно увеличивает периоды повторения выходной последовательности.
При этом увеличение периодов наблюдается также с увеличением задействованных
членов уравнения (3).
100 ISSN 0572-2691
Дальнейшие исследования проводились при увеличении количества разрядов
структурных элементов устройства при n = 4 и тех же значениях ,3)0( iX
,7)0(1 iX ,5)0(2 iX ,3)0(4 iX ,1)0(5 iX ,7)0(6 iX .5)0(7 iX Ре-
зультаты исследований МАГФЗ (в сокращенном виде) приведены в таблице, где
minTp и maxTp — минимальное и максимальное значение Tp на всем множестве
значений начальных состояний регистров Рг4 и Рг9.
Таблица
A
minTp
maxTp
Значения NIST Значения NIST
0 4088 — 4088 —
0a 2044 — 6132 —
10 aa 58254 — 144438238 —
210 aaa 55889092 — >109 +
3210 aaaa 750109555 — >109 +
Для отдельных значений minTp и maxTp исследовались статистические ха-
рактеристики исходной последовательности генератора с помощью статистиче-
ских тестов NISN [9], поскольку они используются для определения качественных
и количественных свойств случайных последовательностей. Набор NIST содер-
жит 15 статистических тестов, в том числе тест определения линейной сложности.
Во время тестирования вычисляется 188 значений вероятности Р, которые можно
рассматривать как результат работы отдельных тестов. По полученным резуль-
татам формируют статистический портрет (рис. 3: а — 0aa , б — 10 aaa ,
в — 210 aaaa , г — 3210 aaaaa ), в котором пунктирными линиями
отмечены границы доверительного интервала [8, 10]. Если результаты тестирования
попадают в эти пределы, то делаем вывод, что исследуемый генератор соответ-
ствует требованиям случайности, т.е. статистически безопасный.
На рис. 3 приведены результаты исследования статистических характеристик
МАГФЗ при n = 4 и minTp . Из статистических портретов четко видно, как влияет
ЛС на статистические характеристики генератора.
Протестирована битовая последовательность длиной 910 бит, которая снима-
лась с младшего разряда регистра Рг1. При этом зафиксировано, что при 910Tp
в большинстве случаев исследуемая последовательность проходит все тесты
(отмечено символом + в таблице), а в случае, когда ,109Tp она не проходит все
тесты. Заметим, что при n = 4 и 210 aaaa период Tp не превышает 910 для
12-ти значений X(0) из 256, а при n = 4 и 3210 aaaaa — только для трех
значений X(0) из тех же 256.
200 0 40 0
В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,2
0,4
0,6
Номер теста
1
0,8
80 120 160
200
0
40 0
В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,4
0,6
0,8
Номер теста
1,2
1
80 120 160
0,2
а б
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 6 101
Продолжение рис. 3
200
0,952
50 0 В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,962
0,982
0,992
Номер теста
1,002
100
0
150
0,972
200
0,976
50 0 В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,98
0,992
0,996
Номер теста
1
100
0
150
0,984
0,988
в г
Рис. 3
На рис. 4 приведены статистические портреты для выходной псевдослу-
чайной последовательности при n = 4, 3210 aaaaa и указанных выше
неизменных начальных значениях чисел в регистрах Рг1, Рг2, Рг3, Рг5, Рг6,
Рг7, Рг8, на рис. 3, а — для случая когда 103 iÕ и 58 iX , при котором
был зафиксирован период 750109555Tp , а на рис. 3, б — для 03 iX
и ,08 iX когда 910Tp .
200
0,976
50 0
В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,984
0,992
0,996
Номер теста
1
100
0
150
0,988
0,98
0,98
0
В
ер
о
ят
н
о
ст
ь
п
р
о
х
о
ж
д
ен
и
я
те
ст
о
в
0,984
0,992
0,996
Номер теста
1,002
0,988
200 40 80 120 160
1
а б
Рис. 4
Из статистических портретов видно, что практически все результаты тестиро-
вания попадают в границы доверительного интервала, что свидетельствует о случай-
ности битовой последовательности и статистической безопасности ГПБП (рис. 4, б),
однако на рис. 4, а один тест не пройден, т.е. ГПБП формирует последователь-
ность, приближенную к случайной.
Заключение
В процессе исследования быстродействующих АГФЗ улучшены статистические
характеристики и увеличены их периоды повторения за счет введения в схему клас-
сического генератора дополнительного элемента, который приводит к усложнению.
При увеличении количества двоичных разрядов структурных элементов генератора
и задействованных членов уравнения (3) происходит стремительное увеличение
периодов повторения исходной псевдослучайной битовой последовательности
и улучшение ее статистических характеристик.
При этом, однако, возникает вопрос оценки величины множества начальных
значений регистров, которая определяет величину статистически безопасного
ключевого пространства (длину ключа).
Исследования для n = 4 при полном переборе начальных значений в двух ре-
гистрах показывают, что в большинстве случаев исходная последовательность
успешно проходит все статистические тесты NIST. В результате можно прогнози-
ровать, что аналогичные результаты будут зафиксированы и при полном переборе
начальных чисел во всех регистрах устройства. Логично также предположить, что
при увеличении количества разрядов n статистические характеристики исходной
последовательности должны улучшаться. Итак, статистически безопасное множество
начальных состояний регистров генератора (см. рис. 1) будет близко к значению n92 ,
что соответствует длине ключа n9 .
102 ISSN 0572-2691
В.М. Максимович, М.М. Мандрона, О.І. Гарасимчук, Ю.М. Костів
ДОСЛІДЖЕННЯ ХАРАКТЕРИСТИК
МОДИФІКОВАНОГО АДИТИВНОГО
ГЕНЕРАТОРА ФІБОНАЧЧІ ІЗ ЗАПІЗНЕННЯМ
Досліджено періоди повторення і статистичні характеристики псевдовипад-
кової бітової послідовності для прогнозування статистично безпечного клю-
чового простору генераторів на основі модифікованого адитивного генератора
Фібоначчі із запізненням.
V.N. Maksymovych, M.N. Mandrona, O.I. Garasimchuk, Yu.M. Kostiv
A STUDY OF CHARACTERISTICS
OF FIBONACCI MODIFIED
ADDITIVE GENERATOR WITH LAG
The investigation of repetition periods and statistical characteristics of pseudorandom bit
sequence for predicting statistically safe key space of generators based on the modified
additive lagged Fibonacci generator is performed.
1. Горбенко І.Д., Горбенко Ю.І. Прикладна криптографія. Теорія. Практика. Застосування. —
Харків: Форт, 2012. — 870 с.
2. Orue A.B., Montoya F., Hernández Encinas L. Trifork, a new pseudorandom number generator
based on lagged Fibonacci maps // Journal of Computer Science and Engineering. — 2010. — 2,
N 2. — P. 46–51.
3. Parallel pseudorandom number generation using additive lagged Fibonacci recursions /
M. Mascagni, M.L. Robinson, D.V. Pryor, S.A. Cuccaro // Lecture Notes in Statistics. — 1995. —
N 106. — P. 263–277.
4. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослу-
чайных последовательностей, — М. : КУДИЦ-ОБРАЗ, 2003. — 240 с.
5. Иванов М.А., Чугунков И.В. Криптографические методы защиты информации в компью-
терных системах и сетях. — М.: Изд–во НИЯУ МИФИ, 2012. — 400 с.
6. Модифікація адитивного генератора Фібоначчі з запізненням / М.М. Мандрона,
В.М. Максимович, Ю.М. Костів, О.І. Гарасимчук // Сучасний захист інформації. — 2014. —
№ 2. — С. 56–62.
7. Пат. 108586 Україна, МПК61G06F 7/58 H04L 9/20. Адитивний генератор Фібоначчі із запіз-
ненням / В.М. Максимович, М.М. Мандрона, О.І. Гарасимчук, Ю.М. Костів. — № a2014 06408 ;
Заявл. 04.07.2014; Опубл. 12.05.2015, Бюл. № 9.
8. Мандрона М.М. Апаратні генератори псевдовипадкових бітових послідовностей з покра-
щеними характеристиками : Дис. … канд. техн. наук : 05.13.21. — Львів, 2015. — 146 с.
9. NIST SP 800–22. A statistical test suite for random and pseudorandom number generators for crypto-
graphic applications. — http://csrc.nist.gov/publications/nistpubs/800–22–rev1a/SP800–22rev1a.pdf.
10. Дослідження впливу параметрів генератора Голлманна на статистичні характеристики
вихідного сигналу / М.М. Мандрона, В.М. Максимович, Ю.М. Костів, О.І. Гарасимчук //
Вісник Кременчуцького національного університету імені Михайла Остроградського. —
2013. — Вип. 4 (81). — С. 98–103.
11. Mandrona M.N., Maksymovych V.N Investigation of the statistical characteristics of the modified
Fibonacci generators // Journal of Automation and Information Sciences. — 2014. — 46.i 12.60. —
P. 48–53.
Получено 18.04.2016
После доработки 05.07.2016
|