Search

Работа посвящена разработке механизмов мандатного контроля целостности в мандатной ДП-модели СУБД MySQL. Вводятся основные элементы модели (решётка уровней целостности сущностей, функции избирательности контроля целостности, уровней целостности сущностей и т.д.), с помощью которых обеспечивается мандатный контроль целостности; описываются некоторые правила преобразования состояний системы; определяются состояния системы, в которых не происходит нарушения целостности, и формулируются условия, которые необходимы, чтобы система оставалась в этих состояниях., The paper reports on mandatory integrity control mechanisms elaborated for mandatory DP-model of DBMS MySQL. The elaboration is aimed at data protection from improper modification. It allows avoid information flows from entities of lower integrity level that modify entities of higher integrity level. The paper provides new elements introduced for mandatory integrity control, describes some rules of system transformation, defines the notion of state without integrity violation and gives a necessary condition for the system to stay in this state.

Рассматривается алгоритм генерации пары простых чисел p и q, таких, что числа g = -(p 1, q 1) и h = -(pq 1) также простые. Такие простые числа впервые 2 2g рассмотрены в 2006 г. М. Дж. Хинеком в связи с предложенной им модификацией криптосистемы RSA, устойчивой к атакам на малые секретные экспоненты. Приводятся экспериментальные данные о времени работы алгоритма., In this paper, a modification is described for an algorithm generating the pair of prime integers p, q such that the integers g = -(p 1,q 1) and h = -(pq 1) are also prime. The primes p, q satisfied this condition are called common 2g primes. In 2006 M. J. Hinek introduced such primes for the variant of RSA cryptosystem resistant to small private exponent attacks. The original algorithm for generating common primes can be optimized with the modification described here. The optimized algorithm is two times faster in worst case and more times in average. It takes 19 seconds to generate a pair of 512-bit common primes p, q with 384-bit prime g. The modification uses sieving technique which is also mentioned in the paper of M. J. Hinek. Despite the speed up of the algorithm, the generation of common primes still takes much more time than the generation of typical primes used in RSA cryptosystem.

Рассматривается задача поиска булевых векторов в потоке данных. Предлагается метод построения конечного автомата, который ищет одновременно несколько векторов, совершая только две простые операции на каждый бит или группу битов. При этом с увеличением количества искомых шаблонов объём требуемой памяти растёт медленнее, чем суммарная длина шаблонов, а трудоёмкость не изменяется совсем. Приводится оценка количества состояний автомата., The task under consideration in this paper is to search for binary subsequencies in a data stream. The article offers the finite automaton able to search for a set of binary vectors simultaneously performing only two operations per every bit or even byte of the data stream. Increasing the number of searched vectors causes a slower increase in memory usage compared to overall vectors' length growth and complexity does not increase at all. The automaton is described by the transition and output tables. Estimates for the size of the automaton's tables are given. Known approaches to the problem are discussed. There is a possibility to generalize the automaton building algorithm to search for partially defined boolean patterns, but the amount of required memory may be greater than the estimate found in the paper

Теоретически исследована зависимость между вероятностью сохранения разности двух величин после их сложения (вычитания) по модулю с третьей равномерно распределённой величиной и весом Хэмминга этой разности. Под разностью понимается общепринятая в криптоанализе операция XOR. Доказано, что если старший бит разности равен 0, то вероятность её сохранения равна 2 -h, где h вес Хэмминга разности, и равна 2 -(h-i), если старший бит разности равен 1., Despite the fact that differential cryptanalysis is a widely used approach to cryptanalysis of iterative block ciphers, the authors of differential attacks rarely provide their strict mathematical reasoning. However, some steps in this direction have been already made. For instance, X. Lai and J. Massey (1991) suggested a model of so-called Markov iterative block cipher and formulated a hypothesis of stochastic equivalence. K. Nyberg and L. Knudsen (1994) showed that it is possible to create a cipher resistant to differential cryptanalysis, and, later, S. Vaudenay (2003) developed a model for creating such a cipher. G. P. Agibalov (2008) presented a general description of differential cryptanalysis for arbitrary iterative block ciphers with additive round keys. A. A. Selcuk analytically calculated probability of a differential attack success. A.I. Pestunov (2013) suggested a formalization of the basic differential cryptanalysis notions and used it for their systematization. One more important, though not thoroughly investigated problem, is finding out how does two-values difference propagate through operations used in block ciphers. The problem consists in estimating the probability that a pair of values with a fixed difference is transformed by an operation into another fixed difference. For some operations (e. g. bitwise rotation or XOR) this task is rather simple, while for some commonly used operations such as modulo addition, subtraction and multiplication, it is not a trivial one. When developing an attack on RC5, A. Biryukov and E. Kushilevitz (1998) claimed that a one-bit difference remains unchanged after modulo addition with the probability 1/2 (or with the probability 1 if the difference is located in the most significant bit). The claim has not been proved theoretically but the authors carried out some experiments verifying the attack. In works devoted to differential cryptanalysis of MARS and CAST-256, A. I. Pestunov (2009) used this fact referencing the paper of A. Biryukov and E. Kushilevitz and verifying developed attacks. Besides, in the second paper (about CAST-256) he used an experimentally found relation between the Hamming weight of a difference and the probability that this difference is preserved after modulo addition. In the current paper, the existence of this relation is proved theoretically. Exactly, it is proved that the difference of two values is preserved after their modulo addition or subtraction with a third randomly chosen value with the probability 2 or 2 -(h-1), if the most significant bit of the difference is equal to 0 or to 1 respectively. The obtained results extend the results obtained by A. I. Pestunov (2013) for one-bit differences

In 2005, Wang et al. developed practical collision attacks on MD4 and RIPEMD hash functions. For RIPEMD however, description of the attack has been presented only at ideological level, raising concerns about the attack complexity claimed by the authors. X. Wang et al. stated that the attack complexity is about 218 calls of compression function. In this paper, the omitted details of the Wang attack on RIPEMD hash function are recovered and the single-step message modification being the first stage of this attack is implemented. The experiments showed that the lower bound of the average complexity of the Wang's attack is greater than 232'49 compression function calls. This estimation is significantly higher than the one stated in the Wang's paper.

Creating a hash function cryptographers almost never prove the selection of algorithmic blocks, the order of blocks. The hash-function HAVAL proposed in 1992 is probably the only exception from this rule.This hash-function is constructed of blocks with specific properties such as strong independence of output bits, strong avalanche effect, 0-1 balance and others for Boolean functions, and the result hash function was proposed to be cryptographically strong. But time had shown that it is not true. The papers, proposing other popular hash-functions such as MD4, MD5, SHA-0, SHA-1, SHA-2, RIPEMD, GOST 34.11-94 and others, do not contain any proof for choice of elements. The algorithms used in construction of the hash-family of MDx contain constant values, addition modulo 232, rotations and primitive Boolean functions, chosen by the author. The cryptanalytics almost had not undertaken yet any attempts to prove the choice of elements and if it is possible to change them to improve the cryptographic properties of the algorithm. The main target of this paper is an analysis of how primitive Boolean functions and rotations influence the resistance of MD5 to differential attacks.

