СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ Российский патент 2015 года по МПК H04L9/06 

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

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

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

Известны способы итерационного криптографического преобразования сообщений фиксированной длины, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые с использованием секретного ключа, например способ, реализованный в виде алгоритма блочного шифрования AES (Advanced Encryption Standard) [1].

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

Введем обозначения:

- V_h - множество всех двоичных векторов длины h;

- m - сообщение (двоичный вектор) длины w;

- n - количество итерационных ключей, причем n>2;

- w - размер сообщения в битах, причем w=b·t,

где t, b∈N (множество натуральных чисел);

- с - сообщение (двоичный вектор) длины w;

- $$\tau :Z_{2^h}\to V_b$$ - взаимно-однозначное преобразование, которое ставит в соответствие целому числу из промежутка 0, …, 2^b-1 вектор его двоичного представления, младшие биты числа находятся справа.

- А||В - операции конкатенации двух векторов А и В, результатом является вектор, в котором левая часть совпадает с вектором А, а правая часть совпадает с вектором В;

- X[K] - линейное преобразование, зависящее от итерационного ключа K, причем

X[K]:V_w→V_w,

X[K](a)=K⊕a,

где а - это сообщение (двоичный вектор) длины w,

K∈V_w;

- S - нелинейное взаимно-однозначное преобразование, причем

S:V_w→V_w,

S(a)=S(a _t-1||…||a ₀)=π(a _t-1)||…||π(a ₀),

где а∈V_w,

a=a _t-1||…||a ₀,

a_i∈V_b,

π - любое взаимно-однозначное преобразование, причем

π:V_b→V_b

- L₁ - линейное взаимно-однозначное преобразование, причем

L₁:V_w→V_w;

- L₂ - линейное взаимно-однозначное преобразование, причем

L₂:V_w→V_w;

- L - линейное взаимно-однозначное преобразование, причем

L:V_w→V_w;

L(a)=a·D,

где D - невырожденная матрица размером w×w;

G=D^-1 - обратная матрица по отношению к D;

G_i - матрица размера b×w, состоящая из подряд расположенных строк матрицы G с номерами

(t-1-i)·b+1, (t-1-i)·b+2, …, (t-i)·b,

где i=0, …, t-1, a∈V_w;

L является композицией линейных преобразований L₁ и L₂:

L(a)=L₁(L₂(a)).

В указанных обозначениях алгоритм зашифрования AES запишется в виде

c=X[K_n]L₂S…X[K₁]LSX[K₀](m),

а алгоритм расшифрования:

m=X[K₀]S^-1L^-1…S^-1L^-1X[K_n-1]S^-1L₂ ^-1X[K_n](c),

где K_i - раундовые ключи K_i∈V_w, i=0, …, n.

Известен способ реализации алгоритма зашифрования, использующего композицию преобразований LS (сначала выполняется S, потом - L), на универсальных вычислительных платформах с достаточным количеством памяти. Основная идея способа заключается в объединении данных преобразований в одно и его табличная реализация. Этот способ описан, например, в работах [2, 3].

Алгоритм расшифрования требует выполнения композиции преобразований S^-1L^-1 (сначала L^-1, потом - S^-1). Такой способ объединения этих преобразований и его табличная реализация в общем случае практически неприменимы из-за чрезвычайного большого объема таблиц, что является его недостатком.

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

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

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

Отметим, что для одной итерации в силу линейности преобразования L^-1 для любого сообщения а, справедливо соотношение

L^-1X[K_i]S^-1(a)=L^-1X[K_i](S^-1(a))=L^-1(S^-1(a)⊕K_i)=L^-1(S^-1(a))⊕L^-1(K_i)=L^-1S^-1(a)⊕L^-1(K_i)=X[L^-1(K_i)]L^-1S^-1(a)

Тогда исходное итерационное криптографическое преобразование

m=X[K₀]S^-1L^-1…S^-1L^-1X[K_n-1]S^-1L^-1X[K_n](c)

заменяется эквивалентным, в котором S^-1 предшествует L^-1:

m=X[KZ₀]S^-1X[KZ₁]L^-1S^-1…X[KZ_n-1]L^-1S^-1X[KZ_n]L^-1S^-1S(c),

где KZ₀=K₀,

а остальные вычисляются по формуле

KZ_j=L^-1(K_j),

где j=1, …, n

