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

Реферат: Спосіб формування послідовностей псевдовипадкових чисел полягає у тому, що ключова послідовність подається у вигляді вектора х0, який ініціалізує початкове значення аргументу функції скалярного добутку точки еліптичної кривої, а вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення цієї функції за допомогою відповідних пристроїв. Додатково введено рекурентні перетворення із формуванням послідовності псевдовипадкових чисел максимального періоду. UA 78038 U (12) UA 78038 U UA 78038 U 5 10 15 20 Корисна модель належить до криптографічного захисту інформації і може бути використана в засобах шифрування та генераторах послідовностей псевдовипадкових чисел у системах обробки інформації для розширення їх можливостей. Відомий "Спосіб формування послідовностей псевдовипадкових чисел" [1], який ґрунтується на тому, що ключова послідовність подається у вигляді вектору, який ініціалізує початкове значення аргументу функції модульного зведення у ступінь. Наступне значення аргументу функції обраховується за допомогою пристроїв модульного зведення у ступінь, а вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції модульного зведення за допомогою відповідних пристроїв. Недоліком відомого способу є те, що він не дозволяє формувати послідовності псевдовипадкових чисел максимального періоду, що суттєво зменшує його ефективність та обмежує можливості щодо практичного використання. Відомий також "Спосіб формування послідовностей псевдовипадкових чисел" [2], який ґрунтується на тому, що ключова послідовність подається у вигляді вектору x 0 , який ініціалізує початкове значення аргументу функції f ( x )  x 2 модульного зведення у квадрат. Як модуль n вибирається добуток великих простих чисел р і q, які тотожні трьом за модулем чотири, тобто: p  3 mod 4 , q  3 mod 4 , n  p  q (ціле число Блюма). Наступне значення аргументу функції обраховується за допомогою пристроїв модульного зведення у квадрат, а вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції модульного зведення за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m є послідовність: b 0 b1 b 2 ... bi ... bm1, i  0,(m  1) , де bi - молодший біт числа xi , 25 30 35 40 45 2 x i  f ( x i1 )  x i1 mod n . Задача вираховування примітивних квадратних коренів за модулем числа n обчислювально еквівалентна задачі розкладення цього числа на множники, тобто важкорозв'язуваної теоретико-складної задачі факторизації. Недоліком відомого способу є те, що він не дозволяє формувати послідовності псевдовипадкових чисел максимального періоду, що суттєво зменшує його ефективність та обмежує можливості щодо практичного використання. Найбільш близьким до запропонованого технічним рішенням, вибраним як прототип, є спосіб формування послідовностей псевдовипадкових чисел [3], який ґрунтується на тому, що ключова послідовність подається у вигляді вектору x 0 , який ініціалізує початкове значення аргументу функції скалярного добутку точки еліптичної кривої: f ( x)  x  P , де P - базова точка еліптичної кривої (загальносистемний параметр), яка належить групі точок EC n порядку n (як Р вибирається елемент групи EC n з якомога більшим порядком). Кожне наступне значення xi обчислюється за допомогою пристрою скалярного множення xi1 на базову точку P : Qi  x i1  P та перетворення (Q) координат отриманої точки Q i , Qi  EC n , яке виконується за допомогою відповідного пристрою (наприклад, xi може дорівнюватися значенню однієї з координат точки Q i ), тобто xi  (Qi )  (f ( xi1))  ((xi1)  P) . Вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції скалярного добутку за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m є послідовність: b 0 b1 b 2 ... bi ... bm1, i  0,(m  1) , де bi - молодший біт числа xi . 50 Задача вираховування функції f ( x )1 , яка є зворотною до функції скалярного добутку точки еліптичної кривої f ( x)  x  P , тобто вирахування деякого значення xi1 за відомим значенням xi , є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування в групі точок еліптичної кривої. 1 UA 78038 U 5 10 15 20 25 30 35 40 Недоліком способу-прототипу є те, що він не дозволяє формувати послідовності псевдовипадкових чисел максимального періоду, що суттєво зменшує його ефективність та обмежує можливості щодо практичного використання. В основу корисної моделі поставлена задача створити спосіб формування послідовностей псевдовипадкових чисел, який, за рахунок додаткового введення рекурентного перетворення із формуванням послідовності максимального періоду, що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, у сукупності із використанням перетворень у групі точок еліптичної кривої, дозволить формувати послідовності псевдовипадкових чисел максимального періоду, що підвищить його ефективність та розширить можливості щодо практичного використання. Поставлена задача вирішується за рахунок додаткового введення рекурентних перетворень із формуванням послідовності максимального періоду, що реалізуються, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, які у сукупності із використанням перетворень у групі точок еліптичної кривої, дозволяють формувати послідовності псевдовипадкових чисел максимального періоду. Технічний результат, який може бути отриманий при здійснені корисної моделі, полягає у формуванні послідовності псевдовипадкових чисел максимального періоду із використанням перетворень у групі точок еліптичної кривої, що підвищує ефективність та розширює його можливості. Суть запропонованого способу формування послідовностей псевдовипадкових чисел полягає у тому, що ключова послідовність подається у вигляді вектору x 0 , який ініціалізує початкове значення рекурентного перетворення L( x ) , та початкове значення аргументу функції скалярного добутку точки еліптичної кривої: f ( x)  x  P , де P - базова точка еліптичної кривої (загальносистемний параметр), яка належить групі точок EC n порядку n (як P обирається елемент групи EC n з якомога більшим порядком). Рекурентне перетворення L( x ) вибирається таким чином, щоб отримана послідовність чисел y i  L( x i ) мала максимальний період. Рекурентне перетворення L( x ) може бути реалізоване, наприклад, за допомогою лінійних рекурентних регістрів зі зворотними зв'язками [4]. Кожне наступне значення xi обчислюється за допомогою пристрою додавання значень xi1 i yi1  L( xi1) , пристрою скалярного множення значення ( x i1  y i1 ) на базову точку Р: Qi  ( xi1  yi1)  P та перетворення (Q) координат отриманої точки Q i , Qi  EC n , яке виконується за допомогою відповідного пристрою (наприклад, xi може дорівнюватися значенню однієї з координат точки Q i ), тобто xi  (Qi )  (f ( xi1  yi1))  ((xi1  L( xi1))  P) Вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції скалярного добутку за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m є послідовність b 0 b1 b 2 ... bi ... bm1, i  0,(m  1) , де bi - молодший біт числа xi . Задача вираховування функції f ( x )1 , яка є зворотною до функції скалярного добутку точки еліптичної кривої f ( x)  x  P , тобто вирахування деякого значення ( x i1  y i1 ) за відомим 45 50 значенням xi є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування в групі точок еліптичної кривої. Таким чином, за рахунок додаткового введення рекурентного перетворення із формуванням послідовності максимального періоду, що реалізуються за допомогою лінійних рекурентних регістрів зі зворотними зв'язками, сформовані послідовності псевдовипадкових чисел максимального періоду, що підвищує ефективність та розширює можливості практичного використання. Джерела інформації: 1. Blum, М., Micali, S. How to generate cryptographically strong sequences of pseudo-random bits. // SIAM Journal on Computing. - Vol. 13. - 1984. - P. 850-864. 2 UA 78038 U 5 2. Blum, L., Blum, M., Shub, M. A simple unpredictable pseudorandom number generator. // SIAM Journal on Computing. - Vol. 15. - 1986. - P. 364-383. 3. Патент на корисну модель № 53792, Україна, МПК G09C 1/00. Спосіб формування послідовностей псевдовипадкових чисел. / О.О. Кузнецов, С.П. Евсеев, В.Ю. Ковтун, Ю.М. Рябуха та ін. - № u 200913201; заявл. 18.12.2009; опубл. 25.10.2010; бюл. № 20. - 4 с. 4. Alfred J. Menezes, Paul С. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography - CRC Press, -1997. - 794 p. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 15 Спосіб формування послідовностей псевдовипадкових чисел, який полягає у тому, що ключова послідовність подається у вигляді вектора х0, який ініціалізує початкове значення аргументу функції скалярного добутку точки еліптичної кривої, а вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення цієї функції за допомогою відповідних пристроїв, який відрізняється тим, що додатково введено рекурентні перетворення із формуванням послідовності псевдовипадкових чисел максимального періоду. Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3