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

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

УДК 681.3.06:519.248.681

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

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

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

Гріненко Тетяна Олексіївна

Харків - 2011

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

Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки, молоді та спорту України.

Науковий керівник: доктор технічних наук, професор Горбенко Іван Дмитрович, завідувач кафедри безпеки інформаційних технологій Харківського національного університету радіоелектроніки.

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

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

кандидат технічних наук, доцент Єсін Віталій Іванович, Харківський національний університет імені В.Н. Каразіна, доцент кафедри безпеки інформаційних систем і технологій факультета комп'ютерних наук.

Захист відбудеться «07» червня 2011 р. о 13-00 годині на засіданні спеціалізованої вченої ради К 64.052.05 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14; т. (057) 7021-016.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки (просп. Леніна, 14).

Автореферат розісланий «05» травня 2011 р.

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

Загальна характеристика роботи

Актуальність теми. Якість надання послуг з криптографічного захисту інформації (КЗІ) в суттєвій мірі визначається методами, механізмами та протоколами управління та сертифікації ключів. Основоположними вимогами, що висуваються до протоколів управління та сертифікації ключів є необхідність генерування ключів та ключової інформації, а в деяких системах і загальних параметрів випадково, рівноймовірно, незалежно та однорідно. Нині при створенні криптографічних систем використовуються по суті два засоби генерування ключів - не детерміновані генератори випадкових послідовностей (бітів) (НГВП) та детерміновані генератори випадкових послідовностей (бітів) (ДГВП). До ДГВП висуваються вимоги в частині забезпечення необхідного періоду повторення послідовності, захищеності від компрометації ключів та ключової інформації, нерозрізнюваності псевдовипадкової послідовності від фізично випадкової, необоротності тощо. Проведені дослідження показали, що ДГВП, які рекомендуються в міжнародних та регіональних стандартах, мають ряд недоліків та обмежень. Основними з них є недостатня швидкодія, обмежений алфавіт, відсутність суворого доведення необоротності та непередбачуваності тощо.

В Україні на етапі гармонізації знаходиться міжнародний стандарт ISO/IEC 18031. Тому важливими та актуальними є задачі аналізу стану питання, дослідження властивостей та розробки нових методів генерування псевдовипадкових послідовностей (ПВП), які б задовольняли вимогам відносно рівня гарантій безпеки. Перспективними, в цьому напрямку, є ДГВП, що будується на основі використання криптографічних перетворень в групі точок еліптичних кривих (ЕК) над полем Галуа з заданим періодом повторення та відображенням точок в ПВП з використанням функцій гешування, який дозволяє будувати ПВП, в тому числі з вищим рівнем гарантій К4 або Р2, а також ДГВП на основі багатомодульних криптографічних перетворень над полями Галуа, який дозволяє генерувати ПВП згідно встановленого ключа генератора з довільною основою алфавіту m, заданим періодом повторення та заданими нерозрізнюваністю, необоротністю і непередбачуваністю.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках держбюджетних науково-дослідних робіт «Розроблення державних стандартів у сфері криптографічного захисту інформації, проведення роботи, спрямованої на гармонізацію міжнародних стандартів» (Шифр «Гармонія»), № 390 (№ держреєстрації 0198U004445) «Розробка політики та концепції побудови захищених інформаційних технологій, розробка та дослідження методів та математичних моделей обробки та захисту інформації в системах та мережах», № 125-1 (№ держреєстрації 0101U005125) «Дослідження та розробка перспективних технологій криптографічного захисту інформації в телекомунікаційних системах і мережах», № 163-1 «Дослідження та розробка перспективних криптографічних систем та протоколів захисту інформації в телекомунікаційних системах та мережах України», № 203-1 (№ держреєстрації 0106U006221) «Обґрунтування вимог, розроблення та впровадження інфраструктури електронного цифрового підпису в МОНУ», № 237-1 (№ держреєстрації 0109U002573) «Напрями, методи та засоби удосконалення та розвитку національної інфраструктури відкритих ключів (включаючи систему електронного цифрового підпису)»; а також в держбюджетних НДР № 08-15 «Дослідження та оптимізація інфраструктур з відкритими ключами на ідентифікаторах», № 07-04 «Аналіз стану створення ІВК в технічно розвинутих державах та обґрунтування напрямків дослідження», у яких здобувач був виконавцем, та № 06-15 «Дослідження перспектив розвитку криптографічних засобів захисту інформації», у якій здобувач був відповідальним виконавцем.

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

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

