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

Размещено на http://www.allbest.ru/

Інститут проблем моделювання в енергетиці НАН України

УДК 621.391.7

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

МЕТОДИ ТА ЗАСОБИ ШИФРУВАННЯ ІНФОРМАЦІЇ НА ОСНОВІ РЕКУРЕНТНИХ ПОСЛІДОВНОСТЕЙ

05.13.21 системи захисту інформації

ЯРЕМЧУК ЮРІЙ ЄВГЕНОВИЧ

Київ 2000

Дисертацією є рукопис

Робота виконана у Вінницькому державному технічному університеті Міністерства освіти і науки України

Науковий керівник: кандидат технічних наук, доцент Лужецький Володимир Андрійович Вінницький державний технічний університет, доцент кафедри обчислювальної техніки

Офіційні опоненти:

доктор технічних наук, професор Тарасенко Володимир Петрович Національний технічний університет України "Київський політехнічний інститут", завідувач кафедри спеціалізованих комп'ютерних систем

кандидат технічних наук, доцент Корченко Олександр Григорович Національний авіаційний університет, директор Європейського субрегіонального навчального центру ICAO з авіаційної безпеки

Провідна установа: Харківський державний технічний університет радіоелектроніки, кафедра безпеки інформаційних технологій, Міністерство освіти і науки України, м. Харків

Захист відбудеться 28 грудня 2000 р. о 14⁰⁰ годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15

Автореферат розісланий 23.11.2000 р.

Вчений секретар спеціалізованої вченої ради Романцов В.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

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

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

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

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

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

Основні задачі, що визначаються поставленою метою:

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

розробка методів шифрування інформації;

розробка та дослідження алгоритмів шифрування інформації;

розробка пакету програм для шифрування інформації;

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

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

Предметом досліджень є методи шифрування інформації на основі рекурентних послідовностей.

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

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

До основних нових наукових результатів, що складають наукову новизну, відносяться:

нові рекурентні послідовності (V_k та U_k послідовності) та доведені їх властивості, що забезпечують прискорення шифрування інформації;

методи шифрування інформації на основі V_k та U_k послідовностей, які є модифікаціями відомих методів Ель-Гамаля та Шаміра і забезпечують при певних умовах меншу складність обчислень, ніж ці методи;

принципи побудови спеціалізованих процесорів для шифрування інформації за модифікованими методами.

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

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

розроблені алгоритми для обчислення елементів V_k ? послідовностей, які дозволяють прискорити обчислення для великих значень індексу елементів; розроблені алгоритми шифрування інформації за модифікованими методами, які прискорюють шифрування інформації в порівнянні з відомими методами;

розроблений пакет програм для шифрування інформації за модифікованими методами;

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

Результати дисертаційної роботи впроваджено на МП “ДИНА” та використовуються в навчальному процесі на кафедрі обчислювальної техніки Вінницького державного технічного університету.

Публікації. Результати дисертаційної роботи опубліковані в 5 статтях у наукових журналах та збірниках наукових праць та 4 матеріалах і тезах наукових конференцій.

Особистий внесок здобувача. У роботах, що написані в співавторстві, автору належать: [1] дослідження властивостей V_k послідовностей; [2] дослідження властивостей U_k послідовностей; [3] метод та алгоритм прискореного обчислення елементів V_k послідовності для великих значень індексу; [4] метод та алгоритм шифрування даних з відкритим ключем; [5] метод та алгоритм шифрування даних без попереднього розподілу ключів; [9] рекурентний підхід до шифрування інформації в системах з відкритим ключем.

Апробація результатів. Основні положення дисертаційної роботи та результати досліджень доповідалися і обговорювалися на:

науково-технічній конференції з міжнародною участю “Приборостроение96” (Вінниця Судак, 1996);

міжнародному симпозіумі “Наука и предпринимательство” (Вінниця Львів, 1997);

міжнародній науково-технічній конференції “Приборостроение 97” (Вінниця Сімеїз, 1997);

міжнародній науково-практичній конференції “Россия на пороге XXI века: закономерности и проблемы развития” (Архангельск, 1998);

щорічних науково-технічних конференціях професорсько-викладацького складу Вінницького державного технічного університету (Вінниця, 1998 2000).