Исследован класс биективных регистров сдвига длины n над множеством Vr двоичных r-мерных векторов, n,r > 1, построенных на основе аддитивных генераторов по модулю 2r, модифицированных с использованием подстановки множества Vr. Функция обратной связи таких регистров является композицией функции обратной связи аддитивного генератора и преобразования множества VT. Задача точного определения существенных переменных для композиции нелинейных функций, как правило, сложна, однако использование комбинаторных свойств биекции Z2r о Vr позволило полностью описать множество существенных переменных функции обратной связи исследуемых регистров., We consider the class of bijective shift registers of length n over the set Vr of binary vectors of length r. In this paper, we research registers constructed on the additive generators modulo 2r modified by a transformation of Vr. The feedback function of such a register is a composition of additive generator feedback function and the transformation of Vr. It is known that determination of sufficient variables for the composition of nonlinear functions is a complicated problem. By using combinative properties of the bijection Z2r о Vr, we describe the set of all sufficient variables for feedback function of the registers researched.

Наиболее распространёнными группами наложения ключа итерационных алгоритмов блочного шифрования являются регулярное подстановочное представление V+ группы векторного наложения ключа, регулярное подстановочное представление Z+ аддитивной группы кольца вычетов и регулярное подстановочное представление Z^+i мультипликативной группы простого поля (2n + 1 простое число). Рассматривается расширение группы Gn = (V+, Z+n) преобразованиями и группами, естественными для криптографической практики. К числу таких преобразований и групп относятся: группы Z+d х V+_d и V+_d х Z+d, подстановка псевдообращения над полем GF(2n) или кольцом Галуа GR(2md, 2m)., Three groups are often used as key addition groups in iterated block ciphers: V+, Z+ and Zfn+1. They are the regular permutation representations, respectively, of the group of vector key addition, of the additive group of the residue ring Z2n, and of the multiplicative group of the residue ring Z2n+1, where 2n +1 is a prime number. In this paper, we describe some properties of the extensions of the group Gn = (V+, Z+) by transformations and groups related to cryptographic applications. The groups Z+d x V+_d, V+_d x Z+d and a pseudoinverse permutation of the field GF(2n) or the Galois ring GR(2md, 2m) are examples of such groups and transformations.

Граф называется 1-вершинно(рёберно)-гамильтоновым, если после удаления любой его вершины (ребра) получившийся граф является гамильтоновым; 1-вер-шинно(рёберно)-гамильтонов граф называется оптимальным, если он имеет минимально возможное число рёбер среди всех 1-вершинно(рёберно)-гамильтоновых графов с тем же числом вершин. В работе перепроверены полученные ранее данные для оптимальных 1-вершиннои 1-рёберно-гамильтоновых графов, а также удалось вычислить новые значения для 28 вершин., A graph is called 1-vertex-hamiltonian (1-edge-hamiltonian) one, if it becomes Hamilto-nian after deleting any its vertex (edge). 1-vertex-hamiltonian (1-edge-hamilton) graph is optimal if it has the minimum number of edges among all 1-vertex-hamiltonian (1-edge-hamiltonian) graphs with the same number of vertices. In the paper, the previous data on the number of optimal 1-vertexand 1-edge-hamiltonian graphs with the number of vertices up to 26 are verified, and new data for 28-vertex graphs are given.

Группа экспоненцирования S2 t Sn, называемая также группой Джевонса, совпадает с группой ASn, порождённой группой сдвигов на n-мерном векторном пространстве Vn над полем GF(2) и группой подстановочных (n х п)-матриц Sn над полем GF(2). Для группы подстановок G ^ S2 t Sn рассматривается её естественное действие на упорядоченных парах векторов из пространства Vn. Орбиты при таком действии называются орбиталами. Каждому орбиталу Г ставится в соответствие граф с множеством вершин Vn, и множеством рёбер Г, называемый графом орбитала. Проводится классификация дистанционно-транзитивных графов орбиталов надгрупп группы Джевонса. Показано, что среди дистанционно-транзитивных графов орбиталов надгрупп группы Джевонса имеются графы, изоморфные следующим графам: полному графу K2n, полному двудольному графу K2„-1 2n-i, половинному (n + 1)-кубу, сложенному (n + 1)-кубу, графам знакопеременных форм, графу Тейлора, графу Адамара., The Jevons group is the exponential group S2 t Sn. It is generated by the group of all permutation (n x n)-matrices over GF(2) and the translation group on the n-dimensional vector space Vn over GF(2). For a permutation group G on Vn being an overgraph of S2 t Sn, an orbital of G is an orbit of G in its natural action on Vn x Vn. The orbital graph associated with an orbital Г is the graph with the vertex set Vn and the edge set Г. In this paper, we classify distance-transitive orbital graphs of overgroups of the Jevons group S2 t Sn and show that some of them are isomorphic to the following graphs: the complete graph K2n, the complete bipartite graph K2n-i,2n-i, the halved (n + 1)-cube, the folded (n + 1)-cube, alternating forms graphs, the Taylor graph, the Hadamard graph.

Одно из направлений исследований итерационных алгоритмов блочного шифрования заключается в описании свойств группы, порожденной множеством всех частичных раундовых функций. Алгоритм «Кузнечик» является новым российским стандартом блочного шифрования. Доказывается, что группа, порождённая множеством всех частичных раундовых функций алгоритма блочного шифрования «Кузнечик», является знакопеременной., One of the research areas for iterative block cyphers is to describe the properties of the group generated by the set of all partial round functions. Kuznechik is a new Russian block encryption standard. In this paper, we prove that the group generated by the set of all partial round functions of Kuznechik is alternating.

С помощью матрично-графового подхода оценены перемешивающие свойства двухкаскадных генераторов: на основе последовательного соединения регистров сдвига; генераторов 1-2 шага; с перемежающимся шагом. Получены условия локальной примитивности (квазипримитивности) перемешивающих графов генераторов и верхние оценки соответствующих локальных экспонентов (квазиэкспонентов), которые при многих значениях параметров близки по порядку к сумме длин регистров генератора., The important properties of the dependence of gamma signs on all signs in the initial state of a gamma generator are called the mixing properties of the generator. It is known that if the mixing properties of a generator are good, then the transition graph of the generator is primitive or local primitive. In this paper, mixing properties are evaluated for the following 2-cascade generators constructed of Linear Feedback Shift Register (LFSRs): generator based on shift register series, generator of 1-2 steps, and generator of intermittent steps. Namely, for these generators, some necessary and sufficient conditions for local primitiveness or quasiprimitiveness are given and upper bounds for appropriate local exponents or quasiexponents depending on the parameters of LFSR are obtained. For many values of parameters, the bounds are close to the sum of lengths of LFSRs in the generator.

