КРИПТОГРАФИЧЕСКИЙ ПРЕОБРАЗОВАТЕЛЬ ДВОИЧНЫХ ДАННЫХ Российский патент 2004 года по МПК H04L9/28 

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

Известны устройства для преобразования двоичных данных.

В работе John В. Kam, George I. Davida "Structured design of Substitution-Permutation encryption networks" IEEE Transactions on computers, vol. c-28, Nr.10, October 1979, pp.747-751, Fig.2 описано устройство для управляемого преобразования двоичных данных. Устройство состоит из трех блоков управляемых подстановок (БУП) и двух блоков фиксированных перестановок (БФП). Каждый БУП состоит из трех управляемых элементов (УЭ), имеющих 3-разрядные информационные входы и выходы и одноразрядные управляющие входы. Информационные 9-разрядные выходы БУП подключены к соответствующим 9-разрядным входам БФП, выходы которых в свою очередь подключены к 9-разрядным входам БУП. Информационные вход первого БУП и выход третьего БУП, являются 9-разрядными информационными входом и выходом устройства. Совокупность управляющих входов УЭ в каждом БУП является его управляющим входом. В свою очередь, управляющие входы всех БУП являются 9-разрядным управляющим входом устройства.

Однако известное устройство имеет недостатки:

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

2. Нетехнологичность изготовления, обусловленная необходимостью использования БУП с различной разрядностью информационного входа при построении устройств с информационным входом, размер которого соответствует типовому размеру блоков данных, а именно равен натуральной степени числа 2, т.е. равен 2^h, где h=3, 4, 5,... .

Известно также устройство для преобразования двоичных данных по Пат. РФ №2140715, МПК H 04 L 9/28, опубл. 27.10.99. Известное устройство состоит из w≥ 2 n-разрядных последовательно соединенных сумматоров и, по крайней мере, одного узла перестановок, который выполнен в виде узла управляемых перестановок. Информационный вход узла перестановок является управляющим входом устройства, а его выход является вторым выходом р-го сумматора, где 1≤ р≤ w.

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

Наиболее близким по своей технической сущности к заявленному является криптографический преобразователь двоичных данных, описанный в книге: Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. - СПб.: БХВ-Петербург, 2002, с.174-176, рис.3.5.

Устройство-прототип состоит из S≥ 2 блоков управляемых подстановок (БУП), S-1 блоков фиксированных перестановок (БФП) и снабжено n-разрядными, где n≥ 4, информационными входом и выходом. Информационный n-разрядный выход i-го, где i=1, 2,... , S-1, БУП подключен к n-разрядному входу i-го БФП, n-разрядный выход которого подключен к n-разрядному информационному входу (i+1)-го БУП. Каждый j-й, где j=1, 2,... , S, БУП снабжен m_j-разрядным управляющим входом, а n-разрядные информационные вход первого и выход 5-го БУП являются n-разрядными информационными соответственно входом и выходом устройства.

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

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

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

Поставленная цель достигается тем, что в известном криптографическом преобразователе двоичных данных, содержащем S≥ 2 БУП, S-1 БФП и снабженным n-разрядными, где n≥ 4, информационными входом и выходом, n-разрядный информационный выход i-го, где i=1, 2,... , S-1, БУП подключен к n-разрядному входу i-го БФП, n-разрядный выход которого подключен к n-разрядному информационному входу (i+1)-го БУП, причем каждый j-й БУП, где j=1, 2,... , S, снабжен m_j-разрядным управляющим входом, а n-разрядные информационные вход первого и выход S-го БУП являются n-разрядными информационными соответственно входом и выходом устройства, i-й и (S+1-i)-й БУП, а также i-й и (S-i)-й БФП выполнены взаимнообратимыми. При S четном S/2-й БФП, а при S нечетном [(S+1)/2]-й БУП выполнены внутренне самообратимыми. Управляющие входы i-го и (S+1-i)-го БУП выполнены равной разрядности, т.е. m_i=m_S+1-i.