Структура та обсяг дисертації. Робота складається зі вступу, чотирьох розділів, чотирьох додатків. Загальний обсяг дисертації складає 179 сторінок, з яких основний зміст викладений на 121 сторінках друкованого тексту, 26 рисунків, 4 таблиці. Список використаних літературних джерел складається з 88 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

криптографічний шифрування рекурентний процесор

У вступі до дисертації обґрунтовано актуальність проблеми, сформульована мета роботи, описані основні наукові результати і показано практичне значення отриманих результатів.

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

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

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

Означення 1. Послідовність чисел, що обчислюються за формулою

v_{n, k} = g_k v_{n 1, k} + g₁ v_{n k, k} (1)

з початковими значеннями v_0,k = 1, v_1,k = g₂ для k = 2; v_0,k = v_1,k = . . . = v_k3,k = 0, v_k2,k = 1, v_k1,k = g_k для k > 2; де g₁ , g_k цілі числа; n і k цілі додатні числа називається послідовністю. Формула (1) описує рекурентну процедуру обчислення елемента v_n,k , однак під час дослідження властивостей таких послідовностей більш зручним є безпосереднє обчислення цього елемента через початкові елементи. Теорема 1. Для будь-яких цілих додатних n і k, таких що n k

. (2)

Для прискорення обчислення елементів за рекурентною формулою (1) може бути використана властивість елементів послідовності, що доведена в такій теоремі.

Теорема 2. Для будь-яких цілих додатних n, m та k

. (3)

Формула (1) дозволяє отримувати значення для зростаючих n, починаючи з n = 0, але певну цікавість становить зворотна процедура, яка складається з того, що елементи обчислюються для спадних n, починаючи з деякого значення n = l. Процедура обчислення елементів в такій послідовності описується виразом

. (4)

Для прискорення обчислення елементів за рекурентною формулою (4) пропонується використовувати властивість елементів послідовності, що доведена в такій теоремі.

Теорема 3. Для будь-яких цілих додатних n та m таких, що 1< m< n

. (5)

Обчислення за формулою (4) може продовжуватись і для n < 0, тобто можна розглянути два види послідовностей. Послідовність першого виду формується для n додатних за формулою (1). Послідовність другого виду формується для n від'ємних за формулою (4).

Означення 2. Послідовність чисел, що обчислюються за формулою (4) для n від'ємних з початковими значеннями v_1,k = 0, v_2,k = для k = 2; v_1,k = 0, v_2,k = , v_3,k = v_4,k = ... = v_k,k =0 для k > 2 називається послідовністю.

Формула (4) описує рекурентну процедуру обчислення елементу v_n,k. Для досліджень рекурентної послідовності більш зручною є формула для безпосереднього обчислення цього елементу.

Теорема 4. Для будь-яких цілого додатного k та цілого від'ємного n, таких що k>2 та n ((k1)(k2)+2)

, (6)

де , t = ( n 2) mod ( k 1).

Для прискореного обчислення елементів за рекурентною формулою (4) для будь-якого k може бути використана властивість, що доведена в такій теоремі.

Теорема 5. Для будь-яких цілих додатних n і m, таких що 1 m< n та будь-якого цілого додатного k

. (7)

Означення 3. Послідовність чисел, яка складається з послідовності та послідовності називається V_k послідовністю.

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

Означення 4. Послідовність чисел, що обчислюються за формулою

u_{n, k} = g_k u_{n 1, k} + g₁ u_{n k, k} (8)

при початкових значеннях u_0,k = g₁, u_1,k = g₂, u_2,k = g₃, ... u_k1,k = g_k; де g₁, g₂, g₃, ..., g_k цілі числа; n і k цілі додатні числа називається U_kпослідовністю.

Більш зручною для досліджень відповідної послідовності є формула безпосереднього обчислення елементу u_n,k через початкові елементи.

Теорема 6. Для будь-яких цілих додатних n і k, таких що n k

. (9)

Встановлена властивість, яка дозволяє обчислювати елемент u_n+m,k виходячи з елементів u_n,k, u_n1,k , . . . , u_nk+1,k. Ця властивість доведена в такій теоремі.