Уровень аффинности двоичной функции определяется как минимальное число переменных, произвольная фиксация значений которых делает функцию аффинной. Обобщённый уровень аффинности определяется как минимальное число фиксаций линейных комбинаций переменных, некоторая фиксация значений которых делает функцию аффинной. Для квадратичной формы ранга 2r обобщённый уровень аффинности совпадает с r. Приводятся свойства распределения ранга случайной квадратичной формы и, как следствие, получается асимптотическая оценка обобщённого уровня аффинности квадратичных форм., An affinity level la(f) of a Boolean function f is defined as minimal number of variable fixations, that produce an affine function. A general affinity level La(f) of Boolean function f is defined as minimal number of fixations of variable linear combination values, that produce an affine function. The general affinity level of quadratic form equals r iff the rank of quadratic form equals 2r. The paper contains some asymptotic properties of the rank of quadratic forms. As a corollary some asymptotic bounds of the general affinity level of quadratic forms are formulated. Let 0 ^ c ^ 1. If n = 2k + e, 0 ^ e ^ 1, then for almost all quadratic forms of n variables, as n ^ го.

Представлен новый метод построения разностных путей в задаче поиска коллизий криптографических хеш-функций, основанный на использовании алгоритмов решения проблемы булевой выполнимости. На начальном этапе метода строится пропозициональная кодировка задачи поиска коллизий рассматриваемой хеш-функции. Затем в полученную кодировку добавляются (в виде КНФ) дополнительные ограничения. Как правило, это значения целочисленных разностей на сообщения, дающие коллизию, а также на отдельные фрагменты дифференциального пути. В качестве отправной точки поиска можно использовать некоторый известный либо случайный дифференциальный путь (во втором случае наличие коллизий, удовлетворяющих такому пути, не гарантируется). Задача варьирования значений разности переменных, кодирующих заполнение хеш-регистров, сводится к SAT. Для эффективного решения соответствующих серий SAT-задач написана MPI-программа, работающая на вычислительном кластере. Основным результатом стало построение дифференциального пути для задачи поиска коллизий криптографической хеш-функции MD4, отличного от известных., In this paper, we present a new method for constructing differential paths to find collisions of cryptographic hash functions in the MD family. The method is based on using the algorithms for solving Boolean satisfiability problem (SAT). The proposed method can be applied to hash functions based on the Merkle Damgard construction, which, on its internal stages, use inner variables of relatively small size. We consider two copies of the algorithm for computing hash function value, that process some messages M and M', respectively. On the initial stage of the method, we construct two "template" CNFs C and C', which encode the process of computing hash-images for M and M'. The sets of Boolean variables used in these two CNFs are disjoint. We combine CNFs C and C via conjunction and add to the result the constraint specifying that hash values for M and M' are equal. Thus, we obtain the CNF C that encodes the problem of finding collisions for the considered hash function. Then we add to C additional constraints (in the form of clauses), that encode the corresponding differential path. In the context of the proposed method, we then explore the satisfiability of CNF of the form CЛ Ca Л C«sfc=c, where by Ca we denote the CNF, that takes the value 1 iff the difference between integer values specified by 512-bit vectors M and M' is equal to some constant A. By C^fc=c we denote the CNF, that takes value 1 iff a variable takes the value c. Here, is a 32-bit variable, that encodes the difference of integer values of hash registers at the step number k. The algorithms in the MD family use 32-bit inner variables. In this case, c is a 32-bit constant. Therefore, it is possible to check all of its possible values and consider SAT for CNFs of the kind C Л Ca Л C^fc=c. The SAT instances of this kind, for which we cannot obtain the answer in relatively small time (several seconds), are interrupted. Let c' be the value of, for which the solving of such SAT instance is interrupted, and assume that c' is not equal to the corresponding value in the known differential path. Then we can consider c' as a possible candidate for the value of in the new differential path. The described algorithm is implemented in the form of parallel MPI program and tested on the computing cluster. As a result we managed to construct new differential path for finding collisions of MD4 hash function. This path differs from the path proposed by X. Wang in differential constraints for steps number k E {13,17, 20, 21}. We incorporated it into the propositional encoding of MD4, constructed the corresponding CNF, and applied to it the SAT solver cryptominisat, that has an option of enumerating multiple solutions. For the constructed CNF, the solver managed to find 1000 solutions in 416 seconds. In the application to the similar CNF produced for the Wang differential path, cryptominisat finds 1000 solutions in 520 seconds.

Известным открытым вопросом в области векторных булевых функций является проблема существования APN-перестановок от чётного числа переменных. Рассматривается множество векторных булевых функций специального вида, добавление к которым аффинной функции приводит к перестановке. Исследуются свойства этого множества, а также возможность и условия существования непустого пересечения с множеством APN-функций., The existence of APN permutation of even dimension is an important unsolved problem on vectorial Boolean functions. In this paper, we consider the special set of vectorial Boolean functions, such that the sum of any function in the set and an affine vectorial function is a permutation. We study properties of this set and conditions for existence of its nonempty intersection with the set of APN functions.

In this paper, we deal with vectorial Boolean functions F : F^ ^ F^ of dimension n ^ 1. Functions F and G are EA-nonequivalent if G = A1 о F о A2 ф A for any affine functions A1, A2 and A, where A1 and A2 are permutations. A function F is called APN if for any a, b Е F^, where a is nonzero, the equation F(x) ф F(x ф a) = b has at most two solutions. We prove that there are no APN functions on the distance one from an APN functions up to dimension 5, from all quadratic APN functions of dimension 6, and from all known EA-nonequivalent APN functions of dimensions 7 and 8.

В циклической полугруппе орграфов исследован признак наличия петель в вершинах из заданного множества. Для показателя этого признака через длины контуров орграфа (образующего элемента циклической полугруппы) получены достижимые оценки и формулы для подсчёта точного значения. Применение формул показано на примере. Результаты позволяют оценить экспоненты широкого класса примитивных систем орграфов., This paper is devoted to describing the character of loop existing at the given vertex subset in a cyclic semigroup of digraphs named as loop-character. Some attained bounds and formulae for the loop-character index are obtained. They are expressed in terms of circuit lengths in a digraph, which is the generator of the cyclic semigroup. An example showing the exactness of the bounds is given. The results can be used for estimating exponents of wide range primitive digraph systems.

