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

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

УДК 621.391.7

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

НА ОСНОВІ РЕКУРЕНТНИХ ПОСЛІДОВНОСТЕЙ

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

Автореферат

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

кандидата технічних наук

Київ 2000

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

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

Міністерства освіти і науки України

Науковий керівник: кандидат технічних наук, доцент

Лужецький Володимир Андрійович

Вінницький державний технічний університет,

доцент кафедри обчислювальної техніки

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

доктор технічних наук, професор Тарасенко Володимир Петрович

Національний технічний університет України "Київський політехнічний інститут",

завідувач кафедри спеціалізованих комп'ютерних систем

кандидат технічних наук, доцент Корченко Олександр Григорович

Національний авіаційний університет,

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

Провідна установа:

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

Захист відбудеться 28 грудня 2000 р. о 1400 годині на засіданні спеціалізованої вченої ради

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

03164, м. Київ, вул. Генерала Наумова, 15

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

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

Вчений секретар

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

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

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

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

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

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

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

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась згідно з планом наукових досліджень Вінницького державного технічного університету.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

vn, k = gk vn 1, k + g1 vn k, k (1)

з початковими значеннями v0,k = 1, v1,k = g2 для k = 2; v0,k = v1,k = . . . = vk3,k = 0, vk2,k = 1, vk1,k = gk для k > 2; де g1 , gk цілі числа; n і k цілі додатні числа називається послідовністю.

Формула (1) описує рекурентну процедуру обчислення елемента vn,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 від’ємних з початковими значеннями v1,k = 0, v2,k = для k = 2; v1,k = 0, v2,k = , v3,k = v4,k = ... = vk,k =0 для k > 2 називається послідовністю.

Формула (4) описує рекурентну процедуру обчислення елементу vn,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. Послідовність чисел, яка складається з послідовності та послідовності називається Vk послідовністю.

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

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

un, k = gk un 1, k + g1 un k, k (8)

при початкових значеннях u0,k = g1, u1,k = g2, u2,k = g3, ... uk1,k = gk; де g1, g2, g3, ..., gk цілі числа; n і k цілі додатні числа називається Ukпослідовністю.

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

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

. (9)

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

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

. (10)

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

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

. (11)

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

. (12)

У випадку, коли треба швидко обчислити значення елементу unm,k використовується властивість елементів послідовності, яка доведена в такій теоремі.

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

. (13)

Властивість (13) встановлює зв’язок між елементами послідовності Uk і , але це є окремий випадок при k=2. Для будь-яких k послідовності Uk притаманна властивість, що доведена в такій теоремі.

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

. (14)

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

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

Процедура шифрування даних за цим методом має вигляд, що представлений на рис. 1.

Рис. 1. Процедура шифрування за модифікованим методом Ель-Гамаля.

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

В зв’язку з цим запропоновано метод обчислення елементу vn,k, який базується на використанні ідеї відомого бінарного методу піднесення до степеня для отримання адитивного ланцюжка

1 = c0, c1, c2, . . . , ct = n.

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

, (15)

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

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

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

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

Алгоритм 1.

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

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

П.3. Вибрати g1, g2, . . ., gk .

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

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

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

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

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

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

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

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

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

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

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

y2 = M ( ua+b,k mod p),

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

П.15. Передавачу передати обчислені ub-i,k, , а також y2 Приймачу.

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

M = y2 ( ub+a,k mod p),

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

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

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

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

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

Алгоритм 2.

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

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

П.3. Вибрати g1, g2, . . ., gk .

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

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

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

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

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

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

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

, .

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

При реалізації модуля обчислення елементів Vk та Uk - послідовностей пропонується виділити окремо такі процедури: обчислення за модулем p vn+i,k, для додатних n; обчислення за модулем p vn+i,k, для від’ємних n; обчислення за модулем p un-i,k, ; обчислення за модулем p un+m-i,k, ; обчислення за модулем p un-m-i,k, .

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

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

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

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

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

Запропоновано універсальний пристрій для виконання обчислень елементів Vk та Uk - послідовностей, а саме обчислення за модулем p елементів vn+i,k, , для додатних значень n, vn+i,k, , для від’ємних n, а також елементів un-i,k, un+m-i,k, un-m-i,k для .

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

Рис.4. Структурна схема процесора шифрування (дешифрування) за модифікованим методом Ель-Гамаля.

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

Tм.ЕГ,ш = QHq(k2 + k)Tмн.Монт.,

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

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

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

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

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

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

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

Tм.Ш,ш = (Q + 2Hq)(k2 + k)T мн.Монт..

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

Рис. 6. Структурна схема процесора дешифрування за модифікованим методом Шаміра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1.

2.

3.

4.

5.

6.

7.

8.

9.

АНОТАЦІЇ

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

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

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

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

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

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

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

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 (Vk- and Uk- sequences) has been investigation. Two variants of the methods of Vk- sequence element speed-up calculation has been developed for large values of the element indexes.

On the basis of Vk- and Uk - 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.

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

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

Проведено исследование Vk и Uk - последовательностей, в результате которого установлены и доказаны их свойства. К ним относятся свойства, позволяющие осуществлять непосредственное вычисление элементов последовательности через начальные элементы; ускоренное вычисление элементов Vk- последовательности (вычисление vn+m,k и vn_m,k); ускоренное вычисление элементов Uk- последовательности (вычисление un+m,k и un_m,k) через элементы двух последовательностей Uk и Vk. Кроме этого, установлено и доказано свойство, позволяющее осуществлять ускоренное вычисление элементов Uk- последовательности только через элементы Vk - последовательности.

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

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

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

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

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

Для некоторых применений программная реализация основных модулей является неприемлемой ввиду низкого быстродействия. Для ускорения вычислений разработаны устройства выполнения арифметических операций сложения, вычитания и умножения по модулю с числами большого диапазона. Предложено также универсальное устройство для вычисления элементов Vk и Uk- последовательностей, а именно для вычисления по модулю элементов vn+i,k, , для положительных значений n, vn+i,k, , для отрицательных n, а также элементов un-i,k, un+m-i,k, un-m-i,k для .

Установлено, что все процедуры по модифицированному методу Эль-Гамаля выполняются принципиально последовательно, поэтому предложен процессор для шифрования, который содержит одно устройство для вычисления элементов Vk и Uk - последовательностей.

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