Теорема 7. Для будь-яких цілих додатних n, m та k

. (10)

Співвідношення (10) показує, що елементи U_k послідовності обчислюються через елементи двох послідовностей U_k і .

Показано, що елементи послідовності U_k можуть бути також обчислені тільки на основі елементів V_k послідовності.

Це доведено в такій теоремі.

Теорема 8. Для будь-яких цілих додатних n та k , таких що n k

. (11)

Виходячи з формули (8) вираз для обчислення елементів для спадних n, починаючи з деякого n = l, має такий вигляд

. (12)

У випадку, коли треба швидко обчислити значення елементу u_nm,k використовується властивість елементів послідовності, яка доведена в такій теоремі. Теорема 9. Для будь-яких цілих додатних n та m таких, що 1< m< n

. (13)

Властивість (13) встановлює зв'язок між елементами послідовності U_k і , але це є окремий випадок при k=2.

Для будь-яких k послідовності U_k притаманна властивість, що доведена в такій теоремі.

Теорема 10. Для будь-яких цілих додатних n і m, таких що 1 m< n та будь-якого цілого додатного k

. (14)

У третьому розділі розглядаються питання розробки та дослідження методів шифрування інформації на основі V_k та U_k послідовностей. Запропоновані модифікації таких відомих методів шифрування інформації, як Ель-Гамаля та Шаміра. Суть модифікації полягає в заміні піднесення до заданого степеня обчисленням заданого елементу V_k та U_k послідовностей.

Модифікований метод Ель-Гамаля, що запропонований, базується на властивості (10), яка дозволяє обчислити елемент u_n+m,k, використовуючи елементи та U_k послідовностей, причому елемент u_n+m,k може бути обчислений двома шляхами: або використовуючи елементи v_m+i,k , , та u_n?i,k, , або використовуючи елементи v_n+i,k, , та u_m?i,k, . Необоротність перетворень в цьому випадку основана на складності обчислення елементу u_n+m,k при відомих елементах u_n?i,k або u_m?i,k, , без знання відповідно m або n.

При реалізації процедури шифрування інформації виникає проблема обчислення елементу v_n,k для великих значень n, оскільки для таких значень обчислення v_n,k за формулою (1) є неприйнятним.

В зв'язку з цим запропоновано метод обчислення елементу v_n,k, який базується на використанні ідеї відомого бінарного методу піднесення до степеня для отримання адитивного ланцюжка 1 = c₀, c₁, c₂, . . . , c_t = n.

Якщо записати n в двійковій системі числення

, (15)

то для кожного правило отримання адитивного ланцюжка має такий вигляд: якщо значення _t-i дорівнює 0, то c_i = 2c_i-1; якщо значення розряду _t-i дорівнює 1, то c_i = 2c_i-1 + 1. Звідси, обчислення v_n,k зводиться до послідовного обчислення або . Розроблено алгоритм для реалізації методу прискореного обчислення елементу v_n,k на основі бінарного методу.

Відомий підхід до реалізації алгоритмів, коли кількість операцій, що виконуються, зменшується за рахунок збільшення кількості проміжних результатів, котрі зберігаються в процесі обчислень. Тому запропоновано ще один метод, який реалізує такий підхід. При цьому n, як і в попередньому методі, записується у вигляді (15) і для кожного , де , формується послідовність чисел x_h за таким правилом: якщо значення _t?i дорівнює 1, то x_h = x_h-1--+--2^t-i. Тоді обчислення v_n,k зводиться до послідовного обчислення , яке здійснюється за формулою (3). Розроблений алгоритм реалізації даного методу.

Аналіз розроблених алгоритмів прискореного обчислення елементу v_n,k показує, що останній алгоритм порівняно з першим є менш складним за кількістю арифметичних операцій, оскільки потребує на кожному кроці обчислень лише k елементів за формулою (3). Однак, перший алгоритм у порівнянні з другим не потребує попередньої процедури обчислень елементів V_k ---послідовності та додаткового використання пам'яті для зберігання цих елементів в процесі роботи алгоритму.

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

Алгоритм 1.

П.1. Задати параметр k.