Исследовано ключевое расписание симметричного r-раундового блочного шифра, при котором все раундовые ключи различны. Ключевое расписание реализуется как последовательное соединение автоматов: автономного автомата A, генерирующего выходную последовательность бинарных векторов с длиной периода не меньше r, и внутренне автономного автомата с постоянной памятью, в которой записан основной ключ блочного шифра. Рассмотрен пример, использующий в качестве автомата A линейный регистр сдвига с максимальной длиной периода., This paper describes the key schedule providing all different round keys for r-round symmetric block cipher. The key schedule is implemented by a series connection of automata: an autonomous automaton A generating an output sequence of binary vectors with the period length is not less than r, and internally autonomous automaton with permanent memory containing the encryption key of a block cipher. As an example, a linear shift register with a maximum period is considered as the automaton A.

Описаны два вида криптосистем Мак-Элиса, построенных на подкодах кода РидаМаллера. Изучен вопрос эквивалентных ключей для этих криптосистем. Получен результат о сводимости одной криптосистемы к другой. Приведены алгоритмы, которые позволяют применить атаку Чижова Бородина к рассматриваемым криптосистемам для некоторых параметров кодов Рида Маллера., In this paper, we describe two types of McEliece cryptosystems based on some Reed Muller subcodes and study the question of equivalent keys for these cryptosystems. A method for reduction of one cryptosystem to the another is obtained. Also, we show that these cryptosystems based on Reed Muller subcode with the most widely used parameters can be attacked with the authors' algorithm.

Ранее был получен следующий результат: минимальное вершинное 1-расширение любой отличной от гамильтоновой ориентации цепи с числом вершин больше 4 содержит по крайней мере четыре дополнительные дуги. В данной работе удалось значительно уточнить эту оценку, а также получить верхнюю оценку на число дополнительных дуг., Previously known result states that the minimal vertex 1-extension of any nonhamiltonian path orientation with the number of vertices more than 4 contains at least 4 additional arcs. In this paper, this bound is significantly refined, and upper bound for the number of additional arcs is given.

Работа посвящена реализации полубайтовых подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ алгебраическими пороговыми функциями (АПФ). Для каждой из подстановок алгоритмов Магма рассмотрен вопрос принадлежности линейных комбинаций координатных функций к классу АПФ. Для подстановок 2-ГОСТ предложено их задание через линейные комбинации АПФ., The paper deals with the implementation of Magma and 2-GOST block cipher semibyte substitutions by algebraic threshold functions (ATF). For each Magma substitution, an ATF-presentation of some linear combinations of its coordinate functions is proposed. Some linear combinations of ATF representing 2-GOST substitutions are found.

Исследуются симметрические свойства APN-функций. Доказана теорема о несуществовании перестановки на координатах, относительно которой APN-функция сохраняет свои значения. Получены верхние оценки количества симметрических булевых функций среди координатных функций APN-функции, а также количества функций, сохраняющих своё значение на циклических сдвигах координат. Получена нижняя оценка числа различных значений APN-функции. Доказаны утверждения о максимально возможном количестве одинаковых значений у APN-функции при малом числе переменных., In the paper, symmetric properties of APN functions are considered. For any APN function F, it is proved that F can not be a symmetric vector function and there is no permutation of its coordinates such that F keeps its value. Theorems about strict upper bounds for the number of its symmetric and rotation symmetric coordinate Boolean functions are proved. The lower bound for the number of distinct values of F is obtained. It is shown that there exists an upper bound for the maximal number of coinciding values of F.

Рассмотрена связь между ^w^h-марковостью итеративных алгоритмов блочного шифрования и методом гомоморфизмов. Для алгоритмов блочного шифрования и разбиений W алфавита текстов X, блоки которых являются смежными классами по некоторой подгруппе абелевой регулярной группы (X, ®), доказана эквивалентность между ^w^h-марковостью алгоритма и существованием нетривиального гомоморфизма. Показано, что класс ^w^h-марковских преобразований не ограничивается только упомянутыми разбиениями. Так, для разбиений W, блоки которых не являются смежными классами по подгруппе аддитивной группы (V+, ®) векторного пространства Vn, описаны классы аффинных и нелинейных ©w^h-марковских преобразований. Приведены условия на разбиения W пространства Vn, при которых аффинное преобразование является ®w, ch-марковским. Получено, что для каждого разбиения W пространства Vn множество всех ©w^h-марковских преобразований из является группой. Приведены примеры таких групп. Тем самым показано, что для данного класса разбиений ^w^h-марковость является обобщением рассмотренных гомоморфизмов., In this paper, we describe relations between ® W)Ch-markovian block ciphers and a wreath product. Let X be an alphabet of plaintexts (ciphertexts) in iterated block ciphers, (X, ®) be a regular abelian group, and W = {W 0,..., W r-1} be a partition of X. In the case when W is the set of cosets of a subgroup of (X, ®), we prove that ®-Markov block cipher is ® W;Ch-markovian iff W is an imprimitivity system of the group generated by round functions of the cipher. We show that there are ® W;Ch-markovian block ciphers where W is not a set of cosets. So, for the additive group (V+, Ф) of the vector space Vn, we describe ф-w^h-markovian classes of nonlinear and affine transformations for W being not a set of cosets. We show that the set of all affine ф-^h-markovian transformations on V n is a group and give examples of it.

Для защиты конфиденциальности и легальности данных вводится понятие шифра с водяным знаком (называемого также w-шифром). Его основная идея следующая: преобразование открытого текста x композицией операций шифрования и расшифрования с использованием соответствующих ключей приводит к некоторому подходящему тексту x', сохраняющему информацию текста x и содержащему некоторый уникальный водяной знак w, идентифицирующий подлинного владельца x'. Ключи зашифрования и расшифрования в w-шифре должным образом связаны друг с другом и с заданным водяным знаком w. В отличие от шифров, обычно изучаемых в криптографии, функция шифрования в w-шифре не обязательно обратимая. Таким образом, фактически w-шифры не являются шифрами в известном смысле этого слова, но шифры суть w-шифры некоторого частного вида, и все термины, понятия и обозначения, относящиеся к шифрам, полностью применимы к w-шифрам. Показано, как применением w-шифра можно осуществить встраивание водяного знака в данные в процессе зашифрования открытого текста либо в процессе расшифрования шифртекста. Приводятся примеры w-шифров, построенных на базе симметричных поточных шифров., In order to protect both the data confidentiality and legality, a concept of a watermarking cipher (also called a w-cipher) is defined. The main idea of this is as follows: the transformation of a plaintext x by the composition of the encryption and decryption operations using some encryption and decryption keys yields a proper text x' containing a unique watermark w. The encryption and decryption keys in the w-cipher are connected in some way with each other and with the given watermark w. In contrast with the ciphers usually studied in cryptography, the encryption function in a w-cipher is not compulsorily invertible. Thus in fact w-ciphers are not ciphers in the known sense of the word but the ciphers are w-ciphers of a certain partial type, and all terms, notions and notations related to ciphers are quite applicable to w-ciphers. It is shown how a data watermarking can be performed by applying a w-cipher in such a way that the concealment of a watermark into a plaintext is accomplished by this w-cipher either in the encryption or in the decryption processes. Some examples of w-ciphers constructed on the basis of symmetric stream ciphers are presented in the paper.