1. Аналіз методів побудування ПВП та ДГВП, обґрунтування вимог до генераторів ПВП в частині рівнів гарантій (непередбачуваності, нерозрізнюваності, необоротності), механізмів та порядку вироблення і застосування ключів генераторів, стійкості проти атак «повного розкриття» та періоду повторення ПВП, що генерується.

2. Аналіз існуючих та розробка комплексної методики дослідження ПВП, що формуються ДГВП, а також інструментальних засобів тематичних досліджень ПВП з використанням методик, що засновані на стандартах США FIPS - 140-1, FIPS 140-2, FIPS 140-3, директиві Німеччини AIS 20 та NIST STS 800-22.

3. Розробка методу і алгоритмів побудови ДГВП на основі використання криптографічних перетворень в групі точок ЕК над простими і розширеннями полів Галуа та застосування стійких до колізій функцій гешування, використання якого дозволить формувати ПВП з необхідними властивостями, та який відповідав би вимогам гарантій класу К4 AIS 20 в частині необоротності, непередбачуваності та нерозрізнюваності.

4. Удосконалення методу побудови ДГВП на основі багатомодульних криптографічних перетворень в кінцевих полях Галуа, використання якого дозволить генерувати ПВП з довільною основою алфавіту, заданим періодом повторення, структурною скритністю, стійкістю проти атаки «повне розкриття» (необоротністю).

5. Аналіз існуючих, розроблення та доведення нових положень теорії побудування ДГВП на основі багатомодульних перетворень в кінцевих полях, що пов'язані з удосконаленням та розвитком теорії генераторів багатомодульних перетворень.

6. Обґрунтування переліку можливих криптоаналітичних атак на розроблені методи генерування ПВП у залежності від рівня порушника та оцінка захищеності від них, за умови застосування ДГВП у криптографічних примітивах та протоколах.

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

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

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

Методи досліджень. При виконанні дисертаційної роботи використовувалися наступні методи: теорії полів і груп Галуа при побудові ДГВП; теорії складності обчислень при оцінці часових характеристик виконання операцій під час генерації ПВП; теорії ймовірностей та математичної статистики при визначенні ймовірності виникнення колізій; практичної криптографії та системного аналізу при порівнянні існуючих ДГВП; програмного моделювання при реалізації процесів генерування ПВП.

Наукова новизна одержаних результатів. У роботі одержано такі нові наукові результати.

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

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

3. Вперше сформульовано та доведено ряд аналітичних співвідношень, які дозволили обґрунтувати вимоги до загальносистемних параметрів ЕК та оцінити рівні гарантій (непередбачуваності, нерозрізнюваності, необоротності), а також дозволили оцінити кількісні показники криптографічної стійкості проти криптоаналітичних атак на ДГВП в залежності від рівня порушника.

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

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

1. Запропонований метод генерування ПВП, що ґрунтується на перетвореннях в групі точок ЕК, допускає програмну, апаратно-програмну та апаратну реалізації, з використанням яких забезпечується генерування ПВП з необхідним рівнем гарантій, в тому числі К4. Дослідження, що стосуються цього методу генерування ПВП на ЕК, використані в ході виконання згідно Постанови Кабінету Міністрів НДР «Гармонія» при гармонізації міжнародного стандарту ISO/IEC 18031 в Україні (Акт впровадження).

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

3. Отримано ряд аналітичних співвідношень, які дозволяють зробити оцінки стійкості ДГВП проти атак «повне розкриття», непередбачуваності та захищеності від колізій, а також обґрунтовані вимоги до загальносистемних параметрів ЕК, які застосовуються в генераторі (Акт впровадження).

4. Отримано ряд аналітичних співвідношень, які дозволяють зробити оцінки періоду повторення ПВП, необоротності та нерозрізнюваності, які використані в НДР «Гармонія» при дослідженні та проектуванні ДГВП (Акт впровадження).

