THE BASICS OF LINEAR ALGEBRA IN CRYPTOGRAPHY

ABSTRACT

This paper surveys a cryptographic analysis of encryption and key distribution schemes based on linear algebra. The relevance of this article is due to certain reasons: an increase in the amount of information accumulated, stored and processed using computers and other automation tools, droviding access to computing resources and data arrays, development in the global Internet An original method is described for finding an encrypted message or a common key, based on the usual apparatus of linear algebra, provided that the corresponding platform can be selected as a finite-dimensional algebra, for example, as a matrix algebra over a field. Connection linear algebra of cryptography is a key-exchange protocol based on tropical matrix algebra. In classic case these schemes were shown to be vulnerable to various linear algebra attacks. The idea to use an algebra with another addition and multiplication came as an attempt to avoid those attacks, as there are no known algorithms for solving systems of linear equations in tropical sense.

Keywords: key generation, ciphertext, cipher, public-key cryptography

Cryptography is science is mainly engaged in the encryption of texts and other data in order to prevent unauthorized access to them. As scientists have proved, texts began to be encrypted already in the third millennium BC and the branch of mathematics abstract from number theory in algebra.

The mathematical methods used in cryptography cannot be successfully mastered without knowledge of algebraic structures such as groups, rings and fields. Therefore, knowledge and ability to work with these objects is a prerequisite for the training of specialists in the field of information protection.

Cryptology deals with the problems of protecting information through its transformation (kryptos-secret, logos-science). Cryptology is divided into two areas – cryptography and cryptanalysis. Goals of these directions are directly opposite. Cryptography is engaged in the search and research of mathematical methods of information conversion. The area of interest of cryptanalysis is the study of the possibility of decrypting information without knowing the keys.

In 1976, Americans Whitfield Diffie and Martin Hellman (Diffi W., Hellman M.) in the article "New Trends in Cryptography" proposed a new principle for constructing cryptosystems, which does not only require transmitting the key to the receiving message, but even keeping the encryption method secret. This method is called the “exponential key exchange method” and is the first cryptosystem with open the key. The method is patented, but the patent expired on April 29 1997 year. Consider its main provisions.

Key generation

Let subscribers A and B agree to organize secret correspondence with each other using the secret key generated using the Diffie – Hellman algorithm. To do this, they choose two together sufficiently large primes n and q so that q is primitive an element in GF (n). These two numbers do not have to be kept secret. Subscribers A and B can transmit these numbers through an open communication channel. Then subscribers implement the following algorithm:

1. A selects a random large integer α, computes

and sends to B number x.

2.  B selects a random large integer β, computes

and sends to A number y.

3. A calculates

4. B calculates

.

As a result, A and B obtained numbers such that . None of attackers with access to this open channel cannot determine these values, since they know n, q, x, and y, but they do not know α and β. To obtain α and β, it is necessary to calculate the discrete logarithm, which is a computationally difficult task. Thus, the value  may be the secret key that A and B calculated independently. In this algorithm, the choice of n and q significantly affects cryptographic resistance.

Example

Let subscribers A and B agree to organize secret correspondence with each other using the secret key generated using the Diffie – Hellman algorithm. Then together they choose the numbers  and . Then

1. A chooses a random integer , calculates

and sends to B number 2.

2. In selects a random integer  calculates

and sends A number 3.

3. A calculates

.

4. B computes

.

As a result, A and B got the secret key .

EL GAMAL ALGORITHM

The search for more effective open encryption systems led to the fact that in 1985. El-Gamal (USA) proposed an algorithm based on raising to a power modulo a large prime number p. The cryptoalgorithm is not patented, but is subject to the patent for the Diffie-Hellman key exchange method. If raising a number to a power in a finite field is easy enough, then it is quite difficult to restore the argument from the value (i.e., find the logarithm).

Consider the scheme of the algorithm. The system is based on the parameters p and n - numbers, the first of which is simple, and the second is the whole.

Subscriber A generates a secret key α and calculates the public key . If subscriber B wants to send A message m, then he selects a random number k less than p and calculates:

 and

 ,

where  is the bitwise addition modulo 2.

Then B sends (y1, y2) to A.

And, having received an encrypted message, restores it:

 .

A known variant of the scheme is when the operation  is replaced by multiplication modulo p. This is more convenient in the sense that in the first case the textmust be broken into blocks of the same length as the number  in the second case is not required. So you can handle blocks text of a predetermined fixed length less than the number p.

The decryption equation in this case will be:

Example

Let subscribers A and B decide to install between.

It is a secret connection with a public key based on the Al-Gamal algorithm.

Subscriber A chose a prime number  and an integer

number .

Subscriber A then generates the secret key , and calculates the public key  and sends the numbers p, n and y to the open channel.

Let subscriber B want to send A message . He selects a random number  smaller than p and calculates:

,

,



and sends A pair (y1, y2).

Subscriber A, having received an encrypted message, restores it:



When using the El-Gamal method in an open encryption system with a module p of 150 characters, the same degree is achieved protection that for the RSA (one of the first public-key cryptosystems) algorithm with a module of 200 characters. This allows for 5-7 times increase the speed of information processing. However, in this open encryption option, there is no authentication of messages.

Conclusions

The choice of encryption method depends on the features of the information, its value and the ability of the owners to protect their information. Each type of information has its own specific features, and these features strongly affect the choice of information encryption methods. Of great importance are the volumes and the required transmission rate of encrypted information. The choice of the type of cipher and its parameters significantly depends on the nature of secrets or secrets being protected. For a professional understanding of cryptographic algorithms and the ability to evaluate their strengths and weaknesses, appropriate mathematical preparation is necessary. This is because modern cryptography is based on the profound results of such branches of mathematics as the theory of computational complexity, number theory, algebra, etc.

References:

1. Sinkov A. « Elementary Cryptanalysis». 2009. pp 1-10.
2. Alko R. M. «Algebra for Cryptologists ». 2016. pp-28-41.
3. Paar C., Pelzl J. «Understanding Cryptography» A Textbook for Students and Practitioners. 2010. pp. 50-101.
4. Dr. Omar M. «Number Theory Toward RSA Cryptography». 2017. pp. 178-185.
5. Kostrikin A.I. «Vvedenie v algebru» [Introduction to Algebra]. Uchebnoe posobie.[Tutorial] . 2004. Pp. 112-131 (in Russian)
6. Malyuk A.A., Gorbatov V.S., Korolev V.I., Fomichev V.M., Durakovskij A.P., Kondrateva T.A. «Vvedenie v informacionnuyu bezopasnost» [Introduction to cybersafety]: Uchebnoe posobie dlya vuzov. [Tutorial]. 2014. pp. 156-178 (in Russian)
7. Singh S. «Code Book, The Secret History of Codes and Code-breaking». 2016. pp. 32-75.