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

Спосіб формування послідовностей псевдовипадкових чисел, який полягає у тому, що ключо 3 38402 де bi - молодший біт числа xi , xi+1 = f (xi ) = xie modn . Задача вираховування функції f (x )-1 , яка є зворотною до функції модульного піднесення до ступеня f (x ) = x e mod n , тобто вирахування деякого значення xi за відомим значенням xi+1 є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування, щодо вирішення якої на сьогоднішній день невідомо ефективних алгоритмів вираховування дискретних логарифмів великих чисел. Тому цей спосіб формування послідовностей псевдовипадкових чисел є криптографічно стійким. Недоліком способу-прототипу є те, що він не дозволяє формувати послідовності псевдовипадкових чисел максимального періоду, що суттєво зменшує його ефективність та обмежує можливості щодо практичного використання. В основу корисної моделі поставлена задача створити спосіб формування послідовностей псевдовипадкових чисел який, за рахунок додаткового введення рекурентних перетворень, що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, дозволить формувати послідовності псевдовипадкових чисел максимального періоду, що підвищить його ефективність та розширить можливості щодо практичного використання. Поставлена задача вирішується за рахунок додаткового введення рекурентних перетворень які дозволяють формувати послідовності псевдовипадкових чисел максимального періоду. Технічний результат, який може бути отриманий при здійснені корисної моделі полягає в отриманні можливості формувати послідовності псевдовипадкових чисел максимального періоду, що підвищує ефективність та розширює його можливості. Сутність запропонованого способу формування послідовностей псевдовипадкових чисел полягає в тому, що ключова послідовність подається у вигляді вектора x0 , який ініціалізує початкове значення аргументу функції f (x ) = x e mod n модульного піднесення до ступеня та початкове значення y0 рекурентного перетворення L(y ) , що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками. У якості модуля n обирається добуток великих простих чисел p і q , у якості ступеня e обирається число, взаємно просте з (p - 1)× (q - 1) . Наступне значення 4 аргументу функції обраховується за допомогою пристроїв модульного піднесення до ступеня та за допомогою рекурентного перетворення, що реалізується, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками. Вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції модульного піднесення за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m буде послідовність b0 b1 b2 K bi K bm-1 , i = 0 , (m - 1), де bi - молодший біт числа xi , xi+1 = f (xi + L(y i )) = ( xi + L(y i ))e modn . Задача вираховування функції f (x )-1 , яка є зворотною до функції модульного піднесення до ступеня f (x ) = x e mod n , тобто вирахування деякого значення ( xi + L(y i ) за відомим значенням xi +1 є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування, щодо вирішення якої на сьогоднішній день невідомо ефективних алгоритмів вираховування дискретних логарифмів великих чисел. Тому цей спосіб формування послідовностей пссвдовипадкових чисел є криптографічно стійким. Додатково введене рекурентне перетворення L(y ) , що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, дозволяє формувати послідовності псевдовипадкових чисел максимального періоду. Запропонований спосіб може бути реалізовано у вигляді пристрою, схема електрична структурна якого зображена на Фіг. Таким чином, за рахунок додаткового введення рекурентних перетворень, що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, вдається формувати послідовності псевдовипадкових чисел максимального періоду, що підвищує ефективність та розширює можливості практичного використання. Джерела інформації: 1. Shamir, A. On the generation of cryptographically strong pseudorandom sequences. // AC M Transactions on Computer Systems, vol.1., 1983, pp.38-34. 2. Blum, M., Micali, S. How to generate cryptographically strong sequences of pseudorandom bits. // SIAM Journal on Computing, vol.13, 1984, pp.850-864. 5 Комп’ютерна в ерстка О. Рябко 38402 6 Підписне Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601