П.2. Вибрати p.

П.3. Вибрати g₁, g₂, . . ., g_k .

П.4. Опублікувати параметри.

П.5. Приймачу вибрати випадкове число a секретний ключ.

П.6. Приймачу обчислити за модулем p v_a+i,k, .

П.7. Приймачу обчислити за модулем p v_a+i,k, за формулою (4).

П.8. Приймачу обчислити відкритий ключ за модулем p u_a?i,k, за формулою (11).

П.9. Приймачу опублікувати відкритий ключ.

П.10. Передавачу вибрати випадкове число b секретний ключ.

П.11. Передавачу обчислити за модулем p v_b+i,k, .

П.12. Передавачу обчислити за модулем p v_b+i,k, за формулою(6).

П.13. Передавачу обчислити за модулем p u_b-i,k, за формулою (11).

П.14. Передавачу зашифрувати повідомлення M за формулою

y₂ = M ( u_a+b,k mod p),

де u_a+b,k обчислюється за формулою (10).

П.15. Передавачу передати обчислені u_b?i,k, , а також y₂ Приймачу.

П.16. Приймачу дешифрувати повідомлення M за формулою

M = y₂ ( u_b+a,k mod p),

де u_b+a,k обчислюється за формулою (10).

Основними особливостями відомого методу шифрування даних Шаміра є те, що в ньому відсутня необхідність попереднього розподілу секретного та відкритого ключів і процес шифрування складається з трьох етапів передавання даних. З метою прискорення цього методу пропонується така модифікація, яка основана на послідовному використанні спочатку властивості обчислення елементу u_n+m,k, а потім властивості обчислення елементу u_n-m,k. Загальна схема шифрування даних за модифікованим методом Шаміра.

При реалізації запропонованого методу, крім обчислення елементів v_n,k для додатних значень n, необхідно проводити обчислення елементів v_n,k і для від'ємних n. Розроблено два варіанти алгоритмів прискореного обчислення елементу v_n,k для від'ємних n. Розробку алгоритмів проведено аналогічно, як і для додатних n, використовуючи бінарний метод та метод з розкладанням індексу.

Розроблені алгоритми прискореного обчислення елементу v_n,k для будь-яких цілих значень n можуть бути покладені в основу такого алгоритму шифрування інформації за модифікованим методом Шаміра.

Алгоритм 2.

П.1. Задати параметр k.

П.2. Вибрати p.

П.3. Вибрати g₁, g₂, . . ., g_k .

П.4. Опублікувати параметри.

П.5. Передавачу вибрати випадкове число a, а Приймачу випадкове число b.

П.6. Передавачу обчислити за модулем p v_a+i,k, а Приймачу обчислити за модулем p v_b+i,k для .

П.7. Передавачу обчислити за модулем p v_a+i,k, , а Приймачу обчислити за модулем p v_b-k,k за формулою (4).

П.8. Передавачу обчислити за модулем p v_-a+i,k, а Приймачу обчислити за модулем p v_-b+i,k для .

П.9. Передавачу обчислити за модулем p u_a-i,k, , за формулою (11).

П.10. Передавачу обчислити , .

П.11. Передавачу передати , Приймачу.

П.12. Приймачу обчислити за модулем p , за формулою (10).

П.13. Приймачу передати , Передавачу.

П.14. Передавачу обчислити за модулем p , за формулою (14).

П.15. Передавачу передати , Приймачу.

П.16. Приймачу дешифрувати повідомлення M за формулою

,

де y^IV обчислюється за модулем p за формулою (14).

В окремому випадку, коли k = 2, можливий варіант алгоритму, якщо при обчислені елементу u_n?m,2 в пп. 15 та 17 замість формули (14) використовувати формулу (13). Це дозволить уникнути обчислення елементу v_n,2 для від'ємних n в п.8, тим самим виключивши взагалі його з алгоритму. Але складність алгоритму при цьому значно не зменшиться, оскільки замість обчислення елементу v_n,2 для від'ємних n необхідно виконувати в формулі (13) піднесення до степеня за основою g₁, а це майже однаково за складністю.

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

