У роботі проведено дослідження методів алгебраїчного криптоанализа. Отримано системи рівнянь для різних розмірів таблиць нелінійних перетворень заміни спрощеного алгоритму шифрування Rijndael, а також виконано рішення однієї з систем методом XL. В ході роботи програмно реалізований алгоритм генерації і рішення системи рівнянь для перетворень заміни. Проведено аналіз отриманих нелінійних систем і виконана оцінка трудомісткості методу XL алгебраїчного криптоанализа для трьох блоків заміни.

Анотація наукової статті з математики, автор наукової роботи - Бабенко Людмила Климентіївна, Маро Катерина Олександрівна


The research of algebraic cryptanalysis method was carried out in this work. Systems of the equations for tables of various sizes of nonlinear transformations of substitution for simplified model of Rijndael algorithm are received, also we solve a one of this systems by a XL method. During this work we produced a program, which has realised a generation and solving of system of equations describing nonlinear transformations of substitution. We analysed a nonlinear systems of equations and calculated a value of complexity of XL method for three blocks of substitution.


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

  • Математика

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


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгебраїчний криптоаналіз спрощеного алгоритму шифрування Rijndael'

    Текст наукової роботи на тему «Алгебраїчний криптоаналіз спрощеного алгоритму шифрування Rijndael»

    ?Розділ III. Методи і засоби криптографії та стеганографії

    УДК 003.26.09

    JI.K. Бабенко, Е.А. Маро

    Алгебраїчних Криптоаналіз СПРОЩЕНОГО АЛГОРИТМА ШИФРУВАННЯ RIJNDAEL *

    У роботі проведено дослідження методів алгебраїчного криптоанализа. Отримано системи рівнянь для різних розмірів таблиць нелінійних перетворень заміни спрощеного алгоритму шифрування Rijndael, а також вико-

    XL. -Вань алгоритм генерації і рішення системи рівнянь для перетворень заміни. Проведено аналіз отриманих нелінійних систем і виконано оцінку Трудоем-XL .

    Алгебраїчний криптоаналіз; XL метод; нелінійні перетворення заміни; линеаризация нелінійних систем; метод виключення Гаусса; кріптографіче-.

    L.K. Babenko, E.A. Maro ALGEBRAIC CRYPTANALYSIS OF SIMPLIFIED RIJNDAEL ALGORITHM

    The research of algebraic cryptanalysis method was carried out in this work. Systems of the equations for tables of various sizes of nonlinear transformations of substitution for simplified model of Rijndael algorithm are received, also we solve a one of this systems by a XL method. During this work we produced a program, which has realised a generation and solving of system of equations describing nonlinear transformations of substitution. We analysed a nonlinear systems of equations and calculated a value of complexity of XL method for three blocks of substitution.

    Algebraic cryptanalysis; XL method; nonlinear transformations of substitution; linearization nonlinear systems; Gauss elimination method; a cryptographic key.

    Криптоаналіз довгий час грунтувався на статистичних підходах. Таким статистичних методів криптоаналізу як лінійний і диференційний для здійснення атаки потрібна велика кількість відкритих текстів і шифр-текстів. Крім того, сучасні алгоритми шифрування розроблялися з урахуванням забезпечення стійкості до подібного роду атакам. актуальність алгебраичен-

    *

    Робота підтримана грантом РФФД № 09-07-00245-а.

    ських методів криптоаналізу базується на можливості злому з їх допомогою алгоритмів шифрування при наявності у криптоаналитика всього однієї пари відкритий текст / шифротекст. Також важливо відзначити, що дані методи застосовні до стійких сучасним шифрів, таким як алгоритми шифрування Rijndael, Serpent.

    У даній роботі проведена розробка і дослідження XL методу алгебраі-.

    ,

    нелінійних перетворень, а саме для S-блоків заміни. Сутність даного методу полягає в отриманні рівнянь, що описують нелінійні перетворень-S- ,

    і отриманням ключа шифрування. Даний метод криптоаналізу відноситься до атак з відомим відкритим текстом, тому в ході роботи використовувалася одна пара відкритий текст / шифротекст. В результаті здійснення атаки криптоаналитик обчислює секретний ключ.

    Алгебраїчні методи криптоаналізу складаються з наступних етапів:

    - складання нелінійної системи рівнянь, яка описує перетворення в S-блоках;

    - .

    Розглянемо докладніше перший етап алгебраїчного криптоанализа. Для шифрів, подібних Rijndael, при складанні рівнянь використовується таблиця S- . , -

    ведення двох змінних. Тоді рівняння, що описують роботу S-блоків, мають вигляд [1]:

    'А..х.х +'в yy + ХУ x.y + '8.х. + 2y.y + V = ^

    ij i j ij i j ij 1 j 11 i i

    де xixj - комбінація вхідних бітів S-блоку; yiyj - комбінація вихідних бітів S-блоку; xiyj - комбінація вхідних і вихідних бітів; xi yi - S-;

    - , 0 1.

    При отриманні рівнянь потрібно розглянути всі можливі комбінації даних одночленним. У разі, коли число біт на вході S-блоків одно s, получа-, , ,

    2s

    t = + 2s + 1 і включає в себе вхідні і вихідні значення S-блоку (2s), всі їхні

    (2s ^ i

    можливі твори I і коефіцієнт Г |. Число всіх можливих комбі-

    2t.

    S- -

    , S- . -

    S- 2s t ,

    . 1. S-

    , -

    дення відповідних елементів.

    1

    S-

    Рівні введення S-блоку Вивід S- S-

    Все віз мож- ні вхід ні зна - ня S-блоку (від 0 до 2s) Xs Xl ys УІ XsXs-l X2X1 ysys-l У2У1 xsys х1у1 T1

    0 0 у середньому 1 1 + 1

    1 + 1 Про 1 + 1

    Для перевірки комбінацій на відповідність таблиці істинності слід здійснити построковую підстановку значень одночленним з таблиці і виконати операцію додавання по модулю 2. Таким чином, для кожної комбінації виконується підстановка і складання для всіх можливих вхідних значень S-блоку (2s раз). Результати підсумовування порівнюються з нулем. Якщо для всіх рядків таблиці істинності рівність справджується, то рівняння, задане даної

    , S- ,

    його слід відібрати для складання шуканої системи. Далі необхідно провести аналіз рівнянь і вибрати для формування системи рівняння, що містять мінімальну кількість нелінійних елементів. Пропонований в роботі метод формування системи буде розкритий нижче на прикладі конкретного S-блоку.

    Другий етап алгебраїчного криптоанализа полягає у вирішенні нелі.

    нелінійних систем булевих рівнянь. Найбільш ефективними, як показує,, -вої системи. У даній роботі досліджено XL метод алгебраїчного .

    XL метод (extended Linearization) запропонований Nicolas Courtois, Alexander Klimov, Jacques Patarin і Adi Shamir в роботі [2].

    Нехай є нелінійна система, що містить m рівнянь і 2s змінних. XL метод базується на збільшенні кожного рівняння 1 .. .m на твори змінних ступеня меншою або рівною D-2. Розглянемо обчислення параметра D алгоритму XL атаки. При множенні вихідних рівнянь системи на

    2s

    одночлени ступеня <(D-2) отримуємо приблизно R |

    D-2

    m нових рівнянні.

    Загальна кількість одночленним, що зустрічаються в цих рівняннях, становить Т =

    f2s

    KDJ

    Так як система буде вирішуватися способом лінеаризації, тобто шляхом заміни всіх нелінійних одночленним на нові змінні, необхідно щоб число

    рівнянь було більше числа одночленним R =

    \

    2s

    D-2

    m >

    = T . -

    чаєм, що m >

    2s

    D

    2s

    D-2

    2 + 2 2s

    ^ (2s) / D. Отже, D ~ -j =. При цьому

    4m

    має виконуватися умова D>2, інакше не буде отримано нових рівнянь, так як ступінь відібраних для множення рівнянь одночленним, що визначається раз-D-2, .

    Алгоритм XL методу складається з двох кроків:

    - Multiply: множення кожного рівняння вихідної системи на твір змінних в ступеня < D-2.

    - Linearize: заміна кожного одночлена в ступеня < D на нову змінну і застосування методу виключення Г Ауссем.

    , D,

    D-2.

    Потім зробити множення рівнянь і додати до вихідної системи отримані в результаті множення нові рівняння. Для вирішення системи кожен нелінійний елемент (виду xixj або xiyj, або yiyj) в цих рівняннях замінюється нової змінної ug. В результаті система стає лінійною щодо нових,. знаходження рішення лінійної системи необхідно, щоб кількість рівнянь було не менше, ніж число нових невідомих. Найчастіше для вирішення лінійної системи використовується метод виключення Гаусса. Після знаходження рішень лінійної системи рівнянь щодо нових змінних виконується обчислення рішень початкової нелінійної системи шляхом вирішення систем спеціального виду (xiyj = ug або xixj = ug, або yiyj = ug,) для кожного отриманого рішення лінійної системи [3].

    Трудомісткість атаки визначається трудомісткістю знаходження рішень системи лінійних рівнянь методом виключення Гауса, нехтуючи трудомісткістю рішення систем спеціального виду. Трудомісткість алгебраїчної атаки методом XL становить (T3).

    XL

    алгоритму шифрування Rijndael, схема якого представлена ​​на рис. 1. Розмір шифруемого блоку даних і розмір ключа шифрування для даного алгоритму 12 .

    вигляді станів. Нехай є 12-бітове значення 100 010 011 101, тоді зі-

    (100 011 ^

    стояння записують у вигляді. В алгоритмі шифрування паралельно

    використовуються чотири S-блоку розмірами 3x3 біта.

    На початку алгоритму шифрування виконується складання по модулю два вхід. , x, -

    , S-, S- ,

    відбувається нелінійне перетворення згідно заданої таблиці заміни. Заме-S-:

    /

    x 0 1 2 3 4 5 б 7

    y 7 б 0 4 2 5 1 3

    Початковий ключ (кп) •

    Відкрито 1 - Г 4 текст (а] Г

    * ^ 1. 7 г

    Б-блоки

    * *

    лінійна частина

    г

    7 г

    Раундовий ключ (кг)

    Шіфротекст (г)

    Мал. 1. Зменшений алгоритм шифрування Ш] п (1ае1

    Виходи Б-блоків (у) конкатенуються, після чого виконуються лінійні перетворення шифру: операція ShiftRow, яка полягає в обміні значень рядків стану, і операція М1хСо1ітш, що здійснює перемішування .

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

    Розглянемо отримання нелінійної системи рівнянь. Для досліджуваного прикладу число одночленним t дорівнює 22, для генерації рівнянь використовуються наступні одночлени {XI, Х2, Хз, У1, У2, Уз, Х1Х2, Х1Х3, х ^ з, у ^ 2, У1Уз, У2У3, х ^ 1, х ^ 2, х ^ з, х ^ 1, х2у2, х ^ з, х ^ 1, х ^ 2, х ^ з, г)}.

    Всього можна згенерувати 222 = 4 194 з04 комбінації одночленним. Складемо таблицю істинності. Для досліджуваного Б-блоку таблиця істинності задається

    . 2.

    2

    Таблиця істинності для 8-блоку

    х з X X 1 з > > г X 1 X з > з з > з > з з X > г X з > г X »>• г X > X з > 1 > 1 + 1 1 з > з >

    0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

    0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1

    0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

    0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1

    1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1

    1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1

    1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1

    1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 + 1

    4 194 з04

    були складені 16 з8з рівняння, вірні для всіх можливих вхідних значень Б-блоку. Позначимо знайдені рівняння «Система 1».

    Для формування шуканої нелінійної системи бажано використовувати рівняння з мінімальним числом квадратних одночленним. Проаналізуємо по. , 16 з8з 10

    містять єдиний квадратний елемент (елемент виду хед, х ^ або у ^). Ці рівняння складають частину шуканої системи рівнянь, яка описує роботу Б-блоку. Позначимо відібрані 10 рівнянь як «Система 2»:

    хз + Х1 + уз + в1 + хзу2 = 0; хз + у2 + в1 + х1у2 = 0; хз + х1 + уз + у2 + в1 + узу2 = 0; х1 + уз + у2у1 = 0; х2 + х1 + уз + у2 + в1 + хзх2 + 1 = 0; х2 + у2 + хзх1 + 1 = 0; хз + х2 + х1 + в1 + х2х1 + 1 = 0; х2 + х1 + уз + у2 + в1 + х2 в1 + 1 = 0; х2 + у2 + х1 у1 + 1 = 0; х2 + х1 + уз + у2 + узу1 + 1 = 0.

    При аналізі наведених вище 10 рівнянь видно, що вони містять не всі квадратні елементи. Відсутні елементи хзуз, хзуь х2уз, х2у2 і х ^ з. Таким , .

    Шукана нелінійна система рівнянь повинна містити максимальну кількість можливих нелінійних (квадратних) одночленним для якнайповнішого завдання перетворень, які виконуються в Б-блоці заміни. Отже, необхідно отримати рівняння, що містять відсутні одночлени. При цьому також потрібно, щоб рівняння містили мінімальну кількість нелінійних елементів. В роботі [4] запропоновано наступний спосіб отримання таких рівнянь. У рівняннях «Системи 1» проводиться обнуління всіх вже зустрічалися квадратних одночленним, шляхом додавання за модулем 2 рівняння, що містить недос-

    , «2»,

    .

    «Системи 1» взяли нульове значення, а що залишилися рівняння містять відсутні одночлени. В результаті отримані 15 рівнянь:

    х2 + х1 + уз + у2 + в1 + хзуз + хзу1 + 1 = 0; хз + х1 + у2 + в1 + хзуз + х2уз = 0; хз + х2 + уз + хзу1 + х2уз + 1 = 0; х2 + у2 + хзуз + х2у2 + 1 = 0; х1 + уз + в1 + хзу1 + х2у2 = 0; хз + х2 + х1 + в1 + х2уз + х2у2 + 1 = 0; хз + уз + у2 + хзуз + хзу1 + х2уз + х2у2 = 0; х2 + х1 + у2 + хзуз + х1уз + 1 = 0;

    уз + в1 + хзу1 + х1уз = 0; хз + х2 + у1 + х2уз + х1уз + 1 = 0; хз + х1 + уз + у2 + хзуз + хзу1 + х2уз + х1уз = 0;

    х1 + х2у2 + х1уз = 0;

    х2 + уз + у2 + в1 + хзуз + хзу1 + х2у2 + х1уз + 1 = 0;

    хз + у2 + в1 + хзуз + х2уз + х2у2 + х1уз = 0; хз + х2 + х1 + уз + хзу1 + х2уз + х2у2 + х1уз + 1 = 0.

    Для подальшого аналізу залишимо рівняння, що містять мінімальну кількість нелінійних елементів. В даному випадку відкинемо рівняння, що містять більше двох квадратних елементів, тобто рівняння під номерами 7,11,1з, 14,15. Залишилося 10 рівнянь ( «Система з»):

    х2 + х1 + уз + у2 + в1 + хзуз + хзу1 + 1 = 0; хз + х1 + у2 + в1 + хзуз + х2уз = 0; хз + х2 + уз + хзу1 + х2уз + 1 = 0; х2 + у2 + хзуз + х2у2 + 1 = 0; х1 + уз + в1 + хзу1 + х2у2 = 0; хз + х2 + х1 + в1 + х2уз + х2у2 + 1 = 0; х2 + х1 + у2 + хзуз + х1уз + 1 = 0;

    уз + в1 + хзу1 + х1уз = 0; хз + х2 + у1 + х2уз + х1уз + 1 = 0; х1 + х2у2 + х1уз = 0.

    Для формування системи, що містить всі квадратні елементи, необяза- «2», -ти. Досить додати 4 рівняння «Системи з», відібрані таким чином, що один квадратний елемент зустрічається в кожному з них, а інші не повторювали-.

    позначимо Сх, де х - номер рівняння «Системи з». Можна скласти 5 варіантів угруповання рівнянь:

    1 варіант: хзуз + хзу1 + С1 = 0 хзуз + х2уз + С2 = 0 хзуз + х2у2 + С4 = 0 хзуз + х1уз + С7 = 0

    2: хзу1 + хзуз + С1 = 0 хзу1 + х2уз + Сз = 0 хзу1 + х2у2 + С5 = 0 хзу1 + х1уз + С8 = 0

    3:

    х2уз + хзуз + С2 = 0 х2уз + хзу1 + Сз = 0 х2уз + х2у2 + С6 = 0 х2уз + х1уз + С9 = 0

    4:

    хзуз + х2у2 + С4 = 0 хзу1 + х2у2 + С5 = 0 х2уз + х2у2 + С6 = 0 х2у2 + х1уз + С9 = 0

    5:

    хзуз + х1уз + С7 = 0 хзу1 + х1уз + С8 = 0 х2уз + х1уз + С9 = 0 х2у2 + х1уз + С10 = 0

    При складанні шуканої нелінійної системи рівнянь можна використовувати будь-який з п'яти варіантів угруповання рівнянь. В роботі використовується пя-:

    х2 + х1 + у2 + хзуз + х1уз + 1 = 0;

    уз + в1 + хзу1 + х1уз = 0; хз + х2 + у1 + х2уз + х1уз + 1 = 0; х1 + х2у2 + х1уз = 0.

    4 «2», -

    лучім систему рівнянь, що описує роботу Б-блоків:

    хз + хі + уз + в1 + ХЗУ 2 = 0;

    хз + у 2 + уі + хіУ2 = 0;

    хз + хі + Уз + У2 + уі + У3У2 = °;

    хі + Уз + У2У1 = 0;

    х2 + хі + Уз + У2 + уі + хзх2 + 1 = °;

    х2 + У2 + хзх1 + 1 = 0;

    хз + х2 + х1 + У1 + х2х1 +1 = 0;

    х2 + х1 + Уз + У2 + У1 + х2У1 + 1 = °;

    х2 + У2 + х1 У1 + 1 = 0;

    х2 + х1 + Уз + У2 + УзУ1 +1 = °;

    х2 + х1 + У2 + хзУз + х1Уз + 1 = °;

    Уз + У1 + хзУ1 + х1Уз = 0;

    хз + х2 + У1 + х2Уз + х1Уз + 1 = 0;

    х1 + х2у2 + х1Уз = °.

    Б-

    2x2 і 4x4:

    х 0 1 2 з

    в (х) з 2 0 1

    (1)

    х 0 1 2 з 4 5 6 7 8 9 10 11 12 +1 з 14 15

    в (х) 10 4 з 11 8 14 2 12 5 7 6 15 0 1 9 1З

    Б (1) 2 + 2 7:

    х2 + у 2 + х 2у2 + 1 = 0

    х1 + у 2 + в1 + х2 у 2 = 0

    х2 + х1 + в1 + х2 у2 + 1 = 0;

    в1 + х2 х1 + у 2у 1 = 0

    х2 + у 2 + х2 х1 + х2 в1 + 1 = 0

    х2 + у1 + х2 х1 + х1 у 2 + 1 = 0

    х1 + у2 + в1 + х2 х1 + х1 у1 = 0.

    Для Б-блоку (2) розміром 4x4 отримана система з 21 рівняння:

    1 + х ^ 2 + х ^ з + х2хз + х ^ 4 + хзх4 + уху2 + уз + у4 = 0;

    х2 + х1х2 + хз + х1хз + х2хз + х4 + х1х4 + х2х4 + у2 + у1уз + у4 = 0;

    1 + х1 + х2 + х ^ 2 + хз + х ^ з + х ^ 4 + уху2 + уз + у4 = 0;

    х1 + х2 + х1х2 + хз + х1хз + х2хз + х4 + у2 + уз + у4 + у1у4 = 0;

    х ^ + х2хз + х4 + х ^ х4 + хзх4 + у 1 + у2 + у2у4 = 0;

    1 + хз + х1хз + х2хз + х1х4 + х2х4 + у2 + уз + узу4 = 0;

    х1 + х2 + х ^ 2 + хз + х ^ з + х2хз + х4 + х ^ 4 + х1у1 + у2 + уз + у4 + х4у4 = 0; 1 + х2хз + х4 + х ^ 4 + х2х4 + у 1 + х ^ 2 + уз + у4 = 0;

    х ^ 2 + хз + х ^ з + хзх4 + у; + У2 + уз + х ^ з + у4 = 0;

    1 + х1 + х2 + х ^ х2 + х4 + х ^ 4 + х2х4 + у4 + х ^ + х4у4 = 0;

    • 1 + хз + х2хз + х4 + х1х4 + хзх4 + в1 + х2у1 + у2 + уз + х4у4 = 0;

    х1 + х2 + х ^ 2 + х4 + х1х4 + хзх4 + х2у2 + уз + х4у4 = 0;

    х1 + х2 + хз + х1хз + х2хз + х4 + х2х4 + у2 + уз + х2уз + у4 = 0;

    1 + х1хз + х2хз + х4 + х2х4 + в1 + уз + у4 + ^ 4 + х4у4 = 0

    1 + хз + х2хз + х1х4 + х2х4 + хзу1 + у 2 + уз + х4у4 = 0;

    1 + х2 + х1х2 + х2хз + х2х4 + хзх4 + хзу2 + уз + у4 = 0;

    х2 + х1хз + х2хз + х4 + хзх4 + в1 + хзуз + х4у4 = 0;

    1 + х1 + х2 + х1х2 + х2хз + х2х4 + хзх4 + в1 + у2 + хзу4 + х4у4 = 0;

    1 + хз + х2хз + х4 + х ^ 4 + хзх4 + х4у1 + у2 + уз = 0;

    х1х2 + хз + х1хз + х4 + х2х4 + в1 + у2 + х4у2 + у4 + ^ 4 = 0;

    х2 + х ^ + хз + х1хз + х2хз + х4 + х ^ + у 2 + х4уз + у 4 + х4у4 = 0.

    У табл. з приведені чисельні характеристики нелінійних системи рівнянь для трьох Б-блоків заміни.

    Таблиця 3

    Чисельні характеристики нелінійних систем рівнянь, отриманих

    для трьох 8-блоків

    Розмір Б-блоку в бітах - нений в системі Кількість змінних Кількість квадратних елементів Трудомісткість хь методу

    2х2 7 4 6 26

    ЗхЗ 14 6 15 213

    4х4 21 8 28 217

    Розглянемо рішення нелінійної системи для Б-блоку розміром 3x3. Вихідна система містить 14 рівнянь з 6 змінними. За формулою обчислення

    : 1,6, але за умовою Б>2,

    2 $ 6

    коефіцієнта Б алгоритму хь маємо В >^ = = - ==

    | \] Ш ->/ 14

    тому використовуємо параметр Б = 3. Отже, систему рівнянь потрібно помножити на всі одночлени першого ступеня (так як Б-2 = 1), а саме, на змінні {х3, х2, х1, у3, у2, у1}. При множенні отримано І = 2 ^ ш = 84 нових рівнянь. У вихідній системі були присутні квадратні елементи, значить, після множення максимальний ступінь одночленним буде дорівнює трьом. Всього в рівняннях використовуються 28 = 6 змінних, отже, число одночленним в новій системі

    дорівнюватиме V =

    25

    V3,

    25

    2

    + 2 $ = 41. При доповненні вихідної системи новими

    рівняннями, отримуємо систему з 98 рівнянь з 41 одночленной:

    хі + У3 + У2У1 = 0;

    х3 + У2 + уі + Х1У2 = 0;

    УзУі + У1 + хзУ1 + х1У3У1 = °;

    хзУ1 + х2У1 + У1 + х 2 у з У1 + х1УзУ1 + У1 = 0;

    Х1у1 + х 2 У 2 У1 + х1УзУ1 = 0.

    Для можливості вирішення системи методом лінеаризації необхідно, щоб вона містила, принаймні стільки ж лінійно-незалежних рівнянь, скільки одночленним в ній зустрічається.

    Все квадратні і кубічні елементи в даній системі відповідно до алгоритму методу хь замінюємо на нові змінні. При приведенні системи рівнянь за алгоритмом Гауса до трикутного вигляду частина з 98 рівнянь перетворилися в тотожності, а саме прийняли вид 0 = 0. Трикутна матриця для ре. 2.

    В результаті виконання зворотного ходу алгоритму виключення Гаусса, обчислено рішення лінійної системи рівнянь.

    Після повернення до первинних змінним і рішення спеціальної системи рівнянь, одержано, що вихідна нелінійна система рівнянь, що описує виконувані в Б-блоках перетворення, має рішення: х3 = 1; х2 = 1; х1 = 0; У3 = 0; у2 = 0; в1 = 1.

    Таким чином, були знайдені значення входів і виходів Б-блоків. Далі, грунтуючись на схемі алгоритму шифрування, можна виконати наступні:

    - вхідний значення Б-блоку представити у вигляді суми по модулю 2 відкритого тексту і початкового ключа: х = а + кп;

    - вихідне значення Б-блоку записати як результат суми по модулю

    2 шифротекста і раундового ключа: у = 2 + кг.

    1, О, О, 0,1,1, О, О, АЛЕ, про, О, О, Ц О, О, 0,0,01 1,0, 0,0,0, 0,0, 0.0, 0, о, о, а про, о, о, о, о, о, о, а 0,0 о, 1,0, 0,1,0, 0,0, 0.0,0, 0,0, 0.0 , 1, 0,0, 1, 1,0, 0,0,0, 0,0, 0.0,0, 0,0, про 0,0, 0,0,0, 0,0, про 0,1 о, 0,1, о, о, о, 0,0, а про, о, 0,1,0 0,1,0,0, про 1,0, 0,0,0, 0,0, 0.0 , 0, о, о, про про, о, о, о, о, о, о, про 0,0 о, 0,0, 1,0,0, 0,0, а 0,0, 1,1 , ЦО, 1,0,0, О. 1,0, 0,0,0, 0,0, 0.0,0, 0,0, а 0,0, 0,0,0, 0,0, а 0 , 0 О, 0,0, 0,1,0, 0,0, 0 ^ 0,0, 1,0, 1, 0,0, 0,0,0 ^ 1,0, 0,0,0, про, про, с; про, про, про, про, с; 0,0, 0,0,0, 0,0, 0,0 О, О, О, 0,0,1, 0,0, а 0,0,1,0,0, 1,0, 0, 0, а 0,0, 0,0,0, 0,0, 1, 0,0, 0,0, а 0,0, 0,0,0, 0,0, а про, про о, 0, 0, 0,0,0, 1,0, а 0,0, 0,0, а 1,1, 0,0,1,1,0, 0,0,0, 0,0, 1, 0, 0, 0,0, а про, 0, 0,0,0, 0,0, а 0,0 о, 0,0, 0,0,0, 0,1, а 0,0, 0,1, 1, 1,1, 0,0, 1, 1,0, 0,0,0, 0,1, 1, 0,0, 0,0, а про, 0, 0,0,0, 0,0 , а 0,0 О, 0,0, 0,0,0, 0,0,1, 0,0, 0,0,1,1,0, 0,0,1,1,0, 0,0 , 0, 0,1, 1, 0,0, 0,0, а про, 0, 0,0,0, 0,0, а 0,0 о, о, о, 0,0,0, 0, 0, а 1,0, 0,0, 1, 0,0, 1,0, 0 ^ 0,0, 0,0,0, 0,0, а 0,0, 0,0, а про, 1 , 0,0,0, 0,0, а 0,0 про, про, про, про, про, про, про, про, про, про, 1,0,1, и, 0,0,1,0 , про, 0,0,0,1,0, про, про, про, про, про, про, про, а, о, и, о, о, о, о, о, а, о, о о, 0,0, 0,0,0, 0,0, а про, 0,1,1,1, 0,0,1,0, Ц 0,1, 0,1, про, про, 0, а про , 0, 0,0, а про, 1, 0,0,0, 0,0, а про, про о, о, о, 0,0,0, 0,0, а 0,0, 0,1 , 1, 0,0,1,1, Ц 0,0, 0,1,1, 0,0, а 0,0, 0,0, а про, 1, о, о, о, 0,1, а 0,0 о, 0,0, 0,0,0, 0,0, а про, 0, 0,0,1, 0,0,1,1, Ц 0,0, 0,1,1, 0,1, а 0,0, 0,0, а про, 1, 0,0,0, 0,1, а о, про о, 0,0, 0,0,0, 0,0, а про , 0, 0,0, а 1,1,1,1,1,1,0, 0,1,1, 0,0, а 0,0, 0,0, а 0,1, 1,0,0, 0,1, а 0,0

    О, 0,0, 0,0,0, 0,0, 0 ^ 0,0, 0,0, Ц 0,1, 1,0, 0 ^ 0,0, 0,1,1, 0,0 , 1, 0,1, 0,0, 0,1, 1,0,0, 0,1, 0,0 О, О, О, О, О, О, О, О, Ц О, О, О , о, Ц 0,0,1,1, про, 0,0, 0,1,1, 0,0, 1, 0,0, 0,0, а 0,1, 1,0,1, 0 , 1, а про, про

    О, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а 0,0, 0,1, Ц 1, о, 0,0,1, 0,0, 1 , о, 0, 0,0, а про, 1, 1,0,1, 0,1, а о, про о, 0,0, 0,0,0, 0,0, а про, 0, 0 , 0, а 0,0, 0,0,1, 0,1, 0,1,0, 0,0, 1, 0,0, 0,0, а про, 1, 1,0,1, 0 , 0, а про, про о, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а о, о, о, о, Ц 1,0, 0,1, о, 0,0, 1, 0,1, 0,0, а про, 1, 1,0,1, 0,0, а про, про

    О, 0,0, 0,0,0, 0,0, О, О, О, О, О, О, 0,0, 0,0, 0 ^ 0,1, 0,0,0, 0, 1, 1, 0,1, про, про, с; 0,1, 1,0,1, про, про, про, про "про про, 0,0,0,0,0, про, про, про, про, про, про, про, про, про, про , про, про, про, про, про, 1,0,0,0,0, и, о, и, 0,0, а, о, и, 1,0, и, 0,0, а, про , про о, 0,0, 0,0,0, 0,0, а про, о, о, о, а про, про, про, про, ц о, о, 0,1,1, про, 0 , а про, 0, 0,0, а про, 1, 0,0,0, 0,1, а про, про о, 0,0, 0,0,0, 0,0, а про, о, о, о, а про, про, про, про, ц о, о, 0,0,1, 0,1, а 0,1, 0,0, а про, 1, 0,0,1, 0, 0, а про, про о, 0,0, 0,0,0, 0,0, а про, о, о, о, а про, про, про, про, ц о, о, о, о, 0 , 1,0, 1, о, 0, 0,0, а про, 0, 1,0,0, 0,0, а про, про о, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а 0,0, 0,0, а про, про, про, про, 0, 0,1, а про, 1, о, 0, а про, 1, 0,0 , 1, 0,1, а про, про

    О, 0,0, 0,0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0,0, 0, 0, 1, 1,1, 0,0, 0,1, 1,0,1, 0,1, 0,0

    О, О, О, О, О, О, 0,0, О, О, О, 0,0, а О, О, 0,0,1} 0,0, 0,0,0, 0,0 , а 1,1, 0,0, а 0,1, 1,0,1, 0,1, 1, о, о о, 0,0, 0,0,0, 0,0, а про, про , о, о, а про, про, про, про, ц о, о, о, о, о, о, 0, а 0,1, 0,0, а про, 0, 1,0,0, 0 , 1, 1, 1, про о, 0,0, 0,0,0, 0,0, а про, о, о, о, а про, про, про, про, ц о, о, о, о , про, про, 0, а про, 0, 1,0, а про, 0, 1,0,0, 0,0, 1, о, о о, 0,0, 0,0,0, 0, 0, а про, о, о, о, 0, 0,0, 0,0, а про, про, про, про, про, про, 0, а про, 0, 0,1, а про, 0, 0,0,1, 0,1, а 1, про

    О, 0,0, 0,0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0,0, О, О, с; 0,0, 0,0, 1, 0,1, 0,0,1, 0,1, 1,0

    О, 0,0, 0,0,0, 0,0, 0, 0,0, 0,0, 0, 0,0, 0,0, 0, 0,0, 0,0,0, 0, 0, 0, 0,0, 0,0, а, 1,1, 1,0,1, 0,1, 1, 1,0 О, 0,0, 0,0,0, 0,0, а о, 0, 0,0, а о, о, о, о, Ц 0,0, 0,0,0, 0,0, а 0,0, 0,0, а про, 1, 1,0, 1, 0,1, 1, 1, про о, 0,0, 0,0,0, 0,0, а про, о, о, о, а про, про, про, про, ц о, о, про, про, про, про, 0, а про, 0, 0,0, а про, 0, 1,1,1, 0,1, 1, 1, про о, 0,0, 0,0,0 , 0,0, а про, о, о, о, а про, про, про, про, ц о, о, о, о, о, о, 0, а про, 0, 0,0, а про, 0, 0,1,1, 1,1, 1, 1, про о, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а 0,0, 0,0 , а про, про, про, про, про, про, 0, а про, про, про, 0, а про, 0, 0,0,1, 1,1, а 1, про

    О, 0,0, 0,0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0, 0 ^ 0,0, 0,0,0, О, О, с; 0,0, 0,0, 0,0, 0,0,0, 1,0, 1,0

    О, О, О, О, О, О, 0,0, 0 ^ О, О, 0,0, а О, О, 0,0,1} 0,0, 0,0,0, 0,0 , а 0,0, 0,0, а 0,0, 0,0,0, 0, 1, а 1,1 о, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а о, о, о, о, Ц 0,0, 0,0,0, 0,0, а 0,0, 0,0, а про, 0, 0,0,0, 0, 0, 1, 1, про о, 0,0, 0,0,0, 0,0, а про, 0, 0,0, а о, о, о, о, Ц 0,0, 0,0, 0, 0,0, а 0,0, 0,0, а про, 0, 0,0,0, 0,0, а 1, про

    Мал. 2. Трикутна матриця системи рівнянь для Б-блоку розміром 3x3

    З даних замін висловимо початковий і раундовий ключі через відомі відкритий текст, шифротекст, входи і виходи Б-блоків:

    кп = а + х,

    кг = г + у.

    За умовою атаки криптоаналітику доступна одна пара відкритий текст / шифротекст. Заданий відкритий текст а = 010 101 001 110 і відповідний йому шифротекст 2 = 111 011 100 101. Тоді обчислення ключів виконується на-:

    кп0 = а0 + х = 010 + 110 = 100, КП1 = а1 + х = 101 + 110 = 011, КП2 = А2 + х = 001 + 110 = 111,

    КПЗ = аз + х = 110 + 110 = 000;

    кГ0 = 20 + у = 111 + 001 = 110, кг1 = ^ 1 + у = 011 + 001 = 010, кг2 = 22 + у = 100 + 001 = 101,

    КГЗ = гз + у = 101 + 001 = 100.

    Початковий ключ kn дорівнює 100 011 111 000, а раундовий kr 110 010 101 100.

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

    , , -тання заміни в S-блоках, виявилося достатнім розгляд тільки вхідних (xj) і вихідних (у;) значень блоку заміни і їх творів виду х; ед, X; Xj і yyj.

    В даній статті запропоновано алгоритм отримання нелінійної системи рівнянь, яка описує перетворення заміни в S-блоках. Показано застосування даного алгоритму для конкретних таблиць заміни S-блоків розмірами 2x2, 3x3 і 4x4 біта. Досліджено XL метод алгебраїчного криптоанализа. Для трьох таблиць заміни обчислені трудомісткості реалізації методу XL. Виконано криптоаналіз спрощеного алгоритму шифрування Rijndael, що використовує чотири S-блоку

    3 3 . ,

    виконана перевірка правильності їх обчислення.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Nicolas T. Courtois. How Fast can be Algebraic Attacks on Block Ciphers./ Nicolas T. Courtois // Cryptology ePrint Archive, Report 2006/168, 2006.

    2. Courtois N., Klimov A., Patarin J., Shamir A. Efficient algorithms for solving overdefined systems of multivariate polynomial equations / N. Courtois, A. Klimov, J. Patarin, A. Shamir // EUROCRYPT, 2000. - P. 392-407.

    3.. .,. . . / . . , . . -

    кін. - М .: Видавничий дім «Солон-Р», 2002. - 511 с.

    4.. . /

    Е.А. Маро // Матеріали I Всеросійської молодіжної конференції з проблем інформаційної безпеки ПЕРСПЕКТИВА - 2009. - Таганрог: Изд-во ТТІ ПФУ, 2009. - С. 259 - 265.

    Бабенко Людмила Климентіївна

    Технологічний інститут Федерального державного освітнього закладу вищої професійної освіти «Південний федеральний університет»

    . .

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928, м Таганрог, вул. Чехова, 2, корпус "І".

    Тел .: 8 (8634) 312-018.

    Кафедра безпеки інформаційних технологій; професор.

    Babenko Lyudmila Klimentevna

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of

    Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Block "I", 2, Chehov str., Taganrog, 347928, Russia.

    Phone: 8 (8634) 312-018.

    The Department of Security of Information Technologies; professor.

    Маро Катерина Олександрівна

    Технологічний інститут Федерального державного освітнього закладу вищої професійної освіти «Південний федеральний університет»

    . .

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928,. ,. , 2, "".

    Тел .: +7 (961) 27-23-100.

    Кафедра безпеки інформаційних технологій; аспірант.

    Maro Ekaterina Aleksandrovna

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Block "I", 2, Chehov str., Taganrog, 347928, Russia.

    Phone: +7 (961) 27-23-100.

    The Department of Security of Information Technologies; post-graduate student.

    УДК 681.3.067

    Д.П. Рубльов, О.Б. Макаревич, В.М. Федоров

    МЕТОД Стеганографічні ВБУДОВУВАННЯ ПОВІДОМЛЕНЬ

    У Аудіодані НА ОСНОВІ ВЕЙВЛЕТ-ПЕРЕТВОРЕННЯ *

    Пропонується стеганографтескій метод вбудовування бінарних повідомлень в аудіо дані, заснований на модифікації вейвлет-коефіцієнтів, призначений для приховування двійкових даних в оцифрованих мовних повідомленнях. Вбудовування здійснюється модуляцією коефіцієнтів вейвлет, -освіту формату зберігання звукової інформації в формати з втратою якості.

    стеганографія; вейвлет-перетворення; кореляція; робастні Стего-.

    D.P. Rublev, O.B. Makarevich, V.M. Fedorov STEGANOGRAPHICAL METHOD FOR MESSAGES EMBEDDING TO AUDIODATA BASED ON THE WAVELET-TRANSFORM

    We propose a steganographical method of binary messages embedding to audio data based on wavelet coefficient modifying, which is intended to hide binary data in digitized speech messages. Embedding in performed via wavelet coefficients modulation which allows to achieve robustness to lossy compression schemes

    Steganography; wavelet transform; correlation; robust stegosystems.

    У зв'язку з широким розповсюдженням мережевих засобів передачі мультіме-

    , , IP

    , -з тим. Застосування в складі стегосистеми методів стеганографії, що використовують модифікацію найменш значущих біт (НЗБ) вихідних мультимедіа-даних ог-, -ведётся із застосуванням того чи іншого методу стиснення, заснованого на психофізіологічної моделі сприйняття людини, тобто варіанти стиснення з втратами.

    , -пространённих джерел мультимедіа-трафіку, то в залежності від області

    * Робота виконана за підтримки гранту РФФД № 09-07-00242-а


    Ключові слова: алгебраїчних криптоаналіз /XL МЕТОД /НЕЛІНІЙНІ ПЕРЕТВОРЕННЯ ЗАМІНИ /Лінеаризація нелінійних СИСТЕМ /МЕТОД виключення Гауса /криптографічні ключі /ALGEBRAIC CRYPTANALYSIS /XL METHOD /NONLINEAR TRANSFORMATIONS OF SUBSTITUTION /LINEARIZATION NONLINEAR SYSTEMS /GAUSS ELIMINATION METHOD /A CRYPTOGRAPHIC KEY

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

    Завантажити