Теория

ShareKey — авторский экспериментальный алгоритм обмена криптографическими ключами (вычисления общего ключа), в котором вместо операций над числами большой разрядности (например, 256-битными) выполняются операции над массивами небольших чисел (32- или 64-битных). Подобно алгоритму Диффи-Хеллмана, основанному на свойстве возведения в степень (a^b)^c = (a^c)^b, в ShareKey реализована функция (назовём её Func), обладающая теми же свойствами: Func(Func(a, b), c) = Func(Func(a, c), b). Только в данном случае a, b и c являются не числами, а массивами.

С учётом свойств функции Func вычисление общего ключа также похоже на реализованное в алгоритме Диффи-Хеллмана:

A = Func(g, a);
B = Func(g, b);
K = K1 = K2 = Func(A, b) = Func(B, a);

где g, A и B передаются открыто, в то время как a и b являются секретными.

Функция Func

Функция Func является ключевой особенностью алгоритма и её идея взята из реализации побитового умножения двух чисел. Для понимания сути рассмотрим для начала умножение 8-битных чисел A = g * a. В 16-битный результат A нужно изначально записать 0, а 8-битное g скопировать в 16-битное G (его старшие 8 битов должны быть заполнены нулями). Само умножение выполняется путём прибавления G к A, если очередной бит a равен 1 (если 0 — прибавление не выполняется) и смещения всех битов G на одну позицию влево. В таком виде умножение обладает свойствами g * a = a * g и (g * a) * b = (g * b) * a.

Замечено, что если оставить A и G 8-битными, а обычные сдвиги G заменить циклическими, то в реализованном в таком виде «умножении» не выполняется условие g * a = a * g, но продолжает выполняться (g * a) * b = (g * b) * a. Это условие продолжает выполняться и в случае, если вместо числа g из восьми бит оперировать массивом g из 8 чисел g0..g7, а сложение выполнять поэлементно: Ai = Ai + gi (i меняется от 0 до 7). Причём число a остаётся 8-битным.

На этом свойстве и основана функция Func, в которой вычисление A = Func(g, a) выполняется путём прибавления к числам массива A чисел массива g (если очередной бит a равен 1) и циклического смещения всех элементов массива g. В показанном на рисунке 1 примере в результате вычисления массива A он будет содержать следующие значения: A0 = g1+g4+g5+g7, A1 = g2+g5+g6+g0, A2 = g3+g6+g7+g1 и так далее.

Преимущество такой схемы в том, что её легко адаптировать к секрету a большей разрядности. То есть, если нужно 256-битное a, то достаточно взять массивы g и A из 256 чисел. Но это значит и то, что при использовании 32-битных чисел массива g его размер будет в 32 раза превышать размер a. То же касается и общего ключа, который может понадобиться сжимать/хешировать.

Операции над числами

Выше отмечено, что элементы A вычисляются путём прибавления к ним элементов g, но в деталях это не совсем так. На самом деле, в качестве операции над числами может применяться любая операция op, удовлетворяющая двум требованиям:

• g1 op g2 = g2 op g1;
• битовый размер результата операции равен битовому размеру каждого из чисел.

В настоящий момент в ShareKey допустимы на выбор три возможные операции.

1. Xor. Самая простая операция — побитовое исключающее ИЛИ.
2. Add — сложение с приведением к прежней разрядности. Для 32-битных чисел вычисляется вначале как 64-битная сумма, а затем от этой суммы отнимается 0xffffffff, если она больше 0xffffffff. Результатом являются оставшиеся младшие 32 бита суммы.
3. Mul — умножение по модулю. Для двух 32-битных чисел вначале вычисляется как 64-битное произведение, а результат определяется взятием остатка от деления этого произведения на 0xfffffffb (здесь 0xfffffffb — наибольшее 32-битное простое число).

По умолчанию в алгоритме применяется операция Mul.

Примечание. Для операций Xor и Add при вычислении A = Func(g, a) все элементы массива A должны инициализироваться нулями, а для Mul — единицами. Также для операции Mul отдельные числа g должны иметь значения от 1 до 0xfffffffa включительно.

Надёжность алгоритма

Следует ещё раз отметить, что алгоритм является экспериментальным, поскольку он не проверялся на многие виды уязвимостей и потому степень его надёжности (стойкости) неизвестна. Алгоритм однозначно уязвим к атаке «человек посредине», потому требует в этом отношении дополнительных мер. В остальном приходится полагаться только на допущение, что для достаточно длинного секрета a, состоящего из случайных бит, а также массива g из преимущественно неповторяющихся (случайных) чисел сложно установить, какие из этих чисел входят в сумму или произведение в каждом элементе массива A, а какие не входят. И, значит, какие биты a равны 1, а какие 0. Отсюда вычислять ключ K = Func(B, a) может только тот, кто знает a, но восстановить a при известных g и A достаточно сложно.

Реализация и примеры

Алгоритм состоит всего из нескольких функций, объединённых в пространство имён ShareKey. Функция Func() принимает g и a в виде динамических массивов типа std::vector и возвращает результат также в виде подобного массива. Функции Gen_g() и Gen_a() возвращают специально сгенерированные массивы g и a. Функции SetSize() и GetSize() позволяют (соответственно) установить и определить текущее значение размера, т. е. количества чисел для g и бит для a (принимается кратным 128: 128, 256, 384, 512 и т.д.). Функции SetXor(), SetAdd() и SetMul() устанавливают тип применяемой в Func() операции. Есть ещё несколько функций, работающих с указателями, но они здесь не рассматриваются.

Если принять, что DWord является псевдонимом для типа unsigned int, а SK — псевдонимом для пространства имён ShareKey, то пример создания общего ключа K = K1 = K2 может выглядеть так:

SK::SetSize(256);
SK::SetAdd();

std::vector<DWord> g = SK::Gen_g();
std::vector<DWord> a = SK::Gen_a();
std::vector<DWord> b = SK::Gen_a();

std::vector<DWord> A = SK::Func(g, a);
std::vector<DWord> B = SK::Func(g, b);

std::vector<DWord> K1 = SK::Func(B, a);
std::vector<DWord> K2 = SK::Func(A, b);

Генерация случайных чисел

При создании массивов g и a функциями Gen_g() и Gen_a() их заполнение случайными числами осуществляется с помощью алгоритма DeepRand. Рандомизация при этом выполняется автоматически по высокоточным часам (с точностью до микро- или даже наносекунд) при каждой генерации. В опытных целях этого может быть достаточно, но в остальных случаях рекомендуется предварительно проводить дополнительную рандомизацию (она в DeepRand накопительная/дополняющая) по случайным данным из хорошего источника (например, из файла /dev/urandom в GNU/Linux).

Example.cpp

В файле Example.cpp приведён простой пример полноценной программы, годной для реального обмена ключами. В программе показана рандомизация по /dev/urandom, генерация или ввод g, генерация a, вычисление и отображение собственного публичного ключа A (или Pub в примере), ввод публичного ключа второго пользователя B (Other_Pub в примере) и вычисление общего ключа K = Func(Other_Pub, a).

После сборки программы можно запустить два её экземпляра (на одном или на разных компьютерах) и в одном генерировать g, а во втором его вставить (нужен эмулятор терминала с возможностью копирования и вставки). Также нужно выведенный публичный ключ из первого экземпляра вставить как ключ другого пользователя во втором, а ключ второго — в первом. В итоге в обоих экземплярах программы вычислится одинаковый общий ключ.