5. Розроблені комплекси програмного забезпечення (програмні моделі) ДГВЧ та ДГВБ дозволяють провести їх дослідження та тестування на різних етапах їх життєвого циклу, включаючи дослідження, тестування, інсталяцію та використання при жорстких вимогах відносно рівнів гарантій, які повинні бути забезпечені в криптографічних додатках та механізмах (Акт впровадження).

6. Розроблений комплекс програмних, апаратно-програмних засобів дозволяє формувати ПВП і ВП потрібного періоду повторення з урахуванням вимог і обмежень на складність його реалізації (продуктивність функціонування). Комплекс програмних засобів застосовується в навчальному процесі ХНУРЕ при виконанні трьох лабораторних робіт в курсі «Основи теорії захисту інформації» (Акт впровадження).

7. Удосконалено методику дослідження властивостей ПВП, що може бути застосована для тестування ПВП при проектуванні, створенні та оцінці існуючих ДГВП, оперативного тестування працездатності ДГВП під час експлуатації, а також детального тестування (Акт впровадження).

Особистий внесок здобувача. В роботах, що написані в спiвавторствi, автору належить: [1] - практичні дослідження атак на еліптичні криві, що реалізовані на основі -методу та -методу Поларда; [2] - розробка та опис методу генерування псевдовипадкових послідовностей на ЕК; [3] - розробка та опис удосконаленого методу генерування псевдовипадкових послідовностей на ЕК; [4] - порівняльний аналіз сучасних методик тестування псевдовипадкових послідовностей; запропонована методика статистичного тестування генераторів випадкових послідовностей; [5] - аналіз та обґрунтування вимог до генераторів випадкових чисел, що використовують детерміновані методи згідно NIST SP 800-90; [6] - аналіз та дослідження ДГВБ на еліптичній кривій, що запропонований в стандарті ISO/IEC 18031; [7] - розробка удосконаленого методу генерування псевдовипадкових послідовностей на основі багатомодульних перетворень в розширеннях поля Галуа; доведення у вигляді тверджень і теорем необхідних та достатніх умов існування багатомодульного перетворення; [8] - аналіз властивості необоротності [1-8].

Апробації результатів дисертації. Основні результати досліджень, що проведені в дисертаційній роботі, доповідалися на наступних конференціях:

- 4-му, 10-му, 12-му міжнародному молодіжному форумі «Радiоелектронiка i молодь у XXI сторiччi» (м. Харків, 2000 р., 2006 р., 2008 р.);

- V, IX, X, XI, XII міжнародній науково-практичній конференції «Безпека iнформацiї в iнформацiйно-телекомунiкацiйних системах» (м. Київ, 2002 р., 2006 р., 2007 р., 2008 р., 2009 р.);

- 1-й, 2-й, 3-й міжнародній науковій конференції «Сучасні інформаційні системи. Проблеми та тенденції розвитку» (Харків, 2006 р., 2007 р., 2008 р.);

Публікації. За результатами дисертаційної роботи опубліковано 8 статей в 8 фахових виданнях, що входять до переліків, затверджених ВАК України, 11 матеріалів і тезисів наукових конференцій.

Структура та обсяг дисертації. Дисертація складається із вступу, п'яти розділів і висновків, має загальний обсяг 243 сторінки, з яких 167 сторінок основного тексту, містить 25 рисунків, 29 таблиць, список використаних джерел із 159 найменувань на 17 сторінках та 9 додатків.

Основний зміст роботи

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

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

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

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

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

У другому розділі дисертаційної роботи обґрунтовано, що генератори ПВП, залежно від умов й етапів використання, можуть аналізуватися із трьома рівнями деталізації. Найбільш повний рівень деталізації повинен здійснюватися в процесі проектування, тематичних і сертифікаційних досліджень генераторів. Він повинен містити в собі залежно від прийнятого рівня угоди мінімальне число незалежних тестів. При щоденних або сеансових запусках генератора він може тестуватися з використанням декількох незалежних тестів. У якості базового для цих цілей найбільше підходить методика США FIPS PUB 140-1. Третій рівень деталізації аналізу послідовностей рекомендується використовувати періодично або при кожному звертанні до ДГВП із метою формування з його використанням ключів.

