Розглядається асиметрична шіфрсістема на булевих функціях з функціональним ключем. Пропонуються атаки з відомим відкритим текстом для двох підмножин ключових параметрів.

Анотація наукової статті з математики, автор наукової роботи - Боровкова Ірина В'ячеславівна, Панкратова Ірина Анатоліївна


Cryptanalysis of the acbf encryption system

The ACBF encryption system with a functional key is considered. A public key in the cryptosystem is a vectorial Boolean function f in n variables obtained by permutation and negation operations on variables and coordinate functions of a bijective vectorial Boolean function g, that is, f (x) = n2 (g ° "2 (n1 (xCT1))), n1, n2? Sn and а1, а2? Fn are key parameters. A private key is fi. For two subsets of key parameters, namely for {n1} and {n1, n2}, attacks with known plaintexts are proposed.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика. додаток


    Наукова стаття на тему 'криптоаналіз ШІФРСІСТЕМИ ACBF'

    Текст наукової роботи на тему «Криптоаналіз ШІФРСІСТЕМИ ACBF»

    ?допустимого набору [avls] (i, ..., j), відповідного [avl, avp] (i, ..., j) з збереженого набору, то набір [avl, avp] (i, ..., j) позначається як неприпустимий і обчислення повертаються до другого етапу для уточнення мінімуму.

    Метод 2. У другому методі оцінюється знизу число активних S-блоків на чотирьох тактах. Використано властивості перетворень L3, S3, P, закладені при проектуванні Bash-f [3]. Особливу важливість має наступний факт: якщо на виході L3 отримана вертикальна площину з малим числом активних ліній, то на вхід була подана площину з великим числом активних ліній. Базові властивості перетворень виступають в ролі аксіом, з яких аналітично виводяться теореми - нові властивості, що мають відношення до оцінювання.

    Потім проглядаються допустимі конфігурації, що представляють собою пари «число активних вертикальних ліній на входах L3 на другому такті, проекція [avp] (2)». Для кожної конфігурації оцінюється знизу проекція [avl] (1) (як ніби то від другого такту ми повертаємося до першого) і проекції [avl] (3, 4). В результаті отримана оцінка

    SA (4) = min ([avl] (1) + [avl] (2) + [avl] (3) + [avl] (4)) ^ 31,

    звідки sa (24) ^ 6sa (4) ^ 186.

    ЛІТЕРАТУРА

    1. Daemen J. and Van Assche G. Differential propagation analysis of Keccak // FSE'2012. LNCS. 2012. V. 7549. P. 422-441.

    2. Mella S., Daemen J., and Van Assche G. New techniques for trail bounds and application to differential trails in Keccak // IACR Trans. Symmetric Cryptology. 2017. No. 1. P. 329-357.

    3. Agievich S., Marchuk V., Maslau A., and Semenov V. Bash-f: another LRX sponge function // Математичні питання криптографії. 2017. Т. 8. №2. С. 7-28.

    519.7 DOI 10.17223 / 2226308X / 12/28

    Криптоаналіз ШІФРСІСТЕМИ ACBF1

    І. В. Боровкова, І. А. Панкратова

    Розглядається асиметрична шіфрсістема на булевих функціях з функціональним ключем. Пропонуються атаки з відомим відкритим текстом для двох підмножин ключових параметрів.

    Ключові слова: криптосистема ACBF, векторні булеві функції, асиметрична криптосистема, криптоаналіз.

    Розглядається шіфрсістема ACBF (Asymmetric Cryptosystem on Boolean Functions) [1]. Вона будується на основі двох операцій - перестановки і заперечення, - застосовуються до змінних і координатами оборотної векторної булевої функції. Відкритий ключ f (x) виходить за формулою f (x) = n2 (ga2 (n \ (xai))), де g: F ^ ^ - биективное векторна булева функція; функції g і g-1 відомі; а \, а 2 Е F ^ - операції заперечення; п1, п2 Е - операції перестановки. Закритий ключ - функція f-1.

    Ключовими параметрами криптосистеми є елементи будь-якого непорожньої підмножини J З {п1, п2, а1, а2}; операції з {п1, п2, а 2} \ J вважаються тотожними. Таким чином, існує 15 різних підмножин ключових параметрів.

    1 Робота підтримана грантом РФФД, проект №17-01-00354.

    Метою роботи є знаходження ключових параметрів за відомими парам відкритих текстів і відповідних шифртекст. Розглянуто два базових випадку: 3 = {^ 1} і 3 = {п ^ п2}. Для кожного з них розроблена атака.

    1. Випадок 3 = {п1}

    Нехай х, у Е РП - пара «відкритий текст - відповідний шифртекст». За визначенням криптосистеми АСБЕ отримуємо

    у = / (х) = # (п1 (х)); п1 (х) = # -1 (у).

    Твердження 1. Нехай Р - матриця розміру т х п з рядками відкритих текстів Р1, ..., Рт в РП, з безліччю Q векторів-стовпців в Рт, розбитим на класи

    ... , Qfc однакових, 1 ^ до ^ п, так, що | Qj • | = Г3-,] = 1, ..., к, г1 + ... + гк = п. Нехай також Сг = ^ (п1 (Р ^)) для деякої перестановки п1 € §га, г = 1, .. ., т. Тоді кількість різних перестановок п Е §га, для яких Сг = д (п (Рг)), г = 1, ..., т, одно

    П г4!

    г = 1

    I

    Таким чином, перестановка п1 визначається однозначно, якщо і тільки якщо всі стовпці в матриці Р різні. Експериментально встановлено, що для цього в середньому знадобиться 21с ^ 2 п відкритих текстів при їх випадковому равновероятном виборі.

    Слідство 1. Якщо проводиться атака з вибраним відкритим текстом, то можна підібрати такі Рг, що при розгляді т = | ~ 1og2 п] пар (Рг, Сг) шукана перестановка п1 знайдеться однозначно.

    Нехай є т пар (Рг, Сг). Розглянемо матрицю Р 'з рядками д-1 (Сг) = п1 (Р ^), г = 1, ..., т; зауважимо, що Р 'містить ті ж вектор-стовпці, що і матриця Р, тільки в іншому порядку - визначеному перестановкою п1. Алгоритм 1 знаходить всі можливі ключі шіфрсістеми АСБЕ.

    Алгоритм 1. Знаходження всіх можливих ключів в разі 3 = {п1} Вхід: (Рг, Сг), г = 1, ..., т.

    Вихід: все п1 € §га, такі, що Сг = г = 1, ..., т.

    / РЛ А-1 (С1) \

    1: Побудуємо матриці Р

    Р2

    Р '

    рт

    9 ~ 1 (С2)

    \ 0 1 (Ст)

    2: Для кожного стовпця 5 матриці Р запам'ятовуємо номера стовпців кг1,

    них 5. Для матриці Р 'робимо те ж саме. 3: Будуємо конструкцію следущего виду:

    . , КМДА, рав-

    кг до

    31

    Г1

    до кг

    Тут кожна дужка відповідає одному значенню стовпчика в; у верхньому рядку знаходяться позиції, на яких стовпець в зустрічається в Р; в нижній - в Р '. 4: Переставляючи елементи нижнього рядка в кожній дужці усіма способами, отримаємо всілякі шукані перестановки п1.

    2. Випадок 3 = {п1, п2}

    За визначенням отримуємо

    У = / (ж) = п2 (# (п1 (х))).

    Твердження 2. Нехай є т пар відкритих текстів і шифртекст виду (Рг, Сг), г = 1, ..., т. Складемо матриці Р і С з відкритих текстів Рг і шіфртек-стов Сг відповідно:

    Р

    Р1 Р2

    рт

    З

    С1 С2

    ст

    Необхідною умовою єдиності рішення системи рівнянь

    Сг = П2 (^ (п1 (Рг))), г = 1, ..., т, є відсутність однакових стовпців в кожній з матриць Р і С. Пошук всіх рішень системи (1) представлений в алгоритмі 2.

    Алгоритм 2. Знаходження всіх можливих пар перестановок (п1, п2)

    1,

    т.

    Вхід: (Рг, Сг), г = 1, ..., т.

    Вихід: всі пари (п1, п2), такі, що Сг = п2 (^ (п1 (Рг))), г 1: Будуємо матрицю Р 'з Сг.

    2: Серед Рг, г = 1, ..., т, вибираємо такий відкритий текст Р3, який урівноважений або найбільше наближений до врівноваженості у порівнянні з іншими відкритими текстами. Нехай С3 - відповідний шифртекст. 3: Шукаємо усі ж, такі, що |№ (?) = W (P3 •) і -№ (д (ж)) = w (C3 •), де |№ (?) -Вага вектора ж. 4: Для кожного такого ж за алгоритмом 1 з вихідними даними (Р3-, ж), т = 1

    знаходимо все перестановки п1 з властивістю д-1 (ж) = п1 (Р3-). 5: Для всіх знайдених перестановок п1: 6: будуємо матрицю

    / $ (П1 (Р1)) \

    Р

    У (П1 (Р2))

    \ ^ (П1 (Рт)) у /

    7:

    Якщо кожен стовпець матриці Р зустрічається в ній стільки ж раз, скільки і в Р ', то, виконуючи кроки 2-4 алгоритму 1, знаходимо все перестановки п2 і пари (п1, п2) записуємо у відповідь.

    Алгоритми 1 і 2 реалізовані програмно, проведена серія експериментів при значеннях п від 3 до 29, кількість вхідних текстів, достатніх для однозначного визначення ключа, і табличному завданні функції д. Алгоритм 1 при всіх п знаходить перестановку п1 за частки секунди; алгоритм 2 працює набагато довше і час його роботи залежить не тільки від п, але і від кількості таких ж, що w (ж) = w (P3 •) і w (g (g)) = w (C3 •). Ця кількість зростає експоненціально з ростом п і, наприклад, для п = 15 в середньому дорівнює 664.

    ЛІТЕРАТУРА

    1. Agibalov G. P. and Pankratova I. A. Asymmetric cryptosystems on Boolean functions // Прикладна дискретна математика. 2018. №40. С. 23-33.

    УДК 519.151, 519.725, 519.165 DOI 10.17223 / 2226308X / 12/29

    Блокування лінійних різноманіття і ТРІЙКИ Штейнер

    М. В. Ведунова, А. О. Ігнатова, К. Л. Геут

    Розглядаються завдання блокування трійок Штейнера, застосовні в схемах поділу секрету. Описано метод побудови блокуючого безлічі мінімальної і максимальної потужності. Для додаткового безлічі знайдений метод оцінки мінімальної потужності доповнення як в лінійних, так і в нелінійних системах трійок Штейнера. Для відповідних матроідов реалізовані ідеальні схеми поділу секрету на основі інтерполяційних многочленів з нульовим слідом. У нелінійної системі трійок Штейнера з 13 елементами знайдені максимальні і мінімальні потужності доповнення блокуючого безлічі.

    Ключові слова: системи трійок Штейнера, схеми поділу секрету, що блокують безлічі.

    У другому раунді міжнародної інтернет-олімпіади з криптографії NSU-CRYPTO-2015 [1] було запропоновано завдання на спеціальний приз програмного комітету «A secret sharing», в 2016 та 2017 років рр. відзначена як все ще не вирішена [2, 3]. Вирішення цього завдання розглядається з точки зору блокування двовимірних афінних многовидів над полем GF (2). Тут під завданням блокування сімейства S підмножин T безлічі E розуміється завдання побудови такого мінімального щодо включення підмножини M, що будь-яка підмножина T з сімейства S має непорожнє перетин з M. Кожне таке підмножина M називається блокуючим безліччю сімейства S, а підмножина L = E \ M - доповненням блокуючого безлічі. Завдання блокування трійок Штейнера може трактуватися як допоміжна при вирішенні вихідної завдання NSUCRYPTO, оскільки кожне таке різноманіття є зрушенням однозначно певного двовимірного лінійного різноманіття, відповідного лінійної трійці Штейнера [4]. Проблемі вложімості довільної системи трійок Штейнера в досконалий двійкового коду присвячена робота [5]. Проблемі реалізації зв'язку блок-схем з сімейством трійок Штейнера, де однорідний Матро-ід, когіперплоскості якого - це трійки Штейнера, відповідає ідеальній схемі поділу секрету, присвячена робота [6]. Лінійні системи трійок Штейнера Sn - системи з v = 2n - 1 елементами - ненульовими бітовими рядками довжини n, n ^ 3, в яких бінарна операція квазігруппи Штейнера є побітове додавання по модулю два. Для матроідов лінійних трійок Штейнера нижче побудовані відповідні їм схеми поділу секрету [7, 8], а також розглянуті методи побудови блокуючих множин мінімальної і максимальної потужності.

    Твердження 1. Потужність l доповнення L блокуючого безлічі задовольняє нерівності l (l + 1) / 2 ^ v.

    Використовуючи таку нерівність, отримаємо, що для нелінійної трійки Штейнера при v = 13 мінімальна потужність доповнення l = 5, а для v = 31 не може бути менше восьми.


    Ключові слова: криптосистема ACBF /ВЕКТОРНІ булевих функцій /Асиметрична криптосистема /криптоаналіз /CRYPTOSYSTEM ACBF /VECTORIAL BOOLEAN FUNCTIONS /ASYMMETRIC CRYPTOSYSTEM /CRYPTANALYSIS

    Завантажити оригінал статті:

    Завантажити