Разностный криптоанализ итеративных алгоритмов блочного шифрования с алфавитом текстов X, как правило, проводится в рамках марковской модели. При этом фиксируется регулярная абелева группа (X, 0) и используется тот факт, что для 0-марковских алгоритмов блочного шифрования последовательность разностей (относительно операции 0) пар промежуточных шифртекстов i-го раунда, i = 1,2,..., образует цепь Маркова. В работе рассматриваются 0-марковские алгоритмы блочного шифрования, у которых существует укрупнение состояний цепи Маркова до блоков разбиения W, также являющееся цепью Маркова. Такие алгоритмы блочного шифрования, а также подстановки на X вместе с операцией 0 наложения ключа, задающие раундовую функцию алгоритма шифрования, названы 0w,ch-марковскими. Получены условия на блоки разбиения W и элементы матрицы разностей переходов раундовой функции, при которых алгоритм блочного шифрования является 0w, ch-марковским. Приведены преобразования, основанные на операциях экспоненцирования и логарифмирования в кольце вычетов Z n и поле GF(n + 1), а также указаны разбиения W, при которых данные преобразования являются +w, ch-марковскими относительно соответствующей операции сложения + в кольце или поле., Let X be an alphabet of plaintexts (ciphertexts) of iterated block ciphers and (X, ®) be a regular abelian group. The group operation ® defines the difference of a text pair. ®-Markov ciphers are defined as iterated ciphers of which round functions satisfy the condition that the differential probability is independent of the choice of plaintexts from X. For ®-Markov ciphers with independent round keys, the sequence of round differences forms a Markov chain. In this paper, we consider ®-Markov ciphers and a partition W = {W 0,..., W r-1} with blocks being lumped states of the Markov chain. An /-round ®-Markov cipher is called ® W;ch-markovian if the cipher and W satisfy the following condition: the block numbers sequence j 0,..., j such that, for all i е {0,...,/}, the i th-round difference belongs to is a Markov chain. This definition can be also extended for permutations on X. For a partition W and differential probabilities of a round function of an /-round ®-Markov cipher, we get conditions that the cipher is ® W;ch-markovian. We describe ® W;ch-markovian permutations on Z n based on an exponential operation and a logarithmic operation, which are defined on Z n and GF(n +1).

Предлагается функция ошибки для постановки задачи идентификации алгоритма ранжирования результатов текстового поиска. Приводится обоснование некорректности применения функций ошибки, используемых в задачах, где выходные значения принимают действительные значения. В качестве альтернативы предлагается функция ошибки, которая учитывает не абсолютное, а относительное изменение результатов ранжирования. Приводится частный случай постановки задачи идентификации, в которой результат ранжирования рассматривается как класс релевантности., In the paper, an error function for text ranking identification problem is proposed. The rationale of incorrect use of error functions for problems where the output values are real numbers is provided. An alternative is the usage of error functions taking values of relative variation ranking results. Also, a special case of identification problem formulation where a ranking result is considered as relevance class is proposed.

Исследуется компонентная алгебраическая иммунность векторных булевых функций. Доказана теорема о соответствии между максимальной компонентной алгебраической иммунностью и сбалансированностью функции. Получена связь между максимальной компонентной алгебраической иммунностью и матрицами специального вида. При малом числе переменных построены функции, имеющие максимальную компонентную алгебраическую иммунность., In the paper, the component algebraic immunity of vector Boolean functions is studied. A theorem on a correspondence between the maximum component algebraic immunity of a function and its balancedness is proven. A relationship between the maximum component algebraic immunity and matrices of a special form is obtained. For a small number of variables, some functions with maximum component algebraic immunity are constructed.

Исследуются пересечения множеств значений производных двух APN-функций. Формулируются два вопроса: какова минимальная мощность таких пересечений и как связаны любые две APN-функции, множества значений производных которых попарно совпадают по каждому направлению. Получены частичные результаты по каждому из вопросов., The class of APN functions is considered in the paper. A vector Boolean function F in n variables from the set of all binary vectors of length n to itself is called an APN function if the equation F(x) ф F(x ф a) = b has at most 2 solutions for any vectors a, b, where a is a nonzero vector. A derivative of the function F in the direction of a is a Boolean function D aF(x) = F(x) ф F(x ф a). Two questions about intersections of the value sets for derivatives of two APN functions are proposed. The first one is about the minimal cardinality of such intersections. The second question is what a relationship these two APN functions have if the value sets of all directional derivatives of them pairwise coincide. Some partial results about both questions are obtained.

Рассматривается реализация функций четырёхзначной логики схемами из ненадёжных функциональных элементов в базисе Россера Туркетта. Предполагается, что все элементы схемы независимо друг от друга с вероятностью p подвержены инверсным неисправностям на выходах, т. е. каждый базисный элемент на любом входном наборе с вероятностью p выдаёт каждое из трёх неверных значений, с вероятностью 1 3p выдаёт верное значение. Найден класс функций K, содержащий почти все четырёхзначные функции, и показано, что любая схема, реализующая функцию из класса K, функционирует с ненадёжностью, которая асимптотически (при малых значениях p) не меньше 9p., We consider the implementation of four-valued logic functions by circuits consisting of unreliable functional gates in the Rosser Tourkett basis. It is assumed that all elements of the circuit independently with probability p are subject to inverse failures on the outputs, i. e. each basic element can give each of incorrect values with the probability p and correct value with the probability 1 3p. In this paper, a class K of four-valued functions is introduced in such a way that almost all four-valued functions are contained in K and any circuit realizing a function from K operates with an unreliability that is asymptotically (for small p) not less than 9p.

Представлены свойства степенной структуры различных классов графов, описана степенная структура минимальных примитивных орграфов с числом вершин n и числом дуг n + 1 и n + 2. При любом n ^ 5 и при k = 2,..., n 3 показано существование n-вершинного минимального примитивного орграфа с числом дуг n + k и со степенной структурой {(1,1) n-1, (k + 1, k + 1) 1}., The paper presents some properties of degree structure for different classes of digraphs and describes degree structure for primitive digraphs with n vertices and n + 1 and n + 2 arcs. For any integer n ^ 5 and k е {2,..., n 3}, the existence of a minimal primitive digraph with n vertices, n + k arcs and degree structure {(1,1) n-1, (k + 1, k + 1) 1} is shown.

