Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

DEVELOPMENT OF A NEW PRINCIPLE THE CODING REDUNDANCY CODE MODULAR TO IMPROVE RELIABILITY SPN-CRYPTOSYSTEM

Kalmykov I.A. 1 Toporkova E.V. 1 Kalmykov M.I. 1 Babenko L.K. 2
1 Federal State Autonomous Educational Institution Higher Professional Education «North-Caucasian Federal University»
2 Southern Federal University
The aim of the research is to increase the reliability of the encoders SPN cryptosystem in terms of the impact of failures of natural and anthropogenic character. The achievement of this goal is possible through the implementation of the SPN cryptosystem using polynomial residue number system (PRNS). The use of codes PRNS allows to defer the implementation of cryptographic transformations from the Galois field GF(28) field in the lower-dimensional GF(24). This transition enables application code PRNS with two polynomials, a generating elements of the fields GF(24). It is known that the use of excess of a polynomial in modular code only allows detecting errors. To ensure reliable operation of the SPN- cryptosystem in terms of failures it is necessary to develop new principles of a redundant modular code. These guidelines will allow you to correct the error resulting from failures in SPN-cryptosystem, using one of the control bases. Therefore, the development of error correction code polynomial residue number system, with minimal redundancy, is an urgent task.
cryptographic ciphers
SPN- cryptographic system
polynomial residue number system
detection error
error correction
positional characteristics
1. Babenko L.K., Ishhukova E.A. Sovremennye algoritmy blochnogo shifrovanija i metody ih analiza. M.: Gelios ARV. 2006. 376 p.
2. Gapochkin A.V., Kalmykov M.I., Vasilev P.S. Obnaruzhenie i korrekcija oshibki na osnove vychislenija intervalnogo nomera koda klassov vychetov // Sovremennye naukojomkie tehnologii. 2014. no. 6. pp. 9–14.
3. Kalmykov I.A., Voronkin R.A., Rezenkov D.N., Emarlukova Ja.V., Falko A.A. Gene-ticheskie algoritmy v sistemah cifrovoj obrabotki signalov // Nejrokompjutery: razra-botka, primenenie 2011. no. 5. pp. 20–27.
4. Kalmykov I.A., Zinovev A.V., Rezenkov D.N., Gahov V.R. Primenenie sistoliche-skih ortogonalnyh preobrazovanij v polinomialnoj sisteme klassov vychetov dlja povy-shenija jeffektivnosti cifrovoj obrabotki signalov // Infokommunikacionnye tehnologii. 2010. Tom 8, no. 3, pp. 4–11.
5. Kalmykov I.A., Dagaeva O.I. Razrabotka psevdosluchajnoj funkcii povyshennoj jef-fektivnosti // Izvestija JuFU. Tehnicheskie nauki. 2011. no. 12 (125). pp. 160–169.
6. Kalmykov I.A., Rezenkov D.N. Lokalizacija oshibok v moduljarnyh kodah polinomi-alnoj sistemy klassov vychetov s minimalnoj izbytochnostju // Fundamentalnye issle-dovanija. 2008. no. 3. pp. 75–76.
7. Strizhkov N.S., Kalmykov M.I. Algoritm preobrazovanija iz moduljarnogo koda v poliadicheskuju sistemu osnovanija dlja sistem obnaruzhenija i korrekcii oshibok // Mezhdunarodnyj zhurnal jeksperimentalnogo obrazovanija. 2014. no. 3. pp. 127–131.
8. Chervjakov N.I., Kalmykov I.A., Shhelkunova Ju.O., Shilov A.A., Berezhnoj V.V. Nejrosetevaja realizacija v PSKV operacij COS povyshennoj razrjadnosti // Nejrokompjutery: razrabotka, primenenie. 2004. no. 5–6. pp. 94–100.
9. Kalmykov I.A., Katkov K.A., Olegovich N.D., Sarkisov A.B., Makarova A.V. Parallel Modular Technologies in Digital Signal Processing // Life Science Journal. 2014. T. 11. no. 11s. pp. 435–438.
10. Stefan Mangard, Manfred Aigner, Sandra Dominikus. A Highly Regular and Scalable AES Hardware Architecture. // IEEE Transactions on Computers. 2003. Volume 52, Issue 4. pp. 483–491.