Одним із важливих та необхідних напрямків досліджень та практичних робіт при створенні ефективних ГВП є розробка методів та засобів оцінки як самих генераторів, так і статистичних властивостей випадкових послідовностей. Статистичні показники мають вагомий вплив на загальну оцінку ефективності ГВП. Результати проведеного аналізу існуючих методик статистичного тестування ГВП показали, що на цей час найбільш доведеними та практичними до використання методиками є NIST STS, FIPS PUB 140-1, FIPS PUB 140-3, AIS 20 та AIS 31. Проведені дослідження показали, що більш детальними є вимоги та механізми тестування, що визначені в методиці тестування AIS 20, яка представляє критерії для оцінки ДГВП та дозволяє реалізувати різні функціональні класи - К1, К2, К3, К4. Класи функціональності К1-К4 описують набір ієрархічних вимог до ДГВП, які виражені на рівні технічних властивостей.

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

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

, де , (1)

, де . (2)

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

. (3)

Вирази (1) та (2) задають способи рекурентного генерування ПВП.

У випадку (1) одержуємо послідовність значень шляхом багаторазового підсумовування точки й базової точки , причому задається згідно (3) через секретний ключ генератора. У випадку (2) отримуємо шляхом скалярного множення точки на число a, причому а залежить від секретного ключа d₀. У цьому випадку виникає питання вибору а, воно може бути секретним ключем генератора, або генеруватись певним чином, наприклад як у нашому випадку , де - функція перетворення точки в число. В цьому випадку ми одержуємо

. (4)

Для обох методів побудову ПВП можна виконати декількома способами:

, якщо , (5)

, якщо , (6)

, якщо , (7)

, якщо , (8)

, якщо . (9)

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

. (10)

Структурні схеми алгоритмів, що реалізують наведені вище методи генерування ПВП наведені на рис. 1-2.

Рис. 1. Детермінований ГВП у групі точок ЕК (згідно методу (1))

Рис. 2. Детермінований ГВП у групі точок ЕК (згідно методу (2))

Даний метод забезпечує необхідний рівень непередбаченості, необоротності, нерозрізнюваності, а також найвищий рівень гарантій К4 згідно AIS 20. У випадку застосування правила (10) задача оцінки необоротності генератора у цілому по суті зводиться до послідовного вирішення двох задач - знаходження по відомому виходу генератора (геш - значення) його прообразу, а потім по відомому прообразу вирішення задачі дискретного логарифмування в групі точок ЕК з визначенням секретного ключа генератора. ДГВП, що ґрунтується на використанні, як скалярного множення на ЕК, так і гешування, має складність обернення більшу ніж атака груба сила. Це означає, що для цього методу атака типу груба сила є найбільш ефективною з точки зору криптоаналітика.

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

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

2. Нехай на виході генератора ПВП, що наведена на рис. 2, із множини значень формуються k випадкових геш-значень, причому і ймовірність появи підкоряється рівноймовірному закону розподілу. За вказаних умов необхідно знайти ймовірність P(n,k) того, що ці безлічі містять в собі хоча б по одному елементу i , такі, що .

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

Ймовірність того, що безлічі містять в собі хоча б по одному елементу і такі, що , можна оцінити, використовуючи -метод. Ймовірність того, що в двох множинах X і Y хоча б по одному елементу співпадуть визначимо як: генерування криптоаналітичний еліптичний

. (11)

Так як зроблено висновок, що при реальних значеннях та практично обмежень на величину не має.

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

Генерування псевдовипадкових чисел на основі багатомодульного перетворення елементів поля Галуа відбувається таким чином.

1. Ввести або генерувати загальносистемні параметри та , де - просте число, а - первісний елемент поля відповідного розміру.

2. Ввести або інсталювати параметр генератора (ключ), .

3. Обчислити початкове значення генератора , використовуючи правило

, (12)

де - основний модуль перетворення.

4. Обчислити елемент ДГВЧ, використовуючи правило

, . (13)

5. Обчислити елемент послідовності , що генерується,

, (14)

де , , .

6. Обчислити елемент послідовності , що генерується,

, (15)