Работа посвящена изучению практической применимости схемы полностью гомоморфного шифрования, созданной в Лаборатории современных компьютерных технологий НИЧ НГУ. Рассмотрено приложение гомоморфного шифрования для построения криптосистемы с открытым ключом, основанной на алгоритме RSA. На примере этой криптосистемы продемонстрирована корректность выполнения арифметических операций над зашифрованными данными, а также отсутствие увеличения размерности зашифрованных сообщений при умножении., In this paper, we discuss the practical usage of fully homomorphic encryption. The application of this encryption to constructing a public-key cryptosystem based on the RSA algorithm is shown. An implementation of this cryptosystem demonstrates that all arithmetical calculations over the encrypted data are correct. Also, it proves that the multiplication of ciphertexts doesn't lead to increasing the dimension of the multiplication result.

Пусть Bk = (к, 3) бернсайдова к-порождённая группа периода 3. В работе вычислены полиномы Холла для Bk при к ^ 4., Let Bk = B(k, 3) be the k-generator Burn-side group of exponent 3. Levi and van der Waerden proved that |B k | = 3 + (2)+(3) and Bk are nilpotent of class at most 3. For each Bk a power commutator presentation can be easily obtained using the system of computer algebra GAP or MAGMA. Let a^ 1... an" and a! 1... an n be two arbitrary elements in the group B k recorded in the commutator form. Then their product is equal to a^ 1... an n · a^... a y™ = a1 1... an. Powers z i are to be found based on the collection process, which is implemented in the computer algebra systems GAP and MAGMA. Furthermore, there is an alternative method for calculating products of elements of the group proposed by Ph. Hall. Hall showed that z i are polynomial functions (over the field Z 3 in this case) depending on the variables x 1,..., x i, y 1,..., y i and now called Hall's polynomials. Hall's polynomials are necessary in solving problems, which require multiple products of the elements of the group. The study of the Cayley graph structure for a group is one of these problems. The computational experiments carried out on the computer in groups of exponent five and seven showed that the method of Hall's polynomials has an advantage over the traditional collection process. Therefore, there is a reason to believe that the use of polynomials would be more preferable than the collection process in the study of Cayley graphs of B k groups. It should also be noted that this method is easily software-implemented including multiprocessor computer systems. Previously unknown Hall's polynomials of B k for k ^ 4 are calculated within the framework of this paper. For k > 4, the polynomials are calculated similarly but their output takes considerably more space

Описывается новая стратегия атаки по шифртекстам на одну линейную полностью гомоморфную криптосистему, чья защищённость обосновывается с привлечением сложности задачи факторизации больших чисел. Приводятся теоретические и практические оценки вероятности раскрытия секретного ключа с использованием данной атаки. Проводится анализ связи трудности факторизации чисел и защищённости криптосистемы против атаки по шифртекстам, на основе которого предлагается более эффективная модификация криптосистемы., The paper proposes a new ciphertexts-only attack on a linear fully homomorphic cryptosystem based on the problem of big numbers factorization. Theoretical and practical estimations of probability to find a key using this attack are given. Also, a link between factorization problem and cryptosystem security is analysed. It is shown how to increase the efficiency by replacing modulo n without loss of cipher strength.

Аддитивные группы кольца вычетов Z2" и векторного пространства V n над полем GF(2), а также порождённая ими группа G n имеют общие системы импримитивности и являются подгруппами силовской 2-подгруппы симметрической группы S(^2"). Данные группы возникают в криптографии при использовании в качестве способа наложения ключа относительно операций сложения из Vn и Z2". В работе приведено подстановочное строение подгрупп группы G n. Показано, что подгруппами G n являются группа нижнетреугольных (пхп)-матриц над полем GF(2) и полная аффинная группа над кольцом вычетов Z2". Рассмотрена характериза-ция импримитивных подгрупп группы G n., In this paper, we consider the additive group Z+n of the residue ring Z 2n, the additive group V+ of the vector space V n over the field GF(2), and subgroups of the group G n generated by Z+, V+. These groups are subgroups of the Sylow 2-subgroup of the symmetrical group S(Z 2n) and have common systems of imprimitivity. In cryptography, Z+, V+ are connected with groups generated by all key additions. We describe a permutation structure of subgroups of G n. We prove that the group of lower triangular (n x n)-matrices over GF(2) and the full affine group over Z 2n are subgroups of G n. We also describe properties of imprimitive subgroups of G n.

Исследуются неэндоморфные совершенные по Шеннону (абсолютно стойкие к атаке по шифртексту) шифры в случае, когда мощность множества шифрве-личин равна двум. В терминах линейной алгебры на основе теоремы Биркгофа о классификации дважды стохастических матриц описаны матрицы вероятностей ключей данных шифров. Построено множество возможных значений априорных вероятностей шифробозначений совершенного шифра., This paper deals with the non-endomorphic perfect ciphers in the case when the plaintext alphabet consists of two elements. According to Shannon, these ciphers are absolutely immune against the attack on ciphertext. In terms of linear algebra on the basis of Birkhoff's theorem (about the classification of doubly stochastic matrices), the matrices of cipher keys probabilities are described. The set of possible values of apriori probabilities for elements of ciphertext alphabet is constructed.

Предлагается решение для делегирования некоторого набора прав от одного пользователя (доверителя) операционной системы другому (доверенному лицу) на определённый промежуток времени. Для этого предложено использовать «доверенности» объекты, содержащие в себе такие поля, как идентификатор доверителя, идентификатор доверенного лица, время действия доверенности, а также набор прав, делегируемых доверенному лицу доверителем. Доверенность должна содержать также цифровую подпись на закрытом ключе доверителя под всеми вышеперечисленными полями. Предложенное решение реализовано для операционной системы Linux с помощью криптографического инструмента OpenSSL и подключаемых модулей аутентификации (PAM). В качестве доверенностей здесь выступают цифровые сертификаты стандарта X.509 v3, а делегируемые полномочия указываются по определённому формату в поле «Расширения» этих сертификатов. Сам функционал авторизации по доверенности реализован в виде модуля PAM., In this paper, a solution for delegation of some set of rights from one user (delegator) to another (proxy user) for a fixed time period is proposed. For this goal, it is offered to use "proxies". "Proxy" is an object containing the following fields: delegator's identifier, proxy user's identifier, time period (set by delegator), list of delegated rights, and delegator's digital signature. This solution is implemented for OS Linux using OpenSSL cryptographic toolkit and pluggable authentication modules (PAM). The object "proxy" is designed as X.509 v3 certificate, and the delegated rights are specified at the field of certificate extensions. Authorization by proxy is implemented as PAM module.

