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

Спосіб формування послідовностей псевдовипадкових чисел, який полягає у тому, що ключову послідовність подають у вигляді вектора, який 3 51869 Недоліком способу – найближчого аналогу є те, що для забезпечення необхідної стійкості використовується велика довжина ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно виконувати над дуже великими числами що значно ускладнює побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. В основу корисної моделі поставлена задача створити спосіб формування послідовностей псевдовипадкових чисел який, за рахунок застосування пристроїв скалярного множення точок еліптичної кривої при порівняних показниках стійкості дозволив би значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно було б виконувати над значно меншими числами що значно спрощує побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Поставлена задача вирішується за рахунок додаткового введення пристроїв скалярного множення дивізорів гіпереліптичної кривої які дозволяють при порівняних показниках стійкості значно скоротити довжину ключової послідовності та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Технічний результат, який може бути отриманий при здійснені корисної моделі полягає в отриманні можливості значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Сутність запропонованого способу формування послідовностей псевдовипадкових чисел полягає в тому, що ключова послідовність подається у вигляді вектору х0, який ініціалізує початкове значення аргументу функції скалярного добутку дивізору гіпереліптичної кривої f(x)=x D, де D - приведений дивізор гіпереліптичної кривої (загальносистемний параметр), який належить групі дивізорів гіпереліптичної кривої Сn порядку n. У якості D обирається елемент групи дивізорів гіпереліптичної кривої з якомога більшим порядком. Наступне значення xi аргументу функції f(x) обчислюється за допомогою пристроїв скалярного множення xi-1 на базовий дивізор D Qi=xi-1 D та перетворення (D) отриманого дивізора Qi, Qi Сn за допомогою відповідних пристроїв (наприклад, xi може дорівнюватися значенню координат точок, що належать дивізору Qi). Комп’ютерна верстка А. Крижанівський 4 Вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції скалярного добутку за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m буде послідовність _________ b0 b1 b2 ... bi ... bm-1, i 0, (m 1) , де bi - молодший біт числа xi, xi f x xi 1 D Задача вираховування функції f(х)-1, яка є зворотною до функції скалярного добутку дивізору гіпереліптичної кривої f(x)=х D, тобто вирахування деякого значення хi-1 за відомим значенням xi, є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування в групі дивізорів гіпереліптичної кривої. Щодо її вирішення на сьогоднішній день невідомо ефективних алгоритмів вираховування дискретних логарифмів для базових дивізорів великого порядку. Тому цей спосіб формування послідовностей псевдовипадкових чисел є криптографічно стійким. При однаковій довжині ключової послідовності задача дискретного логарифмування в групі дивізорів гіпереліптичної кривої значно складніша за теоретико-складну задачу факторизації або класичну задачу дискретного логарифмування. Тому додатково введене у запропонованому способі перетворення у групі дивізорів гіпереліптичної кривої, що реалізуються за допомогою пристроїв скалярного множення дивізорів гіпереліптичної кривої, при порівняних показниках стійкості дозволяє значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно виконувати над значно меншими числами що значно спрощує побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Таким чином, за рахунок додаткового введення перетворень у групі дивізорів гіпереліптичної кривої, що реалізуються за допомогою пристроїв скалярного множення дивізорів гіпереліптичної кривої, вдається значно скоротити довжину ключової послідовності та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Джерела інформації 1. Blum, М., Micali, S. How to generate cryptographically strong sequences of pseudorandom bits. // SIAM Journal on Computing, vol. 13, 1984, pp. 850 -864. 2. Blum, L., Blum, M, Shub, M. A simple unpredictable pseudorandom number generator. // SIAM Journal on Computing, vol. 15, 1986, pp. 364 383. Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601