Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 681.142.2; 622.02.658.284; 621. 325

АФІННІ ПЕРЕТВОРЕННЯ В МОДИФІКАЦІЯХ АЛГОРИТМУ RSA ШИФРУВАННЯ ЗОБРАЖЕНЬ

Рашкевич Ю.М., Ковальчук А.М., Пелешко Д.Д.

Вступ

З розвитком і поширенням інформаційних технологій зростає актуальність питання інформаційної безпеки. Розгляду цього питання присвячуються щорічні тематичні конференції і симпозіуми (напр. RSA Conference, Сан-Франціско, США). Поява нових мережевих технологій, ”хмаркових” обчислень й ін., які дуже активно просуваються на ринок, спричинюють потребу розробки нових стандартів безпеки і удосконалення методів персоніфікованого захисту даних.

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

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

Проблема захисту від несанкціонованого доступу є складнішою в порівнянні з проблемою захисту використання. Основним базисом для організації захисту зображення є таке припущення: зображення – це  стохастичний сигнал. Це спричинює перенесення класичних методів шифрування сигналів на випадок зображень. Але зображення є специфічним сигналом, який володіє, в додаток до типової інформативності (інформативності даних), ще й візуальною інформативністю. А остання привносить в питання захисту нові задачі.

Саме ця інформативність із дуже розвинутими сучасними методами обробки зображень дає можливість для організації несанкціонованого доступу. Фактично організація хакерської атаки на зашифроване зображення можлива у двох варіантах: через традиційний взлом методів шифрування, або через методи візуальної обробки зображень (методи фільтрації, виділення контурів, тощо). Хоча останні не дають повного відтворення зашифрованого зображення, проте дають можливість отримати деяку інформацію із зображення. В зв’язку з цим до методів шифрування у випадку їх використання стосовно зображень висувається ще одне завдання – повна зашумленість зашифрованого зображення. Це  потрібно для того, щоб унеможливити використання методів візуальної обробки зображень.

Алгоритм RSA є одним із найбільш уживаних промислових стандартів шифрування сигналів. По відношенню до зображення існують певні проблеми його шифрування, а саме частково зберігаються контури на різко флуктуаційних зображеннях [4, 5].

Мета роботи

Стосовно зображень актуальною задачею є розробка модифікації методу RSA такої, щоб

-                     зберегти стійкість до дешифрування

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

Одним із шляхів вирішення цієї задачі є використання афінних перетворень.

Характеристики зображення

Нехай задано рисунок P з ширини l і висоти h. Його можна розглядати як матрицю пікселів

<dtp_ij>_{1≤ i ≤ n, 1≤ j ≤ m},                                                   (1)

де dtp_ij – піксел з коoрдинатами i та j,  n і m – число точок по ширині l та висоті. В загальному випадку n і m є залежними від l та h, а тому більш коректним є запис

n = n(l) i m = m(h).                                                  (2)

Матриці (1) у відповідність ставиться матриця кольорів

,                                                  (3)

де с_ij – значення інтенсивності у напівтонових зображень піксела dtp_ij. Тобто має місце відповідність [1]

.                   (4)

Під градацію яскравості звичайно приділяється 1 байт, причому 0 - чорний колір, а 255 - білий (максимальна інтенсивність). У випадку кольорового зображення виділяється по байту на градації яскравостей всіх трьох кольорів. Можливе кодування градацій яскравості іншим числом бітів (4, 12, або 24), але людське око здатне розрізняти тільки 8 біт градацій на кожний колір, хоча спеціальна апаратура може давати і більше точну передачу кольорів

У випадку кольорових зображень с_ij треба розглядати як вектор основних характеристик кольорової палітри. Наприклад, якщо задано зображення у 24-бітному форматі палітри RGB, то

,    

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

Якщо, наприклад, по ширині  ввести в розгляд вектор

,                                                 (5)

то (3) можна записати у вигляді

.                                                        (6)

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

Математично – ідеальний контур це – розрив просторової функції рівнів яскравості в площині зображення. Тому виділення контура означає пошук найбільш різких змін, тобто максимумів модуля вектора градієнта [2]. Це є однією з причин, через що контури залишаються в зображенні при шифруванні в системі RSA, оскільки шифрування тут базується на піднесенні до степеня по модулю деякого натурального числа. При цьому, на контурі  і на сусідніх до контура пікселах  піднесення до степеня значення яскравостей дає ще більший розрив.

Лінійний афінний шифр

Введемо означення  бінарного аффінного перетворення евклідової площини в декартових координатах.

Перетворення евклідової площини називається афінним, якщо це перетворення відображає кожну пряму на пряму.