БУП состоит из Z≥ 2 управляемых элементов (УЭ). Каждый УЭ снабжен t-разрядными, где t=2, 3, информационными входом и выходом и w-разрядным, где w=1, 2, управляющим входом. Совокупности информационных входов, выходов и управляющих входов всех Z_j УЭ являются соответственно n-разрядными информационными входом, выходом и m_j-разрядным управляющим входом БУП. Причем при S нечетном все УЭ [(S+1)/2]-го БУП выполнены внутренне самообратимыми.

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

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

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

Заявленное устройство поясняется чертежами, на которых показаны:

- на фиг.1 - общая структурная схема устройства;

- на фиг.2 - вариант построения схемы БУП;

- на фиг.3 - типовые варианты УЭ;

- на фиг.4 - электрические схемы УЭ типа S_2/1;

- на фиг.5 - электрические схемы УЭ типа S_2/2;

- на фиг.6 - электрические схемы УЭ типа S_3/1;

- на фиг.7 - рисунок, поясняющий взаимообратимость БУП (БФП);

- на фиг.8 - рисунок, поясняющий внутренне самообратимый БУП (БФП);

- на фиг.9 - схема, иллюстрирующая взаимообратимость коммутации в двух БФП;

Криптографический преобразователь двоичных данных, показанный на фиг.1, состоит из S БУП 1₁–1_S, S-1 БФП 2₁-2_S-1.

Число S БУП 1 и, соответственно, БФП 2 выбирают, исходя из компромиссного учета предъявляемых к устройству требований криптостойкости, скорости преобразования и сложности реализации. Однако выбранное значение S должно удовлетворять условию S≥ 2. Каждый БУП 1 снабжен n-разрядными информационными входом и выходом, где значение n определяется разрядностью подлежащего преобразованию блока двоичных данных. Кроме того, каждый j-й, где j=1, 2,... , S, БУП 1 снабжен m_j-разрядным управляющим входом, где значение m_j определяется разрядностью управляющего вектора. В свою очередь, при выборе m_j и n должно соблюдаться условие m_j≥_{4 и n≥ 4. Каждый БФП 2 также снабжен n-разрядными входом и выходом. Информационный n-разрядный выход i-го БУП 1i где i=1, 2,... , S-1, подключен к n-разрядному входу i-го БФП 2i-разрядный выход которого подключен к n-разрядному информационному входу (i+1)-го БУП 1i+1. Информационные n-разрядные вход первого БУП 11 и выход S-го БУП 1s являются соответственно n-разрядными информационными входом и выходом устройства.}

Управляющие входы i-го и (S+1-i)-го БУП 1 выполнены равной разрядности: m_i=m_S+1-i. Кроме того, i-й и (S+1-i)-й БУП 1, а также i-й и (S-i)-й БФП 2 выполнены взаимообратимыми. При S четном S/2-й БФП 2_S/2 и при S нечетном [(S+1)/2]-й БУП 1_(S+1)/2 выполнены внутренне самообратимыми.

На фиг.1 индексами х₁, x₂, x₃,... ,х_n и у₁, у₂, у₃, у_n обозначены разряды n-разрядных информационных входа Х и выхода У устройства. Разряды, приведенные в скобках, указывают на изменение типа преобразования, когда входным является блок двоичных данных У и, соответственно, выходным - X.

Показанный на фиг.2 БУП 1 предназначен для выполнения операции управляемой операционной подстановки над поступающим на его информационный вход n-разрядным блоком двоичных данных в зависимости от m_i-разрядного управляющего вектора, поступающего на управляющий вход.

В общем случае, любой из БУП 1, например, первый 1₁, включает Каждый из УЭ снабжен t-разрядными (t=2,3) информационными входом и выходом и w-разрядными (w=1,2) управляющим входом.

