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

Спосіб формування послідовностей псевдовипадкових чисел, який полягає у тому, що ключова послідовність подається у вигляді вектору, який 3 53792 Недоліком способу-прототипу є те, що для забезпечення необхідної стійкості використовується велика довжина ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно виконувати над дуже великими числами що значно ускладнює побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. В основу корисної моделі поставлена задача створити спосіб формування послідовностей псевдовипадкових чисел який, за рахунок застосування пристроїв скалярного множення точок еліптичної кривої при порівняних показниках стійкості дозволив би значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно було б виконувати над значно меншими числами що значно спрощує побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Поставлена задача вирішується за рахунок додаткового введення пристроїв скалярного множення точок еліптичної кривої які дозволяють при порівняних показниках стійкості значно скоротити довжину ключової послідовності та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Технічний результат, який може бути отриманий при здійснені корисної моделі полягає в отриманні можливості значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Сутність запропонованого способу формування послідовностей псевдовипадкових чисел полягає в тому, що ключова послідовність подається у вигляді вектору х0, який ініціалізує початкове значення аргументу функції скалярного добутку точки еліптичної кривої f(x) = x P, де Р - базова точка еліптичної кривої (загальносистемний параметр), яка належить групі точок ЕСn порядку n. У якості Р обирається елемент групи точок еліптичної кривої з якомога більшим порядком. Наступне значення хi аргументу функції f(x) обчислюється за допомогою пристроїв скалярного множення хi-1 на базову точку Р Qі= xi-1 Р та перетворення Q координат отриманої точки Qi, Qi ЕCn за допомогою відповідних пристроїв (наприклад, хі може дорівнюватися значенню однієї з координат точки Qi). Вихідні елементи послідовності псевдовипадкових чисел формуються шляхом зчитування значення функції скалярного добутку за допомогою відповідних пристроїв, тобто шуканою послідовністю біт довжини m буде послідовність _________ b0 b1, b2 ... bi ... bm-1, i 0, m 1 , де bi - молодший біт числа xi, xi f x xi 1 . 4 Задача вираховування функції f(х)-1, яка є зворотною до функції скалярного добутку точки еліптичної кривої f(x)=х Р, тобто вирахування деякого значення Xi-1 за відомим значенням xi є важкорозв'язуваною теоретико-складною задачею дискретного логарифмування в групі точок еліптичної кривої. Щодо її вирішення на сьогоднішній день невідомо ефективних алгоритмів вираховування дискретних логарифмів для базових точок великого порядку. Тому цей спосіб формування послідовностей псевдовипадкових чисел є криптографічно стійким. При однаковій довжині ключової послідовності задача дискретного логарифмування в групі точок еліптичної кривої значно складніша за теоретикоскладну задачу факторизації або класичну задачу дискретного логарифмування. Тому додатково введене у запропонованому способі перетворення у групі точок еліптичної кривої, що реалізуються за допомогою пристроїв скалярного множення точок еліптичної кривої, при порівняних показниках стійкості дозволяє значно скоротити довжину ключової послідовності (послідовності, що ініціює початкове значення аргументу функції) а відповідні перетворення потрібно виконувати над значно меншими числами що значно спрощує побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Таким чином, за рахунок додаткового введення перетворень у групі точок еліптичної кривої, що реалізуються за допомогою пристроїв скалярного множення точок еліптичної кривої, вдається значно скоротити довжину ключової послідовності та спростити побудову відповідних пристроїв формування послідовностей псевдовипадкових чисел. Можливість здійснення винаходу підтверджується визначеністю операції скалярного множення для кожної точки, яка належить групі точок ЕСn еліптичної кривої. Якщо Р Сn, х Z+ (тобто х - позитивне ціле), тоді скалярне множення де (+) - операція додавання точок еліптичної кривої, яка виконується за допомогою послідовної дії пристроїв „ДОБУТОК", „ПІДНЕСЕННЯ ДО КВАДРАТУ" та „ДОДАВАННЯ" елементів кінцевого поля, над яким визначено еліптичну криву. На практиці для визначення суми двох точок еліптичної кривої ЕС над кінцевим полем GF(2n) користуються проективними координатами Лопеса-Дахаба [3]. У цьому випадку проективній точці P=(X:Y:Z), Z O, ставиться у відповідність точка з афінними координатами (X/Z, Y/Z2). Еліптична крива ЕС над GF(2n) має вигляд Y2+XYZ=X3Z+aX2Z2+bZ4, де a, b GF(2n) при b 0. Процедура додавання двох точок кривої P3(X3:Y3:Z3)=P1(X1:Y1:Z1)+P2(X2:Y2:Z2) у проективних координатах у випадку P1(X1:Y1:Z1)+P2(X2:Y2:Z2) виконується згідно виразів: X3=A2+B2 (D+a C2)+A D; Y3=Z3 (X3+B2 Y2Z2)+A B (X1Z2 Z3+X3 B2); Z3=D2, де 5 A Y1 Z2 2 53792 2 P1(X1/Z1,Y1/ Z1 ) P2(X2/Z2,Y2/ Z 2 ) 2 процедура додавання (у змішаних координатах) виконується згідно виразів 2 Y2 Z1 В=Х1 Z2+Х2 Z1; С=Z1 Z2; у випадку P1(X1:Y1:Z1)=P2(X2:Y2:Z2) й 2 P1 X1 / Z1, Y1 / Z1 6 2 X3=A +A C+(C+a Z1 ) B ; 2 P2 X2 / Z2, Y2 / Z2 2 де процедура додавання (подвоєння) виконується згідно виразів 4 4 Х3= X1 +b- Z1 ; 4 2 4 Y3 =b Z1 -Z3+X3 (a-Z3+ Y1 +b Z1 ); 2 Z3=(X1-Z1) , у випадку, коли одна з точок подана у проективних координатах, а інша в афінних координатах P1(X1:Y1:Z1), P2(X2:Y2:1), 2 Y3=(X2 Z3+X3) AC+(X3+Y2 Z3) Z3; Z3=С2, A=Y1+Y2 Z2; В=X1+X2 Z1, C=Z1 B. У таблиці 1 наведено кількість пристроїв „ДОБУТОК", „ПІДНЕСЕННЯ ДО КВАДРАТУ" та „ДОДАВАННЯ" елементів поля GF(2n). У таблиці позначено: «^2» - кількість операцій піднесення до квадрату; «*» - кількість операцій добутку; «+» кількість операцій додавання. Таблиця 1 Кількість операцій над елементами двійкового розширеного поля для виконання операцій над точками еліптичної кривої Система координат Загальне додавання ^2 Проективні координати Лопеса-Дахаба * + 6 15 8 Виконання послідовної дії пристроїв „ДОБУТОК", „ПІДНЕСЕННЯ ДО КВАДРАТУ" та „ДОДАВАННЯ" елементів кінцевого поля дозволяє реалізувати обчислення операцій додавання точок еліптичної кривої і, відповідно, операцій скалярного множення. Цим підтверджується можливість здійснення запропонованого винаходу, його практичної реалізації через послідовну дію відповідних пристроїв. Джерела інформації Комп’ютерна верстка А. Крижанівський Загальне додавання (змішані координати) ^2 * + 4 10 8 Подвоєння ^2 * + 6 5 4 1. Blum, М., Micali, S. How to generate cryptographically strong sequences of pseudo-random bits. // SLAM 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. 3. J.Lopez and R. Dahab, Improved algorithms for elliptic curve arithmetic's in Gf(2n), Selected Areas in Cryptography -SAC'98, LNCS 1556, 1999, 201212. Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601