Отримано оцінки складності алгоритмів шифрування інформації за модифікованими методами, які показують таке. Мінімальна оцінка складності алгоритму 1 для кодових блоків відкритого повідомлення Q>100 менша, ніж для відомого приблизно у 10² разів. Максимальна оцінка складності алгоритму 1 для Q>100 майже співпадає з відомим для k=2 і більша, ніж відомого приблизно у 300 разів для k=3. Оскільки для k=2 мінімальна оцінка на багато менша, а максимальна співпадає, то можна очікувати, що середня оцінка алгоритму 1 буде менша, ніж для відомого. Максимальна оцінка складності алгоритму 2 для Q>100 приблизно у 10² разів менша, ніж для відомого, а мінімальна оцінка менша, ніж для відомого приблизно у 10² для розрядності машинної одиниці інформації q=16 та у 10³ для q=32.

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

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

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

Головний модуль містить програмні процедури реалізації дій, що виконують окремо Передавач та Приймач за модифікованими методами Ель-Гамаля та Шаміра. В програмному модулі завдання та вибору параметрів задається параметр k, а також здійснюється вибір модуля p та коефіцієнтів рекурентного співвідношення g_i, . Для вибору параметрів та секретних ключів алгоритмів шифрування інформації потрібні генератори звичайних випадкових та простих випадкових чисел. Програмна реалізація цих генераторів здійснюється в модулі генерування випадкових чисел.

При реалізації модуля обчислення елементів V_k та U_k послідовностей пропонується виділити окремо такі процедури: обчислення за модулем p v_n+i,k, для додатних n; обчислення за модулем p v_n+i,k, для від'ємних n; обчислення за модулем p u_n-i,k, ; обчислення за модулем p u_n+m?i,k, ; обчислення за модулем p u_n-m-i,k, .

При реалізації процедур обчислення за модулем p елементу v_n,k пропонується виділити окремо такі процедури: прискорене обчислення елементу v_n,k для додатних n; прискорене обчислення елементу v_n,k для від'ємних n; обчислення елементу v_n,k за формулою (1); обчислення елементу v_n,k за формулою (4).

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

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

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

Запропоновано універсальний пристрій для виконання обчислень елементів V_k та U_k послідовностей, а саме обчислення за модулем p елементів v_n+i,k, , для додатних значень n, v_n+i,k, , для від'ємних n, а також елементів u_n?i,k, u_n+m?i,k, u_n?m?i,k для .

Для реалізації шифрування (дешифрування) інформації Передавачем (Приймачем) за модифікованим методом Ель-Гамаля запропоновано схему процесора, що наведена на рис. 4.

Для реалізації такого процесору необхідно 4 суматори, один пристрій множення та пам'ять ємністю (H+2)[(Hq+1)(2k-1)+8k+12]+4 машинних одиниць інформації, де H кількість машинних одиниць інформації для зберігання великого числа, q кількість розрядів машинної одиниці інформації. Час шифрування за модифікованим методом Ель-Гамаля на цьому процесорі дорівнює

T_м.ЕГ,ш = QHq(k² + k)T_{мн.Монт.},

де T_{мн.Монт.}----- час множення за модулем за методом Монтгомері, а час дешифрування на цьому процесорі дорівнює

T_м.ЕГ,дш = (Q + Hqk)(k + 1)T_{мн.Монт.}.

Аналіз можливості конвеєрної обробки інформації за модифікованим методом Ель-Гамаля з метою прискорення шифрування інформації показав, що побудувати ефективний конвеєр неможливо.

Порівняння процесорів, що реалізують модифікований та відомий методи Ель-Гамаля показує, що перші потребують більше апаратурних витрат і забезпечують майже однаковий час шифрування дешифрування при k=2 та більший час при k>2. Запропонований процесор для реалізації шифрування за модифікованим методом Шаміра. Структурна схема цього процесору представлена на рис. 5.

Для реалізації процесору шифрування інформації за модифікованим методом Шаміра необхідно 4 суматори, один пристрій множення та пам'ять ємністю (H+2)[2(Hq+1)(2k1)+10(k+1)]+4 машинних одиниць інформації. Час шифрування на цьому процесорі дорівнює

T_м.Ш,ш = (Q + 2Hq)(k² + k)T _{мн.Монт.}.