Совокупности информационных входов, выходов и управляющих входов всех , являются, соответственно, n-разрядными информационными входом, выходом и w i-разрядным управляющим входом БУП 1₁, т.e. , ,

где k=1, 2,... ,Z₁.

Каждый УЭ 1.1 предназначен для выполнения элементарной операции управляемой операционной подстановки над малоразрядным (t=2,3) входящим блоком двоичных данных с помощью малоразрядного (w=1,2) управляющего вектора.

На фиг.3 приведены типовые варианты построения УЭ, в общем виде обозначенные как S_t/w (фиг.3а), где t - разрядность информационных входа и выхода, w-разрядность управляющего входа.

Типовыми вариантами УЭ являются S_3/1 (фиг.3б), S_2/1 (фиг.3в) и S_2/2 (фиг.3г), которые выполняют элементарные управляемые подстановки типа 3× 3 (S_3/1) и 2× 2 (S_2/1 и S_2/2). Все варианты УЭ могут быть реализованы в виде простых комбинационных электронных схем, некоторые из которых показаны на фиг.4 (S_2/1), фиг.5 (S_2/2) и фиг.6 (S_3/1).

Так, на фиг.4 показаны варианты электронных схем, реализующих подстановки типа 2× 2, выполняемые над двухбитовым двоичным вектором (х₁, x₂), в зависимости от текущего значения одного управляющего бита (w=1). Каждый бит выходного двоичного вектора (у₁, у₂) является булевой функцией от трех переменных, т.е. у₁=f₁(x₁, х₂, w) и y₂=f₂(x_1, х₂, w). На фиг.4 приведены булевы функции, описывающие подстановки с помощью приведенных вариантов схем УЭ типа S_2/1 (фиг.4а и 4б).

На фиг.5 приведены варианты электронных схем, реализующих подстановки типа 2× 2, выполняемые над двухбитовым двоичным вектором (x₁, x₂), в зависимости от четырех возможных значений двухбитового управляющего вектора (w=2). Например, вариант, соответствующий значению управляющего вектора w=(1, 1) задан как инверсия двух входных битов (х₁, х₂) - операция инверсии обозначена символом “О”. В данном варианте УЭ каждый бит выходного двоичного вектора (у₁, у₂) является булевой функцией от четырех переменных, т.е. у₁=f₁(x₁, x₂, w₁, w₂) и y₂=f₂(x₁, x₂, w₁, w₂).

На фиг.6 приведены варианты электронных схем, реализующих подстановки типа 3× 3, выполняемые над трехбитовым двоичным вектором (х₁, x₂, x₃) в зависимости от текущего значения одного управляющего бита (w=1). На указанных схемах символами “&”, “V” и “⊕ ” обозначены, соответственно, логические элементы И, ИЛИ и операция суммирования по модулю 2. Каждый бит выходного двоичного вектора (у₁, у₂, у₃) является булевой функцией от четырех переменных у₁=f₃(x₁, х₂, х₃, w), y₂=f₂(x₁, х₂, x₃, w), y₃=f₃(x₁, x₂, x₃, w).

В зависимости от конкретного варианта схемотехнической реализации управляемых операционных подстановок из трех типов УЭ 1.1 может быть выбран наиболее подходящий из них, который обеспечит оптимизацию использования схемотехнических ресурсов при заданном уровне криптостойкости и скорости преобразования. В частности, на фиг.2 показан БУП 1, состоящий из четырех УЭ 1.1₁-1.14, Два из которых типа S_2/2, а два S_3/1. Такой БУП 1 реализует управляемую операционную подстановку над 10-разрядным входным двоичным вектором (n=10) в зависимости от 6-разрядного управляющего вектора (m_i=6).

БФП 2₁–2_S предназначены для выполнения операции фиксированной перестановки битов входного n-разрядного двоичного вектора на его выходе. Коммутацию входов и выходов i-го БФП 2 выполняют произвольно. В частности, на фиг.7 в БФП 2_i, разряды 8-разрядного входа (n=8) х₁, х₂, х₃,... , х₈ переставлены на выходе в следующей последовательности x₁, x₃, x₂, x₅, x₄, x₇, x₆, x₈.

