Full-stack шифрование на обобщенных регистрах с линейной обратной связью

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

Введение

В теории кодирования хорошо известны регистры сдвига с линейной обратной связью (РСЛОС или LFSR -- Linear Feedback Shift Register), которые применяются, например, для:

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

Как правило, регистры сдвига оперируют битами, выполняя суммирование по модулю два. Исключением являются помехоустойчивые коды Рида-Соломона, которые по определению не являются двоичными. Что касается криптографических применений РСЛОС, то здесь ситуация сложнее.

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

Предлагается для большей стойкости и возможности масштабирования в качестве базовой криптографической ячейки использовать РСЛОС, оперирующие не битами, а числами по модулю некоторого простого числа, скажем .

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

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

Предлагаемая криптографическая архитектура хорошо ложится на параллелизм современной вычислительной техники (16/32/64 ядра).

Конечно, предлагаемая архитектура требует экспертизы со стороны криптографического сообщества и проверки временем.

РСЛОС по простому модулю

В общем случае РСЛОС содержит в себе ячеек, которые хранят целые числа по модулю . Вектор из чисел называется вектором состояния регистра или просто состоянием. Слово "сдвиг" означает следующий такт. На следующем такте состояние регистра меняется. Начиная с некоторого такта можно получить первоначальное состояние, при этом пройденное количество тактов называют периодом генератора.

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

Алгоритм пересчета состояния $\vec x$ следующий:

Последовательно для всех $i=\overline{m-1, 1}$ выполнить $x[i] = (x[i-1] + vK[i]) \mod p$
Закрепить последний элемент $x[0] = vK[0] \mod p$
Обновить выходное значение

Здесь $\vec K$ -- вектор коэффициентов генератора, определяющий период генератора.

Перед тем, как определять период генератора, его устанавливают в единичное состояние $\vec x = (1, 0, 0, ..., 0)$ , , и прогоняют раз для насыщения. Вообще говоря, можно установить в любое ненулевое состояние $\vec x \neq 0$ и прогнать раз, чтобы состояние стало "своим". В этом есть аналогия с помехоустойчивыми кодами, где имеются разрешенные кодовые слова и запрещенные.

Приведенный алгоритм легко ложится на схему с регистром сдвига, умножителями и сумматорами. В принципе, данные уравнения основаны скорее на схеме, чем на алгебраических предположениях. Хотя с точки зрения алгебры, выход генератора -- это частное от деления степеней на так называемый генераторный полином $g(x) = x^m - K[m-1]{x}^{m-1} - ... - K[1] x - K[0]$ , а состояния генератора -- это соответствующие остатки от деления.

Так как число разных состояний равно , то период не может быть больше этого числа. Нулевое состояние исключается, поэтому $T \le {p}^{m} - 1$ . Генераторы с максимальным периодом генерируют последовательности максимальной длины или М-последовательности. Естественно, что для криптографии интересны именно такие генераторы, либо близкие к ним.

Одна из проблем заключается в том, что отсутствуют рецепты для отыскания "правильных" коэффициентов генератора. Однако, есть предварительно просчитанные таблицы, особенно для двоичных генераторов когда ввиду их широкого применения. Проверено, что для произвольного простого есть возможность относительно быстро посчитать хорошие генераторы для регистра длиной . Например, для и существует более хороших генераторов. Такие генераторы эквивалентны в смысле периода двоичным генераторам с периодом ~ ${2}^{32}.$

Так как период ${2}^{32}$ по современным меркам не очень велик, то хочется как-то увеличить его не прибегая к более длинным регистрам. Предлагается объединить два генератора с одинаковой длиной и модулем , но с разными периодами.

Парное объединение генераторов с одним модулем

Если объединить два генератора с одинаковым периодом, то общий период будет тем же самым и такое объединение теряет смысл. Необходимо чтобы периоды были разными.

Известно, что общий период равен наименьшему общему кратному (НОК) периодов . В свою очередь НОК тем больше, чем меньше наибольший общий делитель (НОД).

Путем численного моделирования показано, что генераторы из ячеек могут иметь периоды ${T}_{2} = {p}^{m-1} - 1$ (малый период) и ${T}_{1} = {p}^{m} - 1$ (большой период). Доказано, что НОД этих периодов равен . Значит общий период равен $T = ({p}^{m-1} - 1)(p^m-1)/(p-1) \approx ({p}^{m-1})^2 \approx (T_2)^2$ .

Получили, что период объединенного генератора равен квадрату малого периода. Для рассмотренных ранее параметров период равен примерно ${2}^{48}$ , то есть вместо -х битов получили почти битов, не увеличивая длину регистра (напомним, более длинный регистр требует более долгого поиска правильных коэффициентов).

Объединять два генератора можно по-разному. Возможна сумма по модулю , возможно побитовое исключающее ИЛИ, если содержимое ячеек хранить в некотором фиксированном регистре. Допустим, при разумно использовать байтовую ячейку, при -- двухбайтовую ячейку и т. д.

