СПОСОБ АСИММЕТРИЧНОГО ШИФРОВАНИЯ СООБЩЕНИЙ НА ОСНОВЕ МОДИФИЦИРОВАННОЙ ЗАДАЧИ О РЮКЗАКЕ

1. Область техники, к которой относится изобретение

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

2. Уровень техники

а) Описание аналогов способа

Известен способ шифрования на основе модифицированной задачи о рюкзаке с использованием Китайской теоремы об остатках (S.C. Lu and L.N. Lee "A Simple and Effective Public-Key Cryptosystem", COMSAT Technical Review, 1979, pp. 15-24). В данном способе:

генерируют на принимающей стороне в устройстве формирования ключей: секретный ключ в виде вектора а'=(р₁, р₂; а₁₁, а₁₂, а₂₁, а₂₂), где: р₁, р₂ - простые большие числа, а₁₁, а₁₂, а₂₁, а₂₂ - числа среднего размера, причем а₁₁а₁₂-а₂₁а₂₂≠0; открытый ключ в виде вектора а=(r, c₁, c₂), где: r=р₁⋅р₂, а c_i получают на основе Китайской теоремы об остатках: с≡a_ij(mod p_i), i=1, 2; j=1, 2;

опубликовывают (пересылают на передающую сторону) открытый ключ а';

делят сообщение X на передающей стороне на блоки S'=(x₁, x₂);

зашифровывают блок S'=(x₁, x₂) и получают криптограмму S на передающей стороне в шифраторе в соответствии со следующим подходом: S≡c₁x₁+c₂x₂(mod r);

пересылают криптограмму S на принимающую сторону;

расшифровывают криптограмму S и получают S'=(x₁, x₂) на принимающей стороне в дешифраторе на основе решения двух линейных уравнений: a_i1x₁+a_i2x₂=s_i, i=1, 2, где: s_i≡S(modp_i), i=1, 2.

Недостатком данного способа является низкая криптостойкость построенных на его основе криптосистем. Линейность функции шифрования позволяет криптоаналитику восстанавливать открытый текст из зашифрованного текста без фактического нахождения секретного ключа (J.-M. Goethals and С.Couvreur. "A Cryptanalytic Attac on the Lu-Lee Public-Key Cryptosystem", Philips Journal of Research, Vol. 35, Nos. 4/5, 1980, pp. 301-306).

