Персональний сайт В'ячеслава Горчіліна
Всі статті
Опис українського (руського) алгоритму для секретної передачі даних

1. Загальний підхід
Алгоритм заснований на методі перетворення вхідних даних (ВД) по відкритому ключу (ОКЛ), і методі перестановці отриманих в результаті перетворення даних по закритому ключу (ЗКЛ). ОКЛ передається разом з отриманої з ВД закодованої рядком (ЗСТР), а його розташування в ЗСТР обчислюється за алгоритмом з ЗКЛ. Останній відомий тільки передавальної і приймаючої сторони. Отримання ВД з ЗСТР відбувається в зворотному порядку.

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

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

2. Опис алгоритму шифрування даних
2.1 Над ВД проводиться алгебраїчне перетворення за алгоритмом [1]. Це може бути просте підсумовування з ОКЛ', причому ОКЛ' в загальному випадку може бути функцією від ОКЛ, ЗКЛ та інших даних. Робити складні перетворення у цій частині алгоритму не має сенсу, а завданням є маскувати ВД. Отримані дані будемо називати Рядком.

2.2 Далі Рядок перетворюється методом перестановки з утворенням так званих "дірок". Дірки представляють собою місця отриманої після перестановки Рядку, які мають свій порядковий номер, але поки не мають значення. Порядок перестановки і утворення дірок визначає ЗКЛ [2].

2.3 діри, отримані в п2.2, підставляється ОКЛ за алгоритмом [3]. Місця дірок визначає ЗКЛ. Таким чином ЗСТР містить у собі перетворені ВД і ОКЛ.

Схема алгоритма шифрования
Рис.1

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

3.1 З ЗСТР з допомогою ЗКЛ витягується невідомий поки ОКЛ за алгоритмом [4].

3.2 ЗСТР перетворюється методом перестановки за алгоритмом [5]. Отримані дані далі будемо називати Рядком.

3.3 Над Рядком проводиться алгебраїчне перетворення за алгоритмом [6]. В результаті отримуємо ВД. ВД на вході (рис.1 Блок1) і ВД на виході (рис.2 Блок1) еквівалентні.

Схема алгоритма дешифрования
Рис.2

4. Генерування ЗКЛ
ЗКЛ не може бути будь-якою комбінацією символів або чисел, його потрібно генерувати за спеціальним алгоритмом [8]. Причому для кожного блоку (двухблочный приклад на рис.1) він повинен бути унікальним. Генерування проводиться один раз, після чого ЗКЛ видається передавальної та приймаючої сторони, і повинен бути відомим тільки їм.

Реалізація алгоритму — модуль UAcoder | Тестування алгоритму і модуля

