Рюкзачная криптосистема Шора-Ривеста / Хабр

В этой статье мы рассмотрим рюкзачную, или ранцевую, криптосистему Шора-Ривеста (Chor-Rivest knapsack). Это один из немногих алгоритмов классической криптографии, который можно рассматривать как постквантовый кандидат. Несмотря на то что сегодня он не считается современной и надёжной постквантовой криптосистемой, его всё равно интересно разобрать как один из нестандартных вариантов такого рода.

Математическая база

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

Структура статьи

Введение в тeорию сложности вычислений
Задача об укладке рюкзака
Рюкзачная криптосистема Шора-Ривеста
Преобразование произвольных битовых строк
Пример работы криптосистемы

Введение в тeорию сложности вычислений

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

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

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

Источник

Vadhan, Salil P. 2011. Computational complexity. In Encyclopedia of Cryptography and Security, second edition, ed. Henk C.A. van Tilborg and Sushil Jajodia. New York: Springer.

Пример

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

Пример

Если , то удвоение входных данных приведет к удвоению времени работы алгоритма, а если , то добавление одного бита к входным данным приведет к удвоению времени работы алгоритма.

В зависимости от функции сложности существуют классы сложности задач. Пусть n - длина битовый строки - входных параметров алгоритма. Алгоритмы, временная сложность которых может быть записана как , где c - константа, называются алгоритмами с полиномиальным временем, так как их функция сложности полиномиальна. Такие задачи считаются "легкими", они могут быть эффективно решены. Их относят к классу сложности P - класс задач, которые могут быть решены за полиномиальное время. Однако если временная сложность алгоритма задается, например, как , где c - константа, то говорят об экспоненциальной сложности и экспоненциальном времени. Такие задачи быстро становятся нерешаемыми при росте размера входных данных и к классу P уже не относятся.

Еще одним важным классом сложности является NP - это класс вычислительных проблем, решение которых может быть проверено за полиномиальное времени (но не может быть за полиномиальное время получено). Таким образом задачи из этого класса отлично подходят для использования в криптосистемах. Задача из класса NP называется NP-полной, если любую задачу из класса NP можно свести к этой задаче за полиномиальное время (т.е. если для какой-нибудь NP-полной задачи будет найден алгоритм решения, работающий за полиномиальное время, то и любую другую задачу из класса NP можно будет решить за такое же время). Таким образом NP-полные задачи являются наиболее "трудными", и потому наиболее вероятно, что для них не будет найдено решения за полиномиальное время.

Задача об укладке рюкзака

Одной из "трудных" задач является задача об укладке рюкзака. В ее основе лежит следующая идея. Есть рюкзак, вместимость которого ограничена, и множество предметов, которые в него можно положить. Необходимо найти подмножество предметов, которое этот рюкзак заполнит доверху. Эта задача интересна тем, что зная подмножество предметов, уложенных в рюкзак, легко подсчитать его вес, однако, зная вес рюкзака, трудно определить подмножество предметов. Другой вариант задачи, в котором в рюкзак можно положить не более одного экземпляра предмета каждого типа, называется рюкзак 0-1.

Более формально, задача о рюкзаке 0-1 является NP-полной задачей комбинаторной оптимизации. Математическая задача формулируется следующим образом: имеется множество $A = \{ a_i | 0 \leq i \leq n-1 \}$ неотрицательных целых чисел и неотрицательное целое число . Необходимо найти решение в целых числах для

$\sum_{i=0}^{n-1} a_i x_i = S$ , где $x_i \in \{ 0, 1 \}$ для всех .

Другой вариант постановки задачи о рюкзаке - снять ограничение 0-1, требуя только чтобы все были неотрицательными целыми числами, и ограничить их вес:

$\sum_{i=0}^{n-1} x_i \leq h$ .

Источник

Chor B., Rivest R. L. A Knapsack-Type Public Key Cryptosystem Based on Arithmetic in Finite Fields. // IEEE Transactions on information theory. 1988. Vol. 34, № 5. pp. 901–909.

Рюкзачным вектором $A = (a_0, \dots, a_{n-1})$ называется упорядоченный набор из предметов, где - вес -го предмета, $0 \leq i \leq n-1$ .

Источник

