Недетермінований генератор рівномірно розподілених випадкових послідовностей

Реферат: Винахід належить до обчислювальної техніки, а саме до системи захисту інформації обчислювальних систем. Недетермінований генератор рівномірно розподілених випадкових послідовностей за рахунок введення рівномірно розподілених випадкових послідовностей додаткових лічильників з коефіцієнтами ділення, що програмуються, дозволяє змінювати параметри рекуренти регістра зсуву у випадкові моменти часу, що підвищує криптостійкість випадкових послідовностей, що генеруються, та значно ускладнює процес криптоаналізу цих послідовностей. UA 103097 C2 (12) UA 103097 C2 UA 103097 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до області обчислювальної техніки і може бути використаний в системах захисту інформації обчислювальних систем, наприклад, при генерації параметрів алгоритмів криптографічного перетворення, в протоколах аутентифікації, в засобах імовірнісного кодування та ін. Відомий генератор рівномірно розподілених випадкових послідовностей (див. патент України № 50386 А, МПК6 G06F7/58, G07C15/00, опублікований 15.10.2002, Бюл. № 10), що містить n джерел ентропії, які складаються з послідовно з'єднаних генератора шуму, підсилювача-обмежувача та лічильного тригера, виходи джерел ентропії підключені до перших входів n елементів «ВИКЛЮЧНЕ АБО», виходи яких з'єднані з входами регістра зсуву, поділеного на n частин, а останні виходи кожної частини регістра зсуву підключені до других входів наступних елементів «ВИКЛЮЧНЕ АБО», входи першого елемента «ВИКЛЮЧНЕ АБО» з'єднані з останнім виходом регістра зсуву та проміжним виходом цього регістра, виходи регістра зсуву підключені до входів вихідного паралельного регістра, а його виходи підключені до шини даних ПЕОМ, тактовий генератор, вихід якого з'єднаний з синхровходами регістра зсуву і входом лічильника імпульсів, вихід якого під'єднаний до синхровходу вихідного паралельного регістра та входу тригера "прапора", а його вихід з'єднаний з входом запиту переривання ПЕОМ і через буферний елемент «І» з шиною даних ПЕОМ, та дешифратор адреси, включений входами до шини адреси ПЕОМ, а першим виходом до входу дозволу вихідного регістра і входу скидання тригера "прапора", і другим виходом до буферного елемента «І». Недоліком цього генератора є невідповідність спеціальним вимогам стандарту ISO/IEC 18031:2005, яких необхідно дотримуватися при розробці генератора випадкових бітів, що буде використовуватися для криптографічних застосувань. Цей генератор не підтримує «вимогу продовження дії недетермінованого генератора випадкових бітів (НГВБ) способом, не менш захищеним, ніж детермінований генератор випадкових бітів (ДГВБ) у випадку повного збою джерела ентропії». Найбільш близьким по сукупності ознак є недетермінований генератор рівномірно розподілених випадкових бітів (див. патент України № 96654, МПК (2011.01) G06F 7/58 (2006.01), G07C 15/00, опублікований 25.11.2011, Бюл. № 22), що містить n джерел ентропії, підключених до перших входів елементів «ВИКЛЮЧНЕ АБО», виходи яких з'єднані з входами регістра зсуву, поділеного на n частин, а останні виходи кожної частини регістра зсуву підключені до других входів наступних елементів «ВИКЛЮЧНЕ АБО», другий та третій входи першого елемента «ВИКЛЮЧНЕ АБО» з'єднані з виходами першого та другого мультиплексорів, інформаційні входи яких підключені до проміжних виходів регістра зсуву, адресні входи першого та другого мультиплексорів з'єднані з виходами першого та другого паралельних регістрів, інформаційні входи яких підключені до проміжних виходів регістра зсуву, синхровходи першого та другого паралельних регістрів підключені відповідно до виходів першого та другого лічильників імпульсів, тактовий генератор, вихід якого з'єднано з синхровходами регістра зсуву, першого та другого лічильника імпульсів та виходом синхросигнала пристрою, додатковий елемент «ВИКЛЮЧНЕ АБО», входи якого підключені до проміжних виходів регістра зсуву, а вихід цього елемента «ВИКЛЮЧНЕ АБО» є виходом пристрою. Недоліком цього генератора є його недостатня крипостійкість у випадку повного збою джерел ентропії. В основу винаходу поставлена задача створення такого недетермінованого генератора рівномірно розподілених випадкових послідовностей, в якому додавання нових схемних елементів і зв'язків дозволило б підвищити криптостійкiсть за рахунок зміни параметрів рекуренти регістра зсуву в випадкові моменти часу. Такий технічний результат може бути досягнутий, якщо в недетермінованому генераторі рівномірно розподілених випадкових послідовностей, що містить n джерел ентропії, підключених до перших входів елементів «ВИКЛЮЧНЕ АБО», виходи яких з'єднані з входами регістра зсуву, поділеного на n частин, а останні виходи кожної частини регістра зсуву підключені до других входів наступних елементів «ВИКЛЮЧНЕ АБО», другий та третій входи першого елемента «ВИКЛЮЧНЕ АБО» з'єднані з виходами першого та другого мультиплексорів, інформаційні входи яких підключені до проміжних виходів регістра зсуву, адресні входи першого та другого мультиплексорів з'єднані з виходами першого та другого паралельних регістрів, інформаційні входи яких підключені до проміжних виходів регістра зсуву у довільному порядку, додатковий елемент «ВИКЛЮЧНЕ АБО», входи якого підключені до проміжних виходів регістра зсуву, а вихід цього елемента «ВИКЛЮЧНЕ АБО» є виходом пристрою, тактовий генератор, вихід якого з'єднано з синхровходами регістра зсуву, а також є 1 UA 103097 C2 5 10 15 20 25 30 35 40 45 50 55 виходом синхросигнала пристрою, згідно з винаходом додатково введені перший та другий лічильники з коефіцієнтами ділення, що програмуються, синхровходи цих лічильників підключені до виходу тактового генератора, а їх виходи з'єднані з синхровходами першого та другого паралельних регістрів, інформаційні входи цих лічильників підключені до проміжних виходів регістра зсуву у довільному порядку. Таким чином, введення в недетермінований генератор рівномірно розподілених випадкових послідовностей додаткових лічильників з коефіцієнтами ділення, що програмуються, дозволяє змінювати параметри рекуренти регістра зсуву у випадкові моменти часу, що підвищує криптостійкiсть випадкових послідовностей, що генеруються, та значно ускладнює процес криптоаналізу цих послідовностей. На кресленні зображена структурна схема недетермінованого генератора рівномірно розподілених випадкових послідовностей. На кресленні використані наступні міжнародні позначення: ES - джерело ентропії, RG регістр, G - генератор, СТ - лічильник, MS - мультиплексор. Генератор містить n джерел 1-1...1-n ентропії, підключених до перших входів елементів 21...2-n «ВИКЛЮЧНЕ АБО», виходи яких з'єднані з входами регістра 3-1...3-n зсуву, поділеного на n частин, а останні виходи кожної частини регістра 3-1...3-n зсуву підключені до других входів наступних елементів 2-2...2-n «ВИКЛЮЧНЕ АБО», другий та третій входи першого елемента 2-1 «ВИКЛЮЧНЕ АБО» з'єднані з виходами першого 4 та другого 5 мультиплексорів, iнформаційні входи яких підключені до проміжних виходів регістра 3-1...3-n зсуву, адресні входи першого 4 та другого 5 мультиплексорів з'єднані з виходами першого 6 та другого 7 паралельних регістрів, інформаційні входи яких підключені до проміжних виходів регістра 3-1...3-n зсуву у довільному порядку, синхровходи першого 6 та другого 7 паралельних регістрів підключені відповідно до виходів першого 8 та другого 9 лічильників з коефіцієнтами ділення, що програмуються, тактовий генератор 10, вихід якого є з'єднано з синхровходами регістра 3-1...3-n зсуву, першого 8 та другого 9 лічильників з коефіцієнтами ділення, що програмуються, та виходом синхросигнала пристрою, додаткововий елемент 11 «ВИКЛЮЧНЕ АБО», входи якого підключені до проміжних виходів регістра 3-1...3-n зсуву, а вихід цього елемента 11 «ВИКЛЮЧНЕ АБО» є виходом пристрою. Недетермінований генератор рівномірно розподілених випадкових послідовностей працює наступним чином. На виходах джерел 1-1...1-n ентропії формуються логічні рівні, які з рівною імовірністю приймають значення нуля або одиниці в випадкові моменти часу. Ці випадкові логічні рівні перемикають на протилежні значення логічні рівні, що подаються з останніх виходів частин регістра 3-1...3-n зсуву до входів наступних частин цього регістра, в випадкові моменти часу за допомогою елементів 2-1...2-n «ВИКЛЮЧНЕ АБО». Тактовий генератор 10 формує частоту зсуву випадкових бітів в регістрі 3-1...3-n і таким чином визначає швидкість формування випадкових бітових послідовностей, які за рахунок дії джерел 1-1...1-n ентропії стають непередбачуваними, тобто - недетермінованими, непрогнозованими. Перший 4 та другий 5 мультиплексори формують сигнали зворотного зв'язку лінійного рекурентного регістра 3-1...3-n зсуву. Логічні рівні з проміжних виходів регістра 3-1...3-n зсуву в випадковому порядку надходять через перший 4 та другий 5 мультиплексори до входів першого елемента 2-1 «ВИКЛЮЧНЕ АБО» та визначають параметри рекуренти. Випадковий характер комутації сигналів мультиплексорами 4, 5 визначається логічними рівнями на їх адресних входах, які підключені до виходів першого 6 та другого 7 паралельних регістрів. Ці регістри запам'ятовують випадкові сигнали з проміжних виходів регістра 3-1...3-n зсуву. Часові інтервали зміни сигналів в першому паралельному регістрі 6 визначаються першим лічильником 8 з коефіцієнтом ділення, що програмується, а в другому паралельному регістрі 7 - другим лічильником 9 з коефіцієнтом ділення, що програмується. Синхровходи лічильників 8, 9 з коефіцієнтами ділення, що програмуються, підключені до виходу тактового генератора 10, а інформаційні входи цих лічильників з'єднані з проміжними виходами регістра зсуву у довільному порядку. Логічні сигнали з проміжних виходів регістра 3-1...3-n зсуву об'єднуються елементом 11 «ВИКЛЮЧНЕ АБО», вихід якого є виходом пристрою. Недетерміновані випадкові бітові послідовності зчитуються зовнішнім пристроєм з виходу елемента 11 «ВИКЛЮЧНЕ АБО» по фронтах синхросигнала з виходу тактового генератора 10. При повному збою джерел 1-1...1-n ентропії криптостійкість пристрою задовольняє вимогам стандарту ISO/IEC 18031:2005, тому що математичний розрахунок параметрів рeкуренти регістра 3-1...3-n зсуву при спостереженні вихідних бітів є неможливим. 60 2 UA 103097 C2 ФОРМУЛА ВИНАХОДУ 5 10 15 Недетермінований генератор рівномірно розподілених випадкових послідовностей, що містить n джерел ентропії, підключених до перших входів n елементів "ВИКЛЮЧНЕ АБО", виходи яких з'єднані з входами регістра зсуву, поділеного на n частин, а останні виходи кожної частини регістра зсуву підключені до других входів наступних з n елементів "ВИКЛЮЧНЕ АБО", другий та третій входи першого з n елемента "ВИКЛЮЧНЕ АБО" з'єднані з виходами першого та другого мультиплексорів, інформаційні входи яких підключені до проміжних виходів регістра зсуву, адресні входи першого та другого мультиплексорів з'єднані з виходами першого та другого паралельних регістрів, інформаційні входи яких підключені до проміжних виходів регістра зсуву у довільному порядку, додатковий елемент "ВИКЛЮЧНЕ АБО", входи якого підключені до проміжних виходів регістра зсуву, а вихід цього елемента "ВИКЛЮЧНЕ АБО" є виходом пристрою, тактовий генератор, вихід якого з'єднано з синхровходами регістра зсуву, а також є виходом синхросигнала пристрою, який відрізняється тим, що додатково введені перший та другий лічильники з коефіцієнтами ділення, що програмуються, синхровходи цих лічильників підключені до виходу тактового генератора, а їх виходи з'єднані з синхровходами першого та другого паралельних регістрів, інформаційні входи цих лічильників підключені до проміжних виходів регістра зсуву у довільному порядку. 3 UA 103097 C2 Комп’ютерна верстка А. Крижанівський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4