де - проміжні модулі, і виконується вимога .

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

. (16)

Схема алгоритму, що реалізує наведений вище метод генерування ПВП, наведена на рис. 3.

Рис. 3. Детермінований ГВП багатомодульного перетворення

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

Теорема 1. Детермінований ГВЧ, що функціонує згідно багатомодульного перетворення на основі алгоритму забезпечує генерування псевдовипадкових символів (цілих чисел) з періодом повторення , рівноймовірно і з певною основою алфавіту , за умови, що , а .

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

Твердження 1. Детермінований ГВЧ, що функціонує згідно алгоритму

, (17)

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

Твердження 2. Детермінований ГВЧ, що функціонує згідно алгоритму

, (18)

де K₀+i є плинний ключ генератора, причому K₀ є початковим ключем, а i - ключем сеансу, є необоротним зі складністю не нижче, ніж О(n).

Теорема 2. Детермінований ГВЧ, що функціонує згідно трьохмодульного перетворення за правилами

(19)

(20)

при виконанні умов , , забезпечує генерування ПВП (символів) з певною основою алфавіту m, періодом повторення , рівноймовірною появою символів на періоді та ансамблем ізоморфізмів .

Генерування ПВП на основі багатомодульного перетворення.

1. Ввести або генерувати загальносистемні параметри - кортежі загальних параметрів згідно вимог твердження 1.

2. Ввести або інсталювати таємний ключ генератора , .

3. Обчислити початкове значення генератора , використовуючи правило

, (21)

де - основний модуль перетворення.

4. Обчислити елемент генератора, використовуючи правило

. (22)

5. Обчислити елемент ДГВЧ, використовуючи правило

(23)

де .

6. Обчислити елемент ДГВЧ, використовуючи правило

, (24)

де - номер елемента ПВП, що генерується, - проміжні модулі.

7. Якщо потрібно, то обчислити -е геш-значення від та прийняти його в якості -го випадкового слова, тобто

. (25)

Схема алгоритму, що реалізує наведений вище метод генерування ПВП, наведена на рис. 4.

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

Рис. 4. Схема алгоритму генерування ПВП у скінченному полі порядку методом багатомодульного перетворення

В п'ятому розділі дисертаційної роботи зроблено порівняння швидкості генерування ПВП (бітів) запропонованих методів зі швидкістю генерування існуючих ДГВП (табл. 1).

Таблиця 1 Оцінка швидкості генерації ПВП різними алгоритмами (Мб/сек)

Функція гешув. Вид ДГВП	Без гешування	SHA-1	SHA-256	SHA-384	SHA-512
ДГВП БМП в	0,1	8,3	10,4	11,4	12,7
ДГВП БМП в	0,003	0,052	0,089	0,131	0,173
ДГВП згідно ДСТУ 4145-2002 для Х9.17	4,3	-	-	-	-
ДГВП на ЕК згідно ISO/IEC 18031	2,0	-	-	-	-
ДГВП на ЕК в	4,45	3,74	5,98	7,61	10,14
ДГВП на ЕК	max 57,6/ min 0,001				max 12,8/ min 0,002

Аналіз даних табл. 1 показує, що ДГВП багатомодульного перетворення в та ДГВП на ЕК у простому полі мають значні переваги по відношенню до дозволеного для використання в додатку А в ДСТУ 4145 - 2002, якщо використовується функція гешування. Наприклад, для SHA-512 виграш у швидкодії складає приблизно в 2,5 - 3 рази. Проведений аналіз показав, що складність (швидкість) функціонування ДГВП на ЕК залежить від обраного методу й способу формування ПВП. Мінімальна складність досягається для методу (1) і способу формування ПВП (9). У цьому випадку за один крок ДГВП формується псевдовипадкове число трикратної довжини.

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

Результати статистичних досліджень розроблених ДГВП з використанням розробленої в другому розділі методики тестування підтвердили високий рівень вихідних даних, що ними генеруються (рис. 5-7).

Рис. 5. Результати тестування ДГВП в групі точок ЕК

Рис. 6. Результати тестування ДГВП багатомодульного перетворення в

У табл. 2 наведено дані з проходження тестів розроблених ДГВП за Правилом 1 згідно методики NIST SP 800-22 у порівнянні із класичним генератором BBS.

