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

1. Общий подход
Алгоритм основан на методе преобразования входных данных (ВД) по открытому ключу (ОКЛ), и методе перестановке полученных в результате преобразования данных по закрытому ключу (ЗКЛ). ОКЛ передаётся вместе с полученной из ВД закодированной строкой (ЗСTP), а его расположение в ЗСТР вычисляется по алгоритму с ЗКЛ. Последний известен только передающей и принимающей стороне. Получение ВД из ЗСТР происходит в обратном порядке.

Алгоритм может состоять из одного, или нескольких блоков, в каждом из которых действуют свои открытые и закрытые ключи. Включение нескольких последовательно включённых блоков повышает криптостойкость. На рис.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] Эта часть Алгоритма является ключевой и предполагает перестановку Строки в зависимости от ЗКЛ. В результате перестановки получается новая Строка, и образуются так называемые "дыры", в которые затем подставляется ОКЛ. Введём определение: ВСТР — Строка до перестановки, ПСТР — Строка после перестановки, i — номер элемента в ВСТР, j — номер элемента в ПСТР, k — номер элемента в ЗКЛ. Элементом строки будем называть значение одного символа строки, имеющего порядковый в ней номер. Все номера начинаем с нуля.

Алгоритм перестановки следующий. Производится последовательный поэлементный перебор ВСТР и ЗКЛ. При этом k=i до того момента, пока k меньше длины ЗКЛ. Далее k=(i)mod(L), где L — длина ЗКЛ, т.е. попросту говоря счёт k начинаем с нуля каждый раз, когда k достигает L. Переставляем i-тый элемент ВСТР в j-тый элемент ПСТР по правилу: j=i+Zk, где Zk — значение k-того элемента ЗКЛ. После перестановки всей ВСТР мы получаем ПСТР длиной, большей чем ВСТР на длину ЗКЛ минус единицу. Это означает, что ПСТР имеет "дыры" — т.е. места без значений.

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

[3] Алгоритм подстановки ОКЛ в дыры такой. В первую по счёту слева направо дыру подставляется первый элемент ОКЛ, во вторую второй, и т.д. до тех пор, пока все дыры не будут заполнены. Номера дыр ищутся по алгоритму [7]. В примере из [2] (рис.4) это будет выглядеть как: -BACDFEGH-- => 5BACDFEGHD0, где ОКЛ равен 5D0.

[4] Алгоритм извлечения ОКЛ из ЗСТР такой. Находим номера дыр по алгоритму [7], далее называемые НД. Извлекаем значение из первого НД, и подставляем его на место первого элемента ОКЛ. На место второго элемента ОКЛ подставляем значение второго НД, и т.д., пока не получим все элементы ОКЛ. Т.е. это алгоритм, обратный алгоритму [3].

[5] Этот алгоритм перестановки — обратный алгоритму [2], только в данном случае ВСТР — известная Строка на входе, а ПСТР — пока неизвестная Строка на выходе алгоритма. Создаём ПСТР из нулей (или любых других значений) длиной, равной длине ВСТР минус количество дыр. Производим последовательный поэлементный перебор ВСТР и ЗКЛ. При этом k=i до того момента, пока k меньше длины ЗКЛ, а далее k=(i)mod(L). Подставляем вместо i-того элемента ВСТР j-тый элемент ПСТР по правилу: i=j-Zk, где Zk — значение k-того элемента ЗКЛ. Таким образом на выходе алгоритма получаем ПСТР длиной, меньшей, чем длина ВСТР на количество дыр.

[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-2017 © Vyacheslav Gorchilin