Search

Тема выпускной квалификационной работы «Исследование арифметики ÐºÐ¾Ð½ÐµÑ‡Ð½Ñ‹Ñ Ð´Ð¸ÑÐºÑ€ÐµÑ‚Ð½Ñ‹Ñ Ð³Ñ€ÑƒÐ¿Ð¿, ÑÐ¾Ð¾Ñ‚Ð²ÐµÑ‚ÑÑ‚Ð²ÑƒÑŽÑ‰Ð¸Ñ Ð¿Ð¾Ð»Ð¸Ð½Ð¾Ð¼Ð°Ð¼ заданной степени». В данной работе рассмотрены основные арифметические операции в ÐºÐ¾Ð½ÐµÑ‡Ð½Ñ‹Ñ Ð¿Ð¾Ð»ÑÑ . В работе представлена программа для расчета Ð½ÐµÐ¿Ñ€Ð¸Ð²Ð¾Ð´Ð¸Ð¼Ñ‹Ñ Ð¿Ð¾Ð»Ð¸Ð½Ð¾Ð¼Ð¾Ð² заданной степени. На основе ÑÑ‚Ð¸Ñ Ð¿Ð¾Ð»Ð¸Ð½Ð¾Ð¼Ð¾Ð² строятся поля Галуа, соответственно степени многочлена и строятся таблицы умножения и степеней. На основе Ð¿Ð¾Ð»ÑƒÑ‡ÐµÐ½Ð½Ñ‹Ñ Ñ€ÐµÐ·ÑƒÐ»ÑŒÑ‚Ð°Ñ‚Ð¾Ð² проводится анализ свойств ÐºÐ¾Ð½ÐµÑ‡Ð½Ñ‹Ñ Ð³Ñ€ÑƒÐ¿Ð¿ и Ð¸Ñ Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ðµ на замкнутость., The topic of the final qualifying work is "The study of arithmetic of finite discrete groups corresponding to polynomials of a given degree". In this paper, the basic arithmetic operations in finite fields are considered. The paper presents a program for calculating irreducible polynomials of a given degree. On the basis of these polynomials, Galois fields are constructed, according to the degree of the polynomial, and multiplication tables and degrees are constructed. Based on the results obtained, the properties of finite groups are analyzed and their study for closure is carried out.

The proper subgroup $B$ of the group $G$ is called {\it strongly embedded}, if $2\in\pi(B)$ and $2\notin\pi(B \cap B^g)$ for any element $g \in G \setminus B $ and, therefore, $ N_G(X) \leq B$ for any 2-subgroup $ X \leq B $. An element $a$ of a group $G$ is called {\it finite} if for all $ g\in G $ the subgroups $ \langle a, a^g \rangle $ are finite. In the paper, it is proved that the group with finite element of order $4$ and strongly embedded subgroup isomorphic to the Borel subgroup of $U_3(Q)$ over a locally finite field $Q$ of characteristic $2$ is locally finite and isomorphic to the group $U_3(Q)$. Keywords: A strongly embedded subgroup of a unitary type, subgroups of Borel, Cartan, involution, finite element., Comment: 8 pages, in Russian

Пусть F(2m) произвольное поле характеристики 2, его квадратичное расширение мы будем рассматривать как алгебру с базисом 1, e над полем F(2m). Здесь 1 рассматривается как единичный элемент алгебры, а элемент e удовлетворяет соотношению e2=e+α. Элемент может быть произвольным из поля F(2m), но неудовлетворяющий условию α=x+ x2 при некотором x из F(2m). Пусть n0(α) обозначает порядок элемента e. Тогда основной результат работы можно сформулировать так: Неприводимый полином 1+t+ αt2 делит полином 1+ tn тогда и только тогда, когда n0(α) делит натуральное n. Аналогичные результаты для произвольных элементов поля F(22m) следуют из этого. Доказательство базируется на свойствах рекуррентных соотношений между полиномами Pn и Qn, определяемые для всех n=0,1,2,… из соотношений en=Pn + Qne. Формулы для производящих рядов этих полиномов содержат наиболее важные такие свойства. Эти формулы были получены и имеют вид: 0Pktk=1+t1+t+t2 и 0Qktk=t1+t+t2 ., Let will be an arbitrary finite field of characteristic 2. It’s square extension will be considered as an algebra with basiс elements 1 and e over the field . Here is considered as the unit element of the algebra, and satisfies the relation: . An element maybe arbitrary from the field , but it is not satisfying to the condition for some element from . Let us denote the order of basis element . Then the main result of the paper can be formulated as: The irreducible polynomial divides the polynomial if and only the order if divides a natural . The similar results for arbitrary elements of field follow from main theorem. The proof of main result based on the properties of the recurrence relations between the polynomials and , definite for all by the relations + . The formulas for the generating series of these polynomials contain the most important such properties. The formulas were obtained and we have: , ., Международный научный журнал "Современные информационные технологии и ИТ-образование", Выпуск 2 2020, Pages 314-320