Таблиця 2 Дані з проходження ДГВП тестів

Генератор	Кількість тестів, в яких тестування пройшли більше 99% послідовн.	Кількість тестів, в яких тестування пройшли більше 96% послідовн.
BBS	134 (70,8%)	189 (100%)
ДГВП на ЕК	138 (73,0%)	189 (100%)
ДГВП БМП в	143 (75,6%)	189 (100%)
ДГВП БМП в	139 (73,5%)	189 (100%)

Рис. 7. Результати тестування ДГВП багатомодульного перетворення в

Висновки

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

В теоретичному плані отримано.

1. Метод побудування ДГВП та його математичну і програмну модель на основі використання криптографічних перетворень в групі точок ЕК над полем Галуа, який дозволяє будувати ПВП з вищим рівнем гарантій К4 або Р2.

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

3. Отримані аналітичні співвідношення для обґрунтування вимог і оцінки рівнів гарантій та оцінки стійкості проти криптоаналітичних атак на детерміновані генератори ПВП в залежності від рівня порушника.

4. Ряд теоретичних положень та аналітичні співвідношення оцінки властивостей ДГВП на основі багатомодульних перетворень над полями Галуа в залежності від вимог відносно необхідного рівня гарантій генератора.

В практичному плані отримано.

1. Запропонований метод генерування ПВП, що ґрунтується на перетвореннях групі точок ЕК, забезпечує генерування ПВП з необхідним рівнем гарантій згідно AIS 20.

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

3. Отримані аналітичні співвідношення оцінки стійкості ДГВП проти атак «повне розкриття», непередбачуваності та захищеності від колізій, а також обґрунтовані вимоги до загальносистемних параметрів ЕК, які застосовуються в генераторі.

4. Отримані аналітичні співвідношення оцінки періоду повторення, нерозрізнюваності та необоротності, які використані в процесі досліджень та при проектуванні ДГВЧ та ДГВБ.

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

Результати досліджень використані в НДР «Гармонія» при гармонізації міжнародного стандарту ISO/IEC 18031 в Україні та в навчальному процесі.

Публікації за темою дисертації

1. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривых / [М.Ф. Бондаренко, И.Д. Горбенко, Е.Г. Качко та ін.] - Радиотехника. Всеукраинский межведомственный научно-технический сборник.- 2000. - Вып. 114. - С. 15-24.

2. Гриненко Т.А. Метод формирования и свойства псевдослучайных последовательностей на эллиптических кривых / Гриненко Т.А., Горбенко Ю.И., Орлова С.Ю. - Радиотехника: Всеукраинский межведомственный научно-техн. сб. - 2001. - Вып.119. - С. 119-123.

3. Т.А. Гриненко. Методы формирования псевдослучайных последовательностей в группах точек эллиптических кривых / Т.А. Гриненко, С.И. Збитнев, Д.В. Мялковский - Радиотехника: Всеукр. межвед. науч.-техн. сб. - 2002. - Вып. 126. - С. 115-122.

4. Гріненко Т.О. Методики та засоби тестування послідовностей випадкових чисел та особливості їх застосування / Гріненко Т.О., Горбенко І.Д. - Прикладная радиоэлектроника. Научно-техн. журнал. Харьков. - 2006. - Том 5, №1. - С. 115-126.

5. Т.О. Гріненко. Аналіз детермінованих генераторів псевдовипадкових бітів / Т.О. Гріненко, Н.В. Шапочка - Прикладная радиоэлектроника. Научно-техн. журнал. Харьков. - 2007. - Том 6, №2. - С. 300-305.

6. Гріненко Т.О. Дослідження властивостей генераторів псевдовипадкових бітів на еліптичній кривій на відповідність міжнародному стандарту ISO/IEC 18031 / Гріненко Т.О., Погребняк К.А. - Прикладная радиоэлектроника. Научно-техн. журнал. Харьков. - 2009. - Том 8, № 3. - С. 372-376.

7. Т.О. Гріненко. Метод генерування псевдовипадкових послідовностей на основі багатомодульних перетворень в скінченних полях / Т.О. Гріненко, Ю.І. Горбенко - Прикладна радіоелектроніка: наук.-техн. журнал. Харьков. - 2011. - Том 10. № 1. - С. 82-85.