Запропонований процесор для реалізації дешифрування за модифікованим методом Шаміра. Структурна схема цього процесору представлена на рис. 6.

Для реалізації процесора дешифрування інформації за модифікованим методом Шаміра необхідно 4 суматори, один пристрій множення та пам'ять ємністю (H+2)[2(Hq+1)(2k1)+9k+11]+4 машинних одиниць інформації. Час дешифрування на цьому процесорі дорівнює

T_м.Ш,дш = [Q(k + 1) + Hqk](k + 1)T _{мн.Монт.}.

Аналіз модифікованого методу Шаміра показує, що обчислення та для при шифруванні інформації, а також та M_j1 для при дешифруванні можна виконувати водночас. Це дозволяє при шифруванні (дешифруванні) використовувати два пристрої Пр.VU для побудови процесорів конвеєрного типу. Аналіз розроблених таким чином процесорів показав, що шифрування дешифрування за допомогою цих процесорів буде виконуватись вдвічі швидше, ніж в процесорах, схеми яких наведені на рис. 5 і рис. 6. Порівняння процесорів, що реалізують модифікований та відомий методи Шаміра показує, що перші потребують більше апаратурних витрат, але забезпечують більш ніж у 10² разів для будь-якого k менший час шифрування дешифрування.

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

1. Запропоновані V_k та U_k послідовності. Для даних послідовностей встановлені властивості, які дозволяють здійснювати безпосереднє обчислення елементів послідовності через початкові елементи та прискорене обчислення елементів послідовності. Крім того отримані властивості прискореного обчислювання елементів U_k послідовності через елементи двох послідовностей U_k і V_k та обчислення елементів U_k послідовності тільки через елементи V_k послідовності.

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

3. Запропоновані методи шифрування інформації, які є модифікаціями відомих методів Ель-Гамаля та Шаміра. Суть модифікації полягає в заміні дискретного піднесення до степеня обчисленням елементу U_k послідовності з певним індексом. Показано, що модифіковані методи мають таку ж криптостійкість, як і відомі методи.

4. Розроблено алгоритми шифрування інформації за модифікованими методами. Показано, що алгоритм на основі модифікованого методу Ель-Гамаля має меншу складність обчислень лише для k=2, а алгоритм на основі модифікованого методу Шаміра має меншу складність обчислень для будь-якого k не менше ніж у 10² разів.

5. Розроблено пакет програм та спеціалізовані процесори для шифрування інформації на основі модифікованих методів. Показано, що при програмній реалізації цих методів їх доцільно представити у вигляді набору модулів, що виконують певні обчислювальні процедури. Встановлено, що всі процедури за модифікованим методом Ель-Гамаля виконуються принципово послідовно, тому запропоновано процесор для шифрування, який містить один пристрій для обчислення елементів V_k та U_k послідовностей. В той же час модифікований метод Шаміра дозволяє виконувати певні обчислення, як послідовно, так і паралельно, тому запропоновано по два варіанти процесорів для шифрування та дешифрування інформації. Перший варіант вимагає менше апаратурних витрат, ніж другий варіант, котрий є процесором конвеєрного типу. Проте другий варіант має вдвічі більшу продуктивність, ніж перший варіант.

6. Порівняльний аналіз програмної та апаратної реалізації модифікованих та відомих методів Ель-Гамаля та Шаміра показує, що модифікований метод Ель-Гамаля доцільно реалізовувати тільки програмно, тоді як модифікований метод Шаміра має переваги над відомим методом, як при програмній, так і при апаратній реалізації.

7. Результати дисертаційної роботи впроваджено на МП “ДИНА” та використовуються в навчальному процесі на кафедрі обчислювальної техніки Вінницького державного технічного університету.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

Лужецький В.А., Яремчук Ю.Є. Рекурентні V_k_послідовності // Вісник ВПІ. 1999. №6. С. 53 59.

Лужецький В.А., Яремчук Ю.Є. Про один клас рекурентних послідовностей // Наукові праці Донецького державного технічного університету. Серія "Проблеми моделювання та автоматизації проектування динамічних систем". 1999. № 10. С. 62 70.

