Криптография с использованием открытых ключей
Криптография предусматривает применение числовых значений, называемых ключами, которые используются для кодирования и декодирования зашифрованных данных. Однако в некоторых методах криптографии ключи, используемые для зашифровки данных, не идентичны ключам, используемым для их расшифровки. Для декодирования сообщения требуется знание дешифровочных ключей. Поэтому ключи шифрования можно широко распространять, не нарушая при этом безопасность системы. Люди, знающие ключи шифрования, смогут закодировать свои сообщения, но не смогут расшифровать сообщения, закодированные другими, даже если при этом использовался тот же ключ шифрования. С помощью подобной шифровальной системы множество людей смогут посылать засекреченные сообщения одному адресату, и только этот адресат будет иметь ключ для дешифровки всех поступающих к нему шифрованных сообщений. Подобная техника шифрования составляет отрасль исследований, известную как криптография с использованием открытых ключей. Последний термин отражает тот факт, что используемые для шифровки сообщений ключи являются общедоступными.
Для иллюстрации метода криптографии с использованием открытых ключей построим последовательность
a0, a1, ..., an-1 из n целых чисел удовлетворяющих условиям
В этой последовательности каждый следующий элемент больше, чем сумма всех предыдущих.
Выберем модуль m, удовлетворяющий неравенству
и определим два числа x и y, которые удовлетворяют равенству xy (mod m) = 1. На основе последовательности a0, a1, a2, ..., an-1 построим последовательность
b0, b1, ... , bn-1, члены которой определяются выражениями
Шифрование информации будет осуществляться с помощью последовательности b0, b1, ... , bn-1, а дешифровка с помощью последовательности a0, a1, ..., an-1 и чисел m, y. Таким образом, числа b0, b1, ... , bn-1 образуют открытый ключ, а числа a0, a1, ..., an-1, m, y закрытый ключ. Данный метод криптографии предполагает следующую процедуру:
исходная информация тем или иным способом представляется в двоичной форме и разбивается на n-разрядные двоичные числа;
каждому двоичному числу C2=сn-1 сn-2 ... с0 ставится в соответствие десятичное число С10, которое рассчитывается по формуле С10=с0b0+с1b1+ ... + сn-1bn-1;
С10 передается получателю сообщения, который определяет числа из последовательности a0, a1, ..., an-1, суммой которых является результат умножения переданного числа С10 на y по модулю m;
индексы найденных чисел из последовательности a0, a1, ..., an-1 указывают на положение единиц в двоичном числе C2 и тем самым позволяют его восстановить.
Возможность использования при шифровании последовательности b0, b1, ... , bn-1, а при дешифровки - a0, a1, ... , an-1 доказывается следующей цепочкой равенств:
(b0+b1+ ... +bn-1) y (mod m) = (a0+a1+ ... +an-1) xy (mod m) = (a0+a1+ ... +an-1) (mod m) = (a0+a1+ ... +an-1).
Стойкость к взлому данного метода криптографии основана на том факте, что алгоритм определения чисел из последовательности a0, a1, ... , an-1, суммой которых является заданное число, более эффективен, чем алгоритм решения подобной задачи для последовательности b0, b1, ... , bn-1. В первом случае, необходимо найти первое в последовательности число, которое больше заданного, запомнить его индекс и вычесть из заданного числа. Если результат операции вычитания не равен нулю, то повторить поиск заново. Во втором случае, решение задачи предполагает осуществление поиска методом перебора всех возможных комбинаций, пока не будет найдено подходящее решение.
Например, пусть требуется передать строку 'Ok'. Представим ее в двоичной форме, использую ASCII-коды символов. Получим следующую кодовую комбинацию: 0100111101101011. Определим последовательность a0, a1, ... , a15 для n=16 следующим образом:
1, 3, 5, 10, 22, 42, 90, 185, 375, 774, 1605, 3235, 6524, 13936, 28725, 61892.
Модуль выберем равным 135757, а числа x и y равными 47515 и 20 соответственно. Рассчитаем последовательность b0, b1, ... , b15. В нашем случае она будет иметь вид:
47515, 6788, 101818, 67879, 95031, 95032, 67883, 101827, 33958, 122220, 101898, 34101, 54629, 82151, 103254, 30246.
Для этой последовательности определим число С10, которое будет равно 680528. Таким образом, получателю вместо строки 'Ok' будет передано число 680528.
Теперь произведем дешифровку полученной информации. Умножим полученное число на 20 по модулю 135757. Получим число 34860, которое является суммой следующих чисел в исходной последовательности: a14, a11, a10, a9, a8, a6, a5, a3, a1, a0. В результате получим кодовую комбинацию 0100111101101011, которая эквивалентна строке 'Ok'.
