Криптографічний захист інформації як процедура кодування
Problems of cryptographic encryption of binary information are considered in terms of the algebraic theory of error-corrected codes. The unity of encryption/encoding procedures is shown, based on which a broad class of new algorithms of cryptoprotection can be obtained.
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/154700 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1866302308877336576 |
|---|---|
| author | Savchenko, Yu. G. Chych, T. V. |
| author_facet | Savchenko, Yu. G. Chych, T. V. |
| author_sort | Savchenko, Yu. G. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-18T15:10:29Z |
| description | Problems of cryptographic encryption of binary information are considered in terms of the algebraic theory of error-corrected codes. The unity of encryption/encoding procedures is shown, based on which a broad class of new algorithms of cryptoprotection can be obtained. |
| first_indexed | 2025-07-17T10:24:27Z |
| format | Article |
| fulltext |
© Ю.Г. Савченко, Т.В. Чич, 2006
Системні дослідження та інформаційні технології, 2006, № 4 133
УДК 681.36
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ КАК
ПРОЦЕДУРА КОДИРОВАНИЯ
Ю.Г. САВЧЕНКО, Т.В. ЧИЧ
Рассмотрены задачи криптографического шифрования двоичной информации
в терминах алгебраической теории кодов с коррекцией ошибок. Показано
единство процедур шифрования и кодирования, на основе чего может быть
получен обширный класс новых алгоритмов криптозащиты.
В настоящее время независимо друг от друга существуют и развиваются две
специфические ветви преобразования двоичной информации: помехозащи-
щенное кодирование и криптографическое шифрование. Эти ветви базиру-
ются на различных подходах: кодирование использует, главным образом,
чисто алгебраический подход; шифрование (в зависимости от класса проце-
дур — разные методы — от комбинаторных до таких, как эллиптические
функции, арифметику в остаточных классах, вычисления в поле Галуа и
др.). В то же время термины «шифрование» и «кодирование» по своей сути
являются почти синонимами, что непосредственно следует из классической
работы К. Шеннона [1], где рассмотрены основные известные к тому време-
ни шифры, в том числе близкие к предлагаемому ниже подходу матричные
системы Л. Хилла. Как при кодировании, так и при шифровании речь идет о
процедуре (алгоритме, правиле, формуле) преобразования одной двоичной
комбинации X в другую Y , т.е.
)(XY F= . (1)
Для описания такой процедуры в стандарте AES (Rijdael) [2], который
призван заменить широко распространенный стандарт DES, используется
матричный подход. Двоичные последовательности представляются в виде
полиномов в поле Галуа (точно так, как и при построении циклических по-
мехозащищенных кодов), а отдельные шаги (раунды) шифрования — мат-
ричными операциями. Вхождениями матриц выступают отдельные байты
информационной последовательности или ключа, что позволяет существен-
но облегчить программную реализацию соответствующих процедур.
Предлагаемый подход базируется также на матричном описании, но на
битовом уровне, т.е. в виде двоичных матриц аналогично процедурам коди-
рования и декодирования групповых кодов, что позволяет сблизить, а в не-
которых случаях и совместить помехозащищенное кодирование и крипто-
графическое шифрование.
В общем случае (по крайней мере, при двоичном представлении X и
Y ) зависимость (1) должна, очевидно, задаваться соответствующими авто-
матными уравнениями. Однако, учитывая реально используемые в настоя-
щее время процедуры кодирования и шифрования, можно ограничиться
лишь булевыми уравнениями вида
Ю.Г. Савченко, Т.В. Чич
ISSN 1681–6048 System Research & Information Technologies, 2006 № 4 134
knnixxxfy kii ≥== ;,...,1),,...,,( 21 , (2)
где ix и jy — компоненты, соответственно, двоичного вектора X и Y .
При помехозащищенном кодировании чаще всего все if — линейные
булевы функции относительно операции сложения по модулю 2, т.е. каждый
символ iy — это некоторая сумма по модулю 2 избранной совокупности
входных символов. Для групповых кодов, включая циклические, процедура
кодирования математически может быть задана умножением слева исход-
ной комбинации X в виде вектор-строки ),...,,( 21 kxxx=X на так называе-
мую порождающую матрицу вида
knkk −= ,AIQ ,
где kI — единичная матрица ранга k ; knk −,A — матрица размерности
)( knk −× , которая задает )( kn − уравнений кодирования
),...,,( 21 kjk xxxy ϕ=+ .
Важно отметить принципиальную для нашего рассмотрения особен-
ность: при таком выборе матрицы Q значения первых k разрядов в слове
Y совпадают со значениями соответствующих разрядов в слове X . И это
понятно, поскольку решается задача защиты от помех, а поэтому процедура
восстановления исходного сообщения X должна быть максимально про-
стой и быстрой.
Совсем иное дело шифрование. В этом случае основная цель — макси-
мально скрыть не только исходное сообщение X , но и замаскировать стати-
стику появления отдельных символов в совокупности сообщений, посту-
пающих (перехваченных) от конкретного источника. Поэтому, если для
шифрования использовать такую же процедуру, как и для кодирования, то
требования к порождающей матрице должны быть коренным образом изме-
нены. В частности, в большинстве случаев kn = , т.е. Q — квадратная мат-
рица ранга k . Кроме того, поскольку именно эта матрица определяет кон-
кретный способ преобразования X в Y , то в случае шифрования она
должна однозначно определяться на основе ключа шифрования =K
( )kkkk ,...,, 21= и соответствующего фрагмента открытого текста. Отметим,
что длина ключа не обязательно должна совпадать с длиной исходного тек-
ста. На основе этих простых соображений можно утверждать, что матрица
Q содержит в качестве вхождений либо компоненты ключа K , либо неко-
торые функции ijψ , зависящие от ключа и от значений разрядов исходного
текста X , т. е.
),( XKijijq ψ= .
Вопрос выбора функций, с помощью которых определяются вхождения
матрицы Q , с одной стороны, достаточно сложный процесс, поскольку
кроме всего прочего необходимо обеспечить возможность однозначного
вычисления каждого ijq получателем сообщения, т.е. должно существовать
преобразование
Криптографическая защита информации как процедура кодирования
Системні дослідження та інформаційні технології, 2006, № 4 135
),(),( YKXK ijij ψψ ′⇒ .
Однако можно предполагать, что матрица Q получена любым доступ-
ным способом, включая случайный выбор, при выполнении некоторых про-
стых ограничений, и заранее известна как отправителю, так и получателю.
В наиболее простом случае Q должна однозначно определяться только
на основе известного ключа K , например, некоторой перестановкой его
компонент либо функциями от их двоичных значений.
Рассмотрим элементарные квадратные матрицы с двоичными элемен-
тами и их очевидные свойства.
1. Нулевая квадратная матрица Y ранга m . Очевидно, что умножение
на такую матрицу дает в результате нулевой вектор-столбец.
2. Единичная диагональная матрица I . Умножение X слева на I не
изменяет X , т.е. XIX =× .
3. Единичная правая диагональная матрица J . Умножение X слева на
J изменяет порядок (нумерацию) разрядов в X на обратный.
4. Умножение на матрицу
01...0000
10...0000
.....................
00...0100
00...1000
00...0001
00...0010
=A
меняет местами четные и нечетные разряды в X .
5. Матрица
00001000
........................
00000010
00000001
10000...00
........................
00100...00
00010...00
=B
соответствует «зеркальной» перестановке позиций слова X : левая половина
становится правой и наоборот.
Перечень примеров аналогичных элементарных матриц можно про-
должать достаточно долго. Легко показать, что любая двоичная матрица,
содержащая точно по одной единице в каждом столбце, при умножении на
нее осуществляет некоторую перестановку разрядов X , а произведение
произвольного подмножества таких матриц даст в результате также элемен-
Ю.Г. Савченко, Т.В. Чич
ISSN 1681–6048 System Research & Information Technologies, 2006 № 4 136
тарную матрицу, содержащую в каждом столбце не более одной единицы.
Поэтому такие матрицы для шифрования представляют ограниченный инте-
рес и могут быть использованы, в основном, для маскирования статистики
(«забеливания» и так называемого гаммирования).
Матрицы же, столбцы которых содержат больше одной единицы, пред-
ставляют большой интерес для построения процедур шифрования. Рассмот-
рим некоторые общие свойства таких матриц, которые могут быть полез-
ными для шифрования.
Возникает естественный вопрос: любая ли двоичная матрица ранга k
пригодна для построения процедуры шифрования? Чтобы ответить на него,
целесообразно рассмотреть процедуру дешифрования принятого сообщения
в предположении, что получателю известна матрица Q .
Каждому столбцу такой матрицы можно поставить в соответствие
уравнение вида (2). В случае использования алгоритма, аналогичного про-
цедуре кодирования для групповых кодов, эти уравнения имеют вид
,,1,, kiUxy ii =∈⊕= ∑ α
α
α (3)
где iU — совокупность номеров позиций i -го столбца матрицы, значения
которых равны 1.
Очевидно, система уравнений (3) разрешима относительно kx ,1, =αα
тогда и только тогда, когда эти уравнения линейно независимы относитель-
но операции поразрядного сложения по модулю 2. Отсюда непосредственно
следует, что и строки матрицы Q должны быть линейно независимыми.
Иными словами, все строки матрицы Q должны быть различными, и ни од-
на из них не может быть представлена в виде суммы любой совокупности
остальных строк. Очевидно также, что выполнить это требование не очень
сложно, используя известные из теории кодирования приемы. По крайней
мере, можно обоснованно предполагать, что комбинаторного разнообразия
матриц достаточно, чтобы обеспечить криптографическую стойкость полу-
ченных таким способом шифров. В пользу такого предположения можно
привести матричное представление одного из широко применяемых алго-
ритмов, например, DES [3]. В этом случае шифрующую матрицу предста-
вим следующим образом:
YYYWYYYY
YYYYYYYW
YYWYYYYY
YYYYYYWY
YWYYYYYY
YYYYYWYY
WYYYYYYY
YYYYWYYY
Q = , (4)
где Y — нулевые матрицы ранга 8, а
Криптографическая защита информации как процедура кодирования
Системні дослідження та інформаційні технології, 2006, № 4 137
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
ij
ij
ij
ij
ij
ij
ij
ij
ψ
ψ
ψ
ψ
ψ
ψ
ψ
ψ
=W , (5)
где, в свою очередь, вхождения ijψ определяются как значения булевых
функций (0 или 1), которые зависят от соответствующих битов ключа K и
входного слова X . В частности,
),,(),( 1+⊕= iiiij fL KRXKψ
где ;XRL =∪ ii iiiif KRKR ⊕′=+ ),( 1 . Здесь знак ∪ соответствует прос-
тому соединению (объединению) двух 32-разрядных комбинаций (левой и
правой половин) в одну 64-разрядную, а R′ — расширение 32-розрядного
вектора iR до 48 разрядов путем добавления нулей. В окончательном (ра-
бочем) виде запись (5) — это двоичная матрица, разная для различных ши-
фруемых блоков. Однако ее структура остается неизменной и всегда соот-
ветствует виду (4), (5).
В заключение приведенного краткого изложения рискнем утверждать,
что преобразование двоичных последовательностей с помощью матричных
операций образует широкий класс легко реализуемых процедур шифрова-
ния. Соответствующие аппаратные и программные решения давно исполь-
зуются при помехозащищенном кодировании и могут быть применены и для
криптографической защиты в телекоммуникационных системах. Важно
также, что в этом случае легко совместить шифрование с помехозащищен-
ным кодированием не только для циклических [4,5], но и в целом для груп-
повых кодов.
ЛИТЕРАТУРА
1. Шеннон К. Теория связи в секретных системах // В сб.: Работы по теории ин-
формации и кибернетике. — М.: Изд. иностр. лит., 1963. — С. 333–413.
2. Зендин О.С., Иванов М.А. Стандарт криптографической защиты AES. — Кн. 1.
— М.: Кудиц-Образ, 2002.— 274 c.
3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные
тексты на языке С. — М.: Триумф, 2002. — 816 с.
4. Горовой И.М., Савченко Ю.Г. Коды с коррекцией ошибок как средство крипто-
защиты // УСиМ. — 2002. — №5. — С. 74–79.
5. Савченко Ю.Г., Горовой И.М. Централизованное управление связью как сред-
ство криптозащиты // Связь. — 2004. — № 7. — С. 32–34.
Поступила 16.03.2006
|
| id | journaliasakpiua-article-154700 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:27Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/b0/5d185f71f0a0a312e034c8080230aab0.pdf |
| spelling | journaliasakpiua-article-1547002019-01-18T15:10:29Z Cryptographic protection of information as an encoding procedure Криптографическая защита информации как процедура кодирования Криптографічний захист інформації як процедура кодування Savchenko, Yu. G. Chych, T. V. Problems of cryptographic encryption of binary information are considered in terms of the algebraic theory of error-corrected codes. The unity of encryption/encoding procedures is shown, based on which a broad class of new algorithms of cryptoprotection can be obtained. Рассмотрены задачи криптографического шифрования двоичной информации в терминах алгебраической теории кодов с коррекцией ошибок. Показано единство процедур шифрования и кодирования, на основе чего может быть получен обширный класс новых алгоритмов криптозащиты. Розглянуто задачі криптографічного шифрування двійкової інформації в термінах алгебраїчної теорії кодів з корекцією помилок. Показана єдність процедур шифрування та кодування, на основі чого можна отримати широкий клас нових алгоритмів криптозахисту. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-01-18 Article Article Peer-reviewed Article application/pdf https://journal.iasa.kpi.ua/article/view/154700 System research and information technologies; No. 4 (2006); 133-137 Системные исследования и информационные технологии; № 4 (2006); 133-137 Системні дослідження та інформаційні технології; № 4 (2006); 133-137 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/154700/154309 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Savchenko, Yu. G. Chych, T. V. Криптографічний захист інформації як процедура кодування |
| title | Криптографічний захист інформації як процедура кодування |
| title_alt | Cryptographic protection of information as an encoding procedure Криптографическая защита информации как процедура кодирования |
| title_full | Криптографічний захист інформації як процедура кодування |
| title_fullStr | Криптографічний захист інформації як процедура кодування |
| title_full_unstemmed | Криптографічний захист інформації як процедура кодування |
| title_short | Криптографічний захист інформації як процедура кодування |
| title_sort | криптографічний захист інформації як процедура кодування |
| url | https://journal.iasa.kpi.ua/article/view/154700 |
| work_keys_str_mv | AT savchenkoyug cryptographicprotectionofinformationasanencodingprocedure AT chychtv cryptographicprotectionofinformationasanencodingprocedure AT savchenkoyug kriptografičeskaâzaŝitainformaciikakprocedurakodirovaniâ AT chychtv kriptografičeskaâzaŝitainformaciikakprocedurakodirovaniâ AT savchenkoyug kriptografíčnijzahistínformacííâkprocedurakoduvannâ AT chychtv kriptografíčnijzahistínformacííâkprocedurakoduvannâ |