Лужецький В.А., Яремчук Ю.Є. Використання рекурентних послідовностей для розповсюдження секретних ключів // Вимірювальна та обчислювальна техніка в технологічних процесах. 1999. №2. С. 168 172.

Лужецький В.А., Яремчук Ю.Є. Метод шифрування даних на основі рекурентних послідовностей // Вестник Харьковского государственного политехнического университета. 1999. № 74. С. 36 42.

Лужецький В.А., Яремчук Ю.Є. Метод шифрування даних без попереднього розподілу ключів на основі рекурентних послідовностей // Моделювання та інформаційні технології. 1999. № 4. С. 77 83.

Яремчук Ю.Е. Проблемы обеспечения безопасности передачи информации в компьютерных системах // Материалы научно-технической конференции с международным участием "Приборостроение 96". Часть 1. Винница Судак. 1996. С.120.

Яремчук Ю.Е. Сравнительный анализ систем аутентификации // Материалы международного симпозиума "Наука и предпринимательство". Винница Львов. 1997. С.74.

Яремчук Ю.Е. Использование рекуррентных последовательностей в системах шифрации информации // Сборник трудов международной научно-технической конференции "Приборостроение 97". Часть 2. ВинницаСимеиз.1997. С.287290.

АНОТАЦІЇ

Яремчук Ю.Є. Методи та засоби шифрування інформації на основі рекурентних послідовностей. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.21 системи захисту інформації. Інститут проблем моделювання в енергетиці НАН України, Київ, 2000.

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

У роботі запропонований новий клас рекурентних послідовностей, при обчисленні елементів яких використовуються рекурентні співвідношення з коефіцієнтами, що пов'язані з початковими елементами послідовностей. Проведено дослідження представників цього класу (V_k та U_k послідовностей) і розроблені два варіанти методів прискореного обчислення елементів V_k послідовності для великих значень індексу елементів.

На основі V_k та U_k послідовностей розроблені методи шифрування інформації, які є модифікаціями відомих методів Ель-Гамаля та Шаміра. Ці методи забезпечують при певних умовах меншу складність обчислень, ніж відомі методи, при такому ж рівні криптостійкості.

Розроблені пакет програм та структури спеціалізованих процесорів для шифрування інформації за модифікованими методами.

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

Yaremchuk Y.E. Information encryption methods and tools on the recurrent sequences basis. Manuscript.

The thesis for obtaining candidate of science degree on the speciality 05.13.21 the information protection systems. The Institute of the problems modeling in the power engineering of the National Academy of Science of Ukraine, Kyiv, 2000. The thesis develops the methods of speed-up information encryption on the basis of recurrent sequences and software - apparatus tools of their realization.

The work suggests the new class of recurrent sequences. When calculating the elements of these sequences, the recurrent ratios with factors that connected with initial elements of the sequences are used. The representative elements of this class (V_k and U_k sequences) has been investigation. Two variants of the methods of V_k sequence element speed-up calculation has been developed for large values of the element indexes.

On the basis of V_k and U_k sequences the methods of information encryption has been developed which are the modification of the known ElGamal and Shamir methods. These methods provide a lower complexity of calculations under certain conditions than the known methods do at the same level of resistance to decryption.

The software and specific processor structures have been developed for information encryption in according with modified methods.

Key words: cryptography, methods of information encryption, recurrent sequences, fast algorithms of calculation, specific processors, the arithmetic of the numbers with large digit position.

Яремчук Ю.Е. Методы и средства шифрования информации на основе рекуррентных последовательностей. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.21 системы защиты информации. Институт проблем моделирования в энергетике НАН Украины, Киев, 2000.

Диссертация посвящена разработке методов ускоренного шифрования информации на основе рекуррентных последовательностей и программно-аппаратных средств их реализации.

В работе предложен новый класс рекуррентных последовательностей, при вычислении элементов которых используются рекуррентные соотношения с коэффициентами, связанными с начальными элементами последовательностей. Впервые предложены рекуррентные последовательности, являющиеся представителями этого класса (V_k и U_k последовательности).