В настоящее время сфера применения криптографических методов защиты информации постоянно увеличивается. Это связано с тем, что системы шифрования играют важную роль в сохранении и передаче конфиденциальных данных. Симметричные алгоритмы по сравнению с асимметричными алгоритмами шифрования обладают целым рядом достоинств, таких как более простая аппаратная и программная реализации, а также высокая скорость зашифрования и расшифрования [1]. Среди симметричных шифров особое место занимают SPN-шифры, в которых используют подстановочно-перестановочную сеть. Однако в процессе работы шифраторы SPN-шифров могут быть подвергнуты атакам типа сбоев. Это приводит к нарушению работы шифратора и снижению степени защиты данных. Поэтому разработка алгоритмов, позволяющих устранить эти последствия, является актуальной задачей.

Цель исследования

В настоящее время для повышения надежности работы SPN-шифр-систем предлагается использовать дублирование, маскирование ошибок методом «2 из 3», а также использовать многократный просчет. Однако данные методы устранения последствий сбоев в работе шифратора характеризуются значительными схемными затратами. Это связано с тем, что они не в полной степени используют математическую основу SPN-шифров, реализованных в полях GF(28). В качестве перспективного направления решения данной проблемы можно отметить использование корректирующих кодов, реализованных в полях Галуа. Поэтому целью работы является повышение надежности SPN-криптосистем за счет применения новых принципов кодирования модулярных кодов полиномиальной системы классов вычетов (ПСКВ).

Материалы и методы исследования

Одним из наиболее известных их представителей является шифр AES. Это итерационный блочный шифр, который реализует схему «квадрат». Блочный шифр AES нашел широкое применение благодаря хорошему сочетанию таких показателей, как криптографическая стойкость, производительность и относительно низкие схемные затраты.

С целью повышения надежности работы его шифратора в [10] предлагается свести шифрование из поля GF(28) к шифрованию в конечных полях меньшего порядка. В этом случае элементы поля Галуа GF(28) представляются в виде элементов полей GF(24). Такой переход позволяет использовать код ПСКВ с двумя информационными основаниями.

В полиномиальной системе классов вычетов двоичный код А = 10…11 представляется в полиномиальной форме A(z) = zm +…+ z + 1, а затем этому полиному в соответствие ставится набор остатков, полученных при делении этого кода на полиномы-основания [8, 9]:

kalm01.wmf, (1)

где kalm02.wmf; kalm03.wmf.

Данный набор оснований кода ПСКВ образует рабочий диапазон

kalm04.wmf.

Так как сравнения по одному и тому же модулю можно почленно складывать, вычитать и умножать, то для двух полиномов A(z) и B(z), имеющих соответственно коды kalm05.wmf и kalm06.wmf, справедливо соотношение:

kalm07.wmf. (2)

Параллельность обработки данных по основаниям ПСКВ позволяет обеспечить высокую скорость выполнения модульных операций. Благодаря этому свойству коды ПСКВ нашли широкое применение в системах реального масштаба времени [3–5]. При этом параллельная и независимая обработка остатков служат идеальной основой для построения процедур обнаружения и коррекции ошибок, возникающих из-за сбоев в работе системы [2, 6, 7].

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

kalm08.wmf. (3)

Для этого вводят избыточные основания kalm09.wmf, выбираемые из условия

kalm10.wmf, (4)

где deg pi(z) – степень неприводимого полинома pi(z); k – количество рабочих оснований.

Чтобы провести такую процедуру в модулярных кодах, применяют различные позиционные характеристики. Если основания ПСКВ являются основаниями обобщенной полиадической системы (ОПС), то имеем, что

kalm11.wmf.

Тогда, используя коэффициенты ОПС, можно представить

kalm12.wmf (5)

Из равенства (5) видно, что если код ПСКВ принадлежит рабочему диапазону, то старшие коэффициенты ОПС, соответствующие контрольным основаниям, должны равняться нулю kalm13.wmf. В работе [7] представлен алгоритм вычисления данной ПХ.

В работе [2] предлагается обнаруживать и корректировать ошибки на основе ПХ-интервала. В этом случае данная позиционная характеристика определяется

kalm14.wmf, (6)

где kalm15.wmf; kalm16a.wmf kalm16b.wmf; kalm17.wmf.

