Адитивний генератор фібоначчі із запізненням

Реферат: Адитивний генератор Фібоначчі із запізненням належить до систем захисту інформації, а також в інших системах для імітації і моделювання випадкових процесів з високими статистичними характеристиками. Адитивний генератор Фібоначчі із запізненням містить комбінаційний суматор та q+1 регістрів пам'яті, тактові входи яких підключені до тактового входу пристрою, інформаційні входи кожного наступного регістра пам'яті з'єднані з виходами попереднього регістра пам'яті, виходи р-го регістра пам'яті підключені до першої групи входів комбінаційного суматора, друга група входів якого з'єднана з виходами q-гo регістра пам'яті, а виходи комбінаційного суматора підключені до інформаційних входів 0-го регістра пам'яті. Додатково містить логічну схему, інформаційні входи якої з'єднані з виходами 0-го регістра пам'яті і виходами пристрою, керуючі входи підключені до керуючих входів пристрою, а її вихід з'єднаний з входом переносу комбінаційного суматора. В адитивному генераторі Фібоначчі із запізненням за рахунок введення нових конструктивних елементів та зв'язків забезпечується збільшення періоду повторення вихідних псевдовипадкових послідовностей чисел і бітів та UA 108586 C2 (12) UA 108586 C2 покращуються їх статистичні характеристики, що значно покращує характеристики систем захисту інформації і інших систем, в яких використовується запропонований пристрій. UA 108586 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до галузі приладобудування, генерування послідовностей псевдовипадкових чисел і псевдовипадкових бітових послідовностей. Генератор може бути використаний в системах захисту інформації, а також в інших системах для імітації і моделювання випадкових процесів з високими статистичними характеристиками. Відомий адитивний генератор Фібоначчі із запізненням [Иванов М.А., Чугунков И.В. Криптографические методы защиты информации в компьютерных системах и сетях: Учебное пособие / Под ред. М.А. Иванова. М.: НИЯУ МИФИ, 2012. - 400 с: ил., ст. 261], який містить комбінаційний суматор і регістри пам'яті q+1, тактові входи яких підключені до тактового входу пристрою, інформаційні входи кожного наступного регістра пам'яті з'єднані з виходами попереднього регістра пам'яті, виходи р-го регістра пам'яті підключені до першої групи входів комбінаційного суматора, друга група входів якого з'єднана з виходами q-гo регістра пам'яті, а виходи комбінаційного суматора підключені до інформаційних входів 0-го регістра пам'яті. Але виходи комбінаційного суматора є виходами пристрою, а вхід переносу комбінаційного суматора є незадіяним, що істотно зменшує період повторення вихідних псевдовипадкових послідовностей чисел і бітів і погіршує їх статистичні характеристики. Це пояснюється тим, що процес додавання молодших розрядів чисел в комбінаційному суматорі і послідовний зсув чисел в регістрах пам'яті спричиняє явище "зациклювання", яке розповсюджується і на усі старші розряди чисел, оскільки на цей процес не впливають ніякі інші сигнали. В основу винаходу поставлено задачу створення адитивного генератора Фібоначчі із запізненням, в якому введення нових конструктивних елементів та зв'язків забезпечувало б збільшення періоду повторення вихідних псевдовипадкових послідовностей чисел і бітів і покращення їх статистичних характеристик. Поставлена задача вирішується тим, що адитивний генератор Фібоначчі із запізненням, який містить комбінаційний суматор і регістри пам'яті q+1, тактові входи яких підключені до тактового входу пристрою, інформаційні входи кожного наступного регістра пам'яті з'єднані з виходами попереднього регістра пам'яті, виходи р-го регістра пам'яті підключені до першої групи входів комбінаційного суматора, друга група входів якого з'єднана з виходами q-гo регістра пам'яті, а виходи комбінаційного суматора підключені до інформаційних входів 0-го регістра пам'яті, згідно з винаходом, він додатково містить логічну схему, інформаційні входи якої з'єднані з виходами 0-го регістра пам'яті і виходами пристрою, керуючі входи підключені до керуючих входів пристрою, а її вихід з'єднаний з входом переносу комбінаційного суматора. Це дає змогу ввести додаткову складову в процес додавання чисел, що зберігаються в регістрах пам'яті, змінити за рахунок цього алгоритм обчислення і, з використанням незначного додаткового обладнання, істотно збільшити період повторення псевдовипадкових послідовностей вихідних чисел і бітів генератора і покращити їх статистичні характеристики, що значно покращує характеристики систем захисту інформації і інших систем, в яких використовується запропонований пристрій. На Фіг. 1 представлена блок-схема адитивного генератора Фібоначчі із запізненням, де 1 комбінаційний суматор, 20, 21, …, 2р, 2р+1,…, 2q – регістри пам'яті, 3 - логічна схема, 4 - тактовий вхід пристрою, 5 - виходи пристрою, 6 - керуючі входи пристрою. На Фіг. 2 наведений приклад реалізації логічної схеми 3, де 7 0, 71,…, 7m-3, 7m-2 - суматори за модулем два; 80, 81,…, 8m-2, 8m-1, - елементи логічного множення. На Фіг. 3 наведені результати імітаційного моделювання запропонованого пристрою і пристрою прототипу: на Фіг. За - результати тестування пристрою-прототипу, а на Фіг. 3б запропонованого пристрою. Адитивний генератор Фібоначчі із запізненням складається з комбінаційного суматора 1, логічної схеми 3 і регістрів пам'яті 20, 21,…, 2р, 2р+1,…, 2q, тактові входи яких підключені до тактового входу 4 пристрою, інформаційні входи кожного наступного регістра пам'яті 2 з'єднані з виходами попереднього регістра пам'яті, виходи регістра пам'яті 2р підключені до першої групи входів комбінаційного суматора 1, друга група входів якого з'єднана з виходами регістра пам'яті 2q, а виходи комбінаційного суматора 1 підключені до інформаційних входів регістра пам'яті 2 0. Інформаційні входи логічної схеми 3 з'єднані з виходами регістра пам'яті 2 0 і виходами пристрою 5, керуючі входи підключені до керуючих входів 6 пристрою, а її вихід з'єднаний з входом переносу комбінаційного суматора 1. Логічна схема 3 складається з суматорів за модулем два 70, 71,…, 7m-3, 7m-2 і елементів логічного множення 80, 81,…, 8m-2, 8m-1, перші входи яких підключені до інформаційних входів 5 логічної схеми 3, другі входи з'єднані з керуючими входами 6 логічної схеми 3, виходи елементів логічного множення 80, 81,…, 8m-2 підключені до перших входів суматорів за модулем два 7 0, 71,…, 7m-3, 7m-2, другі входи кожного наступного суматора за модулем два 7 0, 71,…, 7m-3 з'єднані з виходи попереднього суматора за модулем два 71,…, 7m-3, 7m-2 відповідно, другий вхід суматора 1 UA 108586 C2 5 10 15 20 25 30 35 40 45 50 55 за модулем два 7m-2 підключений до виходу елемента логічного множення 8m-1, а вихід суматора за модулем два 70 з'єднаний з входом логічної схеми 3. Адитивний генератор Фібоначчі із запізненням працює таким чином. З кожним тактовим імпульсом в регістрах 20, 21,…, 2р, 2р+1,…, 2q формуються нові значення чисел. В регістрі 20 число, що визначається вихідним сигналом комбінаційного суматора 1, а в регістрах 2j (j=1, 2,…, q) числа, що визначаються вихідними сигналами в регістрах 2j-1. На виході логічної схеми 3 формується сигнал у відповідності до логічного рівняння: a=b0  b1 …  bs, (1) де bk (k=0, 1,…, s) значення двійкових розрядів числа в регістрі 20, a s може приймати значення від 0 до m-1, де m кількість двійкових розрядів кожного з регістрів 20, 21,…, 2р, 2р+1,…, 2q. Таким чином, в роботі логічної схеми 3, може бути задіяна будь-яка задана кількість двійкових розрядів регістра 20, що визначається значенням коду с0, …, сm-1 на керуючих входах 6 пристрою. Наприклад, якщо на керуючі входи 6 подані значення керуючого коду с 0=1, c1=c2=…=cm-1=0 - на виході логічної схеми 3 буде сформований логічний сигнал у відповідності до рівняння а=b0. При наявності на керуючих входах логічної схеми 3 значень с 0=1, c1=1, с2=…=сm-1=0 - на виході буде сигнал у відповідності до рівняння а=b0  b1 і т.д. З надходженням чергового тактового імпульсу в регістр 20 записується число, що формується на виходах комбінаційного суматора 1, у відповідності з виразом m Qi=(Qi-p+Qi-q+a)mod2 , (2) де Qi, Qi-p і Qi-q - числа в регістрах пам'яті 20, 2р і 2q відповідно. На відміну від пристрою-прототипу, в якому алгоритм додавання не містить додаткової складової - а, в запропонованому генераторі завдяки цій складовій не виникає явище "зациклювання" при додаванні молодших розрядів чисел, яке розповсюджується і на усі старші розряди. В результаті істотно збільшується період повторення псевдовипадкових послідовностей вихідних чисел і бітів і покращуються їх статистичні характеристики. Покращення характеристик запропонованого генератора у порівнянні з пристроємпрототипом підтверджується результатами імітаційного моделювання при будь-якій кількості регістрів пристрою і будь-якій кількості їх двійкових розрядів. Наприклад, при р=3, q=8 і m=10, тобто при умові, що на виході комбінаційного суматора 1 формується число у відповідності до виразу 10 Qi=(Qi-3+Qi-8+a)mod2 , (3) були отримані наступні результати для порівнювальних пристроїв. Період повторення послідовності вихідних чисел пристрою-прототипу становить 261631. В запропонованому пристрої: якщо s=0, тобто а=b0, - період повторення дорівнює 392448; якщо 9 s>0, тобто для випадків a=b0  b1, а=b0  b1  b2 і т.д., - період повторення є більшим від 10 . На Фіг. 3 наведені результати аналізу статистичних характеристик пристроїв за допомогою тестів NIST - пакета статистичних тестів, який розроблений Лабораторією інформаційних технологій Національного Інституту Стандартів і Технологій США (NIST). Пакет NIST STS включає в себе 15 статистичних тестів, які розроблені для перевірки гіпотези про випадковість двійкових послідовностей довільної довжини, що генеруються. Кожен з даних тестів спрямований на виявлення різноманітних дефектів випадковості. Обчислюється 188 значень ймовірності Р, які можна розглядати як результат роботи окремих тестів. Тест вважається пройденим, коли ймовірність проходження тесту Р потрапить у межі від 0,98 до 1,00. Якщо ж імовірність Р буде знаходитись нижче 0,98, вважається, що тест не пройдено. Тестування проводилося при рівні значущості α=0,01, який рекомендований розробниками NIST STS. Тестуванню підлягала псевдовипадкова бітова послідовність що формується на виході 0 молодшого розряду регістра 2 - розряду b0. Результати тестування пристрою-прототипу представлені на Фіг. 3а, а запропонованого пристрою - на Фіг. 3б. Отже, запропонований пристрій значно переважає пристрій-прототип за своїми статистичними характеристиками, оскільки стосовно останнього ціла група тестів є не пройденою, а в запропонованому пристрою вихідний псевдовипадковий сигнал відповідає усім вимогам тестування. Таким чином, в запропонованому пристрої, у порівнянні з відомим, істотно збільшений період повторення псевдовипадкових послідовностей вихідних чисел і бітів і покращені їх статистичні характеристики, що значно покращує характеристики систем захисту інформації і інших систем, де використовуються такі пристрої, в цілому. 2 UA 108586 C2 ФОРМУЛА ВИНАХОДУ 5 10 Адитивний генератор Фібоначчі із запізненням, який містить комбінаційний суматор та q+1 регістрів пам'яті, тактові входи яких підключені до тактового входу пристрою, інформаційні входи кожного наступного регістра пам'яті з'єднані з виходами попереднього регістра пам'яті, виходи р-го регістра пам'яті підключені до першої групи входів комбінаційного суматора, друга група входів якого з'єднана з виходами q-гo регістра пам'яті, а виходи комбінаційного суматора підключені до інформаційних входів 0-го регістра пам'яті, який відрізняється тим, що додатково містить логічну схему, інформаційні входи якої з'єднані з виходами 0-го регістра пам'яті і виходами пристрою, керуючі входи підключені до керуючих входів пристрою, а її вихід з'єднаний з входом переносу комбінаційного суматора. 3 UA 108586 C2 Комп’ютерна верстка О. Рябко Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4