Предлагается использовать вариант с побитовым исключающим ИЛИ, так как он более стоек к атакам -- эта операция не согласована с линейными свойствами арифметики по модулю . Например, $123 + 231 = 354 = 103 \mod 251$ , но $123 \oplus 231 = 156 \neq 103$ . То есть два генератора сами по себе работают в арифметике по модулю , а объединяющий оператор -- нет, что затрудняет анализ такой суммы. Также операция ИЛИ сохраняет баланс нулей и единиц, в отличие, например, от операции И.

Конечно, можно объединять четыре разных генератора: два с малым периодом, два с большим, однако общий период от этого не изменится.

Сочетание парных генераторов по набору модулей

Так как простых чисел много, то предлагается объединить рассмотренные выше парные генераторы побитовым исключающим ИЛИ. Общий период будет равен НОК периодов всех парных генераторов. В настоящее время общий период несложно посчитать используя арифметику длинных целых чисел.

Ограничиваясь, например, $131 \leq p \leq 251$ , а также , можно получать периоды вплоть до примерно битов, при этом объединенный генератор будет содержать примерно пары. Путем численного моделирования можно подобрать оптимальное сочетание простых чисел.

Алгоритм генерации общего секрета

Генерация общего секрета необходима при передаче шифрованного сообщения из точки А в точку Б по той причине, что единый ключ шифрования не должен передаваться по сети в открытом виде. Он должен быть каким-то образом зашифрован, но так, чтобы не создавать нового ключа шифрования, что опять бы породило проблему передачи ключа и т. д.

Существует алгоритм генерации общего секрета на основании разложения числа на простые множители и алгебраического равенства ${({G}^{m})}^{n} = {({G}^{n})}^{m}$ , алгоритм Диффи-Хеллмана. Однако, он требует применения специфических алгоритмов, и не известно к чему приведет развитие математики в плане ускорения таких алгоритмов и, значит, увеличения вероятности взлома.

Предлагается передавать сумму $W_A =P \cdot (x^m + x^n) \mod g(x)$ со стороны абонента А и сумму $W_B = Q \cdot (x^p + x^q) \mod g(x)$ со стороны абонента Б, где -- общий заранее известный генератор, работающий в арифметике по модулю , а набор , , , , , -- случайные секретные коэффициенты: три первых известны только А, три других известны только Б.

Заметим, что сумма -- это состояние регистра, то есть чисел по модулю .

Операция $x^m \mod g(x)$ означает прогон некоторого начального вектора раз через генератор . Умножение на -- это поэлементное умножение итогового результата (состояния регистра) на и приведение его по модулю .

Формируемые суммы могут содержать более двух слагаемых для увеличения криптостойкости.

В данном случае сумма -- это сумма по модулю , что позволяет генерировать общий секрет. Операция ИЛИ, к сожалению, здесь не подходит, однако криптостойкость можно регулировать количеством слагаемых.

Сумма ${W}_{A}$ , переданная абоненту Б, подвергается операции, известной Б -- этой суммой инициализируется генератор и делается прогон раз и раз, результаты складываются и всё это умножается на , -- в результате чего формируется сумма ${W}_{AB}$ , а сумма ${W}_{B}$ , переданная абоненту А, подвергается операции, известной А -- этой суммой инициализируется генератор и делается прогон раз и раз, результаты складываются и всё это умножается на , -- в результате чего формируется сумма ${W}_{BA}$ .

Общий секрет (ключ шифрования) равен $W ={W}_{AB} + {W}_{BA}$ .

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

На практике, поиск генераторной пары для и может занимать суток на одном ядре процессора, что, в принципе, осуществимо. Для среднее время поиска прогнозируется примерно в раз больше -- вероятно, это недостижимый случай...

Заключение

Предложена архитектура Full-stack шифрования на обобщенных LFSR регистрах:

Парные генераторы длиной , модулем и общим периодом $\approx {p}^{2m-2}$ , с нелинейным выходом, формируемым контейнерным исключающим ИЛИ
Сочетание парных генераторов с разными модулями на основе контейнерного исключающего ИЛИ
Алгоритм генерации общего секрета, основанный на обмене суммами (состояниями регистра) по модулю , формируемыми базовыми -ячейками.

Предложенная архитектура требует экспертизы со стороны криптографического сообщества и проверки временем.

Источник: https://habr.com/ru/articles/729638/

Вернуться к списку

Интересные статьи

Artix Linux. Установка с полным/частичным шифрованием

Artix Linux - это systemd-free дистрибутив линукс на основе Arch Linux. Он использует свои репозитории, но присутствует частичная совместимость с репозиториями Arch и AUR. Artix Linux предоставляет вы...

Право на шифрование — как обстоят дела в мире

В прошлый раз мы обсуждали алгоритмы шифрования, которые подготовят вычислительные системы к квантовому будущему. Сегодня мы в T1 Cloud решили продолжить тему и поговорить о настоящем — дать контекст,...

Малоресурсное шифрование

Распространение интеллектуальных технологий резко поднимает проблему безопасности данных. Представляется невозможным использовать обычные криптографические алгоритмы в устройствах с крайне ограниченны...

Использование Windbg для обратной разработки

Статья представляет собой мануал по тому как пользоваться Windbg. Будет рассмотрена "классическая" версия отладчика. Настроим внешний вид и изучим команды, которые можно ...

Аппаратное шифрование DRAM уже близко. Чем оно грозит простым пользователям?

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