Такое представление потребует вычислить новые итерационные ключи, как показано выше.

Таким образом, применение композиции S^-1L^-1 сводится к применению композиции L^-1S^-1, реализация которой требует такого же количества вычислительных ресурсов, что и реализация LS, а значит, эффективно реализуется указанным в работах [2, 3] способом и по сложности эквивалентна преобразованию L.

Рассмотрим композицию Y преобразований L^-1 и S^-1

Y(a)=L^-1(S^-1(a))

Сначала к сообщению а применяется преобразование

S^-1(a)=S^-1(a _t-1||…||a ₀)=π^-1(a _t-1)||…||π^-1(a ₀),

в результате получается новое сообщение (двоичный вектор)

d=S^-1(a)

Затем над вектором d выполняется линейное преобразование, которое эквивалентно умножению вектора d на заданную матрицу G, которая соответствует линейному преобразованию L^-1

L^-1S^-1(a)=d·G

Вектор d разбивается на части

d=d_t-1||…||d₀

и для каждого значения части вычисляется промежуточный вектор

$$u{}_i{}^j=\tau (j)\cdot G_i,$$

где i=0, …, t-1;

j=0, …, 2^b-1

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

$$$$ $$L^{-1}(d)=d\cdot G=(d_{t-1}\Vert \dots \Vert d_0)\cdot \left(\begin{array}{c}{G}_{t-1}\\ G_{t-2}\\ \dots \\ G_0\end{array}\right)=\underset{i=0\dots t-1}{\oplus }{u}_i^{{\tau }^{-1(d_i)}}\text{ (1)}$$

Учитывая, что

d=(d_t-1||…||d₀)=(π^-1(a _t-1)||…||π^-1(a₀)),

из (1) получаем

$$\begin{array}{l}Y(a)=L^{-1}(S^{-1}(a))=L^{-1}(d)=d\cdot G=\\ =(d_{t-1}\Vert \dots \Vert d_0)\cdot \left(\begin{array}{c}{G}_{t-1}\\ G_{t-2}\\ \dots \\ G_0\end{array}\right)=\underset{i=0\dots t-1}{\oplus }{u}_i^{{\tau }^{-1}(d_i)}=\underset{i=0\dots t-1}{\oplus }{u}_i^{{\tau }^{-1}({\pi }^{-1}(a_i))}\text{ (2)}\end{array}$$

Для того чтобы исключить преобразования π^-1, нужно вычислить соответствующие промежуточные значения

$$u{ƒ}_i^j={\pi }^{-1}(\tau (i))\cdot G_i$$

Отметим связь значений

$$u{ƒ}_i^j=u_i^{{\tau }^{-1}({\pi }^{-1}(\tau (j)))}$$

Тогда из (2) получаем

$$Y(a)=\underset{i=0\dots t-1}{\oplus }{u}_i^{{\tau }^{-1}({\pi }^{-1}(a_t))}=\underset{i=0\dots t-1}{\oplus }u{ƒ}_i^{{\tau }^{-1}(a_i)}$$

Описанный способ позволяет объединить два преобразования L^-1 и S^-1 в одно, по сложности равное одному преобразованию L.

Проведем сравнительную оценку известного и предложенного способов.

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

m=X[K₀]S^-1L^-1…X[K_n-1]S^-1L^-1X[K_n](c)

требует выполнения n раз преобразований, по сложности равных преобразованиям L, выполнения n раз преобразований типа S и выполнения n+1 раз преобразований типа X[K_i].

Реализация криптографического преобразования предложенным способом, согласно выражению

m=X[KZ₀]S^-1X[KZ₁]L^-1S^-1…X[KZ_n-1]L^-1S^-1X[KZ_n]L^-1S^-1S(c),

требует выполнения n раз преобразований, по сложности равных преобразованиям L, двух преобразований типа S и выполнения n+1 раз преобразований типа X[KZ_i], также необходимо однократно вычислить новые итерационные ключи

KZ₀=K₀,

KZ_i=L^-1(K_i),

где i=1, …, n,

что потребует выполнения n раз преобразований типа L.

Если для выполнения операции типа L требуется l тактов процессора, а для выполнения операции чипа S необходимо s тактов процессора, то получаем, что предложенный способ становится быстрее известного исходного преобразования, если происходит обработка количества сообщений длины w большего, чем целая часть от величины