Известен способ шифрования на основе модульных рюкзаков (V. Niemi. "A New Trapdoor in Knapsacks", Advances in Cryptology EUROCRYPT'90 Proceedings, Springer-Verlag, 1991, pp. 405-411). В данном способе:

генерируют на принимающей стороне в устройстве формирования ключей: секретный ключ в виде вектора a'=(C, D, S, Δ, R), где: C, D, S∈(Z/pZ)^n×n - матрицы, элементами которых являются числа |g|≤k, Δ∈(Z/pZ)^n×n - диагональная матрица, элементами которой являются числа |g|>[p/2]-k, R∈(Z/pZ)^nxn - невырожденная матрица; открытый ключ в виде вектора а=(р,Е), где: Е=(А В) - матрица размером n×2n, А=R^-1(Δ-SC), В=-R^-1SD;

опубликовывают (пересылают на передающую сторону) открытый ключ а';

зашифровывают сообщение X={x∈{0,l}²ⁿ} и получают криптограмму S={s∈(Z/pZ)ⁿ} в соответствии со следующим подходом ℑ:X→S, ℑ(x)=Ex;

пересылают криптограмму S на принимающую сторону;

расшифровывают криптограмму S и получают исходное сообщение в соответствии с правилом:

где: 1≤i<n. Значение x_i, n+1≤i≤2n вычисляют путем решения уравнения: Вх⁽²⁾=s-Ах⁽¹⁾, где х⁽¹⁾=(х₁, …, x_n)^Т и х^{2)=(x_n+1, …, x_2n)^Т.

Недостатком данного способа также является низкая криптостойкость построенных на его основе криптосистем ввиду возможности восстановления открытого текста из зашифрованного текста без фактического нахождения секретного ключа (Т.М. Chee. "The Cryptanalysis of New Public-Key Cryptosystem Based on Modular Knapsacks", Advances in Cryptology CRYPTO'91 Proceedings, Springer-Verlag, 1992, pp. 204-212).

Успешных криптоаналитических атак не известно на способ, основанный на использовании многостадийной рюкзачной системы (Н.А. Hussain, J,W,A, Sada and S.M. Kalipha, "New Multistage Knapsack Public Key Cryptosystem", International Journal of Systems Science, v. 22, n. 11, Nov 1991, pp. 2313-2320). В нем фиксируют рюкзачный вектор для каждого этапа, и выход (зашифрованный текст) после каждой стадии шифрования используют в качестве входных данных (текста) на следующий этап. Существенным недостатком данного способа является значительное возрастание требований к вычислительным ресурсам.

Не известно успешной атаки также на способ, построенный на основе мультипликативного рюкзака (S.K. Yasuyuki Murakami and М. Kasahara "New Multiplicative Knapsack-Type Public Key Cryptosystems", IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol. E84-A No. 1, 2001, pp. 188-196). Данный способ основан на задаче дискретного логарифмирования, что также существенно увеличивает требования к вычислительным ресурсам в процессе расшифрования.

б) Описание прототипа способа

Наиболее близкими по своей технической сущности (прототипом) к заявляемому способу асимметричного шифрования сообщений является классический способ шифрования с открытым ключом Меркла-Хеллмана (Пат. 218582 U.S.A., МПК H04L 9/04. Public key cryptographic apparatus and method / Martin E. Hellman, Stanford; Ralph C. Merkle, Palo Alto, both of Calif, заявитель и патентообладатель The Board of Trustees of the Leland Stanford Junior University, Stanford, Calif. - №839939, заявл. 06.10.1977; опубл. 19.08.1980). В данном способе:

генерируют на принимающей стороне в устройстве формирования ключей: секретный ключ в виде сверхвозрастающего вектора с количеством элементов, равным n, причем - элементы вектора а'; открытый ключ на основе элементов секретного ключа в виде вектора a={a_l, …, a_i, …, a_n}, где i=1, 2, …, n; m, w - большие взаимно простые целые числа;

опубликовывают (пересылают на передающую сторону) открытый ключ а';

зашифровывают исходное сообщение X и получают криптограмму S на передающей стороне в шифраторе путем суммирования произведений элементов вектора а открытого ключа шифрования с битами исходного сообщения, представленными в виде элементов вектора

пересылают криптограмму S на принимающую сторону;

расшифровывают криптограмму S на принимающей стороне в дешифраторе в соответствии со следующим подходом:

где: S' - откорректированное значение зашифрованного сообщения (объем рюкзака в «простой» задаче о рюкзаке), позволяющее получить исходное сообщение X.

Недостатком указанного способа (прототипа) является низкая криптостойкость построенных на его основе криптосистем, так как с применением алгоритма целочисленного программирования Ленстры они могут быть раскрыты за полиномиальное время (Баричев С.Г., Серов Р.Е. Основы современной криптографии. Учебный курс - М.: Горячая линия - Телеком, 2006. - 152 с.).

3. Раскрытие изобретения

а) Технический результат, на достижение которого направлено изобретение

Целью настоящего изобретения является повышение криптостойкости построенных на его основе криптографических систем. Поставленная цель достигается тем, что перед передачей сообщения по открытым каналам связи производится его зашифрование с использованием модифицированной задачи о рюкзаке, допускающей использование повторяющихся элементов рюкзачного вектора. Криптостойкость соответствующей системы сравнительно выше, чем криптостойкость аналогичных стандартных систем. В самом деле, если обозначить через N(K) - количество всех вариантов выбора ключей, то для стандартного рюкзака оно равно N(K)=2ⁿ, а для модифицированного рюкзака, допускающего повторение элементов рюкзачного вектора: N(K)=pⁿ, где n - количество элементов рюкзачного вектора, р≥3 - максимальное допустимое количество повторений элемента рюкзачного вектора.

