Каскадное шифрование редуцированным алгоритмом RSA04.02.2024 22:15

Введение

Данная публикация была написана в результате применения общей идеи каскадирования, взятой из радиотехники, к широко известному теоретико-числовому алгоритму RSA, но, правда, в его облегченном (редуцированном) виде. Облегчение RSA компенсируется идеей каскадирования. Таким образом возник вариант методики улучшения криптостойкости RSA в противовес классическому удлинению ключа.

Для предварительных исследований использовались возможности встроенной Big Integer арифметики языка Python, а также функция factorint (.) библиотеки SymPy, позволяющая раскладывать числа на простые множители

from sympy import factorint as f
d = f(999_999_999)
factors = list(d)
print(factors)
[3, 37, 333667]

Целью данной публикации является ознакомление широкой публики с предлагаемой идеей.

Генерация ключей

Для ускорения процедуры генерации выбраны два небольших числа: Q=65536 и m=4 . Дополнительно, это позволяет уместиться в -битный регистр процессора. Дальнейшие параметры будут согласованы так, чтобы обрабатывать -битный вход. Процедура генерации ключей состоит в следующем:

Генерируем случайных чисел в диапазоне
Составляем произведение
Раскладываем произведение на простые множители $p_1 = \prod f_i$
Повторяем пп. 1–3 несколько раз (на выбор):
Из найденных множителей формируем множество простых множителей $\{f_k\}$ .

Здесь q_i и r_j — небольшие числа, (1...5) , подбираются экспериментально и обеспечивают некоторую «соль» и разнообразие получаемых множителей (влияет на скорость генерации).

Среди найденного множества в цикле отбираем случайных множителей
Определяем минимальную и максимальную битность множителей (то есть их ширину в битах)
Если min/max битности попадают в определенный интервал, например, больше и меньше бит (помним про -битный вход), то сохраняем множители — будущие ключи — и завершаем цикл.

Рекомендуется брать l=8 . В цикле можно установить максимальное количество итераций, например, . При превышении генерацию начинаем заново.

По отобранным множителям составляем произведение

$p_2 = \left( \prod_{j=1}^{l} f_j \right) - 1,$

которое гарантирует обратимость шифрования.

Найденное произведение раскладываем на множители $p_2 = \prod f_k$ — будущие модули
Если множителей мало (например, меньше ), то генерацию начинаем заново
Среди найденных множителей ищем множитель, битность которого попадает в заданный диапазон, например, от до бит (модуль должен быть большим относительно разрядности входа, которую мы выбрали бита)
Если «хороший» множитель (модуль) найден, то сгенерированные ключи и этот множитель сохраняем. В противном случае генерацию начинаем заново.

Можно отбирать два и более множителя и использовать любой из них, т.к. математически на результат шифрования они не влияют.

Сгенерированные ключей необходимо разделить на две примерно равновесные половины: первая используется для шифрования, K_E , вторая — для дешифрования, K_D .

Время поиска ключей при использовании описанных выше инструментов составляет единицы секунд. Пример найденных ключей и одного модуля

[(3, 61, 12656101, 606059, 17, 7974709, 47, 94153), 32067095497].

Процедура шифрования

Допустим, что шифруется некоторое число .

Последовательно умножаем на ключи шифрования $x \leftarrow x \cdot K_E[i]$
В качестве результата шифрования берем модуль $y = x \mod f$ , где — отобранный модуль.

Пример.

Пусть x=123456789 . Возьмем найденные выше ключи и первые будем использовать для шифрования:
$(12345678 \cdot 3) \mod 32067095497 = 370370367$
$(370370367 \cdot 61) \mod 32067095497 = 22592592387$
$(22592592387 \cdot 12656101) \mod 32067095497 = 17664305822$
$(17664305822 \cdot 606059) \mod 32067095497 = 11690502048.$

y = 11690502048.

Заметим, что после шифрования несколько повышается битность числа: примерно 33,4 бита для рассмотренного примера.

Модуль рекомендуется брать на каждом шаге, как в примере, что позволит ограничить разрядность чисел. Если арифметика BigInt, то модуль можно взять один раз в конце.

Процедура дешифрования

Допустим, принимаем шифрованное число .

Последовательно умножаем на ключи дешифрования $y \leftarrow y \cdot K_D[i]$
В качестве результата дешифрования берем модуль $x = y \mod f$ .
Продолжение примера.

$(11690502048 \cdot 17) \mod 32067095497 = 6335961834$
$(6335961834 \cdot 7974709) \mod 32067095497 = 2895638843$
$(2895638843 \cdot 47) \mod 32067095497 = 7826643633$
$(7826643633 \cdot 94153) \mod 32067095497 = 123456789.$

x = 123456789.

Ключи шифрования являются открытыми ключами, а ключи дешифрования — закрытыми, и, вообще, для предложенного метода шифрования существующие протоколы (вариации применения) алгоритма RSA остаются теми же самыми.

Каскадирование шифра

Если последовательно сгенерировать, допустим, разных наборов ключей и модулей, то описанную процедуру шифрования можно последовательно применить раз. В свою очередь процедура дешифрования должна быть последовательно применена раз.

Каскадирование позволяет увеличить криптостойкость — компенсировать небольшой диапазон используемых множителей, который был выбран для ускорения процедуры генерации ключей. Последняя основана на разложении относительно небольших чисел ( бита) на простые множители.

При каскадировании, чтобы согласовать требование разрядности входа, придется текущее шифрованное число делить на две части: -битный вход и остаток, причем последний передавать как есть. Либо возможен вариант с сортировкой сгенерированных наборов ключей по их модулям в порядке возрастания: набор ключей с наибольшим модулем применяется самым последним (при дешифровании он будет первым). В этом случае данные будут переданы и приняты без потерь.

Предложенный алгоритм является мультипликативным и, естественно, имеет недостаток в виде, например, обнуления шифрованного потока при нулевом входном потоке. Однако, данный недостаток можно нивелировать, например, соответствующим обратимым (линейным) псевдослучайным генератором, который по определению не допускает нулевого состояния: z = PRNG(x, q) — шифровать состояние генератора (полученное после кратного применения функции next), а при дешифровании использовать обратную функцию (back) того же самого генератора: x = PRNG(z, -q) .

Выводы

Предложен упрощенный каскадный вариант алгоритма RSA с ускоренной генерацией ключей.

Каскадирование позволяет:

Регулировать криптостойкость алгоритма, не увеличивая длину фактических ключей, а увеличивая их количество
Ускорить генерацию ключей за счет отсутствия экстремально больших простых чисел.

Предложено мультипликативную природу алгоритмов типа RSA нивелировать обратимым (линейным) псевдослучайным генератором. Про последние можно прочитать в моих статьях на Хабре.

Предлагается итоговый алгоритм назвать Cascaded Reduced RSA (CRRSA).