Лінійний афінний шифр – шифр афінної підстановки – має вигляд:

y = ax + b (mod m).                                                    (7)

Тут ключем є пара , причому a  повинно бути взаємно простим з m.

З (7) одержуємо

x = a′y + b′ (mod m),                                                  (8)

де a′ = a^-1 mod m - обернений до a елемент в кільці лишків за модулем m, b′ = - a′b.

Рівність (8) має той самий вигляд, що й (7), отже шифрування і розшифрування здійснюються за тим самим алгоритмом, тільки з різними параметрами. Умова взаємної простоти a  з m потрібна для того, щоб існував обернений елемент a^-1 і рівняння (7) при фіксованому y мало єдиний розв’язок  x , тобто можливо було однозначно розшифрувати. У протилежному випадку рівняння (8) має не єдиний розв’язок  x або взагалі його не має.

Афінна підстановка легко піддається криптоаналізу, хоча число ключів в цьому шифрі φ(m) · m, де φ(m) – функція Ейлера (число менших за m і взаємно простих з ним чисел). Нехай y^*  і y^** - перша і друга за частотою букви шифрованого тексту, x^*  і x^**  - відповідно найчастіша і наступна за нею букви алфавіту.

Природно припустити, що при шифруванні x^* перейде в y^*, а x^**- в y^**.

Складемо систему рівнянь:

                                                  (9)

Відмітимо, що в цій системі невідомими є  a  і  b, а  x і  y – відомі. З (9) маємо:

.                                              (10)

Якщо пари x^* « y^*, x^** « y^** підібрані  вірно, то рівняння (9) має розв’язок a. Знаючи a, з (10) знаходимо b. Якщо ж ці пари не відповідають дійсності, то (9) або не має розв’язку, або при всіх розв’язках (10), розшифровуючи, одержимо беззмістовний текст.

Формули бінарного афінного перетворення

Бінарне афінне перетворення площини в декартових координатах має вигляд

                                               (11)

де      

.                                                       (12)

Обернене до (11) перетворення також  існує і тоді

,                                                      (13)

де

.                                       (14)

Шифрування і дешифрування по рядках матриці зображення

Шифрування по одному рядку

Нехай P, Q  - довільні прості числа. Виберемо [3]

.                     (15)

Шифрування відбувається з використанням елементів одного рядка по формулах  (11),  де 

.                                    (16)

Вибираються дві сусідні точки, так щоб в кожну пару кожна точка була вибрана тільки один раз. Коефіцієнти

,                (17)

є цілі числа,

.                                   (18)

Дешифрування проводиться по формулах оберненого перетворення (13) з тими ж самими коефіцієнтами  (17).

Результати наведені на Рис.1 – 3.

Рис.1. Початкове зображення

Рис.2. Зашифроване зображення

Рис.3. Дешифроване зображення

Шифрування по двох рядках матриці

Шифрування відбувається з використанням елементів двох рядків по формулах  (11), де

.                                   (19)

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

,              (20)

є цілі числа,

.                           (21)

Дешифрування відбувається по формулах оберненого перетворення (13) з тими ж самими коефіцієнтами .

Результати наведені на рис.4 – 6.

Рис.4. Початкове зображення

Рис.5. Зашифроване зображення

Рис.6. Дешифроване зображення

З порівняння  Рис.2 і Рис.4 видно, що шифрування по одному рядку матриці (2.5) відрізняється від шифрування по двох рядках цієї матриці. Контури в обох зашифрованих зображеннях відсутні.

Висновки

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

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

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

4.                  Стійкість до несанкціонованого дешифрування запропонованими   потоковою модифікацією  забезпечується методом RSA.

ЛІТЕРАТУРА

1.                  Павлидис Т. Алгоритмы машиной графики и обработки изображений. – М.: Радио и связь, 1986.-399с.

2.                  Б.Яне. Цифровая обработка изображений. – Москва, Техносфера , 2007.- 583с.

3.                  Брюс Шнайер. Прикладная криптография. – М.: Триумф, 2003. – 815с.

4.                  Ю.М. Рашкевич, Д.Д. Пелешко А.М. Ковальчук, М.З. Пелешко. Модифікація алгоритму RSA для деяких класів зображень. Технічні вісті  2008/1(27), 2(28). С. 59 – 62

5.                   Y.Rashkevych, A.Kovalchuk, D.Peleshko, M.Kupchak. Stream Modification of RSA Algorithm For Image Coding with precize contour extraction. Proceedings of the X-th International Conference CADSM 2009. 24-28 February 2009, Lviv-Polyana, Ukraine,  Pp. 469-473.