Саломаа А. Криптография с открытым ключом: Пеp. с англ. — М.: Миp, 1995. с. 73-161.

Пример

Пусть - рюкзачный вектор длины 5. Тогда число 25 можно представить в виде суммы элементов рюкзачного вектора . Разложение числа по элементам рюкзачного вектора можно записать в виде бинарного вектора. Для предыдущего примера этот вектор будет равен , где 1 стоит на месте тех элементов, которые участвовали в разложении. При этом, просуммировав элементы рюкзачного вектора, на месте которых стоят 1, можно получить исходное число. Этот факт можно использовать для построения криптосистемы, однако стоит заметить, что в приведенном нами примере одно и то же число может быть представлено несколькими способами, из-за чего преобразования становятся неоднозначными: можно представить как или как .

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

Вектор $A = ( a_0, \dots, a_{n-1} )$ называется сврехрастущим, если $\sum_{i=0}^{j-1} a_i < a_j$ для $j = 1, \dots, n-1$ ,

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

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

Алгоритм.
Вход: ; Выход: $\vec{x}$ ;
$i \leftarrow n-1$
пока
если $a_i \leq S$ , то
$x_i \leftarrow 1$
$S \leftarrow S - a_i$
иначе $x_i \leftarrow 0$
$i \leftarrow i-1$
вернуть $\vec{x}$

Также, не являются надежными рюкзаки с низкой плотностью, они подвержены ряду атак ("low-density" attack).

Источник

J. C. Lagarias and A. M. Odlyzko. Solving Low-Density Subset Sum Problems. Journal of the Association for Computing Machinery. January 1985. Vol. 32, № 1, pp. 229-246.

Плотность рюкзака определяется как отношение количества элементов в нем к размеру в битах его элементов (или размеру максимального элемента):

$d(A) = \frac{n}{ log_2(max A) }$

Пример

Для сверхрастущего вектора .

Рюкзачная криптосистема Шора-Ривеста

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

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

Составляется трудная задача , нерешаемая за полиномиальное время.
Из выделяется легкая задача $T_{easy}$ , которую можно решить за полиномиальное время или даже быстрее.
С помощью некоторых преобразований легкая задача $T_{easy}$ превращается в трудную $T_{hard}$ , не имеющую никакого сходства с $T_{easy}$ , при этом процедура получения $T_{easy}$ из $T_{hard}$ держится в секрете.
$T_{hard}$ используется для конструирования открытой функции зашифрования, а $T_{easy}$ - для конструирования закрытой функции расшифрования. Таким образом для злоумышленника процедура дешифрования будет заключаться в решении $T_{hard}$ , а для добросовестного пользователя, знающего секрет, расшифрование будет осуществляться посредством решения $T_{easy}$ .

Источник

Иванов М.А., Михайлов Д.М., Чугунков И.В., Ковалев А.В., Мацук Н.А. Стохастические методы и средства защиты информации в компьютерных системах и сетях. / Под ред. И.Ю. Жукова. – М.: КУДИЦ-ПРЕСС, 2009. c. 131-134.

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

Источники

Chor B., Rivest R. L. A Knapsack-Type Public Key Cryptosystem Based on Arithmetic in Finite Fields. // IEEE Transactions on information theory. 1988. Vol. 34, № 5. pp. 901–909.
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography, 1996, pp. 303-305.

Для описания работы криптосистемы нам понадобится следующая теорема.

Теорема (Bose-Chowla). Для любого простого и натурального $h \geq 2$ существует последовательность целых чисел $A = ( a_0, \dots, a_{p-1} )$ , удовлетворяющая следующим условиям:
(1)

$1 \leq a_i \leq p^h - 1, \: i = 0, \dots, p-1$

(2) если $(x_0, x_1, \dots, x_{p-1})$ и $(y_0, y_1, \dots, y_{p-1})$ - два вектора с неотрицательными целыми координатами, удовлетворяющие ограничениям

$(x_0, x_1, \dots, x_{p-1}) \neq (y_0, y_1, \dots, y_{p-1})$ $\sum_{i=0}^{p-1} x_i \leq h - 1, \sum_{i=0}^{p-1} y_i \leq h - 1 \quad \text{или} \quad \sum_{i=0}^{p-1} x_i = \sum_{i=0}^{p-1} y_i = h$