Проведено исследование V_k и U_k последовательностей, в результате которого установлены и доказаны их свойства. К ним относятся свойства, позволяющие осуществлять непосредственное вычисление элементов последовательности через начальные элементы; ускоренное вычисление элементов V_k последовательности (вычисление v_n+m,k и v_{n_m,k}); ускоренное вычисление элементов U_kпоследовательности (вычисление u_n+m,k и u_{n_m,k}) через элементы двух последовательностей U_k и V_k. Кроме этого, установлено и доказано свойство, позволяющее осуществлять ускоренное вычисление элементов U_kпоследовательности только через элементы V_k?? последовательности.

Разработано два варианта алгоритмов для ускоренного вычисления элементов V_k последовательности на основе известного бинарного метода и метода с разложением индекса. Показано, что алгоритм на основе метода с разложением индекса является менее сложным, чем алгоритм на основе бинарного метода, но последний не требует предварительных вычислений элементов V_kпоследовательности и дополнительной памяти для хранения этих элементов в процессе работы алгоритма.

Разработаны методы шифрования информации, которые являются модификациями известных методов Эль-Гамаля и Шамира. Суть модификации основана на замене дискретного возведения в степень вычислением элементов V_k и U_k последовательностей.

В основе модифицированного метода Ель-Гамаля лежит свойство вычисления элемента u_n+m,k, позволяющее вычислить этот элемент, используя элементы и U_k последовательностей, причем сделать это двумя путями: или используя элементы v_m+i,k, , и u_n?i,k, , или используя элементы v_n+i,k, , и u_m?i,k, . Модифицированный метод Шамира основан на последовательном использовании сначала свойства вычисления элемента u_n+m,k, а потом свойства вычисления элемента u_n?m,k. Проведено исследование криптостойкости разработанных методов шифрования, которое показало, что эти методы имеют такую же криптостойкость, как и известные методы.

Разработаны алгоритмы шифрования информации по модифицированным методам. Получены оценки сложности алгоритмов, которые показывают, что алго-ритм на основе модифицированного метода Эль-Гамаля имеет меньшую сложность вычислений лишь для k=2, а алгоритм на основе модифицированного метода Шами-ра имеет меньшую сложность вычислений для любого k не меньше чем в 10² раз.

Разработан пакет программ и специализированные процессоры для шифрования информации на основе модифицированных методов. Показано, что при программной реализации этих методов их целесообразно представить в виде набора модулей, выполняющих определенные вычислительные процедуры. Приведены листинги программного модуля выполнения арифметических операций с большими числами, модуля вычисления элементов V_k и U_k последовательностей, а также главных модулей для реализации модифицированных методов.

Для некоторых применений программная реализация основных модулей является неприемлемой ввиду низкого быстродействия. Для ускорения вычислений разработаны устройства выполнения арифметических операций сложения, вычитания и умножения по модулю с числами большого диапазона. Предложено также универсальное устройство для вычисления элементов V_k и U_k последовательностей, а именно для вычисления по модулю элементов v_n+i,k, , для положительных значений n, v_n+i,k, , для отрицательных n, а также элементов u_n?i,k, u_n+m?i,k, u_n?m?i,k для . Установлено, что все процедуры по модифицированному методу Эль-Гамаля выполняются принципиально последовательно, поэтому предложен процессор для шифрования, который содержит одно устройство для вычисления элементов V_k и U_k ? последовательностей.

В то же время модифицированный метод Шамира позволяет выполнять определенные вычисления, как последовательно, так и параллельно, поэтому предложено по два варианта процессоров для шифрования и дешифрования информации. Первый вариант является процессором с одним устройством для вычисления элементов V_k и U_k последовательностей и требует меньше аппаратурных затрат, чем второй вариант, который является процессором конвеерного типа с двумя устройствами для вычисления элементов V_k и U_k ? последовательностей и имеет вдвое большую продуктивность, чем первый вариант.

Сравнительный анализ программной и аппаратной реализации модифицированных и известных методов Эль-Гамаля и Шамира показывает, что модифицированный метод Эль-Гамаля целесообразно реализовывать только программно, тогда как модифицированный метод Шамира имеет преимущества над известным методом, как при программной, так и при аппаратной реализации.

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

Размещено на Allbest.ru

...