Теория

ShareKey-2 — авторский экспериментальный алгоритм обмена криптографическими ключами (вычисления общего ключа), альтернативный по отношению к ShareKey-1. Основан также на циклических сдвигах и операциях XOR (исключающее ИЛИ), но, в отличие от ShareKey-1 с его поэлементными сдвигами внутри массива, здесь выполняются побитовые сдвиги.

На примере отдельных чисел g и a суть главной функции Func(g, a) здесь заключается в следующем: результат изначально устанавливается равным 0 и к нему при помощи операции XOR прибавляется число g, если очередной бит числа a равен 1, и в любом случае над g выполняется циклический побитовый сдвиг. В таком виде функция удовлетворяет условию: Func(Func(g, a), b) = Func(Func(g, b), a), что позволяет вычислять общий ключ, обмениваясь значениями g, A = Func(g, a) и B = Func(g, b), но сохраняя в секрете a и b. В то же время, функция не допускает для известных g и A вычислить x = A xor g и получить ключ простым выполнением B xor x.

Подобно ShareKey-1, преимуществом такой функции является то, что её можно легко применить не только к отдельным числам, но и также к массивам практически неограниченного размера. То есть, g, a и b (а также A и B) могут быть массивами чисел и оперироваться по частям, причём только побитовый циклический сдвиг нужно применять для всего массива, а операцию XOR можно выполнять для каждого отдельного элемента независимо от других. Более того, в отличие от ShareKey-1, в котором массивы g, A и B в разы длиннее массивов a и b, в данной версии все массивы имеют одинаковый размер.

Недостаток ShareKey-2 заключается как минимум в том, что над отдельными числами массивов может применяться только операция XOR, хотя в ShareKey-1 были допустимы также сложение и умножение. Здесь это связано с тем, что такие операции не могут выполняться по частям или вообще нарушают свойство Func(Func(g, a), b) = Func(Func(g, b), a). Кроме того, алгоритм становится предсказуемым и уязвимым для взлома, если все или преимущественно все биты g равны 0 (или все равны 1), потому чем длиннее g и a и чем более они случайны, тем меньше побочных эффектов.

Следует ещё раз отметить и то, что алгоритм является экспериментальным, поскольку степень его надёжности (стойкости) неизвестна и основана лишь на предположительной сложности обратить или предсказать A = A xor g при условии циклических сдвигов g и выполнении или невыполнении xor в зависимости от значений отдельных бит секретного числа a. То есть, на сложности вычислить Func(g, a) при известном g и неизвестном a или восстановить a по известному A = Func(g, a), особенно для чисел/массивов достаточно большого размера.

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

Алгоритм работает с динамическими массивами (типа std::vector) 32-битных целых беззнаковых чисел (типа unsigned int). Для работы с этими массивами реализовано всего несколько функций, объединённых в пространство имён ShareKey2:

• Rand() создаёт массив установленной длины и заполняет его случайными числами, может быть применим для создания g, a или b.

• Func() является основной функцией преобразования (сдвиги и XOR) одного массива по битам второго.

• SetSize() позволяет установить применяемый размер массивов — количество 32-битных чисел. По умолчанию размер установлен равным 4.

• GetSize() возвращает установленный размер массивов.

Генерация случайных чисел функцией Rand(), подобно ShareKey-1, осуществляется с помощью алгоритма DeepRand. Рандомизация DeepRand выполняется автоматически при каждом запуске Rand() по высокоточным системным часам и для опытных целей этого должно быть достаточно, иначе перед запуском Rand() необходимо выполнить дополнительную рандомизацию (напомним, в DeepRand она накопительная).

Простой пример создания общего ключа может выглядеть следующим образом:

SK2::SetSize(8); // здесь SK2 - псевдоним для ShareKey2

std::vector<DWord> g = SK2::Rand(); // DWord = unsigned int
std::vector<DWord> a = SK2::Rand();
std::vector<DWord> b = SK2::Rand();

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

std::vector<DWord> K1 = SK2::Func(B, a);
std::vector<DWord> K2 = SK2::Func(A, b); // K2 должен быть равен K1

Example.cpp

Программа Example.cpp является более подробным примером применения алгоритма, аналогичным таковой для ShareKey-1. После её сборки имеется возможность запустить два экземпляра программы и в одном генерировать g, а во втором его вставить (в эмуляторе терминала с возможностью копирования и вставки). При этом, в каждом экземпляре автоматически генерируется свой секретный массив a, а также вычисляется и отображается массив A, называемый «публичный ключ». Если вставить публичный ключ из первого экземпляра во второй, а публичный ключ из второго в первый — в обоих экземплярах сгенерируется одинаковый общий секретный ключ K.