$$r=\frac{l\cdot n}{(n-2)\cdot s},\text{ (3)}$$

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

Отметим также, что в предлагаемом способе можно выполнить на одно преобразование типа S меньше, но это приведет к тому, что при вычислении будут использоваться два разных преобразования, по сложности равных преобразованиям L: первое преобразование L^-1S^-1, второе L^-1. Тогда преобразование примет вид

m=X[KZ₀]S^-1X[KZ₁]L^-1S^-1…X[KZ_n-1]L^-1S^-1X[KZ_n]L^-1(c),

и оно потребует выполнения n раз преобразований по сложности равных преобразованиям L, одного преобразования типа S и n+1 раз преобразований типа X[K_i].

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

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

Рассмотрим осуществление предложенного способа на примере блочного шифра, по своей структуре совпадающего с AES. Отличие заключается в том, что при шифровании последнее линейное преобразование L₂ заменяется преобразованием L, то есть дополнительно добавляется преобразование L₁ для сохранения единообразия линейного преобразования.

Тогда алгоритм зашифрования сообщения (двоичного вектора) m длины 128 бит в двоичный вектор c также длины 128 бит будет иметь вид (известно, что при зашифровании по стандарту AES используется в совокупности 15 итерационных ключей при длине исходного секретного ключа 256 бит):

c=X[K₁₄]LS…X[K₁]LSX[K₀](m),

а алгоритм расшифрования:

m=[K₀]S^-1L^-1…X[K₁₃]S^-1L^-1X[K₁₄](c)

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

Сначала выбирают преобразования из допустимых множеств:

V_h - множество всех двоичных строк длины h,

X[K_i]:V₁₂₈→V₁₂₈ задается следующим образом:

X[K_i](a)=K_i⊕a,

где K_i - итерационный ключ исходного криптографического преобразования, причем K_i, a∈V₁₂₈, i=0, …, 14;

L:V₁₂₈→V₁₂₈ - линейное взаимно-однозначное преобразование однозначно определяется заданием невырожденной двоичной матрицы D размера 128×128.

L(a)=a·D,

обратная матрица

G=D^-1;

S:V₁₂₈→V₁₂₈ - нелинейное взаимно-однозначное преобразование, причем

a=a ₁₅||…||a ₀,

где a _i∈V₈;

S(a)=S(a ₁₅||…||a ₀)=π(a ₁₅)||…||π(a ₀),

где π:V₈→V₈ - любое взаимно-однозначное преобразование, оно однозначно определяет преобразование S(а),

τ:Z₂₅₆→V₈ - взаимно-однозначное преобразование, которое ставит в соответствие целому числу из промежутка 0…255 вектор его двоичного представления, младшие биты числа находятся справа.

Затем вычисляют новые итерационные ключи KZ₀, …, KZ₁₄ на основе имеющегося набора итерационных ключей K₀, …, K₁₄, причем нулевой ключ в новом наборе определяют по формуле

KZ₀=K₀,

а остальные по формуле

KZ_j=L^-1(K_j),

где j=1, …, 14.

После этого вычисляют двоичные векторы u[i][j] длины 128 бит, по формуле

u[i][j]=π^-1(τ(j))·G_i,

где G_i - матрица, состоящая из подряд расположенных строк матрицы G, которая соответствует линейному преобразованию L^-1, с номерами (15-i)·8+1, (15-i)·8+2, …, (16-i)·8, где i=0, …, 15; j=0, …, 255.

В завершении вычисляют m:

m₁₄=S(c);

$$q_j=\underset{i=0\dots 15}{\oplus }u\left[i\right]\left[{\tau }^{-1}(m_j\left[i\right])\right]$$ ,

m_j-1=X[KZ_j](q_j),

где

m_j=m_j[15]||m_j[14]||…||m_j[0];

j=14, …, 1,

m=X[KZ₀](S^-1(m₀)).

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

В приводимом примере n=14. Подставив это значение в формулу (3), получаем, что предложенный способ становится быстрее исходного преобразования, если происходит обработка количества сообщений длины 128 бит большего, чем целая часть

$$r=\frac{7\cdot l}{6\cdot s},$$

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

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

Источники информации

1. National Institute of Standards and Technology, U.S. Department of Commerce. "Advanced Encryption Standard", Federal Information Processing Standards Publication 197, Washington, DC, November 2001.