В работе [6] представлен алгоритм вычисления ПХ – невязки контрольных остатков. Для получения данной ПХ вычисляют разность между значениями остатков α k + 1(z), αk + 2(z) по контрольным основаниям кода ПСКВ kalm18.wmf и результатам вычисления остатков kalm19.wmf с использованием рабочих оснований:

kalm20.wmf, (7)

где kalm21.wmf; Ra(z) – ранг A(z) в безызбыточной ПСКВ; kalm22.wmf; j = k + 1, k + 2.

Анализ рассмотренных алгоритмов показал, что классические принципы построения корректирующих модулярных кодов невозможно использовать для повышения надежности SPN-криптосистем. Это связано с тем, что для коррекции однократной ошибки в кодах ПСКВ используют два контрольных модуля. А в SPN-криптосистеме контрольным модулем может быть только полином kalm23.wmf. Значит, для проведения коррекции ошибок необходимо разработать новые принципы построения избыточных кодов ПСКВ.

Очевидно, что для коррекции однократной ошибки в модулярном коде необходимо наличие как минимум двух контрольных остатков  αk + 1(z) и αk + 2(z). Первый остаток αk + 1(z) должен указывать глубину ошибки, т.е. kalm24.wmf. Если ошибка произошла по i-му основанию кода ПСКВ, то получаем

kalm25.wmf, (8)

где kalm26.wmf – глубина ошибки по i-му основанию кода ПСКВ.

Тогда получаем, что

kalm27.wmf.

Чтобы определить глубину ошибки, необходимо сложить эти остатки. Получаем

kalm28.wmf. (9)

Второй остаток αk + 2(z) должен указать номер отказавшего основания. Тогда

kalm29.wmf, (10)

где i(z) – полиномиальная форма двоичного представления числа i.

Если ошибка произошла по i-му основанию кода ПСКВ, то остаток αk + 2(z) равен

kalm30.wmf. (11)

Чтобы определить номер отказавшего основания необходимо сложить эти остатки.

kalm31.wmf. (12)

Очевидно, что если разделить значение δk + 2(z) на δk + 1(z), то результат дает i(z) – полиномиальную форму двоичного представления отказавшего канала. Таким образом, разработанный новый принцип построения избыточного кода ПСКВ с одним контрольным модулем позволяет корректировать ошибки, возникающие в процессе работы SPN-криптосистем.

Результаты исследования и их обсуждение

Шифр AES реализуется в GF(28) с использованием kalm32.wmf. Предлагается вместо него использовать код ПСКВ с двумя основаниями kalm33.wmf и kalm34.wmf. В качестве контрольного основания – kalm35.wmf. Рассмотрим применение разработанного принципа при проведении операции MixColums. В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю двучлена z4 + 1 на многочлен

kalm36.wmf.

При этом умножение байтов массива State на {02} и на {03} выполняются по модулю p(z). Пусть на вход преобразователя MixColums поступил 32-битовый столбец kalm37a.wmf kalm37d.wmf kalm37c.wmfkalm37b.wmf. В избыточном коде ПСКВ эти байты, представленные в 16-ричной системе счисления, имеют вид {CA16} = (D, 2, F, 9), {D116}=(5,0,5,5), {E216} = (3, 1, 2,1), {4F16} = (3, 0, 3, 3). Рассмотрим получение нового значения байта:

kalm38.wmf.

При умножении первого байта СА на значение константы {02} получается байт kalm39.wmf. Представим данное произведение в коде ПСКВ с двумя информационными основаниями kalm40.wmf и kalm41.wmf. Получаем kalm42.wmf. Вычислим значения двух контрольных остатков:

kalm43.wmf,

kalm44.wmf

Тогда произведение можно записать в виде кода ПСКВ в следующем виде:

kalm45a.wmf

kalm45b.wmf.

Рассмотрим, как будет получен аналогичный результат с использованием соответствующих таблиц. Информационные остатки первого байта CA = (D, 2) поступают на входы табл. 1 и табл. 2. Представленная часть табл. 1 содержит остатки результата умножения kalm46.wmf, приведенной по модулям kalm47.wmf. На пересечении второй строки и столбца D располагается kalm48.wmf.

