Область наук:

  • Математика

  • Рік видавництва: 2003


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритми безизбиточного кодування перестановок і їх обгрунтування'

    Текст наукової роботи на тему «Алгоритми безизбиточного кодування перестановок і їх обгрунтування»

    ?Надалі передбачається реалізувати оператори циклу з тим, щоб при розрахунку моделі зробити змінним кількість раундів, а також підключити до СВМ підсистему обробки результатів, яка дозволить користувачеві автоматизувати аналіз і обробку результатів обчислень.

    Система візуального моделювання криптоалгоритмів реалізована в Бе1рИ 6 під керуванням операційної системи Windows 98.

    Л.К. Бабенко, Т.А. Мазурова, І.Д. Сидоров, А.Г. Чефранов

    Росія, м Таганрог, ТРТУ

    АЛГОРИТМИ БЕЗИЗБИТОЧНОГО КОДУВАННЯ перестановок ТА ЇХ ОБГРУНТУВАННЯ

    Відомі генератори (алгоритми генерації) псевдовипадкових послідовностей для отримання біжить ключа при потоковому шифруванні. При програмної реалізації найбільш ефективні ті з них, стан яких в поточний момент часу описується перестановкою елементів деякої множини, наприклад ЯС4 або 8оШаге [1].

    В [2] запропоновано один з підходів до генерації наддовгих псевдовипадкових послідовностей на основі ортогональних матриць, отриманих за допомогою алгоритму їх генерації, описаного в [3]. При цьому послідовність утворюється формуванням перестановок комбінацій стовпців згенерованої матриці і записом їх елементів в рядок. В якості початкового стану генератора (зерна) пропонується використовувати деяку вихідну перестановку номерів рядків матриці. Однак при програмної реалізації запропонованого підходу в якості ключа, що формує зерно, зручніше використовувати бітову рядок довільної довжини. Інтерпретуючи бітовий ключ як цілого числа в двійковій системі числення, ми можемо поставити задачу переходу від цілого числа до перестановки таким чином, щоб перестановка залежала від всіх біт ключа. При цьому позначимо безліч, з якого формується перестановка, безліччю А (| А | = п). Для вирішення цієї проблеми пропонується наступний підхід: нумеруються всі можливі перестановки елементів множини А цілими числами від 0 до п! -1. Тоді проблема ефективного кодування вирішується досить просто, так як ключ і являє собою число в двійковій системі числення. Для зручності подальших міркувань покладемо, що безліч А, з якого формуються перестановки, складається з цілих чисел 0..п-1. При цьому не втрачається спільність міркувань, так як елементам будь-якого іншого безлічі можна поставити у відповідність числа з цього інтервалу за допомогою таблиці. Перенумеровувати перестановки природно в тому порядку, в якому вони генеруються. Визначимо генератор перестановок як алгоритм, який видає перестановки елементів заданої множини в порядку, визначеному природою алгоритму.

    Розглянемо два генератора перестановок [4]:

    Генератор перестановок РегшСоіпЙ. Алгоритм працює индуктивно, т. Е. Гарантує отримання всіх перестановок з п елементів, якщо отримані все перестановки з п-1 елементів.

    Опис ітерації алгоритму: є перестановка А1А2 ^ ап-1. Підставляючи п черзі на всі можливі місця, отримуємо п перестановок: па1а2 ^ ап-1, а1па2 ^ ап-1, ..., А1А2 ^ тат-1, А1А2 ^ ап-1п. Застосовуючи алгоритм рекурсивно, отримуємо алгоритм - Нумератор перестановок.

    Приклад: перестановки з 3-х елементів {0,1,2}, отримані алгоритмом РегшСоіпІ

    210 120 102 201 021 012

    2. Генератор перестановок РегшСоіп12. Алгоритм працює индуктивно.

    Опис ітерації алгоритму: є перестановка аіа2 ... ап-ь дописувати справа число до (0 < до < п) і збільшуємо на 1 матеріалів, значення яких > к. Разом отримуємо п перестановок. Застосовуючи алгоритм рекурсивно, отримуємо алгоритм - Нумератор перестановок.

    Приклад: (перестановки з 3-х елементів {0,1,2}, отримані алгоритмом РегшСоіШ2)

    210 201 102 120 021 012

    Однак якщо для кодування перестановки кожен раз перераховувати всі перестановки, то отримаємо тимчасову складність завдання порядку 0 (п!), Що робить задачу нерозв'язною при великих п. Ефективно вирішити цю задачу можна тільки розробивши алгоритми поліноміальної складності.

    Введемо кілька визначень.

    Перестановкою розмірності п назвемо запис

    а0а1 .ап-1, де а1 є 0..п-1, аі = а ^ «і =] .

    Безизбиточним кодом перестановки розмірності п назвемо число 0..п! -1, взаємно однозначно відповідає цій перестановці.

    Відносної записом перестановки назвемо запис виду

    Ь0Ьь..Ьп-ь 0 < Ьі < и,

    де елемент ь1 відповідає вибору на 1-том кроці генератора з безлічі варіантів потужністю 1 + 1, нумерованих 0..1. Для алгоритму РегшСоіШ! Ь1 показує, в яку позицію наявної на 1-том кроці перестановки був вставлений елемент 1. Для алгоритму РегшСоій: 2 ь1 показує, яке число було записано в позицію

    1 наявної на 1-том кроці алгоритму перестановки. З перестановки можна отримати її відносну запис за поліноміальний час. Необхідно тільки знайти, який по порядку вибір зроблений на кожному кроці алгоритму, послідовно «розбираючи» перестановку. Для генератора РегшСоіпІ ми знаходимо, в яку позицію був записаний елемент п-1 - це і буде Іоп-1. Далі ми видаляємо цей елемент і зрушуємо решту перестановки. Знаходячи максимуми, видаляючи і зрушуючи їх, знаходимо Іоп-2,.,'Ь Ь0. Для генератора РегшСоій2 ми дивимося, який елемент був записаний в позицію п-1 - це це і буде Іоп-1. Цей елемент ми відкидаємо і зменшуємо на 1 ті а є {аі} П-25 а > ап-1. Аналогічно отримуємо Іоп-2,.,'Ь Ь0.

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

    п-1 п

    х = Х ь ХП л

    і = 0 Л = і + 2

    0 < Ьі < и

    п

    П = 1

    Л = П + 1

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

    Алгоритм прямого кодування для РегшСоіпЙ.

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

    Вхід: n-розмірність перестановки. a0ai ... an_i - перестановка, отримана PermCountl.

    Вихід: x - номер перестановки в перерахуванні (0 < x < n!).

    Змінні: i - індекс; w-ваговий коефіцієнт; q-множник.

    1 [Ініціалізація] x ^ 0; w ^ l; q ^ n

    2 [Пошук] i ^ 0; Поки аi ^ q-l i ^ i + 1 кц

    3 [Обчислення] x ^ x + (i * w); w ^ w * q; q ^ q-l

    4 [Зміщення] Поки i<q a1 ^ a1 + l; i ^ i + 1 кц

    5 [Вихід] Якщо q = 0 то вихід, інакше крок 2.

    Доведення коректності:

    База індукції: перестановка з 1 елемента 0 повертає x = 0.

    Тіло індукції: припустимо, алгоритм працює коректно для перестановки розмірністю n. Доведемо, що він працює коректно для перестановки розмірністю n + l.

    Кожна перестановка розмірності n служить основою для n + 1 перестановки. Елемент n займає позицію i, яка показує, який за рахунком є ​​дана перестановка серед цих n + 1 перестановок. Ваговий коефіцієнт для всіх інших членів базової перестановки множиться на n + l.

    Тобто xn + l = xn х (n + l) + i; 0 < i < n +1, де xn + l - номер перестановки розмірності n + l, xn - номер перестановки розмірності n, породила перестановку з номером xn + l. Формула показує, що якщо номер xn визначений коректно, то і номер xn + l буде визначений коректно. алгоритм коректний.

    Алгоритм зворотного кодування для PermCountl.

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

    Вхід: n - розмірність перестановки

    x - номер перестановки в перерахуванні (0 < x < n! ).

    Вихід: a0al. an-l - перестановка з номером x у перерахуванні.

    Змінні: i, j - індекси; w-ваговий коефіцієнт; q-множник.

    1 [Ініціалізація] a0, ab ..., an-l ^ 0; w ^ n !; q ^ l

    2 [Обчислення] i ^ x div w; x <- x mod w; q ^ q + l; w ^ w div q

    3 [Зміщення] j ^ q-l; Поки (j > i) aj ^ aj-l j ^ j-l кц; a ^ q-2

    4 [Вихід] Якщо w = 0 то вихід, інакше крок 2.

    Доведення коректності:

    База індукції. Для n = l x = 0 маємо одну перестановку - 0.

    Тіло індукції. Припустимо, алгоритм працює коректно для всіх перестановок розмірності n. Доведемо, що алгоритм коректний для всіх перестановок розмірності n + 1. Перестановка формується за законом xn + l = xn х (n + l) + i; 0 < i < n +1. Аналогічно поводиться алгоритм: ваговий коефіцієнт множиться на n + 1, а i є залишок від ділення на n + 1, тому лежить в потрібних межах. алгоритм коректний.

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

    Для аналізу ємнісний складності знайдемо число знаків, необхідних для подання перестановки, її відносної записи і безизбиточного коду в системі числення з основою s. Для отримання розміру уявлення в бітах і байтах візьмемо відповідно s = 2 або s = 256. Перестановка: n ([lcg n]), де flog, n] - розмір одного знака перестановки, n - загальна кількість знаків.

    26l

    Відносна запис: Г_ | + Ц, де | _1 ° е * г '] +1 "розмір ьтого знака (так

    г = 1

    як 0 < Ьг < г); сума береться по всім 1 = 1..п-1. Перший знак відносної записи завжди 0, тому ми його не враховуємо.

    Безізбиточний код:

    , де п! - загальне число перестановок.

    flog sn!] =

    Звідси випливає, що асимптотична місткість складність уявлень однакова і становить O (n log n). Оцінимо тимчасову складність запропонованих алгоритмів. Зовнішній цикл завжди здійснює n ітерацій. Складність арифметичних операцій пропорційна розміру чисел і становить O (n log n). Час нормалізації частини перестановки пропорційно її розміру і становить також O (n log n). Тоді загальна складність всього алгоритму становить O (n2 log n). Крім запропонованого, існує підхід до кодування перестановок, запропонований в [5], заснований на представленні числа в факторіальною системі числення. Проведена оцінка його складності також дала результат O (n2 log n). Однак даний алгоритм не обгрунтований формально і не розглядається можливість його використання для вирішення поставленого завдання.

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

    Робота підтримана грантами РФФД № 01-07-90211 та 03-07-90075.

    бібліографічний список

    1. Варфоломєєв А. А., Жуков А. А., Пудовкіна М. А. Поточні криптосистеми. Основні властивості і методи аналізу стійкості: Навчальний посібник. М .: ПАІМС, 2000..

    2. Мазурова Т.А., Чефранов А.Г., Бабенко Л.К., Сидоров І.Д. Про різні способи формування псевдовипадкових послідовностей на основі ортогональних матриць. - 8-а Міжнародна конференція «Теорія і техніка передачі, прийому і обробки інформації» ( «Інтегровані інформаційні системи, мережі і технології») «ИИСТ-2002»: Зб. наукових праць. Харків: ХНУ-РЕ.2002, C.580-583.

    3. Мазурова Т.А., Чефранов А.Г. Про генерації ортогональних матриць довільної сили Известия ТРТУ. Спеціальний випуск. Матеріали XLVII НТК. Таганрог: ТРТУ, 2002 № »1, C.8l-82.

    4. Д. Кнут. Мистецтво програмування. Том 1. Основні алгоритми. 3 вид. М, Вільямс, 2001..

    5. Д. Кнут. Мистецтво програмування. Том 2. Получісленние алгоритми. 3 видання. М: Вільямс, 2001..

    О.Б. Макаревич, Т.А. Мазурова, І.Д. Сидоров, А.Г. Чефранов

    Росія, м Таганрог, ТРТУ

    ПРО РЕЗУЛЬТАТИ ТЕСТУВАННЯ ГЕНЕРАТОРА

    Псевдовипадкових послідовностей НА ОСНОВІ ортогональна матриця

    Відомі синхронні потокові криптосистеми, в яких кожен біт відкритих даних підсумовується по модулю 2 з біжучим ключем, в якості якого використовується псевдослучайная послідовність [1]. У кріптосхеми, реалізованих програмно, часто використовуються генератори на основі перестановок, які керують виводом, наприклад RC4 [2]. Відомі також і широко використовуються ортогональні матриці [3] (orthogonal arrays - OA). Під ОА з параметрами L, f, t розуміється прямокутна таблиця з Lt рядками, f стовпцями, елементи якої

    г = 1

    i = 1


    Завантажити оригінал статті:

    Завантажити