Пусть Bk = Bo(2, 7, k) -максимальная конечная двупорождённая группа периода 7 ступени нильпотентности k. В работе вычислены полиномы Холла для Bk при k ^ 4., Let = B 0(2, 7, k) be the largest two-generator finite group of exponent 7 and nilpotency class k. In this class, the largest group is the group B 28, which has the order 7 20416. For each, a power commutator presentation is obtained. Let aX 1... an n and a y1... an n be two arbitrary elements in the group recorded in the commutator form. Then their product is equal a^ 1... an n · a y1... an n = a^ 1... an n. Powers z are to be found based on the collection process which is implemented in the computer algebra systems GAP and MAGMA. Furthermore, there is an alternative method for calculating products of elements of the group, proposed by Ph. Hall. Hall showed that Z are polynomial functions (over the field Z 7 in this case) depending on the variables ж 1,..., ж г, y 1,..., у г, which are now called Hall's polynomials. Hall's polynomials are necessary in solving problems that require multiple products of the elements of the group. Studying the structure of the Cayley graph for a group is one of these problems. The computational experiments carried out on the computer in two-generator groups of exponent five showed that the method of Hall's polynomials has an advantage over the traditional collection process. Therefore, there is a reason to believe that the use of polynomials would be preferable than the collection process in the study of Cayley graphs for groups. It should be also noted that this method is easily software-implemented including multiprocessor computer systems. Previously unknown Hall's polynomials of are calculated within the framework of this paper. For k > 4, polynomials are calculated similarly but their output takes considerably more space so it makes impossible to verify the proof without use of computers.

Работа посвящена количественному стегоанализу определению размера сообщения, встроенного в стеганографический контейнер. Предложен подход к определению размера скрытого сообщения с помощью бинарного стегоаналитическо-го классификатора, приведена формула вычисления математического ожидания ошибки стегоаналитика. Задача определения оптимальной стратегии стегоанали-тика сформулирована в виде задачи минимизации., In this paper, the problem of determining secret message length using binary steganalytic classifier is researched. It is assumed that a steganalyst is able to cut a large stego image into k smaller images and to apply the binary classification to every one of them. According to the information-theoretic approach to the steganographic security, a steganalyst's expected error calculation formula is derived. Determining the optimal choice of k depended on the properties of a binary classifier and a given image is formulated as a minimization problem. Presented approach can be used to estimate impact of various parameters on stegosystem security against quantitative steganalysis.

Исследуется подход к минимизации реализации преобразований, степень которых реализует полное перемешивание входных данных. Введены понятия минимальной примитивной матрицы и высоты примитивной матрицы. Получены оценки числа минимальных примитивных матриц порядка п. Построены и проанализированы алгоритмы поиска минимальных примитивных матриц и оценки близости примитивной матрицы к множеству минимальных примитивных матриц., A quadratic Boolean matrix A is called a primitive matrix if some its degree does not contain 0's. A primitive matrix is called a minimal primitive matrix if it becomes non-primitive matrix after replacing any one 1 in it by 0. The height of a primitive matrix is defined as the least Hamming's distance between it and a minimal primitive matrix. In the paper, properties of minimal primitive matrices are studied. The amount of minimal primitive matrices of order n is estimated. An algorithm for estimating the height of a primitive matrix is proposed.

Рассматривается известная NP-трудная задача нахождения минимального остов-ного k-дерева в простом взвешенном графе. Данную задачу необходимо решать при проектировании надежной телекоммуникационной сети наименьшей стоимости. Предлагается серия эвристических алгоритмов. Определены оценки трудоёмкости алгоритмов, доказана их корректность. Проведён вычислительный эксперимент по сравнению эффективности предложенных алгоритмов, как между собой, так и с известными приближёнными и точными алгоритмами., In this paper, the problem of finding a spanning k-tree of minimum weight in a complete weighted graph is considered. Such problem has a number of applications in designing reliable telecommunication networks. This problem is known to be NP-hard and generalizes a classical problem in graphs, the Minimum Spanning Tree Problem. For solving the problem, the following four effective heuristics are offered. The first heuristic is based on the idea of a well-known Prim's algorithm, the second one is based on a dynamic programming approach, and the other two use the idea of iterative improvement of a starting solution. Preliminary numerical experiment was performed to compare the effectiveness of the proposed algorithms with known heuristics and exact algorithms. Based on the results of the computational experiment, it follows that in order to solve such problem of small and medium dimension, it is advisable to use heuristics based on iterative improvement of a starting solution, and in order to solve the problem of high dimension it is advisable to use an algorithm based on dynamic programming approach, because it computes a solution with sufficient accuracy within reasonable computing time.

Рассматривается функционирование генных сетей циркулянтного типа с пороговыми функциями при значении параметра p = 2. Проведена классификация всех состояний системы в зависимости от длин серий нулей и единиц. Установлено, что все циклы графа функционирования делятся на два типа: состоящие только из состояний с длинными сериями и состоящие только из состояний с короткими сериями. Получена оценка на количество циклов в графе функционирования. Описана конструкция для построения циклов из состояний с короткими сериями., In this paper, the functioning of circulant type gene networks with threshold function are studied. All states of a system are classified according to the length of 0-series and 1-series. It is shown that all cycles of a functional graph are divided into two groups: cycles composed of states with long series and cycles composed of states with short series. Some lower estimate of the number of cycles in a functional graph is obtained. A construction for building cycles composed of states with short series is given.

Рассмотрена реализация на ПЛИС шифра Закревского на основе перестраиваемого автомата, заданного формулами, когда функции переходов и выходов вычисляются с помощью часто используемой в симметричных шифрах операции сложения по модулю целого числа (обычно степени двойки). Установлено, что формульный (аналитический) способ представления автомата по сравнению с табличным приводит к улучшению эффективности ПЛИС-реализации шифра, в частности наблюдается рост производительности на 17-36%., A new version for FPGA implementation of Zakrevskij's cipher is presented. Unlike the previous version, here a configurable FSM is specified not by tables but by some analytical expression using the operation of modulo addition. In the paper, some numerical characteristics (throughput and area) of FPGA implementations are given for both these versions. In partucular, it is shown that the throughput of PLA for the new version is up to 17-36 % higher than for the previous one.

Для модификации аддитивного генератора с помощью инволютивной перестановки координат векторов исследованы условия полного перемешивания. Доказаны достаточные условия примитивности перемешивающего графа и оценки его экспонента в некоторых случаях. Полученные оценки экспонента показывают, что полное перемешивание знаков состояния генератора может быть достигнуто после числа тактов, которое существенно меньше размера состояний., One of the positive properties of a key generator is a complete mixing of input vector sequence. It means that the all bits in output sequence y*y 2... y»... depend on the all bits of the initial state. Complete mixing occurs for bits in the sequence y» when i ^ exp G(^), where is the transformation of internal states of the generator, G(^) is the mixing digraph of transformation ^ and exp G(^) is the exponent of digraph G(^). The criterion of complete mixing is the primitiveness of digraph G(^), the necessary condition is the strong connectivity of digraph G(^). This paper is devoted to some modifications of additive generators. Well known algorithms such as Fish, Pike and Mush are based on additive generators. Native schemes of additive generators do not reach complete mixing. In order to achieve the strong connectivity of digraph G(^), the scheme of additive generator is modified by invo-lutive permutation of vectors coordinates. The complete mixing conditions are researched for this modification of additive generator. Some sufficient conditions for primitiveness of mixing graph G(^) and some estimates for exp G(^) are proved. The obtained estimates show that complete mixing of the generator output sequence can be achieved after a number of cycles, which is significantly smaller than the dimension (in bites) of the generator state