то $\sum_{i=0}^{p-1} x_i a_i \neq \sum_{i=0}^{p-1} y_i a_i$ .

Доказательство

Рассмотрим расширение $GF(p) \subset GF(p^h)$ . Пусть $t \in GF(p^h)$ - алгебраическое число степени над полем (т.е. минимальный многочлен из кольца многочленов имеет степень ), - примитивный элемент поля (и, соответственно, генератор мультипликативной группы) . Рассмотрим аддитивный сдвиг основного поля на элемент :

$t + GF(p) = \{ t + \alpha_i | \alpha_i \in GF(p) \} \subset GF(p^h)$

Пусть $a_i = log_g (t + \alpha_i), \alpha_i \in GF(p)$ - дискретный логарифм элемента $t + \alpha_i$ по основанию в поле . Тогда все лежат в интервале (т.к. $GF(p^h)^* = \{ g^n | 1 \leq n \leq p^h - 1 \}, p^h - 1 \equiv 0 \: (\textrm{mod} \: p^h - 1)$ ), т.е. удовлетворяют первому условию теоремы. Проверим, что все также удовлетворяют и второму условию. Рассмотрим два вектора $\vec{x}, \vec{y}$ с неотрицательными целыми координатами, удовлетворяющие ограничениям (1) и (2), и пусть

$\sum_{i=0}^{p-1} x_i a_i = \sum_{i=0}^{p-1} y_i a_i$

Тогда выполняется следующее равенство:

$g^{ \sum_{i=0}^{p-1} x_i a_i } = g^{ \sum_{i=0}^{p-1} y_i a_i }$

и следовательно

$\prod_{i=0}^{p-1} (g^{a_i})^{x_i} = \prod_{i=0}^{p-1} (g^{a_i})^{y_i}$

Подставляя $g^{a_i} = t + \alpha_i$ , получим

$(t + \alpha_1)^{x_1} (t + \alpha_2)^{x_2} \dots (t + \alpha_{p-1})^{x_{p-1}} = (t + \alpha_1)^{y_1} (t + \alpha_2)^{y_2} \dots (t + \alpha_{p-1})^{y_{p-1}}$

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

Замечание 1.

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

Замечание 2.

В формулировке и доказательстве теоремы требование простоты может быть заменено на требование: - степень простого числа, при этом никаких изменений в формулировке или доказательстве не потребует

Генерация параметров криптосистемы:

Выбрать конечное поле , где - степень простого числа, $h \leq p$ , в котором можно эффективно решать задачу дискретного логарифмирования.
Выбрать случайный элемент $t \in GF(p^h)$ , являющийся алгебраическим числом степени над . Для этого необходимо выбрать случайный неприводимый нормированный (старший коэффициент равен единице) многочлен степени в кольце многочленов и представить поле как $GF(p)[t] / \langle f(t) \rangle$ (т.е. элементы поля - многочлены степени не больше с коэффициентами в , арифметические операции над которыми осуществляются по модулю ).
Выбрать случайный примитивный элемент поля $g \in GF(p^h)$ (т.е. - генератор мультипликативной группы ).
В соответствии с Теоремой Bose-Chowla вычислить дискретные логарифмы $a_i = log_g (t + \alpha_i)$ для всех $\alpha_i \in GF(p)$ .
Выбрать случайную перестановку $\pi: \{ 0, 1, \dots, p-1 \} \rightarrow \{ 0, 1, \dots, p-1 \}$ и перемешать : $b_i = a_{\pi(i)}$ .
Выбрать случайное число $d, 0 \leq d \leq p^h - 2$ и добавить шум: $c_i = b_i + d \: (\textrm{mod} \: p^h - 1), 0 \leq i \leq p - 1$ .

Открытым (публичным) ключом является $((c_0, c_1, \dots, c_{p-1}), p, h)$ , закрытым (секретным) ключом - $(f(t), g, \pi^{-1}, d)$ .

Шифрование:

Чтобы зашифровать бинарное сообщение $M = (x_0, x_1, \dots, x_{p-1})$ длины и веса (количество 1) в точности , необходимо сложить , которые соответствуют битам, равным 1:

$E(M) = \sum_{i=0}^{p-1} x_i c_i \: (\textrm{mod} \: p^h - 1)$

Расшифрование:

Пусть - зашифрованное сообщение, вычислить $c' = c - hd \: (\textrm{mod} \: p^h-1)$ .
Вычислить $u(t) = g^{c'} \: (\textrm{mod} \: f(t))$ .
Вычислить - нормированный многочлен степени в .
Разложить на линейные множители над : $s(t) = (t + \alpha_1) (t + \alpha_2) \dots (t + \alpha_h)$ . Все корней этого многочлена могут быть найдены последовательной подстановкой элементов . Таким образом мы найдем корней $\alpha_i \in GF(p), 1 \leq i \leq h$ .
Применить обратную перестановку $\pi^{-1}$ к полученным корням. Получим индексов $\pi^{-1}(\alpha_i), 1 \leq i \leq h$ , на месте которых в сообщении $M = (x_0, \dots, x_{p-1})$ будут стоять 1, остальные будут равняться 0.

Доказательство

$u(t) = g(t)^{c'} \: (\textrm{mod} \: f(t)) = g(t)^{c - hd} \: (\textrm{mod} \: f(t)) =g(t)^{\sum_{i=0}^{p-1} x_i c_i - hd} \: (\textrm{mod} \: f(t)) =$ $g(t)^{\sum_{i=0}^{p-1} x_i (a_{\pi(i)} + d) - hd} \: (\textrm{mod} \: f(t)) = g(t)^{\sum_{i=0}^{p-1} x_i a_{\pi(i)} + \sum_{i=0}^{p-1} x_i d - hd} \: (\textrm{mod} \: f(t)) =$ $g(t)^{\sum_{i=0}^{p-1} x_i a_{\pi(i)}} \: (\textrm{mod} \: f(t)) =\prod_{i=0}^{p-1} (g(t)^{a_{\pi(i)}})^{x_i} \: (\textrm{mod} \: f(t)) = \prod_{i=0}^{p-1} (t + \alpha_{\pi(i)})^{x_i} \: (\textrm{mod} \: f(t))$

Так как $\prod_{i=0}^{p-1} (t + \alpha_{\pi(i)})^{x_i}$ и - приведенные многочлены степени и конгруэнтны

по модулю , то:

$u(t) = \prod_{i=0}^{p-1} (t + \alpha_{\pi(i)})^{x_i} \: (\textrm{mod} \: f(t)) = \prod_{i=0}^{p-1} (t + \alpha_{\pi(i)})^{x_i} - f(t)$ $s(t) = u(t) + f(t) = \prod_{i=0}^{p-1} (t + \alpha_{\pi(i)})^{x_i}$

Следовательно, все корней лежат в , и применение к ним обратной перестановки $\pi^{-1}$ дает индексы, на месте которых в сообщении стоят 1.

Преобразование произвольных битовых строк

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

Источник

T. M. Cover. Enumerative source encoding. // IEEE Transactions on information theory. 1973. Vol. IT-19, pp. 73-77.

Пусть $\{ 0, 1 \}^n$ - множество бинарных последовательностей длины , $x = (x_1, x_2, \dots, x_n) \in \{ 0, 1 \}^n$ - произвольный элемент этого множества, - подмножество $\{ 0, 1 \}^n$ . Обозначим через количество элементов в множестве и через $n_S(x_1, x_2, \dots, x_k)$ - количество элементов в множестве , первые координат которых равны $(x_1, x_2, \dots, x_k)$ .

Под лексикографическим порядком будем понимать обычный словарный порядок, при котором , т.е. если для первого индекса такого, что $x_k \neq y_k$ .

Пример

Утверждение 1. Лексикографический индекс элемента $x \in S$ рассчитывается по формуле

$i_S(x) = \sum_{j=1}^{n} x_j n_S(x_1, x_2, \dots, x_{j-1}, 0)$

Эта формула определяет лексикографическую биекцию $S \rightarrow \{ 0, 1, \dots, n_S - 1 \}$ .

Доказательство

Слова с префиксом $(x_1, x_2, \dots, x_{j-1}, 0)$ лексикографически предшествуют словам с префиксом $(x_1, x_2, \dots, x_{j-1}, 1)$ . Для каждого такого, что , мы считаем количество $n_S(x_1, \dots, x_{j-1}, 0)$ элементов , которые впервые покоординатно отличаются от в -той координате и поэтому имеют меньший лексикографический индекс. Суммируя количество таких элементов для всех $1 \leq j \leq n$ , мы пересчитаем все элементы в , у которых индекс меньше чем у .

Утверждение 2. Пусть даны индекс и множество . Найти такой, что можно с помощью следующего алгоритма:
Если $i \geq n_S(0)$ , установить $x_1 = 1, \: i = i - n_S(0)$ ; иначе установить .
Для всех $k = 2, \dots, n$ , если $i \geq n_S(x_1, \dots, x_{k-1}, 0)$ , установить $x_k = 1, \: i = i - n_S(x_1, \dots, x_{k-1}, 0)$ ; иначе установить .

Теперь рассмотрим бинарные последовательности с весом :

$S = \left\{ x \in \{ 0, 1\}^n: \sum_{j=1}^{n} x_j = h \right\}$

В этом случае

$n_S(x_1, x_2, \dots, x_{k-1}, 0) = \binom{n-k}{n(h, k)}$

где

$n(h, k) = h - \sum_{j=1}^{k-1} x_j$

поскольку именно такое количество способов разместить оставшиеся единиц в оставшиеся мест в последовательности. Следовательно,

$i_S(x) = \sum_{k=1}^{n} x_k \binom{n-k}{n(h, k)}$

Пример

Для :

$i(1000101) = \binom{6}{3} + \binom{2}{2} + \binom{0}{1} = 20 + 1 + 0 = 21$ $i(1110000) = \binom{6}{3} + \binom{5}{2} + \binom{4}{1} = 20 + 10 + 4 = 34$

что согласуется с

$n_S - 1 = \binom{7}{3} - 1 = 34$

Теперь вернемся к исходной задаче: нам необходимо преобразовать произвольную бинарную строку в сообщения длины и веса . Для этого случая

$n_S = \binom{p}{h}$

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

$\lfloor log_2 \binom{p}{h} \rfloor$

, т.е. чтобы рассчитать количество бит для кодирования числа не больше мы рассчитываем

$log_2 \binom{p}{h}$

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

При кодировании исходного бинарного сообщения, мы разбиваем его на блоки длины

$\lfloor log_2 \binom{p}{h} \rfloor$

бит каждый, и каждый такой блок рассматриваем как бинарное представление числа $0 \leq x \leq n_S$ . Для преобразование числа в бинарный вектор $\vec{y}$ , в соответствии с утверждением 2, можно использовать следующий алгоритм:

Алгоритм 2. Вход: ; Выход: $\vec{y}$
для $k \leftarrow 1$ до :
если $x \geq \binom{p-k}{h}$ , то
$y_k \leftarrow 1$
$x \leftarrow x - \binom{p-k}{h}$
$h \leftarrow h - 1$
иначе $y_k \leftarrow 0$
вернуть $\vec{y}$

Обратное преобразование вектора $\vec{y}$ в число , в соответствии с утверждением 1, осуществляется по алгоритму:

Алгоритм 3. Вход: $\vec{y}, p, h$ ; Выход:
$x \leftarrow 0$
для $k \leftarrow 1$ до :
если , то
$x \leftarrow x + \binom{p-k}{h}$
$h \leftarrow h - 1$
вернуть

Пример работы криптосистемы

Код

Пример был сгенерирован с помощью программы, исходный код которой расположен ниже. Для этого я использовал SageMath. Вы можете установить данное ПО локально по инструкции либо использовать платформу CoCalc. Я воспользовался вторым вариантом, так как на платформе CoCalc есть возможность создать Jupyter Notebook и использовать его бесплатно без доступа в интернет.

from sage.all import *
import numpy as np


# функция, рассчитывающая публичный ключ
def calculate_public_key(p, perm, d, g, t):
    # вычисляем дискретный логарифмы a_i
    a = []
    for i in range(p):
        a.append(discrete_log(t + i, g))
    
    # вычисляем c_i
    c = []
    for i in range(p):
        b = a[perm[i]]
        c.append((b + d) % g.multiplicative_order())
    
    return tuple(c)

# функция, преобразующая число x в вектор y длины p и веса h
def number_to_vector(x, p, h):
    # вычисляем максимальное по величине число, которое может быть
    # зашифровано: 2^(максимальная длина одного сообщения в битах)
    # проверяем, что x меньше максимального числа
    assert x < 2**int(log(binomial(p, h), 2).n())

    y = []

    for k in range(1, p+1):
        bin_coef = binomial(p-k, h)

        if x >= bin_coef:
            y.append(1)
            x = x - bin_coef
            h = h - 1
        else:
            y.append(0)

    return y

# функция зашифрования сообщения
def encrypt(m, c, p, h):
    M = number_to_vector(m, p, h)
    multiplicative_order = p**h - 1

    msg = 0
    for i in range(len(M)):
        if M[i] == 1:
            msg = (msg + c[i] ) % multiplicative_order

    return msg

# функция, преобразующая вектор y длины p и веса h в число x
def vector_to_number(y, p, h):
    x = 0

    for k in range(1, p+1):
        if y[k-1] == 1:
            x = x + binomial(p-k, h)
            h = h - 1

    return x

# функция расшифрования сообщения
def decrypt(msg, p, h, irreducible_poly, g, inverse_perm, d):
    multiplicative_order = p**h - 1
    c_ = (msg - h * d) % multiplicative_order
    u = g ** c_
    # получаем кольцо многочленов над полем GF(p)
    # т.е. коэффициенты многочленов принадлежат полю GF(p)
    R = PolynomialRing(GF(p), "t_")
    # складывает u и irreducible_poly как элементы кольца многочленов
    s = R(u.polynomial()) + R(irreducible_poly)

    M = [0] * p
    # перебираем все множители многочлена s (все линейные)
    for f in factor(s):
        # получаем корень
        coef = 0
        coefs = f[0].coefficients()
        if len(coefs) != 1:
            coef = int(coefs[0])
        
        # восстанавливаем соответствующий бит
        M[inverse_perm[coef]] = 1

    return vector_to_number(M, p, h)

# Генерация параметров криптосистемы

# p - характеристика, h - степень расширения поля
p = 11
h = 5

# определяем символическую переменную
x = var('x')
# неприводимый многочлен (для примера зафиксирован),
# по модулю которого строится поле GF(p^h)
irreducible_polynomial = x**5 + 9*x**3 + 9*x**2 + 3*x + 10

# создаем конечное поле p^h, modulus - неприводимый многочлен
F = GF(p**h, name="t", modulus=irreducible_polynomial)
irreducible_polynomial = F.modulus()
# корень неприводимого многочлена, по модулю
# которого построено поле F
t = F.gen()
# примитивный элемент поля (для примера зафиксирован)
g = 2*t**4 + 8*t**3 + 4*t**2 + 5*t**1 + 2

# случайная перестановка (для примера зафиксирована)
permutation = np.array([5, 6, 7, 2, 8, 10, 4, 0, 1, 3, 9])
# вычисляем обратную перестановку
inverse_permutation = np.arange(p)
inverse_permutation[permutation] = inverse_permutation.copy()

# выбираем случайное число d (для примера зафиксировано)
d = 84997

c = calculate_public_key(p, permutation, d, g, t)

m = 217
print(f"исходное сообщение: {m}")

# Шифрование
msg = encrypt(m, c, p, h)
print(f"зашифрованное сообщение: {msg}")

# Расшифрование
decrypted_msg = decrypt(
    msg, p, h,
    irreducible_polynomial, g,
    inverse_permutation, d,
)
print(f"расшифрованное сообщение: {decrypted_msg}")

Генерация параметров криптосистемы:

Выбираем .
Выбираем неприводимый многочлен степени над : . Элементы конечного поля - многочлены степени не больше с коэффициентами в , арифметические операции в котором выполняются по модулю .
Выбираем примитивный элемент .
Вычисляем дискретные логарифмы

$a_{10} = log_g(t + 10) = 15120$

5. Выбираем случайную перестановку

$\pi = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 6 & 7 & 2 & 8 & 10 & 4 & 0 & 1 & 3 & 9 \end{pmatrix}$

т.е.

$b_0 = a_{\pi(0)} = a_5$ $b_1 = a_{\pi(1)} = a_6$

и т.д.

6. Выбираем случайное число и вычисляем

$c_0 = (b_0 + d) \: (\textrm{mod} \: p^h - 1) = (51642 + 84997) \: (\textrm{mod} \: 161050) = 136639$ $c_1 = (b_1 + d) \: (\textrm{mod} \: p^h - 1) = (38125 + 84997) \: (\textrm{mod} \: 161050) = 123122$ $c_2 = (b_2 + d) \: (\textrm{mod} \: p^h - 1) = (11604 + 84997) \: (\textrm{mod} \: 161050) = 96601$ $c_3 = (b_3 + d) \: (\textrm{mod} \: p^h - 1) = (27756 + 84997) \: (\textrm{mod} \: 161050) = 112753$ $c_4 = (b_4 + d) \: (\textrm{mod} \: p^h - 1) = (103713 + 84997) \: (\textrm{mod} \: 161050) = 27660$ $c_5 = (b_5 + d) \: (\textrm{mod} \: p^h - 1) = (15120 + 84997) \: (\textrm{mod} \: 161050) = 100117$ $c_6 = (b_6 + d) \: (\textrm{mod} \: p^h - 1) = (68089 + 84997) \: (\textrm{mod} \: 161050) = 153086$ $c_7 = (b_7 + d) \: (\textrm{mod} \: p^h - 1) = (134600 + 84997) \: (\textrm{mod} \: 161050) = 58547$ $c_8 = (b_8 + d) \: (\textrm{mod} \: p^h - 1) = (78964 + 84997) \: (\textrm{mod} \: 161050) = 2911$ $c_9 = (b_9 + d) \: (\textrm{mod} \: p^h - 1) = (2911 + 84997) \: (\textrm{mod} \: 161050) = 113210$ $c_{10} = (b_{10} + d) \: (\textrm{mod} \: p^h - 1) = (123616 + 84997) \: (\textrm{mod} \: 161050) = 47563$

Шифрование

Рассмотрим пример шифрования сообщения , или в бинарном виде: . Нам необходимо его преобразовать в бинарный вектор длины и веса в соответствии с алгоритмом 2. Его длина равна , т.е она не больше

$\lfloor log_2 \binom{p}{h} \rfloor = \lfloor log_2 \binom{11}{5} \rfloor = 8$

, соответственно делить это сообщение необходимости нет.

Используя алгоритм 2, преобразуем сообщение в бинарный вектор .
Далее складываем , которые соответствуют битам, равным :

$c = (c_1 + c_2 + c_4 + c_8 + c_{10}) \: (\textrm{mod} \: p^h - 1) =$ $= (123122 + 96601 + 27660 + 2911 + 47563) \: (\textrm{mod} \: 161050) = 136807$

- зашифрованное сообщение, которое будет отправлено.

Расшифрование

Чтобы расшифровать сообщение :

Вычисляем $c' = c - hd \: (\textrm{mod} \: p^h-1) = (136807 - 5 * 84997) (\textrm{mod} \: 161050) = 33922$ .
Вычисляем

$u(t) = g^{c'} \: (\textrm{mod} \: f(t)) = (2t^4 + 8t^3 + 4t^2 + 5t + 2)^{33922} \: (\textrm{mod} \: t^5 + 9t^3 + 9t^2 + 3t + 10) =$

3. Вычисляем

4. Раскладываем на линейные множители:

5. Применяем обратную перестановку к полученным корням:

$\pi^{-1}(1) = 8, \pi^{-1}(6) = 1, \pi^{-1}(7) = 2, \pi^{-1}(8) = 4, \pi^{-1}(9) = 10$

следовательно, .

6. Используя алгоритм 3, восстанавливаем исходное сообщение .

Вот и все

Спасибо всем, кто прочитал статью! Если тема оказалась вам интересна - следите за выходом следующих статей.

Буду рад, если подпишетесь на мой профиль на Хабре и на личный блог: там я публикую свои статьи, проекты, новости и заметки об интересных технологиях. Также код из статьи доступен в GitHub-репозитории в формате Jupyter Notebook.