Introduction. Polynomials in several variables over Galois fields provide the basis for the Reed-Muller coding theory, and are also used in a number of cryptographic problems. The properties of such polynomials specified over the derived Galois fields of fuzzy cardinality are studied. For the results obtained, two real-world applications are proposed: partitioning scheme and Reed-Muller code decoder.Materials and Methods. Using linear algebra, theory of Galois fields, and general theory of polynomials in several variables, we have obtained results related to the differentiation and integration of polynomials in several variables over Galois fields of fuzzy cardinality. An analog of the differentiation operator is constructed and studied for vectors.Research Results. On the basis of the obtained results on the differentiation and integration of polynomials, a new decoder for Reed-Muller codes of the second order is given, and a scheme for organizing the partitioned transfer of confidential data is proposed. This is a communication system in which the source data on the sender is divided into several parts and, independently of one another, transmitted through different communication channels, and then, on the receiver, the initial data is restored of the parts retrieved. The proposed scheme feature is that it enables to protect data, both from the nonlegitimate access, and from unintentional errors; herewith, one and the same mathematical apparatus is used in both cases. The developed decoder for the second-order Reed-Muller codes prescribed over the derived odd Galois field may have a constraint to the recoverable error level; however, its use is advisable for a number of the communication channels.Discussion and Conclusions. The proposed practical applications of the results obtained are useful for the organization of reliable communication systems. In future, it is planned to study the restoration process of the original polynomial by its derivatives, in case of their partial distortion, and the development of appropriate applications.

A number of previous author’s papers proposed methods for constructing various cryptographic algorithms, including block ciphers and cryptographic hash functions, based on generalized cellular automata. This one is aimed at studying a possibility to use the algebraic cryptanalysis methods related to the construction of Grobner bases for the generalized cellular automata to be applied in cryptography, i.e. this paper studies the possibility for using algebraic cryptanalysis methods to solve the problems of inversion of a generalized cellular automaton and recovering the key of such an automaton. If the cryptographic algorithm is represented as a system of polynomial equations over a certain finite field, then its breach is reduced to solving this system with respect to the key. Although the problem of solving a system of polynomial equations in a finite field is NP-difficult in the general case, the solution of a particular system can have low computational cost. Cryptanalysis based on the construction of a system of polynomial equations that links plain text, cipher-text and key, and its solution by algebraic methods, is usually called algebraic cryptanalysis. Among the main methods to solve systems of polynomial equations are those to construct Grobner bases. Cryptanalysis of ciphers and hash functions based on generalized cellular automata can be reduced to various problems. We will consider two such problems: the problem of inversion of a generalized cellular automaton, which, in case we know the values of the cells after k iterations, enables us to find the initial values. And the task of recovering the key, which is to find the initial values of the remaining cells, using the cell values after k steps and the initial values of a part of the cells. A computational experiment was carried out to solve the two problems above stated in order to determine the maximum size of a generalized cellular automaton for which the solution of these problems was possible. Using a Python language program, random 6-regular Ramanujan graphs with the appropriate number of vertices were generated. For each graph, was generated a system of equations that describes the k steps of the corresponding generalized cellular automaton. For the systems obtained, the Grebner bases were constructed using the Fouger algorithm F4, the Magma system v2.21-5, and the Polybori 0.8.3 library. The experiments were carried out both for the inversion task and for the key recovery task. We used a 16-core 16 GB RAM Intel Xeon E5-2690 computer, OS Linux. The article presents the results of experiments that confirm that the algebraic cryptanalysis of block ciphers and hash functions based on generalized cellular automata with the number of cells used in practice (of the order of several hundred or more) available tool based on the use of Grobner bases, is impossible.

Сообщается об одном ошибочном утверждении нашей статьи О минимально полных ассоциативных кольцах., We report on one erroneous statement of our article On minimally complete associative rings., №2(24) (2019)