8. Гріненко Т.О. Властивості та перспективи застосування генераторів псевдовипадкових послідовностей на еліптичних кривих / Гріненко Т.О., Горбенко Ю.І., Мордвінов Р.І. - Системи обробки інформації. ХУПС. - 2011. - Вип. 2(92). - С.76-80.

Анотація

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

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

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

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

Ключові слова: псевдовипадкова послідовність, детермінований генератор випадкових послідовностей, необоротність, нерозрізнюваність, непередбачуваність.

Аннотация

Гриненко Т.А. Методы и средства генерирования псевдослучайных последовательностей произвольного алфавита для криптографических приложений с использованием циклических групп и хеширования. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.21 - Системы защиты информации. - Харьковский национальный университет радиоэлектроники, Харьков, 2011.

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

Разработан метод генерирования псевдослучайных последовательностей, основанный на преобразованиях в группе точек эллиптических кривых, который допускает программную, аппаратно-программную и аппаратную реализации. Данный метод обеспечивает генерирование псевдослучайных последовательностей с необходимым уровнем гарантий в части непредсказуемости, необратимости и неразличимости, а также наивысший уровень гарантий согласно AIS 20. В результате анализа основных положений существующей теории многомодульных преобразований в диссертационной работе сформулированы и доказаны новые положения и теоремы, связанные с усовершенствованием и развитием теории генераторов многомодульных преобразований в конечных полях Галуа. Усовершенствован метод генерирования псевдослучайных чисел на основе многомодульного криптографического преобразования в полях Галуа путем ввода ключа генератора и применения функции хеширования, который позволяет генерировать псевдослучайные последовательности с произвольным алфавитом, заданным периодом повторения и заданными в прикладных криптографических приложениях требованиями непредсказуемости, неразличимости и необратимости. В работе получены аналитические соотношения, которые позволяют сделать оценки устойчивости детерминированных генераторов случайных последовательностей к атакам «полное раскрытие», непредсказуемости и защищенности от коллизий, а также позволяют сделать оценки периода повторения псевдослучайной последовательности, необратимости и неразличимости. Предложенный математический аппарат позволяет сделать оценки вероятностей возникновения коллизий хеш-значений точек эллиптических кривых, а также выбирать длины хеш-значений. Найдено ограничение на число символов псевдослучайной последовательности, которые могут генерироваться на одном и том же ключе. Обоснованы требования к общесистемным параметрам эллиптических кривых, применяемых в генераторе псевдослучайных последовательностей.

Результаты, полученные в ходе выполнения диссертационной работы, использованы в НИР «Гармония» при гармонизации международного стандарта ISO/IEC 18031 в Украине и в учебном процессе по дисциплинам «Основы теории защиты информации», «Криптографические системы и протоколы» и «Технологии создания систем защиты информации».

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

Abstract

Grinenko T.O. Methods and tools for generating of pseudo-random sequences over arbitrary alphabet for cryptographic applications using cyclic groups, and hashing. - Manuscript.

Thesis for the degree of candidate of technical sciences on the speciality 05.13.21 - Information Security Systems. - Kharkiv National University of Radio Electronics, Kharkiv, 2011.

The dissertation is devoted to the development and improvement of methods and tools of pseudorandom sequences generation for cryptographic applications.

It is developed a method for generating of pseudo-random sequences based on transformations in the group of points on elliptic curves, which allows pseudorandom sequences generation with the necessary assurance level. There is improved a method of random numbers generation based on a multimodal cryptographic transformation in Galois fields, which allows generation of pseudorandom sequences over arbitrary alphabets, a given period of repetition and requirements to unpredictability, indistinguishability and irreversibility specified in applied cryptographic applications. A number of analytical relations is obtained that allow estimation of the deterministic random sequence generators stability to the attack of "full disclosure", unpredictability and collision protection, as well as estimation of the pseudorandom sequence repetition period, irreversibility and indistinguishability.

Key words: pseudo-random sequence, deterministic random sequences generator, irreversibility, indistinguishability, unpredictability.

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

...