[1] Алгебраїчне перетворення передбачає будь-які алгебраїчні дії над даними:
СТ=f(ВД,ОКЛ')
де: СТ — отримана в результаті алгебраїчних перетворень Рядок;
f(ВД,ОКЛ') — алгебраїчна функція від ВД і ОКЛ', при цьому в загальному випадку: ОКЛ'=f(ОКЛ,ЗКЛ,...);
Пример алгебраического преобразования
Рис.3
Приклад алгебраїчного перетворення наведено на рис.3, де ВД рівні ABCDE, а ОКЛ' дорівнює 5F61B. Алгоритм заснований на додаванні двох шестнадцатиразрядных чисел після якого залишається один наймолодший розряд, наприклад: A+5=F C+6=2. В результаті перетворення отримуємо Рядок FA2E9, довжина якої дорівнює довжині ВД.

[2] Ця частина Алгоритму є ключовою і передбачає перестановку Рядки в залежності від ЗКЛ. У результаті перестановки виходить новий Рядок, і утворюються так звані "дірки", в які потім підставляється ОКЛ. Введемо визначення: ВМОНТ — Рядок до перестановки, MID — Рядок після перестановки, i — номер елемента в ВБУД, j — номер елемента в MID, k — номер елемента в ЗКЛ. Елементом рядка будемо називати значення одного символу рядка, має порядковий в ній номер. Всі номери починаємо з нуля.

Алгоритм перестановки наступний. Проводиться послідовний поелементний перебір ВБУД і ЗКЛ. При цьому k=i до того моменту, поки k менше довжини ЗКЛ. Далі k=(i)mod(L), де L — довжина ЗКЛ, тобто просто кажучи рахунок k починаємо з нуля кожного разу, коли k досягає L. Переставляємо i-тий елемент ВБУД в j-тий елемент MID за правилом: j=i+Zk, де Zk — значення k-того елемента ЗКЛ. Після перестановки всій ВБУД ми отримуємо MID довжиною, більшою ніж ВБУД на довжину ЗКЛ мінус одиницю. Це означає, що MID має "дірки" — тобто місця без значень.

Пример перестановки данных
Рис.4
Приклад отримання MID з ВБУД наведено на рис.4, де ЗКЛ дорівнює 2011, а ВБУД дорівнює ABCDEFGH. В результаті перестановок отримуємо MID рівну -BACDFEGH-- , де рисками '-' позначені діри. У загальному випадку число дірок визначається так: ЧД=N-1, де: ЧД — число дірок у рядку, N — основа системи числення. Наприклад, для ЗКЛ складається з чотирьох четырехричных чисел число дірок, в загальному випадку, буде дорівнює трьом.

[3] Алгоритм підстановки ОКЛ в дірки такий. У першу по рахунку зліва направо дірку підставляється перший елемент ОКЛ, у другу другої, і т. д. до тих пір, поки всі дірки не будуть заповнені. Номери дірок шукаються за алгоритмом [7]. У прикладі з [2] (рис.4) це буде виглядати як: -BACDFEGH-- => 5BACDFEGHD0, де ОКЛ дорівнює 5D0.

[4] Алгоритм вилучення ОКЛ з ЗСТР такий. Знаходимо номери дірок за алгоритмом [7], далі звані НД. Витягаємо значення з першого НД, і підставляємо його на місце першого елемента ОКЛ. На місце другого елемента ОКЛ підставляємо значення другого НД, тощо, поки не одержимо всі елементи ОКЛ. Тобто це алгоритм, зворотний алгоритмом [3].

[5] Цей алгоритм перестановки — зворотний алгоритмом [2], тільки в даному випадку ВБУД — відома Рядок на вході, а MID — поки невідома Рядок на виході алгоритму. Створюємо MID з нулів (або будь-яких інших значень) довжиною, рівній довжині ВБУД мінус кількість дірок. Виробляємо послідовний поелементний перебір ВБУД і ЗКЛ. При цьому k=i до того моменту, поки k менше довжини ЗКЛ, а далі k=(i)mod(L). Підставляємо замість i-того елемента ВБУД j-тий елемент MID за правилом: i=j-Zk, де Zk — значення k-того елемента ЗКЛ. Таким чином на виході алгоритму отримуємо MID довжиною, меншою, ніж довжина ВБУД на кількість дірок.

[6] Алгоритм алгебраїчного перетворення повинен бути зворотнім для алгоритму [1].

ВД=f(СТ,ОКЛ')
де: ВД — отримані в результаті зворотних алгебраїчних перетворень дані;
f(СТ,ОКЛ') — така алгебраїчна функція від СТ і ОКЛ, що СТ=f(ВД,ОКЛ'), при цьому в загальному випадку: ОКЛ'=f(ОКЛ,ЗКЛ,...); такий же, як в [1].
Пример обратного алгебраического преобразования
Рис.5
Приклад алгебраїчного перетворення наведено на рис.5. Всі дії обратны дій у прикладі з [1] (рис.1). Потрібно із значення елемента вхідних даних відняти значення елемента ОКЛ (або функції від ОКЛ) методом доповнення. Тобто якщо перше число менше іншого, то до одержуваної різниці додається число, відповідне системі числення (наприклад для шістнадцятковій системи числення — це 16).

[7] Алгоритм знаходження номерів дірок у рядку зводиться до перевірки вільних місць у перших і останніх N-1 номерах рядка. N — основа системи числення ОКЛ (наприклад, для шістнадцятковій системи числення — це 16). У прикладі з [2] (рис.4) це будуть місця: 0,9,10.

[8] Алгоритм генерування ЗКЛ наступний. Створюється порожній масив з 3*N елементів, і порожній рядок з N елементів, де: N — основа системи числення. Генерується перше випадкове число R0 в діапазоні 0..N-1. Робиться перевірка на існування в масиві непустого елемента з номерами: 0+R0 і N+0+R0. Якщо обидва елемента порожні, то число R0 вважається вдало згенерованим, і заноситься в рядок на місце під номером '0', а також заноситься в масив під номерами 0+R0 і N+0+R0. Якщо ж хоча б один з двох перевірених елементів масиву непорожній (тобто вже містить число), то число R0 генерується і перевіряється повторно.

Таким же чином потрібно згенерувати N чисел. У загальному випадку генерується число: Ri, а елементи масиву для перевірки і занесення туди значень: i+Ri і N+i+Ri, де: i — порядковий номер від нуля до N-1. На виході отримуємо рядок з N елементів, яка і дорівнює ЗКЛ.


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

« Назад
2009-2018 © Vyacheslav Gorchilin