При выборе структуры и схем реализации УЭ в БУП 1, а также при выборе вариантов коммутации в БФП 2 необходимо выполнение условий:

- БУП 1 с номерами i и (S+1-i), а также БФП 2 с номерами i и (S-i) должны быть выполнены взаимно обратимыми;

- при S четном S/2-й БФП 1 и при 5 нечетном [(S+1)/2]-й БУП 2 должны быть выполнены внутренне самообратимыми.

Под взаимно обратимыми понимают пару БУП 1 или пару БФП 2, которые выполняют взаимно обратное преобразования: один из блоков - прямое преобразование Y=F₁(X), второй блок - обратное преобразование X=F-12

(Y). Например, если на вход первого блока подана n-разрядная последовательность цифровых данных Х (x₁, x₂,... ,x_n) и в результате преобразования на его выходе получена n-разрядная последовательность Y (у₁, y₂, y_n), то при подаче на вход второго блока, взаимно обратимого по отношению к первому, n-разрядной последовательности Y (у₁, y₂, у_n), на его выходе после преобразования должна быть получена n-разрядная последовательность X(x₁, x₂,... , x_n) (см. фиг.7).

Внутренне самообратимым является БУП 1 или БФП 2, который реализует преобразование, являющееся инволюцией: X=F(Y), если Y=F(X), т.е. F(F(X))=Х (см. фиг.8).

Внутренне самообратимым БУП 1 будет, если каждый из его УЭ 1.1 также обеспечивает преобразование, являющееся инволюцией. Схемы УЭ 1.1, реализующие такое преобразование, известны. В частности, на фиг.6 показаны УЭ 1.1 типа S_3/3, типа выполняющие преобразование, являющееся инволюцией.

Вариант выполнения взаимно обратимых БФП 2 показан на фиг.9 - 2_i и 2_i+1. Каждый из этих БФП является также внутренне самообратимым.

Заявленное устройство работает следующим образом. При подаче на вход n-разрядного двоичного вектора Х (прямое преобразование) последовательно в каждом из БУП 1 и затем в подключенном к нему БФП 2 над ним выполняют соответственно управляемую операционную подстановку и фиксированную перестановку. Значение соответствующих разрядов n-разрядного вектора на выходе конкретного (например, первого) БУП 1₁ определяется как структурой БУП (числом Z₁ и типами УЭ 1.1), а также значениями соответствующих разрядов n-разрядного управляющего вектора. На n-разрядном выходе БФП 2₁ положение соответствующих разрядов преобразованного в БУП 1₁ n-разрядного вектора будет определяться выбранным вариантом коммутации входов и выходов БФП 2₁ (см. фиг.9). Число (т.е. число S) таких циклов преобразования выбирают с учетом предъявленных к устройству требований по криптостойкости и скорости преобразования. На выходе устройства значения разрядов (у₁, у₂,... y_n) n-разрядного преобразованного двоичного вектора Y будут определяться совокупно проведенными над ним операциями управляемых операционных подстановок (в БУП 1₁-1_s) и фиксированных перестановок (в БФП 2₁-2_s-1) в зависимости от значений битов m-разрядных управляющих векторов на управляющих входах 1₁-1_s.

Выполнение обратного преобразования, т.е. получение на выходе устройства n-разрядного двоичного вектора X, достигается тем, значениям битов m_i-разрядного управляющего вектора на управляющем входе i-го БУП 1_i, придают значения битов m_S+1-i-го управляющего вектора, которые имел БУП 1_S+1-i на своем управляющем входе при прямом преобразовании. И наоборот, на управляющем входе БУП 1_S+1-i необходимо значениям битов m_S+1-i - разрядного управляющего вектора придать значения битов, которые имел БУП 1_i, на своем управляющем входе при прямом преобразовании.