Табл. 2 содержит результат умножения kalm50.wmf по модулю kalm51.wmf. На пересечении второй строки и столбца D располагается остаток kalm52.wmf.

Кроме того, информационные остатки первого байта CA = (D, 2) поступают на входы табл. 3 и табл. 4. Табл. 3 содержит данные о сумме остатков информационных оснований ПСКВ. На пересечении 2-й строки и столбца D находится kalm54.wmf.

В табл. 4 представлены данные о втором контрольном остатке. На пересечении второй строки и столбца D таблицы находится остаток kalm55.wmf.

Таким образом, после выполнения операции умножения первого байта имеем

kalm56.wmf.

Рассмотрим умножение второго байта состояния {D116} = (5, 0, 5, 5) на коэффициент на {03}. Получаем kalm58.wmf. Тогда

kalm59.wmf; kalm60.wmf.

kalm61.wmf; kalm62.wmf.

Тогда результат умножения на константу {03} имеет вид

kalm63.wmf.

При перемешивании столбцов MixColums получили новое состояние

kalm64.wmf.

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

kalm65.wmf; kalm66.wmf.

Тогда синдром ошибки kalm67.wmf; kalm68.wmf.

Пусть из-за сбоя произошло искажение первого слагаемого на величину kalm69.wmf. Тогда с выхода табл. 1 снимается kalm70.wmf, то есть комбинация

kalm71.wmf.

В результате получили новое состояние:

kalm72.wmf.

Тогда остатки равны

kalm73.wmf; kalm74.wmf.

Синдром ошибки kalm75.wmf; kalm76.wmf. По значению синдрома ошибки kalm77.wmf и kalm78.wmf из памяти берется вектор ошибки, который равен kalm79.wmf, с помощью которого ошибка исправляется:

kalm80.wmf.

Таблица 1

Остатки результата умножения kalm49.wmf

 

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

0

F

9

6

8

7

1

E

E

1

7

8

6

9

F

0

1

D

2

4

B

5

A

C

3

3

C

A

5

B

4

2

D

2

D

2

4

B

5

A

C

3

3

C

A

5

B

4

2

D

3

           

             

F

D

2

4

B

5

A

C

3

3

C

A

5

B

4

2

D

Таблица 2

Остатки результата умножения kalm53.wmf

 

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

0

C

C

0

0

C

C

0

C

0

0

C

C

0

0

C

1

E

2

2

E

E

2

2

E

2

E

E

2

2

E

E

2

2

8

4

4

8

8

4

4

8

4

8

8

4

4

8

8

4

3

           

             

F

B

7

7

B

B

7

7

5

7

B

B

7

7

B

B

7

Таблица 3

Первый контрольный остаток α3(z)

 

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

0

3

5

6

8

B

D

E

2

1

7

4

A

9

F

C

1

3

0

6

5

B

8

E

D

1

2

4

7

9

A

C

F

2

5

6

0

3

D

E

8

B

7

4

2

1

F

C

A

9

3

           

             

F

6

5

3

0

E

D

B

6

4

7

1

2

C

F

9

A

Таблица 4

Второй контрольный остаток α4(z)

 

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

0

8

E

6

8

0

6

E

9

1

7

F

1

9

F

7

1

E

6

0

8

6

E

8

0

7

F

9

1

F

7

1

9

2

2

A

C

4

A

2

4

C

B

3

5

D

3

B

D

5

3

           

             

F

4

C

A

2

C

4

2

9

D

5

3

B

5

D

B

3

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

Заключение

Проведенный анализ известных алгоритмов обнаружения и исправления ошибок в модулярных кодах показал, что они не могут быть применены для повышения надежности работы SPN-криптосистем, так используют два контрольных основания. Исходя из особенностей реализации SPN-криптосистем в полях GF(24), в работе осуществлена разработка и исследование новых принципов построения избыточных кодов полиномиальной системы классов вычетов, позволяющих корректировать ошибки на основе использования одного контрольного основания. Показана возможность применения данных принципов при разработке новых модулярных кодов ПСКВ, способных корректировать ошибки, возникающие в процессе работы криптосистемы AES. Проведенные исследования показали, что применение разработанного алгоритма позволяет вычислять местоположение и глубину ошибки при меньших схемных затратах по сравнению с методом маскирования ошибок «2 из 3».

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-37-50081.