2. П.А. Лебедев. Сравнение старого и нового стандартов РФ на криптографическую хэш-функцию на ЦП и графических процессорах NVIDIA. Математические вопросы криптографии, том 4, вып. 2, 2013, с. 73-80.

3. О. Kazymyrov, V. Kazymyrova, Algebraic Aspects of the Russian Hash Standard COST R 34.11-2012, 2nd Workshop on Current Trends in Cryptology (CTCrypt 2013) June 23-25. 2013. pp. 160-176.

Изобретение относится к криптографии и средствам защиты информации. Технический результат - увеличение скорости обработки информации и снижение количества операций при реализации итерационного криптографического преобразования. Способ криптографического преобразования сообщения с, представленного в двоичном виде, в котором вычисляют на основе имеющегося набора итерационных ключей K₀, …, K_n новый набор итерационных ключей KZ₀, …, KZ_n, причем нулевой ключ в новом наборе определяют по формуле KZ₀=K₀, а остальные по формуле KZ_j=L^-1(K_j); вычисляют двоичные векторы u[i][j] длины w по формуле u[i][j]=π^-1(τ(j))·G_i; вычисляют двоичный вектор m длины w, используя новые итерационные ключи KZ₀, …, KZ_n, выполняя следующие действия: вычисляют m_n=S(с), причем S:V_w→V_w, a=a _t-1||…||a ₀, где a _i∈V_b; S(a)=S(a _t-1||…||a ₀)=π(a _t-1)||…||π(a ₀); вычисляют

m_j-1=X[KZ_j](q_j), где m_j=m_j[t-1]||m_j[t-2]||…||m_j[0]; j=n, …, 1; X[KZ] - линейное преобразование, зависящее от итерационного ключа KZ, причем X[KZ]:V_w→V_w, X[KZ](a)=KZ⊕a, где KZ, а∈V_w; вычисляют m=X[KZ₀](S^-1(m₀)).

Способ криптографического преобразования сообщения с, представленного в двоичном виде, заключающийся в том, что вычисляют на основе имеющегося набора итерационных ключей K₀, …, K_n новый набор итерационных ключей KZ₀, …, KZ_n, причем нулевой ключ в новом наборе определяют по формуле KZ₀=K₀, а остальные по формуле
KZ_j=L^-1(K_j), где j=1, …, n; L - линейное взаимно-однозначное преобразование, причем L:V_w→V_w; L(a)=a·D, где V_n - множество всех двоичных строк длины n,
w - размер сообщения в битах, причем w=b·t,
где t, b∈N (множество натуральных чисел);
D - невырожденная матрица размером w×w;
a - сообщение (двоичный вектор) длины w;
KZ_i, K_i∈V_w,
где i=0, …, n;
вычисляют двоичные векторы u[i][j] длины w по формуле
u[i][j]=π^-1(τ(j))·G_i,
где j=0, …, 2^b-1;
G_i - матрица размером b×w, состоящая из подряд расположенных строк матрицы G с номерами (t-1-i)·b+1, (t-1-i)·b+2, …, (t-i)·b;
i=0, …, t-1;
G=D^-1 - обратная матрица по отношению к D:
$$\tau :Z_{2^b}\to V_b$$ - взаимно-однозначное преобразование, которое ставит в соответствие целому числу из промежутка 0, …, 2^b-1 вектор его двоичного представления, младшие биты числа находятся справа;
π - любое взаимно-однозначное преобразование, причем
π:V_b→V_b;
вычисляют двоичный вектор m длины w, используя новые итерационные ключи KZ₀, …, KZ_n, выполняя следующие действия:
вычисляют
m_n=S(c),
где S - нелинейное взаимно-однозначное преобразование, причем
S:V_w→V_w,
a=a _t-1||…||a ₀,
где a _i∈V_b;
S(a)=S(a _t-1||…||a ₀)=π(a _t-1)||…||π(a ₀);
вычисляют

m_j-1=X[KZ_j](q_j),
где m_j=m_j[t-1]||m_j[t-2]||…||m_j[0];
j=n, …, 1;
X[KZ] - линейное преобразование, зависящее от итерационного ключа KZ, причем
X[KZ]:V_w→V_w,
X[KZ](a)=KZ⊕a,
где KZ, а∈V_w;
вычисляют
m=X[KZ₀](S^-1(m₀)).