Спосіб побудови високонелінійних збалансованих булевих функцій з контрольованим алгебраїчним степенем

Спосіб побудови високонелінійних збалансованих булевих функцій з контрольованим алгебраїчним степенем, заснований на виконанні конкатенації булевих функцій, отриманих шляхом модифікації бент функцій, результатом якої є криптографічно стійка функція, який відрізняється тим, що процедуру конкатенації трьох булевих функцій над V2k+1, де к > 1 , виконують згідно з виразом д(хі, х 2 , , х 2 к + і) = xi(fi(x 2 , ©f2(x2, ,x 2 k + 1 ) © h ( x 2 , , х 2 к + і) ©(х2, , x2k+i)©h(x2, , х 2 к + і), де fi(x 2 , , x 2 k + i ) , f2(x2, , х 2 к + і) - бент функції над V 2k , h (x2, , x 2 k + i) - неконстантна афінна функція над V 2k , g(xi, x2, , x 2 k + i) - отримана високонелінійна збалансована булева функція над V 2k +i a процедуру конкатенації трьох булевих функцій над V 2k , де k > 1, виконують згідно з виразом X2k) = Xi(fi(X3, , x2k) 6 , x2k) © h (хз, , x2k)) £ ©X 2 (fi(X 3 , , x2k) ©f 2 (x 3 , , x2k) © h (хз, , x2k)) ©f 2 (x 3 , , x2k) £ ©h(x 3 , ,x2k), 9(хі, х 2 , ©f2(x3, де fi(x3, , x2k), f2(x3, , x2k) - бент функції над V 2 k 2 , h (хз, , x2k) -неконстантна афінна функція над V2k 2, g(xi, х2, хз, , x2k) - отримана високонелінійна збалансована булева функція над V2k © ,x2k+1)) © О Запропонований винахід відноситься до автоматики й обчислювальної техніки і може бути використаний, зокрема, у системах криптографічного захисту інформації Відомий спосіб побудови високонелінійних збалансованих булевих функцій (див В Preneel, R Govaerts, and J Vandewalle, "Boolean functions satisfying higher order propagation criteria" in Lecture Notes in Computer Science 547, Advances in Cryplology Proc Eurocrypt'91, 1991, pp 141-152 Berlin Sprmger-Verlag), заснований на конкатенації булевих функцій Для виконання побудови використовується булева функція f над заданим векторним простором Vn При цьому побудова складається з наступних двох етапів вибору нелінійної функції f, яка має нульові значення в спектрі Уолша, результатом якого є проміжна булева функція, додавання потрібної лінійної функції h над Vn, ре зультатом якого є високонелінійна збалансована булева функція Алгебраїчний степінь отриманої функції дорівнює алгебраїчному степіню початкової функції f Наведений аналог потребує багато часу для побудови криптографічно стійких булевих функцій за рахунок необхідності знаходження нелінійних функцій з нульовими значеннями в їхньому спектрі Уолшата пошуку необхідної лінійної функції h, яка може бути знайдена шляхом повного перебору над всіма ЛІНІЙНИМИ функціями над Vn Найбільш близьким по сукупності ознак до запропонованого способу є спосіб побудови високонелінійних збалансованих булевих функцій (див J Seberry, X -М Zhang and Y Zheng, "Nonhneanty and Propagation Characteristics of Balanced Boolean Functions", Information and Computation, Vol 119, No 1, pp 1-13, 1995), заснований на конкатенації о (О 60017 булевих функцій Побудова складається з виконання конкатенації булевих функцій, отриманих шляхом модифікації бент функцій, результатом якої є високонелінійна збалансована булева функція Процедура виконання конкатенації двох булевих функцій над V2k+1, де к>1, отриманих шляхом модифікації бент функції, описується наступним виразом g(Xi,X2, ,X2k+i)=(1®Xi)fi(X2l ,X2k+i)©Xif2(X2, ,X2 k+i), ДЄ fi(X 2 , , X 2 k + i ) , f2(X 2 , ,X 2 k+i) " бЄНТ ф у н к ц і ї НЭД V2k, g(xi,x2, ,x2k+i) - отримана високонелінійна збалансована булева функція над V2k+1 Процедура виконання конкатенації чотирьох булевих функцій над V2k де к>1, отриманих шляхом модифікації бент функцій, описується наступним виразом g(x,y)=e o D a (y)f,(x), де f,(x) - бент функції над V 2k 2, У=(Уі,У2), х=(хі, ,х2к2) та а,, є вектором над V2, чиє цілочисельне представлення дорівнює і, д(у, х) - отримана високонелінійна збалансована булева функція над V2k Функція, обчислена над V2k+1 є збалансованою, має нелінійність Ng>22k-2k та алгебраїчний степінь deg(g) = max{deg(f|(x))} + 1 Функція, обчислена над V є збалансованою, має нелінійність Ng>22k 1 -2 k та алгебраїчний степінь deg(g) = max{deg(f,(x))} + 1 При реалізації технічного рішення, прийнятого за прототип, потрібно багато часу для побудови криптографічне стійких булевих функцій над V2k за рахунок необхідності побудови чотирьох бент функцій з необхідними властивостями, крім того, максимальний алгебраїчний степінь deg(g, x,), що дорівнює алгебраїчному степеню отриманих функцій deg(g), мають лише ті координати, що знаходяться в найдовшому доданку функцій, представлених в алгебраїчній нормальній формі, решта координат має менший алгебраїчний степінь, що знижує криптографічну СТІЙКІСТЬ ДО атаки криптоаналізу методом диференціалів вищіх порядків В основу винаходу поставлена задача створити спосіб побудови високонелінійних збалансованих булевих функцій з контролюємим алгебраїчним степенем, який дозволив би будувати високонелінійні збалансовані булеві функції з низькими часовими витратами та контролюємим алгебраїчним степенем кожної координати завдяки виконанню процедури конкатенації булевих функцій за допомогою нових виразів Такий технічний результат може бути отриманий, якщо у способі побудови високонелінійних збалансованих булевих функцій з контролюємим алгебраїчним степенем, заснованому на виконанні конкатенації булевих функцій, отриманих шляхом модифікації бент функцій, результатом якої є криптографічне стійка функція, згідно з винаходом, процедуру конкатенації трьох булевих функцій над V2k+1 де к>1, виконують згідно з виразом g(Xi,X2, ,X2k+i)=Xi(fi(X2l ,X2k+i) ©f2(X2, ,X2k+i), ©h(X2, ,X2k+i), ©f2(X2, ,X2k+i), ©h(X2, ,X2k+i), ДЄ fi(X 2 , ,X2k+i), f2(X2, ДЄ fi(X 3 , ,X 2 k ), f2(X 3 , ,X 2 k+i), - бЄНТ фуНКЦІІ над V2k, h(x2, ,X2k+i) - неконстантна афінна функція над V2k, g(xi,X2, ,X2k+i) - отримана високонелінійна збалансована булева функція над V2k+1 а процедуру конкатенації трьох булевих функцій над V2k де к>1, виконують згідно з виразом g(Xi,X2, ,X2k)=Xi(fi(X3, ,X2k) ©f2(X3, ,X2k), ©h(x3, ,x2k), ©x 2 (fi(x 3 , ,x2k), ®f2(x3, ,x2k), ©h(x3, ,x2k), ©f2(x3, ,x2k), ©h(x3, ,x2k), ,X 2k ) - бЄНТ фуНКЦІІ НЭД V2k2, h(x3, ,X2k) неконстантна афінна функція над V2k2, g(xi,X2,x3, ,X2k) - отримана високонелінійна збалансована булева функція над \^k Функція g над V2k+1 є збалансованою функці2k k єю, має нелінійність Ng>2 -2 Ta алгебраїчний степінь кожної координати deg(g) = (deg(fi(x)) = deg(f2(x))) + 1 = deg(g, x,), і = 1, , 2k + 1 Функція g над V2k є збалансованою функцією, має нелінійність Ng > 2 U " 2 - 2* та алгебраїчний степінь кожної координати deg(g) = (deg(fi(x)) = deg(f2(x))) + 1 = deg(g, x,), i = 1, , 2k Таким чином, виконання процедури конкатенації булевих функцій за допомогою запропонованих виразів дозволяє скоротити час, потрібний для побудови високонелінійних збалансованих булевих функцій над V2k в 2 рази за рахунок побудови лише двох бент функцій, та підвищити СТІЙКІСТЬ ДО атаки криптоаналізу методом диференціалів вищіх порядків за рахунок контролю алгебраїчного степіня кожної координати Спосіб побудови високонелінійних збалансованих булевих функцій над \^к+і з контролюємим алгебраїчним степенем кожної координати може бути реалізований таким чином Виконується побудова бент функції fi(x2, ,X2k+i), над V2k таким чином, що обирається довільна квадратична бент функція з додаванням нелінійного доданку виду Х2 Х Х к та рахується КІЛЬКІСТЬ "0" та " 1 " в її ВИХІДНІЙ 4 2 ПОСЛІДОВНОСТІ Виконується побудова бент функції h(x2, ,X2k+i) над V2k таким чином, що обирається довільна квадратична бент функція з додаванням нелінійного доданку виду х3 xs X2k Далі випадково обирається неконстантна афінна функція h(x2, ,X2k+i), над V2k та рахується КІЛЬКІСТЬ "0" та " 1 " в ВИХІДНІЙ ПОСЛІДОВНОСТІ конкатенації функцій f2®h Якщо КІЛЬКІСТЬ "0" та " 1 " в ВИХІДНІЙ ПОСЛІДОВНОСТІ fi дорівнює КІЛЬКОСТІ "0" та " 1 " в ВИХІДНІЙ ПО СЛІДОВНОСТІ f2®h, то функція h комплементується одиницею h = h S 1, інакше - не комплементується Після визначення fi, f2 та h виконується застосування процедури побудови високонелінійних збалансованих булевих функцій над \^к+і згідно з виразом g(Xi,X 2 , Фп(Х 2 , ,X2k+i)=Xi(fi(X 2 l ,Х2к+і), ©f2(X 2 , ,Х 2 к+і) ,X 2 k+i), ®h(X 2 , ©f2(X 2 , ,X2k+i), ,X2k+i), Результатом застосування є функція д з високими криптографічними показниками СТІЙКОСТІ Над V2k побудова високонелінійних збалансованих булевих функцій з контролюємим алгебраїчним степенем кожної координати може бути реалізована таким чином Виконується побудова бент функції fi(x3, ,X2k) над V2k і таким чином, що обирається довільна квадратична бент функція з додаванням нелінійного доданку виду х3 xs X2k і та рахується КІЛЬКІСТЬ "0" та " 1 " в її ВИХІДНІЙ ПОСЛІДОВНОСТІ ВИКО 60017 нується побудова бент функції f2(x3, ,X2k) над \^k 1 таким чином, що обирається довільна квадратична бент функція з додаванням нелінійного доданку виду Х4 хє Х2к Далі виконується побудова випадкової неконстантної афінної функції п(хз, ,Х2к) над інакше - не комплементується Після визначення fi, f2 та h виконується застосування процедури побудови високонелінійних збалансованих булевих функцій над \^к згідно з виразом V2k і та рахується КІЛЬКІСТЬ "0" та " 1 " в ВИХІДНІЙ ПО Фп(Х 3 , ,Х 2 к ), СЛІДОВНОСТІ конкатенації функцій f2 Ф h Якщо КІЛЬ Фп(Х 3 , ,Х 2 к ), ®f2(X 3 , КІСТЬ "0" та " 1 " в ВИХІДНІЙ ПОСЛІДОВНОСТІ fi дорівнює Результатом застосування є функція д з високими криптографічними показниками СТІЙКОСТІ КІЛЬКОСТІ "0" та " 1 " в ВИХІДНІЙ ПОСЛІДОВНОСТІ f2 Ф h то g(Xi,X 2 , ,X 2 k)=Xi(fi(X 3 , ®X2(fi(X3, ,Х 2 к ) ,X 2 k ), ,Х 2 к ), Ф п ( Х 3 , ®f2(X 3 , ,X 2 k ), ®f2(X 3 , ,Х 2 к ), ,Х2к), функція h комплементується одиницею h = h Ф 1, Комп'ютерна верстка С Волобуев Підписано до друку 06 10 2003 Тираж39 прим Міністерство освіти і науки України Державний департамент інтелектуальної власності, Львівська площа, 8, м Київ, МСП, 04655, Україна ТОВ "Міжнародний науковий комітет", вул Артема, 77, м Київ, 04050, Україна