Тези Кодування інформації бінарними поліномами

« Назад

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

Методи захисту від несанкціонованого прочитання зводяться до перетворення даних у набір зі скінченною кількістю символів і здійснення над цими символами підстановок і перестановок. Підстановка полягає в заміні одних символів на інші, а перестановка — в зміні порядку символів. Символами при цьому можуть бути різні елементи повідомлення; при шифруванні текстів, поданих природними мовами, підстановці й перестановці піддаються як окремі букви, так і слова або цілі фрази. У сучасних алгоритмах ці операції виконують над блоками послідовних бітів. Більшість криптографічних методів, які використовують нескладні алгоритми шифрування чи ключі до 64 бітів, не є досконалими, і закодовану з їхньою допомогою інформацію легко розкодувати, застосувавши метод грубої сили — перебір ключів з множини можливих.

Найнадійнішим на даний час алгоритмом кодування є Rijndael [1]. Цей алгоритм симетричний (використовує один ключ для шифрування й дешифрування), інформація обробляється блоками по 128, 192 чи 256 бітів. Ключі завдовжки 128 бітів застосовують на рівні secret, а 192 і 256 бітів — на рівні top secret.

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

У кожному циклі кодування виконуються 4 дії: нелінійна оборотна байтова заміна, зсув рядків, перемішування стовпчиків, додавання ключа [2]. При байтовій заміні кожен байт даних  замінюють оберненим . Зсув рядків полягає в циклічному зсуві вліво трьох останніх рядків матриці відповідно на 1, 2 і 3 байти. При перемішуванні стовпчики, які є 4-байтовими векторами і яким відповідають поліноми степеня не вище 3 з коефіцієнтами із , множать за модулем  на поліном . Додавання ключа виконують залежно від номера циклу над стовпчиками побітним додаванням за модулем 2 до кожного байта інформації відповідного байта розширеного ключа. Результатом таких дій є лавинний ефект, при якому дуже швидко втрачається відповідність між бітами початкових і закодованих даних.

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