б) Сходными признаками способа (прототипа) Меркла-Хеллмана с заявляемым способом являются следующие:

генерируют на принимающей стороне в устройстве формирования ключей открытый ключ на основе элементов секретного ключа в виде вектора a={a_l, …, a_i, …, a_n}, где , i=1, 2, …, n; m, w - большие взаимно простые целые числа;

опубликовывают (пересылают на передающую сторону) открытый ключ а';

пересылают криптограмму S на принимающую сторону.

в) Существенными отличительными признаками заявляемого способа асимметричного шифрования сообщений на основе модифицированной задачи о рюкзаке от известного способа шифрования с открытым ключом Меркла-Хеллмана являются следующие:

генерируют секретный ключ на принимающей стороне в устройстве формирования ключей в виде сверхвозрастающего вектора так, чтобы для каждого элемента вектора а' выполнялось неравенство - элементы вектора а', р - максимальное допустимое количество повторений j-го элемента вектора а';

делят сообщение X на передающей стороне на блоки S' в виде вектора элементов x_i размером по b двоичных разрядов;

зашифровывают блок S' исходного сообщения на передающей стороне в шифраторе путем суммирования произведений элементов вектора а открытого ключа шифрования с элементами x_i блока S';

расшифровывают блок S' исходного сообщения X на принимающей стороне в дешифраторе путем обратного модульного преобразования и последовательного вычитания одного и того же значения элемента секретного ключа до тех пор, пока зашифрованное значение не станет меньше значения вычитаемого элемента, и только тогда перехода к следующему элементу при вычитании:

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

4. Краткое описание чертежей

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

5. Осуществление изобретения

Рассмотрим процесс зашифрования и расшифрования текстового сообщения с применением заявляемого способа асимметричного шифрования сообщений на основе модифицированной задачи о рюкзаке. В качестве исходного сообщения рассмотрим слово «XCODE», где каждая буква кодируется 8-битным числом, совместимым со стандартом ACSII. Выберем р (максимальное количество повторений элементов рюкзака) равным 21. Выберем b (публикуемое количество разрядов для коэффициентов повторений) равным 4.

Соответственно, исходное сообщение переводят в двоичную форму и разбивают на группы по 4 бита. Данное преобразование приведено в таблице 1.

В соответствии с преобразованием, приведенным в таблице 1, исходное сообщение X можно рассматривать, как последовательность элементов разрядностью 4 бита: (5, 8, 4, 3, 4, 15, 4, 4, 4, 5).

Далее выберем сверхвозрастающий обобщенный рюкзачный вектор а':

Также выберем m равным 13722115 и w равным 12498357. Соответственно, выбранные w и m являются взаимно простыми. Обратный w^-l по модулю m равен 6856348:

w⋅w^-lmodm=12498357⋅6856348mod13722115=1.

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

a=w⋅а'modm={10050841,340904,2263952,2705373,9527698}.

Соответственно, так как каждому элементу (которых всего n, равное 5) рюкзачного вектора необходимо сопоставить часть исходного сообщения разрядностью 4 бита (разрядность равна b в соответствии с выбранным р) то исходное сообщение необходимо разбить на порции по 5 элементов:

X1=(5,8,4,3,4); Х2=(15,4,4,4,5).

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

S1=5⋅10050841+8⋅340904+4⋅2263952+3⋅2705373+4⋅9527698=108264156;

S2=15⋅10050841+4⋅340904+4⋅2263952+4⋅2705373+5⋅9527698=219642021.

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

На стороне получателя полученные шифрограммы подвергаются обратному модульному преобразованию:

S1'=S1⋅w^-1modm=108264156⋅6856348mod13722115=2584373;

S2'=S2⋅w^-1modm=219642021⋅6856348mod13722115=3236088.

Полученные значения являются суммами повторяющихся элементов сверхвозрастающего рюкзачного вектора а', из которых можно тривиально получить исходные коэффициенты повторения:

В результате выполнения операции получаются значения, соответствующие порции исходного сообщения X1=(5, 8, 4, 3, 4). Аналогичные действия затем выполняются для S2, в результате чего получается вторая порция исходного сообщения Х2=(15, 4, 4, 4, 5). Путем соединения полученных порций и обратного перекодирования согласно таблице 1, получается исходное сообщение «XCODE» принятое получателем.

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

Сначала получатель формирует публичный (открытый) Е и секретный D ключи посредством блока формирования ключей 10, передавая в качестве исходных данных подготовленные исходные параметры для генерации ключей (а', b, w, w^-l, m). Величина выбранных значений должна быть достаточно велика для того, чтобы обеспечить нецелесообразность попыток прямого подбора сгенерированных ключей. Например, достаточно надежной можно считать систему, в которой значения w, m и элементы векторов а' и а имеют разрядность не менее 512 бит. При этом значение b не рекомендуется брать близким к единице, так как подобные значения приводят к генерации рюкзачного вектора с малым количеством повторяющихся элементов, что негативно отражается на криптостойкости системы.

Полученный секретный ключ D передается в дешифратор 9, а публичный ключ Е передается в узел передачи информации 8 через открытые каналы передачи 7 на узла передачи отправителя 2, который передает полученный публичный ключ Е шифратору 1.

Также передаваемый публичный ключ Е может быть перехвачен устройством криптоаналитика 4 (при этом криптоаналитик получает информацию об элементах вектора a и о значении b). При этом перехваченный публичный ключ Е передается в блок криптоанализа 6. Устройство блока криптоанализа 6 полностью зависит методов криптоанализа, используемых криптоанатиком и в данном случае не рассматривается. Функция блока криптоанализа 6 заключается в подборе по перехваченному публичному ключу Е и шифрограмм S таких исходных параметров для блока формирования ключей 5, которые позволят получить секретный ключ Dx, который позволит получить сообщение Хх, равное исходному сообщению X. Соответственно, для криптосистемы, в которой исходные параметры генерации ключей выбраны в соответствии с описанными ранее рекомендациями, процесс поиска подходящего ключа Dx будет нецелесообразен по вычислительной сложности, либо по доступным ресурсам.

После того, как публичный ключ Е будет передан в шифратор 1, отправитель может передавать в шифратор 1 исходное сообщение X, подлежащее передачи по открытым каналам 7 получателю. При этом шифратор 1, получая сообщение X, генерирует зашифрованные порции информации (шифрограммы) S, которые передает посредством узла передачи 2 через открытые каналы 7 на устройство получателя 8. Устройство получателя 8 принимает шифрограммы S и передает в дешифратор 9. Дешифратор 9, имея секретный ключ D, и шифрограмму S, формирует расшифрованную порцию исходного сообщения X, которую передает получателю.

Также передаваемые шифрограммы S могут быть перехвачены устройством криптоаналитика 4. Устройство криптоаналитика 4 получает шифрограммы S и передает их в блок криптоанализа 6. Далее по описанной ранее схеме криптоаналитик производит попытки подбора исходных параметров для блока формирования ключей 5 с целью подбора секретного ключа Dx, который должен быть передан на дешифратор 3 с целью получения порций сообщения Хх, соответствующих порциям исходного сообщения X. Соответственно, для криптосистемы, в которой исходные параметры генерации ключей выбраны в соответствии с описанными ранее рекомендациями, процесс поиска подходящего ключа Dx будет нецелесообразен по вычислительной сложности, либо по доступным ресурсам.