Анализ перемешивающих свойств операций, заданных на одном носителе

Анализ перемешивающих свойств операций, заданных на одном носителе

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

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Штучний інтелект
Дата:2011
Автори: Ковальчук, Л.В., Сиренко, О.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2011
Теми:
Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/60235
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Анализ перемешивающих свойств операций, заданных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Штучний інтелект. — 2011. — № 3. — С. 490-496. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-60235
record_format dspace
spelling Ковальчук, Л.В.
Сиренко, О.А.
2014-04-12T15:05:49Z
2014-04-12T15:05:49Z
2011
Анализ перемешивающих свойств операций, заданных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Штучний інтелект. — 2011. — № 3. — С. 490-496. — Бібліогр.: 6 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/60235
621.391:519.2:519.7
В статье анализируется возможность применения атак гомоморфизма (групповых атак) к блочным шифрам в случае, когда в раундовых функциях используется чередование различных операций, таких как операции модульного и побитового сложения, модульного умножения. Получены результаты, характеризующие перемешивающие свойства операций побитового и модульного сложения на множестве двоичных векторов, а также результаты, характеризующие перемешивающие свойства операций сложения и умножения в кольце Z₂n.
У статті аналізується можливість застосування атак гомоморфізмів (групових атак) до блочних шифрів у випадку, коли в раундових функціях використовується чергування різних операцій, таких як операції модульного та побітового додавання, а також модульного множення. Отримані результати, які характеризують перемішувальні властивості операцій побітового та модульного додавання на множині двійкових векторів, а також результати, що характеризують перемішувальні властивості операцій додавання та множення в кільці Z₂n.
The paper is devoted to the analysis of the possibility of homomorphism attacks (group attack) to the block cipher in the case when the round functions use the interchange of various operations such as bitwise and modular addition, modular multiplication. Some results characterizing the mixing properties of bitwise and modular addition on the set of binary vectors and the results that characterize the mixing properties of addition and multiplication in the ring Z₂n are obtained.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Штучний інтелект
Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
Анализ перемешивающих свойств операций, заданных на одном носителе
Аналіз перемішувальних властивостей операцій, визначених на одному носії
Analysis of Mixing Features of the Operations, Defined on One Carrier
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Анализ перемешивающих свойств операций, заданных на одном носителе
spellingShingle Анализ перемешивающих свойств операций, заданных на одном носителе
Ковальчук, Л.В.
Сиренко, О.А.
Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
title_short Анализ перемешивающих свойств операций, заданных на одном носителе
title_full Анализ перемешивающих свойств операций, заданных на одном носителе
title_fullStr Анализ перемешивающих свойств операций, заданных на одном носителе
title_full_unstemmed Анализ перемешивающих свойств операций, заданных на одном носителе
title_sort анализ перемешивающих свойств операций, заданных на одном носителе
author Ковальчук, Л.В.
Сиренко, О.А.
author_facet Ковальчук, Л.В.
Сиренко, О.А.
topic Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
topic_facet Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
publishDate 2011
language Russian
container_title Штучний інтелект
publisher Інститут проблем штучного інтелекту МОН України та НАН України
format Article
title_alt Аналіз перемішувальних властивостей операцій, визначених на одному носії
Analysis of Mixing Features of the Operations, Defined on One Carrier
description В статье анализируется возможность применения атак гомоморфизма (групповых атак) к блочным шифрам в случае, когда в раундовых функциях используется чередование различных операций, таких как операции модульного и побитового сложения, модульного умножения. Получены результаты, характеризующие перемешивающие свойства операций побитового и модульного сложения на множестве двоичных векторов, а также результаты, характеризующие перемешивающие свойства операций сложения и умножения в кольце Z₂n. У статті аналізується можливість застосування атак гомоморфізмів (групових атак) до блочних шифрів у випадку, коли в раундових функціях використовується чергування різних операцій, таких як операції модульного та побітового додавання, а також модульного множення. Отримані результати, які характеризують перемішувальні властивості операцій побітового та модульного додавання на множині двійкових векторів, а також результати, що характеризують перемішувальні властивості операцій додавання та множення в кільці Z₂n. The paper is devoted to the analysis of the possibility of homomorphism attacks (group attack) to the block cipher in the case when the round functions use the interchange of various operations such as bitwise and modular addition, modular multiplication. Some results characterizing the mixing properties of bitwise and modular addition on the set of binary vectors and the results that characterize the mixing properties of addition and multiplication in the ring Z₂n are obtained.
issn 1561-5359
url https://nasplib.isofts.kiev.ua/handle/123456789/60235
citation_txt Анализ перемешивающих свойств операций, заданных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Штучний інтелект. — 2011. — № 3. — С. 490-496. — Бібліогр.: 6 назв. — рос.
work_keys_str_mv AT kovalʹčuklv analizperemešivaûŝihsvoistvoperaciizadannyhnaodnomnositele
AT sirenkooa analizperemešivaûŝihsvoistvoperaciizadannyhnaodnomnositele
AT kovalʹčuklv analízperemíšuvalʹnihvlastivosteioperacíiviznačenihnaodnomunosíí
AT sirenkooa analízperemíšuvalʹnihvlastivosteioperacíiviznačenihnaodnomunosíí
AT kovalʹčuklv analysisofmixingfeaturesoftheoperationsdefinedononecarrier
AT sirenkooa analysisofmixingfeaturesoftheoperationsdefinedononecarrier
first_indexed 2025-11-24T17:54:12Z
last_indexed 2025-11-24T17:54:12Z
_version_ 1850490411661918208
fulltext «Искусственный интеллект» 3’2011 490 8К УДК 621.391:519.2:519.7 Л.В. Ковальчук1, О.А. Сиренко2 1 Институт специальной связи и защиты информации Национального технического университета Украины «Киевский политехнический институт», г. Киев, Украина 2 Киевский национальный университет имени Тараса Шевченко, г. Киев, Украина lv_kov_crypto@mail.ru, Olga_Sirenko@ukr.net Анализ перемешивающих свойств операций, заданных на одном носителе В статье анализируется возможность применения атак гомоморфизма (групповых атак) к блочным шифрам в случае, когда в раундовых функциях используется чередование различных операций, таких как операции модульного и побитового сложения, модульного умножения. Получены результаты, характеризующие перемешивающие свойства операций побитового и модульного сложения на множестве двоичных векторов, а также результаты, характеризующие перемешивающие свойства операций сложения и умножения в кольце n2  . Введение Основой обеспечения криптографической защиты информации с ограниченным доступом являются симметрические криптосистемы, среди которых наиболее широкое применение находят блочные шифры (БШ). Важнейшее требование к современным БШ – это практическая криптографическая стойкость относительно всех известных в настоящее время криптоаналитических атак. Традиционный подход построения БШ основан на общепринятых принципах – рас- сеивании и перемешивании, сформулированных в основополагающей работе К. Шеннона [1]. Под рассеиванием подразумевается влияние одного знака открытого текста на многие знаки шифрованного текста, что позволяет «сгладить» статистические свойства откры- тых сообщений. Принципом перемешивания К. Шеннон назвал разрушение статисти- ческих зависимостей между открытым и шифрованным текстом при криптографическом преобразовании. Поэтому наиболее распространенным методом построения БШ на сегод- няшний день является метод, основанный на применении так называемых итерацион- ных схем, в которых шифрующие преобразования реализуются в виде суперпозиции до- статочно простых преобразований (с точки зрения программной реализации и вычисли- тельной сложности), каждое из которых вносит небольшой вклад в существенное суммарное рассеивание и перемешивание. Последовательность таких преобразований (примитивов), которая многократно повторяется в БШ, обычно называется раундом (циклом). Тогда необходимая криптографическая стойкость такого шифра достигается за счет применения большого числа простых преобразований, которые в совокупности обеспечивают «хорошие» перемешивающие и рассеивающие свойства. Одним из общих требований к современным БШ является их обоснованная стойкость к аналитическим атакам, которые условно можно разделить на два боль- ших класса – алгебраические и статистические методы криптоанализа. Алгебраические методы криптоанализа основаны на группировании открытых, шифрованных со- общений или ключей БШ в классы эквивалентных (или близких, в том или ином смысле) объектов, позволяющем понизить трудоемкость алгоритмов решения (размер- ность) соответствующих криптоаналитических задач. Стойкость БШ к подобным методам Анализ перемешивающих свойств операций, заданных на одном носителе «Штучний інтелект» 3’2011 491 8К криптоанализа, получившим в ряде публикаций название методов гомоморфизмов или группового криптоанализа [2], [3], как правило, определяется алгебраическими свойст- вами различных групп подстановок, связанных с системой раундовых шифрующих пре- образований данного БШ. В работе [4] рассматривалось действие операции сложения (умножения) в конеч- ном поле на смежные классы относительно умножения (сложения). Было показано, что действие операции сложения (умножения) на элементы классов смежности относитель- но операции умножения (сложения) существенно разрушают структуру соответствующей факторгруппы. Исходя из полученных результатов, в указанной работе был сделан вы- вод о том, что использование композиции этих операций при построении алгоритма шифрования делает его стойким к криптоанализу на основе гомоморфизмов и позволяет проектировать итеративные шифры с использованием только операций в конечном поле, без необходимости реализовывать дополнительные примитивы [4-6]. В современных алгоритмах шифрования в раундовых функциях БШ гораздо чаще используются композиции таких операций, как операции модульного и побитового сложения, операция модульного умножения. Поэтому не менее актуальной и интерес- ной задачей на сегодняшний день является задача исследования перемешивающих свойств этих групповых операций, носителем которых является множество двоичных векторов. Целью данной работы является анализ возможности применения групповых атак (атак гомоморфизма) в случае, когда в раундовых функциях блочного шифра используется чередование различных операций, заданных на множестве двоичных векторов. Вспомогательные обозначения Введем следующие обозначения. Здесь и далее под  ,nV будем понимать мно- жество векторов длины n с операцией побитового сложения, а под   , 2 n и   ,* 2 n – аддитивную и мультипликативную группы кольца вычетов n2  . Каждому целому числу nZz 2  поставим в соответствие битовый вектор длины n , который является двоичным представлением этого числа. Таким образом, отождествим множества nZ 2 и nV . Целое число и соответствующий ему двоичный вектор будем обозначать одинаково, а из контекста будет понятно, какое именно представление используется. Обозначение вида 1 1 1бит бит бит бит бит ... 0 ... 0 ... ... 0 ... 0 ...    k k kb a b a b (1) будем использовать для битового вектора длины 1 1 1 k k i i i i n a b       , у которого слева 1kb  произвольных бит, далее ka нулевых бит и т.д. Влияние операции модульного сложения на структуру факторгруппы  ,nV  по ее подгруппе Определение 1. Обозначим через  1 2 1 2 1, ,..., ; , ,..., ,k k kG a a a b b b b  подгруппу индекса 2a группы  ,nV  , элементы которой содержат k «нулевых» блоков kAA ,...,1 , то есть имеют следующую структуру: Ковальчук Л.В., Сиренко О.А. «Искусственный интеллект» 3’2011 492 8К  битбитбитбитбитбитбит 11221 ...0...0...0...0......0...0... bababab kkk  1122kk1k BABABAB блок блок блок блок блок блок блок , где биты из «ненулевых» блоков 1 1,..., kB B  принимают произвольные значения, причем 1 k i i a a   , 1 k i i b b   и 1 ,ka b b n   0, 0i ia b  при 2,..., ;i k 01 b , 01 a , 01 kb . Лемма 1. В указанных обозначениях: а) все подгруппы в  ,nV  имеют структуру 1 2 2 1 1бит бит бит бит бит бит бит ... 0 ... 0 ... ... 0 ... 0 ... 0 ... 0 ... ,    k k kb a b a b a b где 1 1 1 , 0, 0 k k i i i i i i a b n a b         при 2,..., ;i k 01 b , 01 a , 01 kb ; б) все подгруппы в  2 ,n Z имеют структуру бит бит ... 0 ... 0,   n k k для некоторого 0,..., .k n Теорема 1. Пусть  1 2 1 2 1, ,..., ; , ,..., ,k k kG a a a b b b b  – некоторая подгруппа индекса 2a группы  ,nV  ; 1v и 2v – случайные элементы, равновероятно распределенные в классах смежности iH и jH подгруппы G , соответственно; aji 2,...,1,  . Тогда: 1) количество классов смежности по подгруппе G , в которые сумма элемен- тов 1v и 2v по модулю 2n попадает с ненулевой вероятностью, равно k2 , если 01 b , 12 k , если 01 b ; а количество классов смежности, в которые сумма элементов 1v и 2v по модулю 2n попадает с нулевой вероятностью, равно ka 22  , если 01 b , 122  ka , если 01 b ; 2) если ji HH  , то классы смежности, в которые разность элементов 1v и 2v по модулю 2n попадает с ненулевой вероятностью, имеют следующий вид:  битбитбитбитбитбит 1121 ..................... babbab kkk  112kk1k BABBAB блок блок блок блок блок блок , где блоки lA содержат либо только 0, либо 1, для любого kl ,...,1 , и количество этих классов смежности равно k2 , если 01 b , 12 k , если 01 b ; Анализ перемешивающих свойств операций, заданных на одном носителе «Штучний інтелект» 3’2011 493 8К а количество классов смежности, в которые разность элементов 1v и 2v по модулю 2n попадает с нулевой вероятностью, равно ka 22  , если 01 b , 122  ka , если 01 b . При этом вероятности попадания разности элементов 1v и 2v в различные классы смежности будут одинаковые при любом выборе класса смежности iH (т.е. класса смежности, которому принадлежат 1v и 2v ) и будут зависеть только от вида подгруппы, по которой строятся эти классы смежности; 3) ненулевые вероятности попадания суммы (разности) элементов 1v и 2v по модулю 2n в соответствующие классы смежности будут лежать в пределах от 1 i k b i q   до 1 i k b i p   . Следует отметить, что если в подгруппе только «нулевые» блоки единичной длины, то количество классов смежности, в которые сумма векторов по модулю 2n попадает с ненулевой вероятностью, будет наибольшим. Если же «нулевые» блоки будут большой длины, то количество классов смежности, в которые сумма векторов по модулю 2n будет попадать с ненулевой вероятностью, уменьшается. Чем длиннее будут «нулевые» блоки, тем в меньшее количество классов смежности попадает сумма векторов по модулю 2n с ненулевой вероятностью, то есть перемешивающие свойства операции модульного сложения относительно побитового сложения будут зависеть от структуры подгруппы. Влияние операции побитового сложения на структуру факторгруппы  2 ,n Z по ее подгруппе Теорема 2. Пусть kG  подгруппа  2 ,n Z индекса 2k . Тогда: 1) kG (в соответствующем представлении) – подгруппа  ,nV  ; 2) классы смежности по подгруппе kG (относительно операции +) имеют вид , 0 2k k i G i   ; 3) классы смежности по подгруппе kG (относительно операции  ) имеют вид ki G , причем , 0 2 ;k k ki G i G i     4) если 1 2, ,kv v i G  то с вероятностью 1 1 2 ;kv v G  0 2ki  ; 5) если 1 2, ,kv v i G  то с вероятностью 1 1 2 ;kv v G  0 2ki  ; 6) если 1 2, ,k kv i G v j G    то с вероятностью 1 1 2 ,kv v i j G    причем класс смежности ki j G  , вообще говоря, не совпадает с ,ki j G  0 , 2ki j  ; 7) если 1 ,kv i G  2 ,kv j G  то с вероятностью 1 1 2 k v v i j G    ; 0 , 2ki j  . Ковальчук Л.В., Сиренко О.А. «Искусственный интеллект» 3’2011 494 8К Из данной теоремы можно сделать следующий вывод: если подгруппа имеет структуру, описанную в п. б) леммы 1, то есть для некоторого 0,...,k n элементы этой подгруппы имеют следующий вид бит бит ... 0 ... 0   n k k , то операция побитового (модульного) сложения сохраняет структуру соответствующей факторгруппы относительно модульного (побитового) сложения. Анализ перемешивающих свойств операции умножения по модулю 2n на классах смежности, построенных по группе   , 2n Лемма 2. О структуре группы   , 2n : 1) Группа ),( n2 Z – циклическая группа, генераторами которой будут все не- парные числа от 1 до 12 n . 2) Все подгруппы группы   , 2n в битовом представлении имеют вид:  120,2  knk k aaH , то есть каждый элемент из kH имеет следующий вид: бит бит ... 0 ... 0 ,    n k k для 0,..., .k n Рассмотрим группу   , 2n . Все ее подгруппы будут иметь порядки nkkn ,...,0,2  , а индексами соответственно будут числа nkk ,...,0,2  . Рассмотрим подгруппу H группы   , 2n , индекс которой равен k2 . Элементы этой подгруппы в битовом представлении будут иметь следующий вид:  битkбитkn 0...0...  . Выпишем все классы смежности по подгруппе H :  12,...,0,201  kk llHH ;  12,...,0,1212  kk llHH ; …  12,...,0,12212 2  kkkk llHH k . Теорема 3. Пусть H – подгруппа группы   , 2n порядка kn2 и индекса k2 , nk ,...,0 ; 1v и 2v – случайные элементы, которые равновероятно распределены в классах смежности Hi  и Hj  , где  12,..,0,  kji , соответственно. Тогда   1; 2mod 21 21         HivHiv HjivvP k , где  12,..,0,  kji . Из полученных результатов можно сделать вывод, что операция умножения практически не разрушает структуру факторгруппы аддитивной группы   , 2n , другими словами, операция модульного умножения относительно операции модуль- ного сложения будет обладать плохими перемешивающими свойствами. Анализ перемешивающих свойств операций, заданных на одном носителе «Штучний інтелект» 3’2011 495 8К Анализ перемешивающих свойств операции сложения по модулю 2n на классах смежности, построенных по группе   ,* 2n Лемма 3. О структуре группы   ,* 2n : 1) группа   ,* 2n не будет циклической при 3n ; 2) элемент данной группы 5g порождает ее циклическую подгруппу следующего вида: },14:{ * 2 NkkuZuG n  ; 3) эта подгруппа будет максимальной в том смысле, что если для некоторой подгруппы 1G выполняется: GG 1 и GG 1 , то * 21 nZG  . Теорема 4. Пусть H – подгруппа группы   ,* 2n порядка 22,...,2  nk и со- ответствующего индекса 2,...,2 2 nm ; mHH ,...,1 – соответствующие классы смеж- ности по подгруппе H ; 1v и 2v – случайные элементы, которые равновероятно распределены в этих классах смежности iH и jH , где  mji ...,,1,  , соответ- ственно. Тогда 0; 21 21         ji l HvHv HvvP , где  mlji ...,,1,,  . Из полученных результатов можно сделать вывод, что операция модульного сложения относительно операции модульного умножения будет также обладать пло- хими перемешивающими свойствами. Другими словами, операция сложения в кольце n2  не разрушает структуру факторгруппы мультипликативной группы кольца, по- строенной по ее любой подгруппе. Выводы Результаты, полученные в данной работе, характеризуют перемешивающие свойства операций побитового и модульного сложения, а также операций модульного сложения и умножения, заданных на одном носителе. Наиболее интересным является тот факт, что действие операции модульного сло- жения на факторгруппу относительно операции побитового сложения существенно зависит от выбора подгруппы в  ,nV  , а действие операции побитового сложения сохраняет структуру соответствующей факторгруппы по любой подгруппе в   , 2n . Операция ум- ножения в кольце n2  практически не разрушает структуру факторгруппы его аддитив- ной группы (по любой подгруппе). Аналогичное утверждение будет справедливо также и для операции сложения в этом кольце. Данный факт дает потенциальную возможность применять атаку гомоморфизмов (групповую атаку) при некоторых дополнительных условиях в том случае, когда в раундовых функциях блочного шифра используется чередование этих операций. Ковальчук Л.В., Сиренко О.А. «Искусственный интеллект» 3’2011 496 8К Литература 1. Шеннон К. Теория связи в секретных системах // Работы по теории информации и кибернетике / К. Шеннон. – М. : Издательство иностранной литературы, 1963. – С. 333-402. 2. Paterson K.G. Imprimitive permutation groups and trapdoors in iterated block ciphers / K.G. Paterson // Fast Software Encryption. – FSE’99, Proceedings. – Springer Verlag, 1999. – P. 201-214. 3. Wagner D. Towards a unifying view of block cipher cryptanalysis / D. Wagner // Fast Software Encryption. – FSE’04, Proceedings. – Springer Verlag, 2004. – P. 116-135. 4. Шемякина О.В. О перемешивающих свойствах операций в конечном поле / О.В. Шемякина // Труды Восьмой Общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-09), (30 октября – 2 ноября 2009). – М. : МЦНМО, 2010. – Т. 2. – С. 87-90. 5. Горчинский Ю.Н. О гомоморфизмах многоосновных универсальных алгебр в связи с криптогра- фическими применениями / Ю.Н. Горчинский // Труды по дискретной математике. – М. : ТВП, 1997. – Т. 1. – C. 67-84. 6. Горчинский Ю.Н. Стохастические алгебры / Ю.Н. Горчинский // Труды по дискретной математике. – М. : ТВП, 1998. – Т. 2. – C. 55-87. Literatura 1. Shennon K. Rabotypoteoriiinformacii i kibernetike. M.: Izdatel’stvoinostrannojliteratury. 1963. S. 333-402. 2. Paterson K.G. FastSoftwareEncryption. FSE’99, Proceedings. SpringerVerlag. 1999. P. 201-214. 3. Wagner D. FastSoftwareEncryption. FSE’04, Proceedings. SpringerVerlag. 2004. P. 116-135. 4. Shemjakina O.V. TrudyVos'mojObshherossijskojnauchnojkonferencii «Matematika i bezopasnost’ informacionnyh tehnologij» (MaBIT-09), 30 oktjabrja – 2 nojabrja 2009. T. 2. M. : MCNMO. 2010. S. 87-90. 5. GorchinskijJu.N. Trudypodiskretnojmatematike. T 1. M.: TVP. 1997. S. 67-84. 6. GorchinskijJu.N. Trudypodiskretnojmatematike. T 2. M. : TVP. 1998. S. 55-87. Л.В. Ковальчук, О.О. Сіренко Аналіз перемішувальних властивостей операцій, визначених на одному носії У статті аналізується можливість застосування атак гомоморфізмів (групових атак) до блочних шифрів у випадку, коли в раундових функціях використовується чергування різних операцій, таких як операції модульного та побітового додавання, а також модульного множення. Отримані результати, які характеризують перемішувальні властивості операцій побітового та модульного додавання на множині двійкових векторів, а також результати, що характеризують перемішувальні властивості операцій додавання та множення в кільці n2  . L. Kovalchuk, O. Sirenko Analysis of Mixing Features of the Operations, Defined on One Carrier The paper is devoted to the analysis of the possibility of homomorphism attacks (group attack) to the block cipher in the case when the round functions use the interchange of various operations such as bitwise and modular addition, modular multiplication. Some results characterizing the mixing properties of bitwise and modular addition on the set of binary vectors and the results that characterize the mixing properties of addition and multiplication in the ring n2  are obtained. Статья поступила в редакцию 08.07.2011.

Схожі ресурси