RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2017, номер 38, страницы 57–65 (Mi pdm598)  

Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)

Математические методы криптографии

Substitution block ciphers with functional keys

G. P. Agibalov

National Research Tomsk State University, Tomsk, Russia

Аннотация: We define a substitution block cipher $\mathcal C$ with the plaintext and ciphertext blocks in $\mathbb F_2^n$ and with the keyspace $K_{s_0,n}(g)$ that is the set $\{f(x)\colon f(x)=\pi_2(g^{\sigma_2}(\pi_1(x^{\sigma_1}))); \sigma_1,\sigma_2\in\mathbb F_2^n; \pi_1,\pi_2\in S_n\}$, where $s_0$ is an integer, $1\leq s_0\leq n$; $g\colon\mathbb F_2^n\to\mathbb F_2^n$ is a bijective vector function $g(x)=g_1(x)g_2(x)…g_n(x)$ such that every its coordinate function $g_i(x)$ essentially depends on some $s_i\leq s_0$ variables in the string $x=x_1x_2…x_n$; $S_n$ is the set of all permutations of the row $(1 2…n)$; $\pi_i$ and $\sigma_i$ are the permutation and negation operations, that is, $(\pi=(i_1i_2…i_n))\Rightarrow(\pi(a_1a_2…a_n)=a_{i_1}a_{i_2}…a_{i_n})$, $(\sigma=b_1b_2…b_n)\Rightarrow((a_1a_2…a_n)^\sigma=a_1^{b_1}a_2^{b_2}…a_n^{b_n})$ and, for $a$ and $b$ in $\mathbb F_2$, $a^b=a$ if $b=1$ and $a^b=\neg a$ if $b=0$. Like $g$, any key $f$ in $K_{s_0,n}(g)$ is a bijection on $\mathbb F_2^n$, $f(x)=f_1(x)f_2(x)…f_n(x)$, and every its coordinate function $f_i(x)$ essentially depends on not more than $s_0$ variables in $x$. The encryption of a plaintext block $x$ and the decryption of a ciphertext block $y$ on the key $f$ are defined in $\mathcal C$ as follows: $y=f(x)$ and $x=f^{-1}(y)$. Here, we suggest a known plaintext attack on $\mathcal C$ with the threat of discovering the key $f$ that was used. Let $P_1,P_2,…,P_m$ be some blocks of a plaintext, $C_1,C_2,…,C_m$ be the corresponding blocks of a ciphertext, i.e., $C_l=f(P_l)$ for $l=1,2,…,m$, and $P_l=P_{l1}P_{l2}…P_{ln}$, $C_l=C_{l1}C_{l2}…C_{ln}$. The object is to determine the coordinate function $f_i(x)$ of $f$ for each $i\in\{1,2,…,n\}$. The suggested attack consists of two steps, namely we first determine the essential variables $x_{i_1},…,x_{i_s}$ of $f_i(x)$ and then compute a Boolean function $h(x_{i_1},…,x_{i_s})$ such that $h(a_{i_1},…,a_{i_s})=f_i(a_1,…,a_n)$ for all $n$-tuples $(a_1a_2…a_n)\in\mathbb F_2^n$. For determining the essential variables of $f_i$, we construct a Boolean matrix $\|\inf D(f_i)\|$ with the set of rows $\inf D(f_i)$, where $D(f_i)=\{P_l\oplus P_j\colon C_{li}\neq C_{ji}; l,j =1,2,…,m\}$, $C_{li}=f_i(P_l)$, $l=1,…,m$, $i=1,…,n$, and $\inf D(f_i)$ is the subset of all the minimal vectors in $D(f_i)$. Then the numbers of essential variables for $f_i$ are the numbers of columns in the intersection of all covers of $\|\inf D(f_i)\|$ with the cardinalities not more than $s_0$, where a cover of a Boolean matrix $M$ is defined as a subset $C$ of its columns such that each row in $M$ has '1' in a column in $C$. For computing $h(x_{i_1},…,x_{i_s})$, we first set $h(P_{li_1},…,P_{li_s})=C_{li}$ for $l=1,…,m$ and then, if $h_i$ is not yet completely determined on $\mathbb F_2^s$, we increase the number $m$ of known blocks $(P_i,C_i)$ of plain- and ciphertexts or extend $h_i$ on $\mathbb F_2^s$ in such a way that the vector function $h=h_1h_2…h_n$ with the completely defined coordinate functions is a bijection on $\mathbb F_2^n$. We also describe some special known plaintext attacks on substitution block ciphers with keyspaces being subsets of $K_{s_0,n}(g)$.

Ключевые слова: substitution ciphers, block ciphers, functional keys, cryptanalysis, known plaintext attack, Boolean functions, essential variables, bijective functions.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-01-00354
The author was supported by the RFBR-grant no. 17-01-00354.


DOI: https://doi.org/10.17223/20710410/38/4

Полный текст: PDF файл (608 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7
Язык публикации: английский

Образец цитирования: G. P. Agibalov, “Substitution block ciphers with functional keys”, ПДМ, 2017, no. 38, 57–65

Цитирование в формате AMSBIB
\RBibitem{Agi17}
\by G.~P.~Agibalov
\paper Substitution block ciphers with functional keys
\jour ПДМ
\yr 2017
\issue 38
\pages 57--65
\mathnet{http://mi.mathnet.ru/pdm598}
\crossref{https://doi.org/10.17223/20710410/38/4}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm598
  • http://mi.mathnet.ru/rus/pdm/y2017/i4/p57

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. G. P. Agibalov, I. A. Pankratova, “Asymmetric cryptosystems on Boolean functions”, ПДМ, 2018, № 40, 23–33  mathnet  crossref
    2. Г. П. Агибалов, И. А. Панкратова, “Криптосистемы с открытым ключом на булевых функциях”, ПДМ. Приложение, 2018, № 11, 54–57  mathnet  crossref
    3. G. P. Agibalov, “ElGamal cryptosystems on Boolean functions”, ПДМ, 2018, № 42, 57–65  mathnet  crossref
    4. И. А. Панкратова, “Свойства компонент некоторых классов векторных булевых функций”, ПДМ, 2019, № 44, 5–11  mathnet  crossref
    5. Н. М. Киселева, Е. С. Липатова, И. А. Панкратова, Е. Е. Трифонова, “Алгоритмы вычисления криптографических характеристик векторных булевых функций”, ПДМ, 2019, № 46, 78–87  mathnet  crossref
    6. Л. А. Карпова, И. А. Панкратова, “Перемешивающие свойства некоторых классов подстановок на $\mathbb{F}_2^n$”, ПДМ. Приложение, 2019, № 12, 47–50  mathnet  crossref
    7. А. И. Метальникова, И. А. Панкратова, “О классах булевых функций ограниченной сложности”, ПДМ. Приложение, 2019, № 12, 58–60  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:153
    Полный текст:53
    Литература:25
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020