Работа посвящена разработке защищённой клиент-серверной СУБД при недоверенном сервере БД. Конфиденциальные данные шифруются на стороне клиента с помощью специализированных шифров, позволяющих производить операции над данными без их предварительного расшифрования. Для этого используется шифр mOPE с сохранением порядка, который позволяет производить операции сравнения над зашифрованными данными. Разработан и реализован асинхронный NoSQL-протокол взаимодействия клиента и сервера БД, поддерживающий простой набор операций над конфиденциальными данными. Разработанный протокол интегрирован в свободно распространяемую СУБД MySQL., The paper presents a computationally secure database management system based on order-preserving encryption. The threat model is the following: the DB server is leased to the client thus the DB server is untrusted; the threat is a malicious database administrator who tries to learn private data by snooping on the DB server. To protect data confidentiality against this threat, it is proposed to execute queries over encrypted data on the untrusted server. Namely, to perform order operations on ciphertexts in the same way as on plaintexts, an order-preserving encryption, in particular mOPE scheme, is used. The mOPE scheme achieves IND-OCPA security, where an adversary learns no information about the plaintexts besides order. A MySQL plugin that implements a NoSQL protocol for MySQL server is developed. The NoSQL client/server protocol supports simple operations on private data, in particular it ranges queries over encrypted data. The protocol allows client applications to communicate remotely with MySQL storage engines.

Предложен новый подход для обнаружения информации в растровых изображениях. Предполагается, что для внедрения информации использовалась либо ±1-стеганография, либо LSB-замещение. Предлагается новый сценарий обнаружения информации, в котором наблюдателю известны пиксели изображения, куда производилось внедрение. Показано, что обнаружение информации возможно уже при 0,001 bpp ("bits per pixel") внедрении., The problem of detecting information, embedded into non-distorted bitmap images (such as bmp, pgm, tiff etc.) via LSB-replacement and LSB-matching methods (the latter is also known as ±1-steganography) is considered. There are two main approaches to address this problem in contemporary steganalysis: ordinary and quantitative. The first one is aimed at finding out only a fact of the embedding, while the second one tries to estimate a volume of the embedded information. The mostly widespread quantitative methods for detecting LSB-replacement are RS-analysis, Sample Pairs analysis, WS-steganalysis and Improved WS steganalysis. One more, a so-called shift-method, is especially effective for color images. The enlisted methods allow to detect the embedding up to 0.01 bits-per-pixel (bpp) depending on the image (in particular, noisy images are more difficult to analyse). There are no effective quantitative methods for detecting ±1-steganography, therefore, the most popular ones are ordinary methods Support Vector Machine and Linear Discriminant Analysis, which are able to detect up to 0.1 bpp. These methods are also can be applied to LSB-replacement and are able to detect the embedding up to 0.01 bpp. In the current paper, a new scenario and a new quantitative method within this scenario are suggested. The scenario assumes that a Warden knows exact pixels, where the information is supposed to be embedded, and it can be implemented, for instance, in the following situation. Assume that the Warden is given a device which is used for the information embedding (a key can be already injected into it). The task is to detect whether a given image has some embedded information via this device, or not. It is experimentally shown that the new method allows to detect up to 0.001 bits-per-pixel embedding, that is much more than known methods.

Рассматривается реализация булевых функций схемами из ненадёжных функциональных элементов в произвольном полном базисе B. Предполагается, что все элементы схемы независимо друг от друга с вероятностью е £ (0,1/2) подвержены инверсным неисправностям на выходах. Найдено множество G функций, таких, что для почти всех функций ненадёжность асимптотически оптимальных по надёжности схем в базисе B, содержащем функции множества G, равна е (при е ^ 0)., Circuits composed of unreliable functional elements in a complete finite basis B are considered. It is assumed that all elements are independently of each other subjected to inverse failures at the outputs with the probability e (e E (0,1/2)). In the paper, a set G of Boolean functions is found, and it is proved that if B П G = 0, then almost all Boolean functions are realized in basis B by asymptotically optimal on reliability circuits with unreliability e under e ^ 0.

Рассматривается предложенный недавно способ разбиения S-блоков для защиты от атак по сторонним каналам. Известно, что для всех классов эквивалентности S-блоков, кроме одного, такое разбиение возможно. Доказано, что для этого одного класса не существует искомого разбиения., A known method of S-boxes partition applied against side-channel attacks is considered. Nowadays, necessary partitions are found for all the affine equivalence classes except one. In the paper, it is proved that S-boxes of this class do not have admissible partition.

Предлагается новый алгоритм восстановления секретного ключа по открытому для криптосистемы Мак-Элиса, построенной на основе двоичных кодов Рида — Маллера RM(r, m). В случае, если значение d = (r,m — 1) ограничено, алгоритм имеет полиномиальную сложность O(n d + n 4 log2 n), где n = 2 m. Практические результаты показывают, что предложенная атака позволяет осуществить взлом криптосистемы Мак-Элиса, построенной на основе двоичного кода Рида — Мал-лера длины n = 65526 битов, менее чем за 7 ч на персональном компьютере., This paper describes new algorithm for breaking McEliece cryptosystem, being built on Reed — Muller binary code RM(r, m).The algorithm calculates the private key from the public key using O(n d + n 4 log 2 n) bit operations, where n = 2 m, d = (r, m — 1). In case of limited d, the attack has a polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the Reed — Muller binary code of length n = 65526 bits, can be broken in less than 7 hours on a personal computer.

Работа посвящена генерации неприводимых многочленов степени 2 n посредством поликвадратичного расширения поля над GF(2). Построено полное бинарное дерево неприводимых многочленов, рассмотрены свойства этого расширения., The paper is devoted to generation of irreducible polynomials of degree 2 n by using polyquadratic field extension of GF(2). Full binary tree of these polynomials is constructed. Some properties of such extension are formulated.

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимого расширения (ТНР). Приводится способ построения всех неизоморфных ТНР для подкласса сверхстройных деревьев — равнолучевых звезд., Tirreducible extension is a kind of the optimal extension of a graph. In the paper, all nonisomorphic T-irreducible extensions are constructed for starlike trees with paths of one and the same length.