Рассматриваются векторные отображения над множеством из нуля и единицы, заданные множеством булевых функций. Булевы функции, входящие в отображение, в свою очередь, задаются полиномами Жегалкина. Зафиксировав правило, по которому двоичным векторам ставятся в соответствие элементы конечного поля характеристики два, получаем взаимно-однозначное соответствие между отображениями векторного пространства в себя и функциями над конечным полем. Конечное поле рассматривается как кольцо многочленов с операциями сложения и умножения по модулю выбранного неприводимого многочлена. Известно, что любую функцию над конечным полем можно записать в виде полинома. При этом для различных неприводимых многочленов полиномы над конечным полем, соответствующие заданному векторному отображению, в общем случае, могут быть различными и иметь различные степени. Рассматривается задача поиска такого неприводимого многочлена, чтобы степень полинома над конечным полем была минимальной, при условии, что соответствие между двоичными векторами и элементами конечного поля задаётся использованием полиномиального базиса конечного поля. Для решения задачи булевы функции представляются своими трейс-формами. Из этого представления коэффициенты полинома над конечным полем выражаются через элементы дуального базиса конечного поля. Затем элементы дуального базиса выражаются через полиномиальный базис конечного поля и коэффициенты неприводимого многочлена. Таким образом, коэффициент полинома над конечным полем выражаются в полиномиальном базисе конечного поля. Полученные уравнения сводятся к системе булевых уравнений для коэффициентов неприводимого многочлена. Для решения системы булевых уравнений используется SAT-решатель. Приведены оценки сложности получения указанной системы булевых уравнений., We consider vector mappings over the set of 0 and 1 given by the set of Boolean functions. Boolean functions included in the map are given in ANF. Having fixed the rule according to which the binary vectors are associated with the elements of a finite field of characteristic two, we obtain a one-to-one correspondence between the mappings of the vector space into itself and the functions over the finite field. The finite field is considered as a ring of polynomials with the operations of addition and multiplication modulo the selected irreducible polynomial. It is known that any function over a finite field can be written as a polynomial. Moreover, for various irreducible polynomials, the polynomials over a finite field, corresponding to a given vector map, may in general be different and have different properties. We consider the problem of finding an irreducible polynomial such that the degree of a polynomial over a finite field is minimal, provided that the correspondence between binary vectors and elements of a finite field is given by using a polynomial basis of a finite field. We present an algorithm to solve this problem. Firstly we rewrite Boolean functions in trace form and calculate expressions for finite field polynomial coefficients. Then we calculate elements of dual basis as an expression of polynomial basis. Using them we obtain system pf Boolean equations. Finally we solve system of Boolean equations by SAT-solver and filter reducible polynomials. We estimate of the complexity of obtaining the specified system of Boolean equations is bitwise operations., №1 (2019)

The sequences are an important part of the cryptography and analysis of their properties is of great interest. In this paper, the following characteristics of combined generator are analyzed: period of output sequences and the distribution of elements in the output sequences over finite field.

Большинство криптосистем современной криптографии естественным образом можно реализовать на эллиптических кривых. Мы рассматриваем алгебраические кривые в форме Эдвардса над простым полем, Fp, которые сейчас являются одними из наиболее перспективных носителей групп, используемых в асимметричных криптосистемах. Показано, что проективная кривая Эдвардса не является эллиптической. Исследовано некоторые интересные свойства группы точек этих кривых. Найдено род скрученной кривой Эдвардса и ее особые точки. Показано возможность построения генератора случайных крипто стойких последовательностей на этой кривой. Предложена нормализация скрученной кривой Эдвардса. Исследованы условия делимости на два элемента из группы точек скрученной кривой Эдвардса над полем . Целью роботы есть поиск критерия делимости точки кривой напополам над полем и анализ свойств скрученной кривой Эдвардса необходимых для построения генератора псевдослучайных крипто стойких последовательностей., Більшість криптосистем сучасної криптографії природним чином можна реалізувати на еліптичні криві. Ми розглядаємо алгебраїчні криві Едвардса над скінченним полем , які на даний час є одним з найбільш перспективних носіїв множин точок, що використовують для швидких групових операцій, які наявні в асиметричних криптосистемах, зокрема для побудови випадкових криптостійких послідовностей. Показано, що проективна крива не є еліптичною. Досліджено умови існування подільності навпіл елемента з групи точок скрученої кривої Едвардса , що є важливим в алгоритмах. Знайдено рід скрученої кривої Едвардса. Метою роботи є пошук критерію подільності точки кривої навпіл над полем і аналіз властивостей скрученої кривої Едвардса необхідних для побудови генератора псевдовипадкових криптостійких послідовностей і побудова односторонньої функції для нього., Most cryptosystems of modern cryptography can be naturally transformed into elliptic curves. We review Edwards algebraic curves over a finite field, which at the present time is one of the most promising carriers of sets of points that are used for fast group operations. These are found in asymmetric cryptosystems. In particular, for constructing random crypto-stable sequences. It is shown that the projective curve is not elliptic.The conditions of the existence of divisibility in half an element from the group of points of the twisted curve of Edwards , which is important in algorithms, are investigated. The type of twisted curve Edwards is found. The purpose of the work is to find the criterion of the divisibility of the point of the curve in half over the field and to analyze the properties of the twisted curve of Edwards necessary for constructing a generator of pseudo-random crypto-stable sequences and constructing a one-way function for it.

Изучается плотность полугрупп на коротких интервалах., We study the distribution of semigroups of integers on small intervals., №1 (2018)