В силу взаимной обратимости i-го и (S+1-i)-го БУП в i-м БУП 1_i реализуется обратная операция управляемой подстановки по отношению к БУП с номером (S+1-i) и соответственно в БУП с номером (S+1-i) реализуется обратная операция управляемой подстановки по отношению к БУП с i-м номером.

При S нечетном управляющий вектор, подаваемый на БУП с номером [(S+1)/2], остается неизменным, и в силу внутренней самообратимости этого БУП процесс прямого и обратного преобразования в нем происходит автоматически.

В БФП 2 прямое и обратное преобразование обеспечивается взаимно обратимыми схемами коммутации входов и выходов в БФП с номерами i и (S-i) (см. фиг.9), а также использованием S/2-го БФП при S четном с внутренней самообратимостью (см. фиг.9)

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

Изобретение относится к области электросвязи, а именно к области криптографических устройств для защиты информации, передаваемой по телекоммуникационным сетям.Устройство состоит из S ≥ 2 блоков управляемых подстановок (БУП) 1 и S-1 блоков фиксированных перестановок (БФП) 2. Каждый БУП 1 снабжен m-разрядным управляющим входом (m ≥ 4) и n-разрядными информационными входом и выходом (n ≥ 4). БУП 1 и БФП 2 включены каскадно по n-разрядным информационным входам (выходам). Информационные n-разрядные вход первого БУП и выход S-го БУП являются информационными n-разрядными входом и выходом преобразователя. БУП с номерами i и (S+1-i), а также i-й и (S-i)-й БФП выполнены взаимообратимыми. Кроме того, при четном S S/2-й БФП, а при S нечетном (S+1)/2-й БУП выполнены внутренне самообратимыми. Разрядности управляющих входов i-го и (S+1-i)-го БУП выбраны равными. Техническим результатом, достигаемым в заявленном устройстве, является обеспечение прямого и обратного преобразования n-разрядного двоичного вектора. 1 з.п. ф-лы, 9 ил.

1. Криптографический преобразователь двоичных данных, содержащий S ≥ 2 блоков управляемых подстановок и S-1 блоков фиксированных перестановок, n-разрядный, где n ≥ 4, информационный выход i-го, где i = 1, 2,..., S-1, блока управляемых подстановок подключен к n-разрядному входу i-го блока фиксированных перестановок, n-разрядный выход которого подключен к n-разрядному информационному входу (i+1)-го блока управляемых подстановок, а n-разрядный информационный вход первого и n-разрядный информационный выход S-го блоков управляемых подстановок являются соответственно n-разрядными информационными входом и выходом криптографического преобразователя двоичных данных, причем j-й блок управляемых подстановок, где j =1,2,..,S, снабжен m_j-разрядным, где m_j ≥ 4, управляющим входом, отличающийся тем, что i-й и [(S+1)-i]-й блоки управляемых подстановок, а также i-й и (S-i)-й блоки фиксированных перестановок выполнены взаимообратимыми, при S четном S/2-й блок фиксированных перестановок и при S нечетном [(S+1)/2]-й блок управляемых подстановок выполнены внутренне самообратимыми, причем управляющие входы i-го и [(S+1)-i]-го блоков управляемых подстановок выполнены равной разрядности: m_i = m_S+1-i.2. Криптографический преобразователь двоичных данных по п.1, отличающийся тем, что j-й блок управляемых подстановок состоит из Z_j ≥ 2 управляемых элементов, каждый из которых снабжен t-разрядными, где t = 2, 3, информационными входом и выходом и w-разрядным, где w = 1, 2, управляющим входом, а совокупности информационных входов, выходов и управляющих входов всех Z_j управляющих элементов являются соответственно n-разрядными информационными входом, выходом и m_j-разрядным управляющим входом j-го блока управляемых подстановок, причем при S нечетном все управляющие элементы [(S+1)/2]-го блока управляемых подстановок выполнены внутренне самообратимыми.